/*

 * 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 static org.graalvm.compiler.debug.GraalError.shouldNotReachHere;

import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;

import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.BitSet;

import java.util.Deque;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

import java.util.SortedMap;

import java.util.TreeMap;

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

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

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

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

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

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

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

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.graph.Edges;

import org.graalvm.compiler.graph.Graph;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeBitMap;

import org.graalvm.compiler.graph.NodeClass;

import org.graalvm.compiler.graph.NodeInputList;

import org.graalvm.compiler.graph.NodeList;

import org.graalvm.compiler.graph.NodeSourcePosition;

import org.graalvm.compiler.graph.NodeSuccessorList;

import org.graalvm.compiler.graph.spi.Canonicalizable;

import org.graalvm.compiler.graph.spi.CanonicalizerTool;

import org.graalvm.compiler.nodeinfo.InputType;

import org.graalvm.compiler.nodeinfo.NodeInfo;

import org.graalvm.compiler.nodes.GraphDecoder.MethodScope;

import org.graalvm.compiler.nodes.GraphDecoder.ProxyPlaceholder;

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

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

import org.graalvm.compiler.nodes.graphbuilderconf.LoopExplosionPlugin.LoopExplosionKind;

import org.graalvm.compiler.options.OptionValues;

import jdk.vm.ci.code.Architecture;

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

import jdk.vm.ci.meta.ResolvedJavaType;

/**

 * Decoder for {@link EncodedGraph encoded graphs} produced by {@link GraphEncoder}. Support for

 * loop explosion during decoding is built into this class, because it requires many interactions

 * with the decoding process. Subclasses can provide canonicalization and simplification of nodes

 * during decoding, as well as method inlining during decoding.

 */

public class GraphDecoder {

    /** Decoding state maintained for each encoded graph. */

    protected class MethodScope {

        /** The loop that contains the call. Only non-null during method inlining. */

        public final LoopScope callerLoopScope;

        /**

         * Mark for nodes that were present before the decoding of this method started. Note that

         * nodes that were decoded after the mark can still be part of an outer method, since

         * floating nodes of outer methods are decoded lazily.

         */

        public final Graph.Mark methodStartMark;

        /** The encode graph that is decoded. */

        public final EncodedGraph encodedGraph;

        /** The highest node order id that a fixed node has in the EncodedGraph. */

        public final int maxFixedNodeOrderId;

        /** Access to the encoded graph. */

        public final TypeReader reader;

        /** The kind of loop explosion to be performed during decoding. */

        public final LoopExplosionKind loopExplosion;

        /** All return nodes encountered during decoding. */

        public final List<ControlSinkNode> returnAndUnwindNodes;

        /** All merges created during loop explosion. */

        public final EconomicSet<Node> loopExplosionMerges;

        /**

         * The start of explosion, and the merge point for when irreducible loops are detected. Only

         * used when {@link MethodScope#loopExplosion} is {@link LoopExplosionKind#MERGE_EXPLODE}.

         */

        public MergeNode loopExplosionHead;

        protected MethodScope(LoopScope callerLoopScope, StructuredGraph graph, EncodedGraph encodedGraph, LoopExplosionKind loopExplosion) {

            this.callerLoopScope = callerLoopScope;

            this.methodStartMark = graph.getMark();

            this.encodedGraph = encodedGraph;

            this.loopExplosion = loopExplosion;

            this.returnAndUnwindNodes = new ArrayList<>(2);

            if (encodedGraph != null) {

                reader = UnsafeArrayTypeReader.create(encodedGraph.getEncoding(), encodedGraph.getStartOffset(), architecture.supportsUnalignedMemoryAccess());

                maxFixedNodeOrderId = reader.getUVInt();

                if (encodedGraph.nodeStartOffsets == null) {

                    int nodeCount = reader.getUVInt();

                    int[] nodeStartOffsets = new int[nodeCount];

                    for (int i = 0; i < nodeCount; i++) {

                        nodeStartOffsets[i] = encodedGraph.getStartOffset() - reader.getUVInt();

                    }

                    encodedGraph.nodeStartOffsets = nodeStartOffsets;

                    graph.setGuardsStage((StructuredGraph.GuardsStage) readObject(this));

                }

            } else {

                reader = null;

                maxFixedNodeOrderId = 0;

            }

            if (loopExplosion != LoopExplosionKind.NONE) {

                loopExplosionMerges = EconomicSet.create(Equivalence.IDENTITY);

            } else {

                loopExplosionMerges = null;

            }

        }

        public boolean isInlinedMethod() {

            return false;

        }

        public NodeSourcePosition getCallerBytecodePosition() {

            return getCallerBytecodePosition(null);

        }

        public NodeSourcePosition getCallerBytecodePosition(NodeSourcePosition position) {

            return position;

        }

    }

