/*

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

import java.util.List;

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

import org.graalvm.compiler.debug.Debug.Scope;

import org.graalvm.compiler.debug.Fingerprint;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.debug.internal.method.MethodMetricsImpl;

import org.graalvm.compiler.debug.internal.method.MethodMetricsInlineeScopeInfo;

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

            if (shouldLogInliningDecision()) {

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

            }

        }

    }

    @SuppressWarnings("try")

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

        try (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) {

        if (shouldLogInliningDecision()) {

            String methodString = invoke.toString();

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

                methodString += " callTarget=null";

            } else {

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

                if (!methodString.endsWith(targetName)) {

                    methodString += " " + targetName;

                }

            }

            logInliningDecision(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) {

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

        if (shouldLogInliningDecision()) {

            String methodString = methodName(method, invoke);

            logInliningDecision(methodString, false, msg, args);

        }

    }

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

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

        if (!success) {

            inliningMsg = "not " + inliningMsg;

        }

        logInliningDecision(inliningMsg, args);

    }

    @SuppressWarnings("try")

    public static boolean shouldLogInliningDecision() {

        try (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("->");

        }

        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();

        MethodMetricsInlineeScopeInfo m = MethodMetricsInlineeScopeInfo.create(graph.getOptions());

        try (Debug.Scope s = Debug.methodMetricsScope("InlineEnhancement", m, false)) {

            if (Fingerprint.ENABLED) {

                Fingerprint.submit("inlining %s into %s: %s", formatGraph(inlineGraph), formatGraph(invoke.asNode().graph()), inlineGraph.getNodes().snapshot());

            }

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

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

            UnmodifiableEconomicMap<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);

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

            }

            if (unwindNode != null) {

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

            }

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

            GraphUtil.killCFG(invokeNode);

            if (Debug.isMethodMeterEnabled() && m != null) {

                MethodMetricsImpl.recordInlinee(m.getRootMethod(), invoke.asNode().graph().method(), inlineeMethod);

            }

            return duplicates;

        }

    }

    /**

     * Inline {@code inlineGraph} into the current replacoing 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) {

        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)) {

            InliningUtil.inline(invoke, inlineGraph, receiverNullCheck, inlineeMethod);

        }

        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 {

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

                merge.setStateAfter(stateAfter);

                returnValue = mergeReturns(merge, returnNodes);

                invokeNode.replaceAtUsages(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())) {

            graph.updateFields(inlineGraph);

        }

        if (inlineGraph.hasUnsafeAccess()) {

            graph.markUnsafeAccess();

        }

        assert inlineGraph.getSpeculationLog() == null : "Only the root graph should have a speculation log";

        return returnValue;

    }

    private static String formatGraph(StructuredGraph graph) {

        if (graph.method() == null) {

            return graph.name;

        }

        return graph.method().format("%H.%n(%p)");

    }

    @SuppressWarnings("try")

    private static void updateSourcePositions(Invoke invoke, StructuredGraph inlineGraph, UnmodifiableEconomicMap<Node, Node> duplicates) {

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

            if (invoke.asNode().getNodeSourcePosition() == null) {

                // Temporarily ignore the assert below.

                return;