/*

 * Copyright (c) 2011, 2019, 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.nodes;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Iterator;

import java.util.List;

import java.util.SortedSet;

import java.util.TreeSet;

import java.util.concurrent.atomic.AtomicLong;

import java.util.function.Consumer;

import java.util.stream.Collectors;

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

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

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

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

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

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

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

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

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

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

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

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.JavaMethodContext;

import org.graalvm.compiler.debug.TTY;

import org.graalvm.compiler.graph.Graph;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeMap;

import org.graalvm.compiler.graph.NodeSourcePosition;

import org.graalvm.compiler.nodes.calc.FloatingNode;

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

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

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

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

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

import org.graalvm.compiler.options.OptionValues;

import jdk.vm.ci.code.BytecodeFrame;

import jdk.vm.ci.meta.Assumptions;

import jdk.vm.ci.meta.Assumptions.Assumption;

import jdk.vm.ci.meta.DefaultProfilingInfo;

import jdk.vm.ci.meta.JavaMethod;

import jdk.vm.ci.meta.ProfilingInfo;

import jdk.vm.ci.meta.ResolvedJavaField;

import jdk.vm.ci.meta.ResolvedJavaMethod;

import jdk.vm.ci.meta.SpeculationLog;

import jdk.vm.ci.meta.TriState;

import jdk.vm.ci.runtime.JVMCICompiler;

/**

 * A graph that contains at least one distinguished node : the {@link #start() start} node. This

 * node is the start of the control flow of the graph.

 */

public final class StructuredGraph extends Graph implements JavaMethodContext {

    /**

     * The different stages of the compilation of a {@link Graph} regarding the status of

     * {@link GuardNode guards}, {@link DeoptimizingNode deoptimizations} and {@link FrameState

     * framestates}. The stage of a graph progresses monotonously.

     *

     */

    public enum GuardsStage {

        /**

         * During this stage, there can be {@link FloatingNode floating} {@link DeoptimizingNode}

         * such as {@link GuardNode GuardNodes}. New {@link DeoptimizingNode DeoptimizingNodes} can

         * be introduced without constraints. {@link FrameState} nodes are associated with

         * {@link StateSplit} nodes.

         */

        FLOATING_GUARDS,

        /**

         * During this stage, all {@link DeoptimizingNode DeoptimizingNodes} must be

         * {@link FixedNode fixed} but new {@link DeoptimizingNode DeoptimizingNodes} can still be

         * introduced. {@link FrameState} nodes are still associated with {@link StateSplit} nodes.

         */

        FIXED_DEOPTS,

        /**

         * During this stage, all {@link DeoptimizingNode DeoptimizingNodes} must be

         * {@link FixedNode fixed}. New {@link DeoptimizingNode DeoptimizingNodes} can not be

         * introduced any more. {@link FrameState} nodes are now associated with

         * {@link DeoptimizingNode} nodes.

         */

        AFTER_FSA;

        public boolean allowsFloatingGuards() {

            return this == FLOATING_GUARDS;

        }

        public boolean allowsGuardInsertion() {

            return this.ordinal() <= FIXED_DEOPTS.ordinal();

        }

        public boolean areFrameStatesAtDeopts() {

            return this == AFTER_FSA;

        }

        public boolean areFrameStatesAtSideEffects() {

            return !this.areFrameStatesAtDeopts();

        }

        public boolean areDeoptsFixed() {

            return this.ordinal() >= FIXED_DEOPTS.ordinal();

        }

    }

    /**

     * Constants denoting whether or not {@link Assumption}s can be made while processing a graph.

     */

    public enum AllowAssumptions {

        YES,

        NO;

        public static AllowAssumptions ifTrue(boolean flag) {

            return flag ? YES : NO;

        }

        public static AllowAssumptions ifNonNull(Assumptions assumptions) {

            return assumptions != null ? YES : NO;

        }

    }

    public static class ScheduleResult {

        private final ControlFlowGraph cfg;

        private final NodeMap<Block> nodeToBlockMap;

        private final BlockMap<List<Node>> blockToNodesMap;

        public ScheduleResult(ControlFlowGraph cfg, NodeMap<Block> nodeToBlockMap, BlockMap<List<Node>> blockToNodesMap) {

            this.cfg = cfg;

            this.nodeToBlockMap = nodeToBlockMap;

            this.blockToNodesMap = blockToNodesMap;

        }

        public ControlFlowGraph getCFG() {

            return cfg;

        }

        public NodeMap<Block> getNodeToBlockMap() {

            return nodeToBlockMap;

        }

        public BlockMap<List<Node>> getBlockToNodesMap() {

            return blockToNodesMap;

        }