    /** Decoding state maintained for each loop in the encoded graph. */

    protected static class LoopScope {

        public final MethodScope methodScope;

        public final LoopScope outer;

        public final int loopDepth;

        public final int loopIteration;

        /**

         * Upcoming loop iterations during loop explosions that have not been processed yet. Only

         * used when {@link MethodScope#loopExplosion} is not {@link LoopExplosionKind#NONE}.

         */

        public Deque<LoopScope> nextIterations;

        /**

         * Information about already processed loop iterations for state merging during loop

         * explosion. Only used when {@link MethodScope#loopExplosion} is

         * {@link LoopExplosionKind#MERGE_EXPLODE}.

         */

        public final EconomicMap<LoopExplosionState, LoopExplosionState> iterationStates;

        public final int loopBeginOrderId;

        /**

         * The worklist of fixed nodes to process. Since we already the correct processing order

         * from the orderId, we just set the orderId bit in the bitset when a node is ready for

         * processing. The lowest set bit is the next node to process.

         */

        public final BitSet nodesToProcess;

        /** Nodes that have been created, indexed by the orderId. */

        public final Node[] createdNodes;

        /**

         * Nodes that have been created in outer loop scopes and existed before starting to process

         * this loop, indexed by the orderId. Only used when {@link MethodScope#loopExplosion} is

         * not {@link LoopExplosionKind#NONE}.

         */

        public final Node[] initialCreatedNodes;

        protected LoopScope(MethodScope methodScope) {

            this.methodScope = methodScope;

            this.outer = null;

            this.nextIterations = methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN ? new ArrayDeque<>(2) : null;

            this.loopDepth = 0;

            this.loopIteration = 0;

            this.iterationStates = null;

            this.loopBeginOrderId = -1;

            int nodeCount = methodScope.encodedGraph.nodeStartOffsets.length;

            this.nodesToProcess = new BitSet(methodScope.maxFixedNodeOrderId);

            this.createdNodes = new Node[nodeCount];

            this.initialCreatedNodes = null;

        }

        protected LoopScope(MethodScope methodScope, LoopScope outer, int loopDepth, int loopIteration, int loopBeginOrderId, Node[] initialCreatedNodes, Node[] createdNodes,

                        Deque<LoopScope> nextIterations, EconomicMap<LoopExplosionState, LoopExplosionState> iterationStates) {

            this.methodScope = methodScope;

            this.outer = outer;

            this.loopDepth = loopDepth;

            this.loopIteration = loopIteration;

            this.nextIterations = nextIterations;

            this.iterationStates = iterationStates;

            this.loopBeginOrderId = loopBeginOrderId;

            this.nodesToProcess = new BitSet(methodScope.maxFixedNodeOrderId);

            this.initialCreatedNodes = initialCreatedNodes;

            this.createdNodes = createdNodes;

        }

        @Override

        public String toString() {

            return loopDepth + "," + loopIteration + (loopBeginOrderId == -1 ? "" : "#" + loopBeginOrderId);

        }

    }

    protected static class LoopExplosionState {

        public final FrameState state;

        public final MergeNode merge;

        public final int hashCode;

        protected LoopExplosionState(FrameState state, MergeNode merge) {

            this.state = state;

            this.merge = merge;

            int h = 0;

            for (ValueNode value : state.values()) {

                if (value == null) {

                    h = h * 31 + 1234;

                } else {

                    h = h * 31 + ProxyPlaceholder.unwrap(value).hashCode();

                }

            }

            this.hashCode = h;

        }

        @Override

        public boolean equals(Object obj) {

            if (!(obj instanceof LoopExplosionState)) {

                return false;

            }

            FrameState otherState = ((LoopExplosionState) obj).state;

            FrameState thisState = state;

            assert thisState.outerFrameState() == otherState.outerFrameState();

            Iterator<ValueNode> thisIter = thisState.values().iterator();

            Iterator<ValueNode> otherIter = otherState.values().iterator();

            while (thisIter.hasNext() && otherIter.hasNext()) {

                ValueNode thisValue = ProxyPlaceholder.unwrap(thisIter.next());

                ValueNode otherValue = ProxyPlaceholder.unwrap(otherIter.next());

                if (thisValue != otherValue) {

                    return false;

                }

            }

            return thisIter.hasNext() == otherIter.hasNext();

        }

        @Override

        public int hashCode() {

            return hashCode;

        }

    }

    /**

     * Additional information encoded for {@link Invoke} nodes to allow method inlining without

     * decoding the frame state and successors beforehand.

     */

    protected static class InvokeData {

        public final Invoke invoke;

        public final ResolvedJavaType contextType;

        public final int invokeOrderId;

