/*

 * 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 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 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.NodeClass;

import org.graalvm.compiler.graph.NodeSourcePosition;

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.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.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;

        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;

        }

        public NodeSourcePosition getCallerBytecodePosition() {

            if (caller == null) {

                return null;

            }

            if (callerBytecodePosition == null) {

                JavaConstant constantReceiver = caller.invokeData == null ? null : caller.invokeData.constantReceiver;

                NodeSourcePosition callerPosition = caller.getCallerBytecodePosition();

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

                callerBytecodePosition = invokePosition != null ? invokePosition.addCaller(constantReceiver, callerPosition) : callerPosition;

            }

            return callerBytecodePosition;

        }

    }

    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;

        }

        @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().mayHaveNodeSourcePosition()) {

                return getGraph().withNodeSourcePosition(methodScope.getCallerBytecodePosition());

            }

            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;

                return key.invokeKind.equals(this.invokeKind) && key.targetMethod.equals(this.targetMethod) && key.contextType.equals(this.contextType) && key.receiverStamp.equals(this.receiverStamp);

            }

            return false;

        }

    }

    private final LoopExplosionPlugin loopExplosionPlugin;

    private final InvocationPlugins invocationPlugins;

    private final InlineInvokePlugin[] inlineInvokePlugins;

    private final ParameterPlugin parameterPlugin;

    private final NodePlugin[] nodePlugins;

    private final EconomicMap<SpecialCallTargetCacheKey, Object> specialCallTargetCache;

    private final EconomicMap<ResolvedJavaMethod, Object> invocationPluginCache;

    private final ResolvedJavaMethod callInlinedMethod;

    public PEGraphDecoder(Architecture architecture, StructuredGraph graph, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,

                    StampProvider stampProvider, LoopExplosionPlugin loopExplosionPlugin, InvocationPlugins invocationPlugins, InlineInvokePlugin[] inlineInvokePlugins,

                    ParameterPlugin parameterPlugin,

                    NodePlugin[] nodePlugins, ResolvedJavaMethod callInlinedMethod) {

        super(architecture, graph, metaAccess, constantReflection, constantFieldProvider, stampProvider, true);

        this.loopExplosionPlugin = loopExplosionPlugin;

        this.invocationPlugins = invocationPlugins;

        this.inlineInvokePlugins = inlineInvokePlugins;

        this.parameterPlugin = parameterPlugin;

        this.nodePlugins = nodePlugins;

        this.specialCallTargetCache = EconomicMap.create(Equivalence.DEFAULT);

        this.invocationPluginCache = EconomicMap.create(Equivalence.DEFAULT);

        this.callInlinedMethod = callInlinedMethod;

    }

    protected static LoopExplosionKind loopExplosionKind(ResolvedJavaMethod method, LoopExplosionPlugin loopExplosionPlugin) {

        if (loopExplosionPlugin == null) {

            return LoopExplosionKind.NONE;

        } else {

            return loopExplosionPlugin.loopExplosionKind(method);

        }

    }

    public void decode(ResolvedJavaMethod method) {

        PEMethodScope methodScope = new PEMethodScope(graph, null, null, lookupEncodedGraph(method, null), method, null, 0, loopExplosionPlugin, null);

        decode(createInitialLoopScope(methodScope, null));

        cleanupGraph(methodScope);

        debug.dump(DebugContext.VERBOSE_LEVEL, graph, "After graph cleanup");

        assert graph.verify();

        try {

            /* Check that the control flow graph can be computed, to catch problems early. */

            assert CFGVerifier.verify(ControlFlowGraph.compute(graph, true, true, true, true));

        } catch (Throwable ex) {

            throw GraalError.shouldNotReachHere("Control flow graph not valid after partial evaluation");

        }

    }

    @Override

    protected void cleanupGraph(MethodScope methodScope) {

        super.cleanupGraph(methodScope);

        for (FrameState frameState : graph.getNodes(FrameState.TYPE)) {

            if (frameState.bci == BytecodeFrame.UNWIND_BCI) {

                /*

                 * handleMissingAfterExceptionFrameState is called during graph decoding from

                 * InliningUtil.processFrameState - but during graph decoding it does not do

                 * anything because the usages of the frameState are not available yet. So we need

                 * to call it again.

                 */

                PEMethodScope peMethodScope = (PEMethodScope) methodScope;

                Invoke invoke = peMethodScope.invokeData != null ? peMethodScope.invokeData.invoke : null;

                InliningUtil.handleMissingAfterExceptionFrameState(frameState, invoke, null, true);

                /*

                 * The frameState must be gone now, because it is not a valid deoptimization point.

                 */

                assert frameState.isDeleted();

            }

        }

    }

    @Override

    protected void checkLoopExplosionIteration(MethodScope s, LoopScope loopScope) {

        PEMethodScope methodScope = (PEMethodScope) s;

        if (loopScope.loopIteration > Options.MaximumLoopExplosionCount.getValue(options)) {

            throw tooManyLoopExplosionIterations(methodScope, options);

        }

    }