        public List<Node> nodesFor(Block block) {

            return blockToNodesMap.get(block);

        }

    }

    /**

     * Object used to create a {@link StructuredGraph}.

     */

    public static class Builder {

        private String name;

        private final Assumptions assumptions;

        private SpeculationLog speculationLog;

        private ResolvedJavaMethod rootMethod;

        private CompilationIdentifier compilationId = CompilationIdentifier.INVALID_COMPILATION_ID;

        private int entryBCI = JVMCICompiler.INVOCATION_ENTRY_BCI;

        private boolean useProfilingInfo = true;

        private boolean recordInlinedMethods = true;

        private boolean trackNodeSourcePosition;

        private final OptionValues options;

        private Cancellable cancellable = null;

        private final DebugContext debug;

        private NodeSourcePosition callerContext;

        private boolean isSubstitution;

        /**

         * Creates a builder for a graph.

         */

        public Builder(OptionValues options, DebugContext debug, AllowAssumptions allowAssumptions) {

            this.options = options;

            this.debug = debug;

            this.assumptions = allowAssumptions == AllowAssumptions.YES ? new Assumptions() : null;

            this.trackNodeSourcePosition = Graph.trackNodeSourcePositionDefault(options, debug);

        }

        /**

         * Creates a builder for a graph that does not support {@link Assumptions}.

         */

        public Builder(OptionValues options, DebugContext debug) {

            this.options = options;

            this.debug = debug;

            this.assumptions = null;

            this.trackNodeSourcePosition = Graph.trackNodeSourcePositionDefault(options, debug);

        }

        public String getName() {

            return name;

        }

        public Builder name(String s) {

            this.name = s;

            return this;

        }

        /**

         * @see StructuredGraph#isSubstitution

         */

        public Builder setIsSubstitution(boolean flag) {

            this.isSubstitution = flag;

            return this;

        }

        public ResolvedJavaMethod getMethod() {

            return rootMethod;

        }

        public Builder method(ResolvedJavaMethod method) {

            this.rootMethod = method;

            return this;

        }

        public DebugContext getDebug() {

            return debug;

        }

        public SpeculationLog getSpeculationLog() {

            return speculationLog;

        }

        public Builder speculationLog(SpeculationLog log) {

            this.speculationLog = log;

            return this;

        }

        public CompilationIdentifier getCompilationId() {

            return compilationId;

        }

        public Builder compilationId(CompilationIdentifier id) {

            this.compilationId = id;

            return this;

        }

        public Cancellable getCancellable() {

            return cancellable;

        }

        public Builder cancellable(Cancellable cancel) {

            this.cancellable = cancel;

            return this;

        }

        public int getEntryBCI() {

            return entryBCI;

        }

        public Builder entryBCI(int bci) {

            this.entryBCI = bci;

            return this;

        }

        public boolean getUseProfilingInfo() {

            return useProfilingInfo;

        }

        public Builder useProfilingInfo(boolean flag) {

            this.useProfilingInfo = flag;

            return this;

        }

        public boolean getRecordInlinedMethods() {

            return recordInlinedMethods;

        }

        public Builder recordInlinedMethods(boolean flag) {

            this.recordInlinedMethods = flag;

            return this;

        }

        public Builder trackNodeSourcePosition(boolean flag) {

            if (flag) {

                this.trackNodeSourcePosition = true;

            }

            return this;

        }

        public Builder callerContext(NodeSourcePosition context) {

            this.callerContext = context;

            return this;

        }

        public StructuredGraph build() {

            List<ResolvedJavaMethod> inlinedMethods = recordInlinedMethods ? new ArrayList<>() : null;

            // @formatter:off

            return new StructuredGraph(name,

                            rootMethod,

                            entryBCI,

                            assumptions,

                            speculationLog,

                            useProfilingInfo,

                            isSubstitution,

                            inlinedMethods,

                            trackNodeSourcePosition,

                            compilationId,

                            options,

                            debug,

                            cancellable,

                            callerContext);

            // @formatter:on

        }

    }

    public static final long INVALID_GRAPH_ID = -1;

    private static final AtomicLong uniqueGraphIds = new AtomicLong();

    private StartNode start;

    private ResolvedJavaMethod rootMethod;

    private final long graphId;

    private final CompilationIdentifier compilationId;

    private final int entryBCI;

    private GuardsStage guardsStage = GuardsStage.FLOATING_GUARDS;

    private boolean isAfterFloatingReadPhase = false;

    private boolean isAfterFixedReadPhase = false;

    private boolean hasValueProxies = true;

