/*

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

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

import java.util.concurrent.atomic.AtomicLong;

import java.util.function.Consumer;

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

import org.graalvm.compiler.graph.Graph;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeMap;

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 org.graalvm.util.EconomicMap;

import org.graalvm.util.EconomicSet;

import org.graalvm.util.Equivalence;

import org.graalvm.util.UnmodifiableEconomicMap;

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 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 final OptionValues options;

        private Cancellable cancellable = null;

        /**

         * Creates a builder for a graph.

         */

        public Builder(OptionValues options, AllowAssumptions allowAssumptions) {

            this.options = options;

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

        }

        /**

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

         */

        public Builder(OptionValues options) {

            this.options = options;

            assumptions = null;

        }

        public Builder name(String s) {

            this.name = s;

            return this;

        }

        public Builder method(ResolvedJavaMethod method) {

            this.rootMethod = method;

            return this;

        }

        public Builder speculationLog(SpeculationLog log) {

            this.speculationLog = log;

            return this;

        }

        public Builder compilationId(CompilationIdentifier id) {

            this.compilationId = id;

            return this;

        }

        public Builder cancellable(Cancellable cancel) {

            this.cancellable = cancel;

            return this;

        }

        public Builder entryBCI(int bci) {

            this.entryBCI = bci;

            return this;

        }

        public Builder useProfilingInfo(boolean flag) {

            this.useProfilingInfo = flag;

            return this;

        }

        public StructuredGraph build() {

            return new StructuredGraph(name, rootMethod, entryBCI, assumptions, speculationLog, useProfilingInfo, compilationId, options, cancellable);

        }

    }

    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;

    /**

     * The assumptions made while constructing and transforming this graph.

     */

    private final Assumptions assumptions;

    private ScheduleResult lastSchedule;

    /**

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

     * specific method is used.

     */

    private final List<ResolvedJavaMethod> methods = new ArrayList<>();

    /**

     * 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,

                    CompilationIdentifier compilationId,

                    OptionValues options,

                    Cancellable cancellable) {

        super(name, options);

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

        this.rootMethod = method;

        this.graphId = uniqueGraphIds.incrementAndGet();

        this.compilationId = compilationId;

        this.entryBCI = entryBCI;

        this.assumptions = assumptions;

        this.speculationLog = speculationLog;

        this.useProfilingInfo = useProfilingInfo;

        this.cancellable = cancellable;

    }

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

                } else {

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

                }

            }

        }

        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;

    }

    public int getEntryBCI() {

        return entryBCI;

    }

    public Cancellable getCancellable() {

        return cancellable;

    }

    public void checkCancellation() {

        if (cancellable != null && cancellable.isCancelled()) {

            CancellationBailoutException.cancelCompilation();

        }

    }

    public boolean isOSR() {

        return entryBCI != JVMCICompiler.INVOCATION_ENTRY_BCI;

    }

    public long graphId() {

        return graphId;

    }

    /**

     * @see CompilationIdentifier

     */

    public CompilationIdentifier compilationId() {

        return compilationId;

    }

    public void setStart(StartNode start) {

        this.start = start;

    }

    /**

     * Creates a copy of this graph.

     *

     * @param newName the name of the copy, used for debugging purposes (can be null)

     * @param duplicationMapCallback consumer of the duplication map created during the copying

     */

    @Override

    protected Graph copy(String newName, Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback) {

        return copy(newName, duplicationMapCallback, compilationId);

    }

    private StructuredGraph copy(String newName, Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, CompilationIdentifier newCompilationId) {

        AllowAssumptions allowAssumptions = AllowAssumptions.ifNonNull(assumptions);

        StructuredGraph copy = new StructuredGraph(newName,

                        method(),

                        entryBCI,

                        assumptions == null ? null : new Assumptions(),

                        speculationLog,

                        useProfilingInfo,

                        newCompilationId,

                        getOptions(), null);

        if (allowAssumptions == AllowAssumptions.YES && assumptions != null) {

            copy.assumptions.record(assumptions);

        }

        copy.hasUnsafeAccess = hasUnsafeAccess;

        copy.setGuardsStage(getGuardsStage());

        copy.isAfterFloatingReadPhase = isAfterFloatingReadPhase;

        copy.hasValueProxies = hasValueProxies;

        copy.isAfterExpandLogic = isAfterExpandLogic;

        EconomicMap<Node, Node> replacements = EconomicMap.create(Equivalence.IDENTITY);

        replacements.put(start, copy.start);

        UnmodifiableEconomicMap<Node, Node> duplicates = copy.addDuplicates(getNodes(), this, this.getNodeCount(), replacements);

        if (duplicationMapCallback != null) {

            duplicationMapCallback.accept(duplicates);

        }

        return copy;

    }

    public StructuredGraph copyWithIdentifier(CompilationIdentifier newCompilationId) {

        return copy(name, null, newCompilationId);

    }

    public ParameterNode getParameter(int index) {

        for (ParameterNode param : getNodes(ParameterNode.TYPE)) {

            if (param.index() == index) {

                return param;

            }

        }

        return null;

    }

    public Iterable<Invoke> getInvokes() {

        final Iterator<MethodCallTargetNode> callTargets = getNodes(MethodCallTargetNode.TYPE).iterator();

        return new Iterable<Invoke>() {

            private Invoke next;

            @Override

            public Iterator<Invoke> iterator() {

                return new Iterator<Invoke>() {

                    @Override

                    public boolean hasNext() {

                        if (next == null) {

                            while (callTargets.hasNext()) {

                                Invoke i = callTargets.next().invoke();

                                if (i != null) {

                                    next = i;

                                    return true;

                                }

                            }

                            return false;

                        } else {

                            return true;

                        }

                    }

                    @Override

                    public Invoke next() {

                        try {

                            return next;

                        } finally {

                            next = null;

                        }

                    }

                    @Override

                    public void remove() {

                        throw new UnsupportedOperationException();

                    }

                };

            }

        };

    }

    public boolean hasLoops() {

        return hasNode(LoopBeginNode.TYPE);

    }

    /**

     * Unlinks a node from all its control flow neighbors and then removes it from its graph. The

     * node must have no {@linkplain Node#usages() usages}.

     *

     * @param node the node to be unlinked and removed

     */

    @SuppressWarnings("static-method")

    public void removeFixed(FixedWithNextNode node) {

        assert node != null;

        if (node instanceof AbstractBeginNode) {

            ((AbstractBeginNode) node).prepareDelete();

        }

        assert node.hasNoUsages() : node + " " + node.usages().count() + ", " + node.usages().first();

        GraphUtil.unlinkFixedNode(node);

        node.safeDelete();

    }