/*

 * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package org.graalvm.compiler.replacements;

import java.net.URI;

import static org.graalvm.compiler.debug.GraalError.unimplemented;

import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;

import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import jdk.internal.vm.compiler.collections.EconomicMap;

import jdk.internal.vm.compiler.collections.Equivalence;

import org.graalvm.compiler.api.replacements.Fold;

import org.graalvm.compiler.bytecode.Bytecode;

import org.graalvm.compiler.bytecode.BytecodeProvider;

import org.graalvm.compiler.core.common.PermanentBailoutException;

import org.graalvm.compiler.core.common.cfg.CFGVerifier;

import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;

import org.graalvm.compiler.core.common.type.Stamp;

import org.graalvm.compiler.core.common.type.StampFactory;

import org.graalvm.compiler.core.common.type.StampPair;

import org.graalvm.compiler.debug.DebugCloseable;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.Node.NodeIntrinsic;

import org.graalvm.compiler.graph.NodeClass;

import org.graalvm.compiler.graph.NodeSourcePosition;

import org.graalvm.compiler.graph.SourceLanguagePosition;

import org.graalvm.compiler.graph.SourceLanguagePositionProvider;

import org.graalvm.compiler.graph.spi.Canonicalizable;

import org.graalvm.compiler.java.GraphBuilderPhase;

import org.graalvm.compiler.nodeinfo.NodeInfo;

import org.graalvm.compiler.nodes.AbstractBeginNode;

import org.graalvm.compiler.nodes.AbstractMergeNode;

import org.graalvm.compiler.nodes.CallTargetNode;

import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind;

import org.graalvm.compiler.nodes.ControlSinkNode;

import org.graalvm.compiler.nodes.DeoptimizeNode;

import org.graalvm.compiler.nodes.EncodedGraph;

import org.graalvm.compiler.nodes.FixedNode;

import org.graalvm.compiler.nodes.FixedWithNextNode;

import org.graalvm.compiler.nodes.FrameState;

import org.graalvm.compiler.nodes.IfNode;

import org.graalvm.compiler.nodes.Invoke;

import org.graalvm.compiler.nodes.InvokeWithExceptionNode;

import org.graalvm.compiler.nodes.MergeNode;

import org.graalvm.compiler.nodes.NodeView;

import org.graalvm.compiler.nodes.ParameterNode;

import org.graalvm.compiler.nodes.ReturnNode;

import org.graalvm.compiler.nodes.SimplifyingGraphDecoder;

import org.graalvm.compiler.nodes.StateSplit;

import org.graalvm.compiler.nodes.StructuredGraph;

import org.graalvm.compiler.nodes.UnwindNode;

import org.graalvm.compiler.nodes.ValueNode;

import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;

import org.graalvm.compiler.nodes.extended.ForeignCallNode;

import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;

import org.graalvm.compiler.nodes.graphbuilderconf.GeneratedInvocationPlugin;

import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext;

import org.graalvm.compiler.nodes.graphbuilderconf.InlineInvokePlugin;

import org.graalvm.compiler.nodes.graphbuilderconf.InlineInvokePlugin.InlineInfo;

import org.graalvm.compiler.nodes.graphbuilderconf.IntrinsicContext;

import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugin;

import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins;

import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins.InvocationPluginReceiver;

import org.graalvm.compiler.nodes.graphbuilderconf.LoopExplosionPlugin;

import org.graalvm.compiler.nodes.graphbuilderconf.LoopExplosionPlugin.LoopExplosionKind;

import org.graalvm.compiler.nodes.graphbuilderconf.NodePlugin;

import org.graalvm.compiler.nodes.graphbuilderconf.ParameterPlugin;

import org.graalvm.compiler.nodes.java.LoadFieldNode;

import org.graalvm.compiler.nodes.java.LoadIndexedNode;

import org.graalvm.compiler.nodes.java.MethodCallTargetNode;

import org.graalvm.compiler.nodes.java.MonitorIdNode;

import org.graalvm.compiler.nodes.java.NewArrayNode;

import org.graalvm.compiler.nodes.java.NewInstanceNode;

import org.graalvm.compiler.nodes.java.NewMultiArrayNode;

import org.graalvm.compiler.nodes.java.StoreFieldNode;

import org.graalvm.compiler.nodes.java.StoreIndexedNode;

import org.graalvm.compiler.nodes.spi.StampProvider;

import org.graalvm.compiler.nodes.type.StampTool;

import org.graalvm.compiler.nodes.util.GraphUtil;

import org.graalvm.compiler.options.Option;

import org.graalvm.compiler.options.OptionKey;

import org.graalvm.compiler.options.OptionType;

import org.graalvm.compiler.options.OptionValues;

import org.graalvm.compiler.phases.common.inlining.InliningUtil;

import jdk.vm.ci.code.Architecture;

import jdk.vm.ci.code.BailoutException;

import jdk.vm.ci.code.BytecodeFrame;

import jdk.vm.ci.meta.Assumptions;

import jdk.vm.ci.meta.ConstantReflectionProvider;

import jdk.vm.ci.meta.DeoptimizationAction;

import jdk.vm.ci.meta.DeoptimizationReason;

import jdk.vm.ci.meta.JavaConstant;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.JavaType;

import jdk.vm.ci.meta.MetaAccessProvider;

import jdk.vm.ci.meta.ResolvedJavaField;

import jdk.vm.ci.meta.ResolvedJavaMethod;

import jdk.vm.ci.meta.ResolvedJavaType;

/**

 * A graph decoder that performs partial evaluation, i.e., that performs method inlining and

 * canonicalization/simplification of nodes during decoding.

 *

 * Inlining and loop explosion are configured via the plugin mechanism also used by the

 * {@link GraphBuilderPhase}. However, not all callback methods defined in

 * {@link GraphBuilderContext} are available since decoding is more limited than graph building.

 *

 * The standard {@link Canonicalizable#canonical node canonicalization} interface is used to

 * canonicalize nodes during decoding. Additionally, {@link IfNode branches} and

 * {@link IntegerSwitchNode switches} with constant conditions are simplified.

 */