        public final int callTargetOrderId;

        public final int stateAfterOrderId;

        public final int nextOrderId;

        public final int nextNextOrderId;

        public final int exceptionOrderId;

        public final int exceptionStateOrderId;

        public final int exceptionNextOrderId;

        public JavaConstant constantReceiver;

        protected InvokeData(Invoke invoke, ResolvedJavaType contextType, int invokeOrderId, int callTargetOrderId, int stateAfterOrderId, int nextOrderId, int nextNextOrderId, int exceptionOrderId,

                        int exceptionStateOrderId, int exceptionNextOrderId) {

            this.invoke = invoke;

            this.contextType = contextType;

            this.invokeOrderId = invokeOrderId;

            this.callTargetOrderId = callTargetOrderId;

            this.stateAfterOrderId = stateAfterOrderId;

            this.nextOrderId = nextOrderId;

            this.nextNextOrderId = nextNextOrderId;

            this.exceptionOrderId = exceptionOrderId;

            this.exceptionStateOrderId = exceptionStateOrderId;

            this.exceptionNextOrderId = exceptionNextOrderId;

        }

    }

    /**

     * A node that is created during {@link LoopExplosionKind#MERGE_EXPLODE loop explosion} that can

     * later be replaced by a ProxyNode if {@link LoopDetector loop detection} finds out that the

     * value is defined in the loop, but used outside the loop.

     */

