/*

 * Copyright (c) 2012, 2015, 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.phases.common.inlining;

import static jdk.vm.ci.meta.DeoptimizationAction.InvalidateReprofile;

import static jdk.vm.ci.meta.DeoptimizationReason.NullCheckException;

import static org.graalvm.compiler.core.common.GraalOptions.HotSpotPrintInlining;

import java.lang.reflect.Constructor;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.List;

import java.util.Objects;

import java.util.function.Consumer;

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

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

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

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

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

import org.graalvm.compiler.core.common.util.Util;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.graph.GraalGraphError;

import org.graalvm.compiler.graph.Graph;

import org.graalvm.compiler.graph.Graph.DuplicationReplacement;

import org.graalvm.compiler.graph.Graph.NodeEventScope;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeInputList;

import org.graalvm.compiler.graph.NodeMap;

import org.graalvm.compiler.graph.NodeSourcePosition;

import org.graalvm.compiler.graph.NodeWorkList;

import org.graalvm.compiler.nodeinfo.Verbosity;

import org.graalvm.compiler.nodes.AbstractBeginNode;

import org.graalvm.compiler.nodes.AbstractEndNode;

import org.graalvm.compiler.nodes.AbstractMergeNode;

import org.graalvm.compiler.nodes.BeginNode;

import org.graalvm.compiler.nodes.CallTargetNode;

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

import org.graalvm.compiler.nodes.DeoptimizeNode;

import org.graalvm.compiler.nodes.EndNode;

import org.graalvm.compiler.nodes.FixedGuardNode;

import org.graalvm.compiler.nodes.FixedNode;

import org.graalvm.compiler.nodes.FixedWithNextNode;

import org.graalvm.compiler.nodes.FrameState;

import org.graalvm.compiler.nodes.Invoke;

import org.graalvm.compiler.nodes.InvokeNode;

import org.graalvm.compiler.nodes.InvokeWithExceptionNode;

import org.graalvm.compiler.nodes.KillingBeginNode;

import org.graalvm.compiler.nodes.LogicNode;

import org.graalvm.compiler.nodes.MergeNode;

import org.graalvm.compiler.nodes.ParameterNode;

import org.graalvm.compiler.nodes.PhiNode;

import org.graalvm.compiler.nodes.PiNode;

import org.graalvm.compiler.nodes.ReturnNode;

import org.graalvm.compiler.nodes.StartNode;

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

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

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

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

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

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

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

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

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

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

import org.graalvm.compiler.phases.common.inlining.info.InlineInfo;

import org.graalvm.compiler.phases.common.util.HashSetNodeEventListener;

import org.graalvm.compiler.phases.util.ValueMergeUtil;

import org.graalvm.util.EconomicMap;

import org.graalvm.util.EconomicSet;

import org.graalvm.util.Equivalence;

import org.graalvm.util.UnmodifiableEconomicMap;

import org.graalvm.util.UnmodifiableMapCursor;

import jdk.vm.ci.code.BytecodeFrame;

import jdk.vm.ci.meta.Assumptions;

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

import jdk.vm.ci.meta.ResolvedJavaType;

public class InliningUtil extends ValueMergeUtil {

    private static final String inliningDecisionsScopeString = "InliningDecisions";

    /**

     * Print a HotSpot-style inlining message to the console.

     */

    private static void printInlining(final InlineInfo info, final int inliningDepth, final boolean success, final String msg, final Object... args) {

        printInlining(info.methodAt(0), info.invoke(), inliningDepth, success, msg, args);

    }

    private static void printInlining(final ResolvedJavaMethod method, final Invoke invoke, final int inliningDepth, final boolean success, final String msg, final Object... args) {

        if (HotSpotPrintInlining.getValue(invoke.asNode().getOptions())) {

            Util.printInlining(method, invoke.bci(), inliningDepth, success, msg, args);

        }

    }

    public static void logInlinedMethod(InlineInfo info, int inliningDepth, boolean allowLogging, String msg, Object... args) {

        logInliningDecision(info, inliningDepth, allowLogging, true, msg, args);

    }

    public static void logNotInlinedMethod(InlineInfo info, int inliningDepth, String msg, Object... args) {

        logInliningDecision(info, inliningDepth, true, false, msg, args);

    }

    public static void logInliningDecision(InlineInfo info, int inliningDepth, boolean allowLogging, boolean success, String msg, final Object... args) {

        if (allowLogging) {

            printInlining(info, inliningDepth, success, msg, args);

            DebugContext debug = info.graph().getDebug();

            if (shouldLogInliningDecision(debug)) {

                logInliningDecision(debug, methodName(info), success, msg, args);

            }

        }

    }

    @SuppressWarnings("try")

    public static void logInliningDecision(DebugContext debug, final String msg, final Object... args) {

        try (DebugContext.Scope s = debug.scope(inliningDecisionsScopeString)) {

            // Can't use log here since we are varargs

            if (debug.isLogEnabled()) {

                debug.logv(msg, args);

            }

        }

    }

    public static void logNotInlinedMethod(Invoke invoke, String msg) {

        DebugContext debug = invoke.asNode().getDebug();

        if (shouldLogInliningDecision(debug)) {

            String methodString = invoke.toString();

            if (invoke.callTarget() == null) {

                methodString += " callTarget=null";

            } else {

                String targetName = invoke.callTarget().targetName();

                if (!methodString.endsWith(targetName)) {

                    methodString += " " + targetName;

                }

            }

            logInliningDecision(debug, methodString, false, msg, new Object[0]);

        }

    }

    public static void logNotInlined(Invoke invoke, int inliningDepth, ResolvedJavaMethod method, String msg) {

        logNotInlinedInvoke(invoke, inliningDepth, method, msg, new Object[0]);

    }

    public static void logNotInlinedInvoke(Invoke invoke, int inliningDepth, ResolvedJavaMethod method, String msg, Object... args) {

        DebugContext debug = invoke.asNode().getDebug();

        printInlining(method, invoke, inliningDepth, false, msg, args);

        if (shouldLogInliningDecision(debug)) {

            String methodString = methodName(method, invoke);

            logInliningDecision(debug, methodString, false, msg, args);

        }

    }

    private static void logInliningDecision(DebugContext debug, final String methodString, final boolean success, final String msg, final Object... args) {

        String inliningMsg = "inlining " + methodString + ": " + msg;

        if (!success) {

            inliningMsg = "not " + inliningMsg;

        }

        logInliningDecision(debug, inliningMsg, args);

    }

    @SuppressWarnings("try")

    public static boolean shouldLogInliningDecision(DebugContext debug) {

        try (DebugContext.Scope s = debug.scope(inliningDecisionsScopeString)) {

            return debug.isLogEnabled();

        }

    }

    private static String methodName(ResolvedJavaMethod method, Invoke invoke) {

        if (invoke != null && invoke.stateAfter() != null) {

            return methodName(invoke.stateAfter(), invoke.bci()) + ": " + method.format("%H.%n(%p):%r") + " (" + method.getCodeSize() + " bytes)";

        } else {

            return method.format("%H.%n(%p):%r") + " (" + method.getCodeSize() + " bytes)";

        }

    }

    private static String methodName(InlineInfo info) {

        if (info == null) {

            return "null";

        } else if (info.invoke() != null && info.invoke().stateAfter() != null) {

            return methodName(info.invoke().stateAfter(), info.invoke().bci()) + ": " + info.toString();

        } else {

            return info.toString();

        }

    }

    private static String methodName(FrameState frameState, int bci) {

        StringBuilder sb = new StringBuilder();

        if (frameState.outerFrameState() != null) {

            sb.append(methodName(frameState.outerFrameState(), frameState.outerFrameState().bci));

            sb.append("->");

        }

        ResolvedJavaMethod method = frameState.getMethod();

        sb.append(method != null ? method.format("%h.%n") : "?");

        sb.append("@").append(bci);

        return sb.toString();

    }

    public static void replaceInvokeCallTarget(Invoke invoke, StructuredGraph graph, InvokeKind invokeKind, ResolvedJavaMethod targetMethod) {

        MethodCallTargetNode oldCallTarget = (MethodCallTargetNode) invoke.callTarget();

        MethodCallTargetNode newCallTarget = graph.add(new MethodCallTargetNode(invokeKind, targetMethod, oldCallTarget.arguments().toArray(new ValueNode[0]), oldCallTarget.returnStamp(),

                        oldCallTarget.getProfile()));

        invoke.asNode().replaceFirstInput(oldCallTarget, newCallTarget);

    }

    public static PiNode createAnchoredReceiver(StructuredGraph graph, GuardingNode anchor, ResolvedJavaType commonType, ValueNode receiver, boolean exact) {

        return createAnchoredReceiver(graph, anchor, receiver,

                        exact ? StampFactory.objectNonNull(TypeReference.createExactTrusted(commonType)) : StampFactory.objectNonNull(TypeReference.createTrusted(graph.getAssumptions(), commonType)));

    }

    private static PiNode createAnchoredReceiver(StructuredGraph graph, GuardingNode anchor, ValueNode receiver, Stamp stamp) {

        // to avoid that floating reads on receiver fields float above the type check

        return graph.unique(new PiNode(receiver, stamp, (ValueNode) anchor));

    }

    /**

     * @return null iff the check succeeds, otherwise a (non-null) descriptive message.

     */

    public static String checkInvokeConditions(Invoke invoke) {

        if (invoke.predecessor() == null || !invoke.asNode().isAlive()) {

            return "the invoke is dead code";

        }

        if (!(invoke.callTarget() instanceof MethodCallTargetNode)) {

            return "the invoke has already been lowered, or has been created as a low-level node";

        }

        MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();

        if (callTarget.targetMethod() == null) {

            return "target method is null";

        }

        assert invoke.stateAfter() != null : invoke;

        if (!invoke.useForInlining()) {

            return "the invoke is marked to be not used for inlining";

        }

        ValueNode receiver = callTarget.receiver();

        if (receiver != null && receiver.isConstant() && receiver.isNullConstant()) {

            return "receiver is null";

        }

        return null;

    }

    /**

     * Performs an actual inlining, thereby replacing the given invoke with the given inlineGraph.

     *

     * @param invoke the invoke that will be replaced

     * @param inlineGraph the graph that the invoke will be replaced with

     * @param receiverNullCheck true if a null check needs to be generated for non-static inlinings,

     *            false if no such check is required

     * @param inlineeMethod the actual method being inlined. Maybe be null for snippets.

     */

    @SuppressWarnings("try")

    public static UnmodifiableEconomicMap<Node, Node> inline(Invoke invoke, StructuredGraph inlineGraph, boolean receiverNullCheck, ResolvedJavaMethod inlineeMethod) {

        FixedNode invokeNode = invoke.asNode();

        StructuredGraph graph = invokeNode.graph();

        final NodeInputList<ValueNode> parameters = invoke.callTarget().arguments();

        assert inlineGraph.getGuardsStage().ordinal() >= graph.getGuardsStage().ordinal();

        assert !invokeNode.graph().isAfterFloatingReadPhase() : "inline isn't handled correctly after floating reads phase";

        if (receiverNullCheck && !((MethodCallTargetNode) invoke.callTarget()).isStatic()) {

            nonNullReceiver(invoke);

        }

        ArrayList<Node> nodes = new ArrayList<>(inlineGraph.getNodes().count());

        ArrayList<ReturnNode> returnNodes = new ArrayList<>(4);

        ArrayList<Invoke> partialIntrinsicExits = new ArrayList<>();

        UnwindNode unwindNode = null;

        final StartNode entryPointNode = inlineGraph.start();

        FixedNode firstCFGNode = entryPointNode.next();

        if (firstCFGNode == null) {

            throw new IllegalStateException("Inlined graph is in invalid state: " + inlineGraph);

        }

        for (Node node : inlineGraph.getNodes()) {

            if (node == entryPointNode || (node == entryPointNode.stateAfter() && node.usages().count() == 1) || node instanceof ParameterNode) {

                // Do nothing.

            } else {

                nodes.add(node);

                if (node instanceof ReturnNode) {

                    returnNodes.add((ReturnNode) node);

                } else if (node instanceof Invoke) {

                    Invoke invokeInInlineGraph = (Invoke) node;

                    if (invokeInInlineGraph.bci() == BytecodeFrame.UNKNOWN_BCI) {

                        ResolvedJavaMethod target1 = inlineeMethod;

                        ResolvedJavaMethod target2 = invokeInInlineGraph.callTarget().targetMethod();

                        assert target1.equals(target2) : String.format("invoke in inlined method expected to be partial intrinsic exit (i.e., call to %s), not a call to %s",

                                        target1.format("%H.%n(%p)"), target2.format("%H.%n(%p)"));

                        partialIntrinsicExits.add(invokeInInlineGraph);

                    }

                } else if (node instanceof UnwindNode) {

                    assert unwindNode == null;

                    unwindNode = (UnwindNode) node;

                }

            }

        }

        final AbstractBeginNode prevBegin = AbstractBeginNode.prevBegin(invokeNode);

        DuplicationReplacement localReplacement = new DuplicationReplacement() {

            @Override

            public Node replacement(Node node) {

                if (node instanceof ParameterNode) {

                    return parameters.get(((ParameterNode) node).index());

                } else if (node == entryPointNode) {

                    return prevBegin;

                }

                return node;

            }

        };

        assert invokeNode.successors().first() != null : invoke;

        assert invokeNode.predecessor() != null;

        EconomicMap<Node, Node> duplicates = graph.addDuplicates(nodes, inlineGraph, inlineGraph.getNodeCount(), localReplacement);

        FrameState stateAfter = invoke.stateAfter();

        assert stateAfter == null || stateAfter.isAlive();

        FrameState stateAtExceptionEdge = null;

        if (invoke instanceof InvokeWithExceptionNode) {

            InvokeWithExceptionNode invokeWithException = ((InvokeWithExceptionNode) invoke);

            if (unwindNode != null) {

                ExceptionObjectNode obj = (ExceptionObjectNode) invokeWithException.exceptionEdge();

                stateAtExceptionEdge = obj.stateAfter();

            }

        }

        updateSourcePositions(invoke, inlineGraph, duplicates, !Objects.equals(inlineGraph.method(), inlineeMethod));

        if (stateAfter != null) {

            processFrameStates(invoke, inlineGraph, duplicates, stateAtExceptionEdge, returnNodes.size() > 1);

            int callerLockDepth = stateAfter.nestedLockDepth();

            if (callerLockDepth != 0) {

                for (MonitorIdNode original : inlineGraph.getNodes(MonitorIdNode.TYPE)) {

                    MonitorIdNode monitor = (MonitorIdNode) duplicates.get(original);

                    processMonitorId(invoke.stateAfter(), monitor);

                }

            }

        } else {

            assert checkContainsOnlyInvalidOrAfterFrameState(duplicates);

        }

        firstCFGNode = (FixedNode) duplicates.get(firstCFGNode);

        for (int i = 0; i < returnNodes.size(); i++) {

            returnNodes.set(i, (ReturnNode) duplicates.get(returnNodes.get(i)));

        }

        for (Invoke exit : partialIntrinsicExits) {

            // A partial intrinsic exit must be replaced with a call to

            // the intrinsified method.

            Invoke dup = (Invoke) duplicates.get(exit.asNode());

            if (dup instanceof InvokeNode) {

                InvokeNode repl = graph.add(new InvokeNode(invoke.callTarget(), invoke.bci()));

                dup.intrinsify(repl.asNode());

            } else {

                ((InvokeWithExceptionNode) dup).replaceWithNewBci(invoke.bci());

            }

        }

        if (unwindNode != null) {

            unwindNode = (UnwindNode) duplicates.get(unwindNode);

        }

        finishInlining(invoke, graph, firstCFGNode, returnNodes, unwindNode, inlineGraph.getAssumptions(), inlineGraph);

        GraphUtil.killCFG(invokeNode);

        return duplicates;

    }

    /**

     * Inline {@code inlineGraph} into the current replacing the node {@code Invoke} and return the

     * set of nodes which should be canonicalized. The set should only contain nodes which modified

     * by the inlining since the current graph and {@code inlineGraph} are expected to already be

     * canonical.

     *

     * @param invoke

     * @param inlineGraph

     * @param receiverNullCheck

     * @param inlineeMethod

     * @return the set of nodes to canonicalize

     */

    @SuppressWarnings("try")

    public static EconomicSet<Node> inlineForCanonicalization(Invoke invoke, StructuredGraph inlineGraph, boolean receiverNullCheck, ResolvedJavaMethod inlineeMethod) {

        return inlineForCanonicalization(invoke, inlineGraph, receiverNullCheck, inlineeMethod, null);

    }

    @SuppressWarnings("try")

    public static EconomicSet<Node> inlineForCanonicalization(Invoke invoke, StructuredGraph inlineGraph, boolean receiverNullCheck, ResolvedJavaMethod inlineeMethod,

                    Consumer<UnmodifiableEconomicMap<Node, Node>> duplicatesConsumer) {

        HashSetNodeEventListener listener = new HashSetNodeEventListener();

        /*

         * This code relies on the fact that Graph.addDuplicates doesn't trigger the

         * NodeEventListener to track only nodes which were modified into the process of inlining

         * the graph into the current graph.

         */

        try (NodeEventScope nes = invoke.asNode().graph().trackNodeEvents(listener)) {

            UnmodifiableEconomicMap<Node, Node> duplicates = InliningUtil.inline(invoke, inlineGraph, receiverNullCheck, inlineeMethod);

            if (duplicatesConsumer != null) {

                duplicatesConsumer.accept(duplicates);

            }

        }

        return listener.getNodes();

    }

    private static ValueNode finishInlining(Invoke invoke, StructuredGraph graph, FixedNode firstNode, List<ReturnNode> returnNodes, UnwindNode unwindNode, Assumptions inlinedAssumptions,

                    StructuredGraph inlineGraph) {

        FixedNode invokeNode = invoke.asNode();

        FrameState stateAfter = invoke.stateAfter();

        assert stateAfter == null || stateAfter.isAlive();

        invokeNode.replaceAtPredecessor(firstNode);

        if (invoke instanceof InvokeWithExceptionNode) {

            InvokeWithExceptionNode invokeWithException = ((InvokeWithExceptionNode) invoke);

            if (unwindNode != null && unwindNode.isAlive()) {

                assert unwindNode.predecessor() != null;

                assert invokeWithException.exceptionEdge().successors().count() == 1;

                ExceptionObjectNode obj = (ExceptionObjectNode) invokeWithException.exceptionEdge();

                obj.replaceAtUsages(unwindNode.exception());

                Node n = obj.next();

                obj.setNext(null);

                unwindNode.replaceAndDelete(n);

                obj.replaceAtPredecessor(null);

                obj.safeDelete();

            } else {

                invokeWithException.killExceptionEdge();

            }

            // get rid of memory kill

            AbstractBeginNode begin = invokeWithException.next();

            if (begin instanceof KillingBeginNode) {

                AbstractBeginNode newBegin = new BeginNode();

                graph.addAfterFixed(begin, graph.add(newBegin));

                begin.replaceAtUsages(newBegin);

                graph.removeFixed(begin);

            }

        } else {

            if (unwindNode != null && unwindNode.isAlive()) {

                DeoptimizeNode deoptimizeNode = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.NotCompiledExceptionHandler));

                unwindNode.replaceAndDelete(deoptimizeNode);

            }

        }

        ValueNode returnValue;

        if (!returnNodes.isEmpty()) {

            FixedNode n = invoke.next();

            invoke.setNext(null);

            if (returnNodes.size() == 1) {

                ReturnNode returnNode = returnNodes.get(0);

                returnValue = returnNode.result();

                invokeNode.replaceAtUsages(returnValue);

                returnNode.replaceAndDelete(n);

            } else {

                MergeNode merge = graph.add(new MergeNode());

                merge.setStateAfter(stateAfter);

                returnValue = mergeReturns(merge, returnNodes);

                invokeNode.replaceAtUsages(returnValue);

                if (merge.isPhiAtMerge(returnValue)) {

                    fixFrameStates(graph, merge, (PhiNode) returnValue);

                }

                merge.setNext(n);

            }

        } else {

            returnValue = null;

            invokeNode.replaceAtUsages(null);

            GraphUtil.killCFG(invoke.next());

        }

        // Copy assumptions from inlinee to caller

        Assumptions assumptions = graph.getAssumptions();

        if (assumptions != null) {

            if (inlinedAssumptions != null) {

                assumptions.record(inlinedAssumptions);

            }

        } else {

            assert inlinedAssumptions == null : String.format("cannot inline graph (%s) which makes assumptions into a graph (%s) that doesn't", inlineGraph, graph);

        }

        // Copy inlined methods from inlinee to caller

        graph.updateMethods(inlineGraph);

        // Update the set of accessed fields

        if (GraalOptions.GeneratePIC.getValue(graph.getOptions())) {