public abstract class PEGraphDecoder extends SimplifyingGraphDecoder {

    private static final Object CACHED_NULL_VALUE = new Object();

    public static class Options {

        @Option(help = "Maximum inlining depth during partial evaluation before reporting an infinite recursion")//

        public static final OptionKey<Integer> InliningDepthError = new OptionKey<>(1000);

        @Option(help = "Max number of loop explosions per method.", type = OptionType.Debug)//

        public static final OptionKey<Integer> MaximumLoopExplosionCount = new OptionKey<>(10000);

        @Option(help = "Do not bail out but throw an exception on failed loop explosion.", type = OptionType.Debug)//

        public static final OptionKey<Boolean> FailedLoopExplosionIsFatal = new OptionKey<>(false);

    }

    protected class PEMethodScope extends MethodScope {

        /** The state of the caller method. Only non-null during method inlining. */

        protected final PEMethodScope caller;

        protected final ResolvedJavaMethod method;

        protected final InvokeData invokeData;

        protected final int inliningDepth;

        protected final ValueNode[] arguments;

        private SourceLanguagePosition sourceLanguagePosition = UnresolvedSourceLanguagePosition.INSTANCE;

        protected FrameState outerState;

        protected FrameState exceptionState;

        protected ExceptionPlaceholderNode exceptionPlaceholderNode;

        protected NodeSourcePosition callerBytecodePosition;

        protected PEMethodScope(StructuredGraph targetGraph, PEMethodScope caller, LoopScope callerLoopScope, EncodedGraph encodedGraph, ResolvedJavaMethod method, InvokeData invokeData,

                        int inliningDepth, LoopExplosionPlugin loopExplosionPlugin, ValueNode[] arguments) {

            super(callerLoopScope, targetGraph, encodedGraph, loopExplosionKind(method, loopExplosionPlugin));

            this.caller = caller;

            this.method = method;

            this.invokeData = invokeData;

            this.inliningDepth = inliningDepth;

            this.arguments = arguments;

        }

        @Override

        public boolean isInlinedMethod() {

            return caller != null;

        }

        @Override

        public NodeSourcePosition getCallerBytecodePosition(NodeSourcePosition position) {

            if (caller == null) {

                return position;

            }

            if (callerBytecodePosition == null) {

                NodeSourcePosition invokePosition = invokeData.invoke.asNode().getNodeSourcePosition();

                if (invokePosition == null) {

                    assert position == null : "should only happen when tracking is disabled";

                    return null;

                }

                callerBytecodePosition = invokePosition;

            }

            if (position != null) {

                return position.addCaller(caller.resolveSourceLanguagePosition(), callerBytecodePosition);

            }

            final SourceLanguagePosition pos = caller.resolveSourceLanguagePosition();

            if (pos != null && callerBytecodePosition != null) {

                return new NodeSourcePosition(pos, callerBytecodePosition.getCaller(), callerBytecodePosition.getMethod(), callerBytecodePosition.getBCI());

            }

            return callerBytecodePosition;

        }