    @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)

    protected static final class ProxyPlaceholder extends FloatingNode implements Canonicalizable {

        public static final NodeClass<ProxyPlaceholder> TYPE = NodeClass.create(ProxyPlaceholder.class);

        @Input ValueNode value;

        @Input(InputType.Association) Node proxyPoint;

        public ProxyPlaceholder(ValueNode value, MergeNode proxyPoint) {

            super(TYPE, value.stamp(NodeView.DEFAULT));

            this.value = value;

            this.proxyPoint = proxyPoint;

        }

        void setValue(ValueNode value) {

            updateUsages(this.value, value);

            this.value = value;

        }

        @Override

        public Node canonical(CanonicalizerTool tool) {

            if (tool.allUsagesAvailable()) {

                /* The node is always unnecessary after graph decoding. */

                return value;

            } else {

                return this;

            }

        }

        public static ValueNode unwrap(ValueNode value) {

            ValueNode result = value;

            while (result instanceof ProxyPlaceholder) {

                result = ((ProxyPlaceholder) result).value;

            }

            return result;

        }

    }

    protected final Architecture architecture;

    /** The target graph where decoded nodes are added to. */

    protected final StructuredGraph graph;

    protected final OptionValues options;

    protected final DebugContext debug;

    private final EconomicMap<NodeClass<?>, ArrayDeque<Node>> reusableFloatingNodes;

    public GraphDecoder(Architecture architecture, StructuredGraph graph) {

        this.architecture = architecture;

        this.graph = graph;

        this.options = graph.getOptions();

        this.debug = graph.getDebug();

        reusableFloatingNodes = EconomicMap.create(Equivalence.IDENTITY);

    }

    @SuppressWarnings("try")

    public final void decode(EncodedGraph encodedGraph) {

        try (DebugContext.Scope scope = debug.scope("GraphDecoder", graph)) {

            MethodScope methodScope = new MethodScope(null, graph, encodedGraph, LoopExplosionKind.NONE);

            decode(createInitialLoopScope(methodScope, null));

            cleanupGraph(methodScope);

            assert graph.verify();

        } catch (Throwable ex) {

            debug.handle(ex);

        }

    }

    protected final LoopScope createInitialLoopScope(MethodScope methodScope, FixedWithNextNode startNode) {

        LoopScope loopScope = new LoopScope(methodScope);

        FixedNode firstNode;

        if (startNode != null) {

            /*

             * The start node of a graph can be referenced as the guard for a GuardedNode. We

             * register the previous block node, so that such guards are correctly anchored when

             * doing inlining during graph decoding.

             */

            registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, AbstractBeginNode.prevBegin(startNode), false, false);

            firstNode = makeStubNode(methodScope, loopScope, GraphEncoder.FIRST_NODE_ORDER_ID);

            startNode.setNext(firstNode);

            loopScope.nodesToProcess.set(GraphEncoder.FIRST_NODE_ORDER_ID);

        } else {

            firstNode = graph.start();

            registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, firstNode, false, false);

            loopScope.nodesToProcess.set(GraphEncoder.START_NODE_ORDER_ID);

        }

        return loopScope;

    }

    protected final void decode(LoopScope initialLoopScope) {

        LoopScope loopScope = initialLoopScope;

        /* Process (inlined) methods. */

        while (loopScope != null) {

            MethodScope methodScope = loopScope.methodScope;

            /* Process loops of method. */

            while (loopScope != null) {

                /* Process nodes of loop. */

                while (!loopScope.nodesToProcess.isEmpty()) {

                    loopScope = processNextNode(methodScope, loopScope);

                    methodScope = loopScope.methodScope;

                    /*

                     * We can have entered a new loop, and we can have entered a new inlined method.

                     */

                }

                /* Finished with a loop. */

                if (loopScope.nextIterations != null && !loopScope.nextIterations.isEmpty()) {

                    /* Loop explosion: process the loop iteration. */

                    assert loopScope.nextIterations.peekFirst().loopIteration == loopScope.loopIteration + 1;

                    loopScope = loopScope.nextIterations.removeFirst();

                } else {

                    propagateCreatedNodes(loopScope);

                    loopScope = loopScope.outer;

                }

            }

            /*

             * Finished with an inlined method. Perform end-of-method cleanup tasks.

             */

            if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {

                LoopDetector loopDetector = new LoopDetector(graph, methodScope);

                loopDetector.run();

            }

            if (methodScope.isInlinedMethod()) {

                finishInlining(methodScope);

            }

            /* continue with the caller */

            loopScope = methodScope.callerLoopScope;

        }

    }

    protected void finishInlining(@SuppressWarnings("unused") MethodScope inlineScope) {

    }

    private static void propagateCreatedNodes(LoopScope loopScope) {

        if (loopScope.outer == null || loopScope.createdNodes != loopScope.outer.createdNodes) {

            return;

        }

        /* Register nodes that were created while decoding the loop to the outside scope. */

        for (int i = 0; i < loopScope.createdNodes.length; i++) {

            if (loopScope.outer.createdNodes[i] == null) {

                loopScope.outer.createdNodes[i] = loopScope.createdNodes[i];

            }

        }

    }

    protected LoopScope processNextNode(MethodScope methodScope, LoopScope loopScope) {

        int nodeOrderId = loopScope.nodesToProcess.nextSetBit(0);

        loopScope.nodesToProcess.clear(nodeOrderId);

        FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId);

        if (node.isDeleted()) {

            return loopScope;

        }

        if ((node instanceof MergeNode ||

                        (node instanceof LoopBeginNode && (methodScope.loopExplosion == LoopExplosionKind.FULL_UNROLL || methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE ||

                                        methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN))) &&

                        ((AbstractMergeNode) node).forwardEndCount() == 1) {

            AbstractMergeNode merge = (AbstractMergeNode) node;

            EndNode singleEnd = merge.forwardEndAt(0);

            /* Nodes that would use this merge as the guard need to use the previous block. */

            registerNode(loopScope, nodeOrderId, AbstractBeginNode.prevBegin(singleEnd), true, false);

            FixedNode next = makeStubNode(methodScope, loopScope, nodeOrderId + GraphEncoder.BEGIN_NEXT_ORDER_ID_OFFSET);

            singleEnd.replaceAtPredecessor(next);

            merge.safeDelete();

            singleEnd.safeDelete();

            return loopScope;

        }

        LoopScope successorAddScope = loopScope;

        boolean updatePredecessors = true;

        if (node instanceof LoopExitNode) {

            if (methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN || (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE && loopScope.loopDepth > 1)) {

                /*

                 * We do not want to merge loop exits of inner loops. Instead, we want to keep

                 * exploding the outer loop separately for every loop exit and then merge the outer

                 * loop. Therefore, we create a new LoopScope of the outer loop for every loop exit

                 * of the inner loop.

                 */

                LoopScope outerScope = loopScope.outer;

                int nextIterationNumber = outerScope.nextIterations.isEmpty() ? outerScope.loopIteration + 1 : outerScope.nextIterations.getLast().loopIteration + 1;

                successorAddScope = new LoopScope(methodScope, outerScope.outer, outerScope.loopDepth, nextIterationNumber, outerScope.loopBeginOrderId,

                                outerScope.initialCreatedNodes == null ? null : Arrays.copyOf(outerScope.initialCreatedNodes, outerScope.initialCreatedNodes.length),

                                Arrays.copyOf(loopScope.initialCreatedNodes, loopScope.initialCreatedNodes.length), outerScope.nextIterations, outerScope.iterationStates);

                checkLoopExplosionIteration(methodScope, successorAddScope);

                /*

                 * Nodes that are still unprocessed in the outer scope might be merge nodes that are

                 * also reachable from the new exploded scope. Clearing them ensures that we do not

                 * merge, but instead keep exploding.

                 */

                for (int id = outerScope.nodesToProcess.nextSetBit(0); id >= 0; id = outerScope.nodesToProcess.nextSetBit(id + 1)) {

                    successorAddScope.createdNodes[id] = null;

                }