    private boolean isAfterExpandLogic = false;

    private final boolean useProfilingInfo;

    private final Cancellable cancellable;

    private final boolean isSubstitution;

    /**

     * The assumptions made while constructing and transforming this graph.

     */

    private final Assumptions assumptions;

    private SpeculationLog speculationLog;

    private ScheduleResult lastSchedule;

    private final InliningLog inliningLog;

    /**

     * Call stack (context) leading to construction of this graph.

     */

    private final NodeSourcePosition callerContext;

    /**

     * Records the methods that were used while constructing this graph, one entry for each time a

     * specific method is used. This will be {@code null} if recording of inlined methods is

     * disabled for the graph.

     */

    private final List<ResolvedJavaMethod> methods;

    /**

     * Records the fields that were accessed while constructing this graph.

     */

    private EconomicSet<ResolvedJavaField> fields = null;

    private enum UnsafeAccessState {

        NO_ACCESS,

        HAS_ACCESS,

        DISABLED

    }

    private UnsafeAccessState hasUnsafeAccess = UnsafeAccessState.NO_ACCESS;

    public static final boolean USE_PROFILING_INFO = true;

    public static final boolean NO_PROFILING_INFO = false;

    private StructuredGraph(String name,

                    ResolvedJavaMethod method,

                    int entryBCI,

                    Assumptions assumptions,

                    SpeculationLog speculationLog,

                    boolean useProfilingInfo,

                    boolean isSubstitution,

                    List<ResolvedJavaMethod> methods,

                    boolean trackNodeSourcePosition,

                    CompilationIdentifier compilationId,

                    OptionValues options,

                    DebugContext debug,

                    Cancellable cancellable,

                    NodeSourcePosition context) {

        super(name, options, debug, trackNodeSourcePosition);

        this.setStart(add(new StartNode()));

        this.rootMethod = method;

        this.graphId = uniqueGraphIds.incrementAndGet();

        this.compilationId = compilationId;

        this.entryBCI = entryBCI;

        this.assumptions = assumptions;

        this.methods = methods;

        this.speculationLog = speculationLog;

        this.useProfilingInfo = useProfilingInfo;

        this.isSubstitution = isSubstitution;

        assert checkIsSubstitutionInvariants(method, isSubstitution);

        this.cancellable = cancellable;

        this.inliningLog = new InliningLog(rootMethod, GraalOptions.TraceInlining.getValue(options));

        this.callerContext = context;

    }

    private static boolean checkIsSubstitutionInvariants(ResolvedJavaMethod method, boolean isSubstitution) {

        if (method != null) {

            if (method.getAnnotation(Snippet.class) != null || method.getAnnotation(MethodSubstitution.class) != null) {

                assert isSubstitution : "Graph for method " + method.format("%H.%n(%p)") +

                                " annotated by " + Snippet.class.getName() + " or " +

                                MethodSubstitution.class.getName() +

                                " must have its `isSubstitution` field set to true";

            }

        }

        return true;

    }

    public void setLastSchedule(ScheduleResult result) {

        lastSchedule = result;

    }

    public ScheduleResult getLastSchedule() {

        return lastSchedule;

    }

    public void clearLastSchedule() {

        setLastSchedule(null);

    }

    @Override

    public boolean maybeCompress() {

        if (super.maybeCompress()) {

            /*

             * The schedule contains a NodeMap which is unusable after compression.

             */

            clearLastSchedule();

            return true;

        }

        return false;

    }

    public Stamp getReturnStamp() {

        Stamp returnStamp = null;

        for (ReturnNode returnNode : getNodes(ReturnNode.TYPE)) {

            ValueNode result = returnNode.result();

            if (result != null) {

                if (returnStamp == null) {

                    returnStamp = result.stamp(NodeView.DEFAULT);

                } else {

                    returnStamp = returnStamp.meet(result.stamp(NodeView.DEFAULT));

                }

            }

        }

        return returnStamp;

    }

    @Override

    public String toString() {

        StringBuilder buf = new StringBuilder(getClass().getSimpleName() + ":" + graphId);

        String sep = "{";

        if (name != null) {

            buf.append(sep);

            buf.append(name);

            sep = ", ";

        }

        if (method() != null) {

            buf.append(sep);

            buf.append(method());

            sep = ", ";

        }

        if (!sep.equals("{")) {

            buf.append("}");

        }

        return buf.toString();

    }

    public StartNode start() {

        return start;

    }

    /**

     * Gets the root method from which this graph was built.

     *

     * @return null if this method was not built from a method or the method is not available

     */

    public ResolvedJavaMethod method() {

        return rootMethod;

    }