        private SourceLanguagePosition resolveSourceLanguagePosition() {

            SourceLanguagePosition res = sourceLanguagePosition;

            if (res == UnresolvedSourceLanguagePosition.INSTANCE) {

                res = null;

                if (arguments != null && method.hasReceiver() && arguments.length > 0 && arguments[0].isJavaConstant()) {

                    JavaConstant constantArgument = arguments[0].asJavaConstant();

                    res = sourceLanguagePositionProvider.getPosition(constantArgument);

                }

                sourceLanguagePosition = res;

            }

            return res;

        }

    }

    private static final class UnresolvedSourceLanguagePosition implements SourceLanguagePosition {

        static final SourceLanguagePosition INSTANCE = new UnresolvedSourceLanguagePosition();

        @Override

        public String toShortString() {

            throw new IllegalStateException(getClass().getSimpleName() + " should not be reachable.");

        }

        @Override

        public int getOffsetEnd() {

            throw new IllegalStateException(getClass().getSimpleName() + " should not be reachable.");

        }

        @Override

        public int getOffsetStart() {

            throw new IllegalStateException(getClass().getSimpleName() + " should not be reachable.");

        }

        @Override

        public int getLineNumber() {

            throw new IllegalStateException(getClass().getSimpleName() + " should not be reachable.");

        }

        @Override

        public URI getURI() {

            throw new IllegalStateException(getClass().getSimpleName() + " should not be reachable.");

        }

        @Override

        public String getLanguage() {

            throw new IllegalStateException(getClass().getSimpleName() + " should not be reachable.");

        }

    }

    protected class PENonAppendGraphBuilderContext implements GraphBuilderContext {

        protected final PEMethodScope methodScope;

        protected final Invoke invoke;

        @Override

        public ExternalInliningContext getExternalInliningContext() {

            return new ExternalInliningContext() {

                @Override

                public int getInlinedDepth() {

                    int count = 0;

                    PEGraphDecoder.PEMethodScope scope = methodScope;

                    while (scope != null) {

                        if (scope.method.equals(callInlinedMethod)) {

                            count++;

                        }

                        scope = scope.caller;

                    }

                    return count;

                }

            };

        }

        public PENonAppendGraphBuilderContext(PEMethodScope methodScope, Invoke invoke) {

            this.methodScope = methodScope;

            this.invoke = invoke;

        }

        /**

         * {@link Fold} and {@link NodeIntrinsic} can be deferred during parsing/decoding. Only by

         * the end of {@linkplain SnippetTemplate#instantiate Snippet instantiation} do they need to

         * have been processed.

         *

         * This is how SVM handles snippets. They are parsed with plugins disabled and then encoded

         * and stored in the image. When the snippet is needed at runtime the graph is decoded and

         * the plugins are run during the decoding process. If they aren't handled at this point

         * then they will never be handled.

         */

        @Override

        public boolean canDeferPlugin(GeneratedInvocationPlugin plugin) {

            return plugin.getSource().equals(Fold.class) || plugin.getSource().equals(Node.NodeIntrinsic.class);

        }

        @Override

        public BailoutException bailout(String string) {

            BailoutException bailout = new PermanentBailoutException(string);

            throw GraphUtil.createBailoutException(string, bailout, GraphUtil.approxSourceStackTraceElement(methodScope.getCallerBytecodePosition()));

        }

        @Override

        public StampProvider getStampProvider() {

            return stampProvider;

        }

        @Override

        public MetaAccessProvider getMetaAccess() {

            return metaAccess;

        }

        @Override

        public ConstantReflectionProvider getConstantReflection() {

            return constantReflection;

        }

        @Override

        public ConstantFieldProvider getConstantFieldProvider() {

            return constantFieldProvider;

        }

        @Override

        public StructuredGraph getGraph() {

            return graph;

        }

        @Override

        public int getDepth() {

            return methodScope.inliningDepth;

        }

        @Override

        public IntrinsicContext getIntrinsic() {

            return null;

        }

        @Override

        public <T extends ValueNode> T append(T value) {

            throw unimplemented();

        }

        @Override

        public void push(JavaKind kind, ValueNode value) {

            throw unimplemented();

        }

        @Override

        public void handleReplacedInvoke(InvokeKind invokeKind, ResolvedJavaMethod targetMethod, ValueNode[] args, boolean inlineEverything) {

            throw unimplemented();

        }

        @Override

        public void handleReplacedInvoke(CallTargetNode callTarget, JavaKind resultType) {

            throw unimplemented();

        }

        @Override

        public boolean intrinsify(BytecodeProvider bytecodeProvider, ResolvedJavaMethod targetMethod, ResolvedJavaMethod substitute, InvocationPlugin.Receiver receiver, ValueNode[] args) {

            return false;

        }

        @Override

        public void setStateAfter(StateSplit stateSplit) {

            throw unimplemented();

        }

        @Override

        public GraphBuilderContext getParent() {

            throw unimplemented();

        }

        @Override

        public Bytecode getCode() {

            throw unimplemented();

        }

        @Override

        public ResolvedJavaMethod getMethod() {

            throw unimplemented();

        }

        @Override

        public int bci() {

            return invoke.bci();

        }

        @Override

        public InvokeKind getInvokeKind() {

            throw unimplemented();

        }

        @Override

        public JavaType getInvokeReturnType() {

            throw unimplemented();

        }

    }

    protected class PEAppendGraphBuilderContext extends PENonAppendGraphBuilderContext {

        protected FixedWithNextNode lastInstr;

        protected ValueNode pushedNode;

        protected boolean invokeConsumed;

        public PEAppendGraphBuilderContext(PEMethodScope inlineScope, FixedWithNextNode lastInstr) {

            super(inlineScope, inlineScope.invokeData != null ? inlineScope.invokeData.invoke : null);

            this.lastInstr = lastInstr;

        }

        @Override

        public void push(JavaKind kind, ValueNode value) {

            if (pushedNode != null) {

                throw unimplemented("Only one push is supported");

            }

            pushedNode = value;

        }

        @Override

        public void setStateAfter(StateSplit stateSplit) {

            Node stateAfter = decodeFloatingNode(methodScope.caller, methodScope.callerLoopScope, methodScope.invokeData.stateAfterOrderId);

            getGraph().add(stateAfter);

            FrameState fs = (FrameState) handleFloatingNodeAfterAdd(methodScope.caller, methodScope.callerLoopScope, stateAfter);

            stateSplit.setStateAfter(fs);

        }

        @SuppressWarnings("try")

        @Override

        public <T extends ValueNode> T append(T v) {

            if (v.graph() != null) {

                return v;

            }

            try (DebugCloseable position = withNodeSoucePosition()) {

                T added = getGraph().addOrUniqueWithInputs(v);

                if (added == v) {

                    updateLastInstruction(v);

                }

                return added;

            }

        }

        private DebugCloseable withNodeSoucePosition() {

            if (getGraph().trackNodeSourcePosition()) {

                NodeSourcePosition callerBytecodePosition = methodScope.getCallerBytecodePosition();

                if (callerBytecodePosition != null) {

                    return getGraph().withNodeSourcePosition(callerBytecodePosition);

                }

            }

            return null;

        }

        private <T extends ValueNode> void updateLastInstruction(T v) {

            if (v instanceof FixedNode) {

                FixedNode fixedNode = (FixedNode) v;

                if (lastInstr != null) {

                    lastInstr.setNext(fixedNode);

                }

                if (fixedNode instanceof FixedWithNextNode) {

                    FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) fixedNode;

                    assert fixedWithNextNode.next() == null : "cannot append instruction to instruction which isn't end";

                    lastInstr = fixedWithNextNode;

                } else {

                    lastInstr = null;

                }

            }

        }

        @Override

        public void handleReplacedInvoke(CallTargetNode callTarget, JavaKind resultType) {

            if (invokeConsumed) {

                throw unimplemented("handleReplacedInvoke can be called only once");

            }

            invokeConsumed = true;

            appendInvoke(methodScope.caller, methodScope.callerLoopScope, methodScope.invokeData, callTarget);

            updateLastInstruction(invoke.asNode());

        }

    }

    @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)

    static class ExceptionPlaceholderNode extends ValueNode {

        public static final NodeClass<ExceptionPlaceholderNode> TYPE = NodeClass.create(ExceptionPlaceholderNode.class);

        protected ExceptionPlaceholderNode() {

            super(TYPE, StampFactory.object());

        }

    }

    protected static class SpecialCallTargetCacheKey {

        private final InvokeKind invokeKind;

        private final ResolvedJavaMethod targetMethod;

        private final ResolvedJavaType contextType;

        private final Stamp receiverStamp;

        public SpecialCallTargetCacheKey(InvokeKind invokeKind, ResolvedJavaMethod targetMethod, ResolvedJavaType contextType, Stamp receiverStamp) {

            this.invokeKind = invokeKind;

            this.targetMethod = targetMethod;

            this.contextType = contextType;

            this.receiverStamp = receiverStamp;

        }

        @Override

        public int hashCode() {

            return invokeKind.hashCode() ^ targetMethod.hashCode() ^ contextType.hashCode() ^ receiverStamp.hashCode();

        }

        @Override

        public boolean equals(Object obj) {

            if (obj instanceof SpecialCallTargetCacheKey) {

                SpecialCallTargetCacheKey key = (SpecialCallTargetCacheKey) obj;