xref: /openjdk9/hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/GraphDecoder.java

/*
 * Copyright (c) 2015, 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 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.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

import org.graalvm.compiler.common.PermanentBailoutException;
import org.graalvm.compiler.core.common.Fields;
import org.graalvm.compiler.core.common.util.TypeReader;
import org.graalvm.compiler.core.common.util.UnsafeArrayTypeReader;
import org.graalvm.compiler.debug.Debug;
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 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;
        /** The target graph where decoded nodes are added to. */
        public final StructuredGraph graph;
        /**
         * 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;
        /** Access to the encoded graph. */
        public final TypeReader reader;
        /** The kind of loop explosion to be performed during decoding. */
        public final LoopExplosionKind loopExplosion;
        /** A list of tasks to run before the method scope is closed. */
        public final List<Runnable> cleanupTasks;

        /** All return nodes encountered during decoding. */
        public final List<ReturnNode> returnNodes;
        /** The exception unwind node encountered during decoding, or null. */
        public final List<UnwindNode> unwindNodes;

        /** All merges created during loop explosion. */
        public final NodeBitMap 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.graph = graph;
            this.methodStartMark = graph.getMark();
            this.encodedGraph = encodedGraph;
            this.loopExplosion = loopExplosion;
            this.cleanupTasks = new ArrayList<>();
            this.returnNodes = new ArrayList<>();
            this.unwindNodes = new ArrayList<>();

            if (encodedGraph != null) {
                reader = UnsafeArrayTypeReader.create(encodedGraph.getEncoding(), encodedGraph.getStartOffset(), architecture.supportsUnalignedMemoryAccess());
                if (encodedGraph.nodeStartOffsets == null) {
                    int nodeCount = reader.getUVInt();
                    long[] nodeStartOffsets = new long[nodeCount];
                    for (int i = 0; i < nodeCount; i++) {
                        nodeStartOffsets[i] = encodedGraph.getStartOffset() - reader.getUV();
                    }
                    encodedGraph.nodeStartOffsets = nodeStartOffsets;
                }
            } else {
                reader = null;
            }

            if (loopExplosion != LoopExplosionKind.NONE) {
                loopExplosionMerges = new NodeBitMap(graph);
            } else {
                loopExplosionMerges = null;
            }
        }
    }

    /** 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 Map<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.
         */
        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<>() : null;
            this.loopDepth = 0;
            this.loopIteration = 0;
            this.iterationStates = null;
            this.loopBeginOrderId = -1;

            int nodeCount = methodScope.encodedGraph.nodeStartOffsets.length;
            this.nodesToProcess = new BitSet(nodeCount);
            this.initialCreatedNodes = new Node[nodeCount];
            this.createdNodes = new Node[nodeCount];
        }

        protected LoopScope(MethodScope methodScope, LoopScope outer, int loopDepth, int loopIteration, int loopBeginOrderId, Node[] initialCreatedNodes, Node[] createdNodes,
                        Deque<LoopScope> nextIterations, Map<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(initialCreatedNodes.length);
            this.initialCreatedNodes = initialCreatedNodes;
            this.createdNodes = Arrays.copyOf(createdNodes, createdNodes.length);
        }

        @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.Unchecked) Node proxyPoint;

        public ProxyPlaceholder(ValueNode value, MergeNode proxyPoint) {
            super(TYPE, value.stamp());
            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;

    public GraphDecoder(Architecture architecture) {
        this.architecture = architecture;
    }

    @SuppressWarnings("try")
    public final void decode(StructuredGraph graph, EncodedGraph encodedGraph) {
        try (Debug.Scope scope = Debug.scope("GraphDecoder", graph)) {
            MethodScope methodScope = new MethodScope(null, graph, encodedGraph, LoopExplosionKind.NONE);
            decode(createInitialLoopScope(methodScope, null));
            cleanupGraph(methodScope);
            assert methodScope.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 = methodScope.graph.start();
            registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, firstNode, false, false);
            loopScope.nodesToProcess.set(GraphEncoder.START_NODE_ORDER_ID);
        }

        if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
            methodScope.cleanupTasks.add(new LoopDetector(methodScope, startNode));
        }
        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 all registered end-of-method cleanup tasks
             * and continue with loop that contained the call.
             */
            for (Runnable task : methodScope.cleanupTasks) {
                task.run();
            }
            loopScope = methodScope.callerLoopScope;
        }
    }

    private static void propagateCreatedNodes(LoopScope loopScope) {
        if (loopScope.outer == null) {
            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,
                                loopScope.initialCreatedNodes, 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;
                }

                outerScope.nextIterations.addLast(successorAddScope);
            } else {
                successorAddScope = loopScope.outer;
            }
            updatePredecessors = methodScope.loopExplosion == LoopExplosionKind.NONE;
        }

        methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
        int typeId = methodScope.reader.getUVInt();
        assert node.getNodeClass() == methodScope.encodedGraph.getNodeClasses()[typeId];
        readProperties(methodScope, node);
        makeSuccessorStubs(methodScope, successorAddScope, node, updatePredecessors);
        makeInputNodes(methodScope, loopScope, node, true);

        LoopScope resultScope = loopScope;
        if (node instanceof LoopBeginNode) {
            if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
                handleLoopExplosionBegin(methodScope, loopScope, (LoopBeginNode) node);
            }

        } else if (node instanceof LoopExitNode) {
            if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
                handleLoopExplosionProxyNodes(methodScope, loopScope, successorAddScope, (LoopExitNode) node, nodeOrderId);
            } else {
                handleProxyNodes(methodScope, loopScope, (LoopExitNode) node);
            }

        } else if (node instanceof MergeNode) {
            handleMergeNode(((MergeNode) node));

        } else if (node instanceof AbstractEndNode) {
            LoopScope phiInputScope = loopScope;
            LoopScope phiNodeScope = loopScope;

            if (methodScope.loopExplosion != LoopExplosionKind.NONE && node instanceof LoopEndNode) {
                node = handleLoopExplosionEnd(methodScope, loopScope, (LoopEndNode) node);
                phiNodeScope = loopScope.nextIterations.getLast();
            }

            int mergeOrderId = readOrderId(methodScope);
            AbstractMergeNode merge = (AbstractMergeNode) lookupNode(phiNodeScope, mergeOrderId);
            if (merge == null) {
                merge = (AbstractMergeNode) makeStubNode(methodScope, phiNodeScope, mergeOrderId);

                if (merge instanceof LoopBeginNode) {
                    assert phiNodeScope == phiInputScope && phiNodeScope == loopScope;
                    resultScope = new LoopScope(methodScope, loopScope, loopScope.loopDepth + 1, 0, mergeOrderId,
                                    Arrays.copyOf(loopScope.createdNodes, loopScope.createdNodes.length), loopScope.createdNodes, //
                                    methodScope.loopExplosion != LoopExplosionKind.NONE ? new ArrayDeque<>() : null, //
                                    methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE ? new HashMap<>() : null);
                    phiInputScope = resultScope;
                    phiNodeScope = resultScope;

                    registerNode(loopScope, mergeOrderId, null, true, true);
                    loopScope.nodesToProcess.clear(mergeOrderId);
                    resultScope.nodesToProcess.set(mergeOrderId);
                }
            }

            handlePhiFunctions(methodScope, phiInputScope, phiNodeScope, (AbstractEndNode) node, merge);

        } else if (node instanceof Invoke) {
            InvokeData invokeData = readInvokeData(methodScope, nodeOrderId, (Invoke) node);
            resultScope = handleInvoke(methodScope, loopScope, invokeData);

        } else if (node instanceof ReturnNode) {
            methodScope.returnNodes.add((ReturnNode) node);
        } else if (node instanceof UnwindNode) {
            methodScope.unwindNodes.add((UnwindNode) node);

        } else {
            handleFixedNode(methodScope, loopScope, nodeOrderId, node);
        }

        return resultScope;
    }

    private InvokeData readInvokeData(MethodScope methodScope, int invokeOrderId, Invoke invoke) {
        ResolvedJavaType contextType = (ResolvedJavaType) readObject(methodScope);
        int callTargetOrderId = readOrderId(methodScope);
        int stateAfterOrderId = readOrderId(methodScope);
        int nextOrderId = readOrderId(methodScope);

        if (invoke instanceof InvokeWithExceptionNode) {
            int nextNextOrderId = readOrderId(methodScope);
            int exceptionOrderId = readOrderId(methodScope);
            int exceptionStateOrderId = readOrderId(methodScope);
            int exceptionNextOrderId = readOrderId(methodScope);
            return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, nextNextOrderId, exceptionOrderId, exceptionStateOrderId,
                            exceptionNextOrderId);
        } else {
            return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, -1, -1, -1, -1);
        }
    }

    /**
     * {@link Invoke} nodes do not have the {@link CallTargetNode}, {@link FrameState}, and
     * successors encoded. Instead, this information is provided separately to allow method inlining
     * without decoding and adding them to the graph upfront. For non-inlined methods, this method
     * restores the normal state. Subclasses can override it to perform method inlining.
     *
     * The return value is the loop scope where decoding should continue. When method inlining
     * should be performed, the returned loop scope must be a new loop scope for the inlined method.
     * Without inlining, the original loop scope must be returned.
     */
    protected LoopScope handleInvoke(MethodScope methodScope, LoopScope loopScope, InvokeData invokeData) {
        assert invokeData.invoke.callTarget() == null : "callTarget edge is ignored during decoding of Invoke";
        CallTargetNode callTarget = (CallTargetNode) ensureNodeCreated(methodScope, loopScope, invokeData.callTargetOrderId);
        if (invokeData.invoke instanceof InvokeWithExceptionNode) {
            ((InvokeWithExceptionNode) invokeData.invoke).setCallTarget(callTarget);
        } else {
            ((InvokeNode) invokeData.invoke).setCallTarget(callTarget);
        }

        assert invokeData.invoke.stateAfter() == null && invokeData.invoke.stateDuring() == null : "FrameState edges are ignored during decoding of Invoke";
        invokeData.invoke.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, invokeData.stateAfterOrderId));

        invokeData.invoke.setNext(makeStubNode(methodScope, loopScope, invokeData.nextOrderId));
        if (invokeData.invoke instanceof InvokeWithExceptionNode) {
            ((InvokeWithExceptionNode) invokeData.invoke).setExceptionEdge((AbstractBeginNode) makeStubNode(methodScope, loopScope, invokeData.exceptionOrderId));
        }
        return loopScope;
    }

    /**
     * Hook for subclasses to perform simplifications for a non-loop-header control flow merge.
     *
     * @param merge The control flow merge.
     */
    protected void handleMergeNode(MergeNode merge) {
    }

    protected void handleLoopExplosionBegin(MethodScope methodScope, LoopScope loopScope, LoopBeginNode loopBegin) {
        checkLoopExplosionIteration(methodScope, loopScope);

        List<EndNode> predecessors = loopBegin.forwardEnds().snapshot();
        FixedNode successor = loopBegin.next();
        FrameState frameState = loopBegin.stateAfter();

        if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
            LoopExplosionState queryState = new LoopExplosionState(frameState, null);
            LoopExplosionState existingState = loopScope.iterationStates.get(queryState);
            if (existingState != null) {
                loopBegin.replaceAtUsagesAndDelete(existingState.merge);
                successor.safeDelete();
                for (EndNode predecessor : predecessors) {
                    existingState.merge.addForwardEnd(predecessor);
                }
                return;
            }
        }

        MergeNode merge = methodScope.graph.add(new MergeNode());
        methodScope.loopExplosionMerges.markAndGrow(merge);

        if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
            if (loopScope.iterationStates.size() == 0 && loopScope.loopDepth == 1) {
                if (methodScope.loopExplosionHead != null) {
                    throw new PermanentBailoutException("Graal implementation restriction: Method with %s loop explosion must not have more than one top-level loop", LoopExplosionKind.MERGE_EXPLODE);
                }
                methodScope.loopExplosionHead = merge;
            }

            List<ValueNode> newFrameStateValues = new ArrayList<>();
            for (ValueNode frameStateValue : frameState.values) {
                if (frameStateValue == null || frameStateValue.isConstant() || !methodScope.graph.isNew(methodScope.methodStartMark, frameStateValue)) {
                    newFrameStateValues.add(frameStateValue);

                } else {
                    ProxyPlaceholder newFrameStateValue = methodScope.graph.unique(new ProxyPlaceholder(frameStateValue, merge));
                    newFrameStateValues.add(newFrameStateValue);

                    /*
                     * We do not have the orderID of the value anymore, so we need to search through
                     * the complete list of nodes to find a match.
                     */
                    for (int i = 0; i < loopScope.createdNodes.length; i++) {
                        if (loopScope.createdNodes[i] == frameStateValue) {
                            loopScope.createdNodes[i] = newFrameStateValue;
                        }
                        if (loopScope.initialCreatedNodes[i] == frameStateValue) {
                            loopScope.initialCreatedNodes[i] = newFrameStateValue;
                        }
                    }
                }
            }

            FrameState newFrameState = methodScope.graph.add(new FrameState(frameState.outerFrameState(), frameState.getCode(), frameState.bci, newFrameStateValues, frameState.localsSize(),
                            frameState.stackSize(), frameState.rethrowException(), frameState.duringCall(), frameState.monitorIds(), frameState.virtualObjectMappings()));

            frameState.replaceAtUsages(newFrameState);
            frameState.safeDelete();
            frameState = newFrameState;
        }

        loopBegin.replaceAtUsagesAndDelete(merge);
        merge.setStateAfter(frameState);
        merge.setNext(successor);
        for (EndNode predecessor : predecessors) {
            merge.addForwardEnd(predecessor);
        }

        if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
            LoopExplosionState explosionState = new LoopExplosionState(frameState, merge);
            loopScope.iterationStates.put(explosionState, explosionState);
        }
    }

    /**
     * Hook for subclasses.
     *
     * @param methodScope The current method.
     * @param loopScope The current loop.
     */
    protected void checkLoopExplosionIteration(MethodScope methodScope, LoopScope loopScope) {
        throw shouldNotReachHere("when subclass uses loop explosion, it needs to implement this method");
    }

    protected FixedNode handleLoopExplosionEnd(MethodScope methodScope, LoopScope loopScope, LoopEndNode loopEnd) {
        EndNode replacementNode = methodScope.graph.add(new EndNode());
        loopEnd.replaceAtPredecessor(replacementNode);
        loopEnd.safeDelete();

        assert methodScope.loopExplosion != LoopExplosionKind.NONE;
        if (methodScope.loopExplosion != LoopExplosionKind.FULL_UNROLL || loopScope.nextIterations.isEmpty()) {
            int nextIterationNumber = loopScope.nextIterations.isEmpty() ? loopScope.loopIteration + 1 : loopScope.nextIterations.getLast().loopIteration + 1;
            LoopScope nextIterationScope = new LoopScope(methodScope, loopScope.outer, loopScope.loopDepth, nextIterationNumber, loopScope.loopBeginOrderId, loopScope.initialCreatedNodes,
                            loopScope.initialCreatedNodes, loopScope.nextIterations, loopScope.iterationStates);
            checkLoopExplosionIteration(methodScope, nextIterationScope);
            loopScope.nextIterations.addLast(nextIterationScope);
            registerNode(nextIterationScope, loopScope.loopBeginOrderId, null, true, true);
            makeStubNode(methodScope, nextIterationScope, loopScope.loopBeginOrderId);
        }
        return replacementNode;
    }

    /**
     * Hook for subclasses.
     *
     * @param methodScope The current method.
     * @param loopScope The current loop.
     * @param nodeOrderId The orderId of the node.
     * @param node The node to be simplified.
     */
    protected void handleFixedNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId, FixedNode node) {
    }

    protected void handleProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopExitNode loopExit) {
        assert loopExit.stateAfter() == null;
        int stateAfterOrderId = readOrderId(methodScope);
        loopExit.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, stateAfterOrderId));

        int numProxies = methodScope.reader.getUVInt();
        for (int i = 0; i < numProxies; i++) {
            int proxyOrderId = readOrderId(methodScope);
            ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId);
            /*
             * The ProxyNode transports a value from the loop to the outer scope. We therefore
             * register it in the outer scope.
             */
            registerNode(loopScope.outer, proxyOrderId, proxy, false, false);
        }
    }

    protected void handleLoopExplosionProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopScope outerScope, LoopExitNode loopExit, int loopExitOrderId) {
        assert loopExit.stateAfter() == null;
        int stateAfterOrderId = readOrderId(methodScope);

        BeginNode begin = methodScope.graph.add(new BeginNode());

        FixedNode loopExitSuccessor = loopExit.next();
        loopExit.replaceAtPredecessor(begin);

        MergeNode loopExitPlaceholder = null;
        if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE && loopScope.loopDepth == 1) {
            /*
             * This exit might end up as a loop exit of a loop detected after partial evaluation. We
             * need to be able to create a FrameState and the necessary proxy nodes in this case.
             */
            loopExitPlaceholder = methodScope.graph.add(new MergeNode());
            methodScope.loopExplosionMerges.markAndGrow(loopExitPlaceholder);

            EndNode end = methodScope.graph.add(new EndNode());
            begin.setNext(end);
            loopExitPlaceholder.addForwardEnd(end);

            begin = methodScope.graph.add(new BeginNode());
            loopExitPlaceholder.setNext(begin);
        }

        /*
         * In the original graph, the loop exit is not a merge node. Multiple exploded loop
         * iterations now take the same loop exit, so we have to introduce a new merge node to
         * handle the merge.
         */
        MergeNode merge = null;
        Node existingExit = lookupNode(outerScope, loopExitOrderId);
        if (existingExit == null) {
            /* First loop iteration that exits. No merge necessary yet. */
            registerNode(outerScope, loopExitOrderId, begin, false, false);
            begin.setNext(loopExitSuccessor);

        } else if (existingExit instanceof BeginNode) {
            /* Second loop iteration that exits. Create the merge. */
            merge = methodScope.graph.add(new MergeNode());
            registerNode(outerScope, loopExitOrderId, merge, true, false);
            /* Add the first iteration. */
            EndNode firstEnd = methodScope.graph.add(new EndNode());
            ((BeginNode) existingExit).setNext(firstEnd);
            merge.addForwardEnd(firstEnd);
            merge.setNext(loopExitSuccessor);

        } else {
            /* Subsequent loop iteration. Merge already created. */
            merge = (MergeNode) existingExit;
        }

        if (merge != null) {
            EndNode end = methodScope.graph.add(new EndNode());
            begin.setNext(end);
            merge.addForwardEnd(end);
        }

        /*
         * Possibly create phi nodes for the original proxy nodes that flow out of the loop. Note
         * that we definitely do not need a proxy node itself anymore, since the loop was exploded
         * and is no longer present.
         */
        int numProxies = methodScope.reader.getUVInt();
        boolean phiCreated = false;
        for (int i = 0; i < numProxies; i++) {
            int proxyOrderId = readOrderId(methodScope);
            ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId);
            ValueNode phiInput = proxy.value();

            if (loopExitPlaceholder != null) {
                if (!phiInput.isConstant()) {
                    phiInput = methodScope.graph.unique(new ProxyPlaceholder(phiInput, loopExitPlaceholder));
                }
                registerNode(loopScope, proxyOrderId, phiInput, true, false);
            }

            ValueNode replacement;
            ValueNode existing = (ValueNode) outerScope.createdNodes[proxyOrderId];
            if (existing == null || existing == phiInput) {
                /*
                 * We are at the first loop exit, or the proxy carries the same value for all exits.
                 * We do not need a phi node yet.
                 */
                registerNode(outerScope, proxyOrderId, phiInput, true, false);
                replacement = phiInput;

            } else if (!merge.isPhiAtMerge(existing)) {
                /* Now we have two different values, so we need to create a phi node. */
                PhiNode phi = methodScope.graph.addWithoutUnique(new ValuePhiNode(proxy.stamp(), merge));
                /* Add the inputs from all previous exits. */
                for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) {
                    phi.addInput(existing);
                }
                /* Add the input from this exit. */
                phi.addInput(phiInput);
                registerNode(outerScope, proxyOrderId, phi, true, false);
                replacement = phi;
                phiCreated = true;

            } else {
                /* Phi node has been created before, so just add the new input. */
                PhiNode phi = (PhiNode) existing;
                phi.addInput(phiInput);
                replacement = phi;
            }

            proxy.replaceAtUsagesAndDelete(replacement);
        }

        if (loopExitPlaceholder != null) {
            registerNode(loopScope, stateAfterOrderId, null, true, true);
            loopExitPlaceholder.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, stateAfterOrderId));
        }

        if (merge != null && (merge.stateAfter() == null || phiCreated)) {
            FrameState oldStateAfter = merge.stateAfter();
            registerNode(outerScope, stateAfterOrderId, null, true, true);
            merge.setStateAfter((FrameState) ensureNodeCreated(methodScope, outerScope, stateAfterOrderId));
            if (oldStateAfter != null) {
                oldStateAfter.safeDelete();
            }
        }
        loopExit.safeDelete();
        assert loopExitSuccessor.predecessor() == null;
        if (merge != null) {
            merge.getNodeClass().getSuccessorEdges().update(merge, null, loopExitSuccessor);
        } else {
            begin.getNodeClass().getSuccessorEdges().update(begin, null, loopExitSuccessor);
        }
    }

    protected void handlePhiFunctions(MethodScope methodScope, LoopScope phiInputScope, LoopScope phiNodeScope, AbstractEndNode end, AbstractMergeNode merge) {

        if (end instanceof LoopEndNode) {
            /*
             * Fix the loop end index and the number of loop ends. When we do canonicalization
             * during decoding, we can end up with fewer ends than the encoded graph had. And the
             * order of loop ends can be different.
             */
            int numEnds = ((LoopBeginNode) merge).loopEnds().count();
            ((LoopBeginNode) merge).nextEndIndex = numEnds;
            ((LoopEndNode) end).endIndex = numEnds - 1;

        } else {
            if (merge.ends == null) {
                merge.ends = new NodeInputList<>(merge);
            }
            merge.addForwardEnd((EndNode) end);
        }

        /*
         * We create most phi functions lazily. Canonicalization and simplification during decoding
         * can lead to dead branches that are not decoded, so we might not need all phi functions
         * that the original graph contained. Since we process all predecessors before actually
         * processing the merge node, we have the final phi function when processing the merge node.
         * The only exception are loop headers of non-exploded loops: since backward branches are
         * not processed yet when processing the loop body, we need to create all phi functions
         * upfront.
         */
        boolean lazyPhi = allowLazyPhis() && (!(merge instanceof LoopBeginNode) || methodScope.loopExplosion != LoopExplosionKind.NONE);
        int numPhis = methodScope.reader.getUVInt();
        for (int i = 0; i < numPhis; i++) {
            int phiInputOrderId = readOrderId(methodScope);
            int phiNodeOrderId = readOrderId(methodScope);

            ValueNode phiInput = (ValueNode) ensureNodeCreated(methodScope, phiInputScope, phiInputOrderId);

            ValueNode existing = (ValueNode) lookupNode(phiNodeScope, phiNodeOrderId);
            if (lazyPhi && (existing == null || existing == phiInput)) {
                /* Phi function not yet necessary. */
                registerNode(phiNodeScope, phiNodeOrderId, phiInput, true, false);

            } else if (!merge.isPhiAtMerge(existing)) {
                /*
                 * Phi function is necessary. Create it and fill it with existing inputs as well as
                 * the new input.
                 */
                registerNode(phiNodeScope, phiNodeOrderId, null, true, true);
                PhiNode phi = (PhiNode) ensureNodeCreated(methodScope, phiNodeScope, phiNodeOrderId);

                phi.setMerge(merge);
                for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) {
                    phi.addInput(existing);
                }
                phi.addInput(phiInput);

            } else {
                /* Phi node has been created before, so just add the new input. */
                PhiNode phi = (PhiNode) existing;
                phi.addInput(phiInput);
            }
        }
    }

    protected boolean allowLazyPhis() {
        /* We need to exactly reproduce the encoded graph, including unnecessary phi functions. */
        return false;
    }

    protected Node instantiateNode(MethodScope methodScope, int nodeOrderId) {
        methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
        NodeClass<?> nodeClass = methodScope.encodedGraph.getNodeClasses()[methodScope.reader.getUVInt()];
        return nodeClass.allocateInstance();
    }

    protected void readProperties(MethodScope methodScope, Node node) {
        node.setNodeSourcePosition((NodeSourcePosition) readObject(methodScope));
        Fields fields = node.getNodeClass().getData();
        for (int pos = 0; pos < fields.getCount(); pos++) {
            if (fields.getType(pos).isPrimitive()) {
                long primitive = methodScope.reader.getSV();
                fields.setRawPrimitive(node, pos, primitive);
            } else {
                Object value = readObject(methodScope);
                fields.set(node, pos, value);
            }
        }
    }

    /**
     * Process the input edges of a node. Input nodes that have not yet been created must be
     * non-fixed nodes (because fixed nodes are processed in reverse postorder. Such non-fixed nodes
     * are created on demand (recursively since they can themselves reference not yet created
     * nodes).
     */
    protected void makeInputNodes(MethodScope methodScope, LoopScope loopScope, Node node, boolean updateUsages) {
        Edges edges = node.getNodeClass().getEdges(Edges.Type.Inputs);
        for (int index = 0; index < edges.getDirectCount(); index++) {
            if (skipEdge(node, edges, index, true, true)) {
                continue;
            }
            int orderId = readOrderId(methodScope);
            Node value = ensureNodeCreated(methodScope, loopScope, orderId);
            edges.initializeNode(node, index, value);
            if (updateUsages && value != null && !value.isDeleted()) {
                edges.update(node, null, value);

            }
        }
        for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
            if (skipEdge(node, edges, index, false, true)) {
                continue;
            }
            int size = methodScope.reader.getSVInt();
            if (size != -1) {
                NodeList<Node> nodeList = new NodeInputList<>(node, size);
                edges.initializeList(node, index, nodeList);
                for (int idx = 0; idx < size; idx++) {
                    int orderId = readOrderId(methodScope);
                    Node value = ensureNodeCreated(methodScope, loopScope, orderId);
                    nodeList.initialize(idx, value);
                    if (updateUsages && value != null && !value.isDeleted()) {
                        edges.update(node, null, value);
                    }
                }
            }
        }
    }

    protected Node ensureNodeCreated(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
        if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
            return null;
        }
        Node node = lookupNode(loopScope, nodeOrderId);
        if (node != null) {
            return node;
        }

        node = decodeFloatingNode(methodScope, loopScope, nodeOrderId);

        if (node instanceof ProxyNode || node instanceof PhiNode) {
            /*
             * We need these nodes as they were in the original graph, without any canonicalization
             * or value numbering.
             */
            node = methodScope.graph.addWithoutUnique(node);
        } else {
            /* Allow subclasses to canonicalize and intercept nodes. */
            node = handleFloatingNodeBeforeAdd(methodScope, loopScope, node);
            if (!node.isAlive()) {
                node = addFloatingNode(methodScope, node);
            }
            node = handleFloatingNodeAfterAdd(methodScope, loopScope, node);
        }
        registerNode(loopScope, nodeOrderId, node, false, false);
        return node;
    }

    protected Node addFloatingNode(MethodScope methodScope, Node node) {
        /*
         * We want to exactly reproduce the encoded graph. Even though nodes should be unique in the
         * encoded graph, this is not always guaranteed.
         */
        return methodScope.graph.addWithoutUnique(node);
    }

    /**
     * Decodes a non-fixed node, but does not do any post-processing and does not register it.
     */
    protected Node decodeFloatingNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
        long readerByteIndex = methodScope.reader.getByteIndex();
        Node node = instantiateNode(methodScope, nodeOrderId);
        if (node instanceof FixedNode) {
            /*
             * This is a severe error that will lead to a corrupted graph, so it is better not to
             * continue decoding at all.
             */
            throw shouldNotReachHere("Not a floating node: " + node.getClass().getName());
        }

        /* Read the properties of the node. */
        readProperties(methodScope, node);
        /* There must not be any successors to read, since it is a non-fixed node. */
        assert node.getNodeClass().getEdges(Edges.Type.Successors).getCount() == 0;
        /* Read the inputs of the node, possibly creating them recursively. */
        makeInputNodes(methodScope, loopScope, node, false);
        methodScope.reader.setByteIndex(readerByteIndex);
        return node;
    }

    /**
     * Hook for subclasses to process a non-fixed node before it is added to the graph.
     *
     * @param methodScope The current method.
     * @param loopScope The current loop.
     * @param node The node to be canonicalized.
     * @return The replacement for the node, or the node itself.
     */
    protected Node handleFloatingNodeBeforeAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
        return node;
    }

    /**
     * Hook for subclasses to process a non-fixed node after it is added to the graph.
     *
     * If this method replaces a node with another node, it must update its source position if the
     * original node has the source position set.
     *
     * @param methodScope The current method.
     * @param loopScope The current loop.
     * @param node The node to be canonicalized.
     * @return The replacement for the node, or the node itself.
     */
    protected Node handleFloatingNodeAfterAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
        return node;
    }

    /**
     * Process successor edges of a node. We create the successor nodes so that we can fill the
     * successor list, but no properties or edges are loaded yet. That is done when the successor is
     * on top of the worklist in {@link #processNextNode}.
     */
    protected void makeSuccessorStubs(MethodScope methodScope, LoopScope loopScope, Node node, boolean updatePredecessors) {
        Edges edges = node.getNodeClass().getEdges(Edges.Type.Successors);
        for (int index = 0; index < edges.getDirectCount(); index++) {
            if (skipEdge(node, edges, index, true, true)) {
                continue;
            }
            int orderId = readOrderId(methodScope);
            Node value = makeStubNode(methodScope, loopScope, orderId);
            edges.initializeNode(node, index, value);
            if (updatePredecessors && value != null) {
                edges.update(node, null, value);
            }
        }
        for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
            if (skipEdge(node, edges, index, false, true)) {
                continue;
            }
            int size = methodScope.reader.getSVInt();
            if (size != -1) {
                NodeList<Node> nodeList = new NodeSuccessorList<>(node, size);
                edges.initializeList(node, index, nodeList);
                for (int idx = 0; idx < size; idx++) {
                    int orderId = readOrderId(methodScope);
                    Node value = makeStubNode(methodScope, loopScope, orderId);
                    nodeList.initialize(idx, value);
                    if (updatePredecessors && value != null) {
                        edges.update(node, null, value);
                    }
                }
            }
        }
    }

    protected FixedNode makeStubNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
        if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
            return null;
        }
        FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId);
        if (node != null) {
            return node;
        }

        long readerByteIndex = methodScope.reader.getByteIndex();
        node = (FixedNode) methodScope.graph.add(instantiateNode(methodScope, nodeOrderId));
        /* Properties and edges are not filled yet, the node remains uninitialized. */
        methodScope.reader.setByteIndex(readerByteIndex);

        registerNode(loopScope, nodeOrderId, node, false, false);
        loopScope.nodesToProcess.set(nodeOrderId);
        return node;
    }

    /**
     * Returns false for {@link Edges} that are not necessary in the encoded graph because they are
     * reconstructed using other sources of information.
     */
    protected static boolean skipEdge(Node node, Edges edges, int index, boolean direct, boolean decode) {
        if (node instanceof PhiNode) {
            /* The inputs of phi functions are filled manually when the end nodes are processed. */
            assert edges.type() == Edges.Type.Inputs;
            if (direct) {
                assert index == edges.getDirectCount() - 1 : "PhiNode has one direct input (the MergeNode)";
            } else {
                assert index == edges.getCount() - 1 : "PhiNode has one variable size input (the values)";
                if (decode) {
                    /* The values must not be null, so initialize with an empty list. */
                    edges.initializeList(node, index, new NodeInputList<>(node));
                }
            }
            return true;

        } else if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs && !direct) {
            /* The ends of merge nodes are filled manually when the ends are processed. */
            assert index == edges.getCount() - 1 : "MergeNode has one variable size input (the ends)";
            assert Edges.getNodeList(node, edges.getOffsets(), index) != null : "Input list must have been already created";
            return true;

        } else if (node instanceof LoopExitNode && edges.type() == Edges.Type.Inputs && edges.getType(index) == FrameState.class) {
            /* The stateAfter of the loop exit is filled manually. */
            return true;

        } else if (node instanceof Invoke) {
            assert node instanceof InvokeNode || node instanceof InvokeWithExceptionNode : "The only two Invoke node classes. Got " + node.getClass();
            assert direct : "Invoke and InvokeWithException only have direct successor and input edges";
            if (edges.type() == Edges.Type.Successors) {
                assert edges.getCount() == (node instanceof InvokeWithExceptionNode ? 2 : 1) : "InvokeNode has one successor (next); InvokeWithExceptionNode has two successors (next, exceptionEdge)";
                return true;
            } else {
                assert edges.type() == Edges.Type.Inputs;
                if (edges.getType(index) == CallTargetNode.class) {
                    return true;
                } else if (edges.getType(index) == FrameState.class) {
                    assert edges.get(node, index) == null || edges.get(node, index) == ((Invoke) node).stateAfter() : "Only stateAfter can be a FrameState during encoding";
                    return true;
                }
            }
        }
        return false;
    }

    protected Node lookupNode(LoopScope loopScope, int nodeOrderId) {
        return loopScope.createdNodes[nodeOrderId];
    }

    protected void registerNode(LoopScope loopScope, int nodeOrderId, Node node, boolean allowOverwrite, boolean allowNull) {
        assert node == null || node.isAlive();
        assert allowNull || node != null;
        assert allowOverwrite || lookupNode(loopScope, nodeOrderId) == null;
        loopScope.createdNodes[nodeOrderId] = node;
    }

    protected int readOrderId(MethodScope methodScope) {
        return methodScope.reader.getUVInt();
    }

    protected Object readObject(MethodScope methodScope) {
        return methodScope.encodedGraph.getObjects()[methodScope.reader.getUVInt()];
    }

    /**
     * Removes unnecessary nodes from the graph after decoding.
     *
     * @param methodScope The current method.
     */
    protected void cleanupGraph(MethodScope methodScope) {
        assert verifyEdges(methodScope);
    }

    protected boolean verifyEdges(MethodScope methodScope) {
        for (Node node : methodScope.graph.getNodes()) {
            assert node.isAlive();
            for (Node i : node.inputs()) {
                assert i.isAlive();
                assert i.usages().contains(node);
            }
            for (Node s : node.successors()) {
                assert s.isAlive();
                assert s.predecessor() == node;
            }

            for (Node usage : node.usages()) {
                assert usage.isAlive();
                assert usage.inputs().contains(node) : node + " / " + usage + " / " + usage.inputs().count();
            }
            if (node.predecessor() != null) {
                assert node.predecessor().isAlive();
                assert node.predecessor().successors().contains(node);
            }
        }
        return true;
    }
}

class LoopDetector implements Runnable {

    /**
     * Information about loops before the actual loop nodes are inserted.
     */
    static class Loop {
        /**
         * The header, i.e., the target of backward branches.
         */
        MergeNode header;
        /**
         * The ends, i.e., the source of backward branches. The {@link EndNode#successors successor}
         * is the {@link #header loop header}.
         */
        List<EndNode> ends = new ArrayList<>();
        /**
         * Exits of the loop. The successor is a {@link MergeNode} marked in
         * {@link MethodScope#loopExplosionMerges}.
         */
        List<AbstractEndNode> exits = new ArrayList<>();
        /**
         * Set to true when the loop is irreducible, i.e., has multiple entries. See
         * {@link #handleIrreducibleLoop} for details on the handling.
         */
        boolean irreducible;
    }

    private final MethodScope methodScope;
    private final FixedNode startInstruction;

    private Loop irreducibleLoopHandler;
    private IntegerSwitchNode irreducibleLoopSwitch;

    protected LoopDetector(MethodScope methodScope, FixedNode startInstruction) {
        this.methodScope = methodScope;
        this.startInstruction = startInstruction;
    }

    @Override
    public void run() {
        Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "Before loop detection");

        List<Loop> orderedLoops = findLoops();
        assert orderedLoops.get(orderedLoops.size() - 1) == irreducibleLoopHandler : "outermost loop must be the last element in the list";

        for (Loop loop : orderedLoops) {
            if (loop.ends.isEmpty()) {
                assert loop == irreducibleLoopHandler;
                continue;
            }

            /*
             * The algorithm to find loop exits requires that inner loops have already been
             * processed. Therefore, we need to iterate the loops in order (inner loops before outer
             * loops), and we cannot find the exits for all loops before we start inserting nodes.
             */
            findLoopExits(loop);

            if (loop.irreducible) {
                handleIrreducibleLoop(loop);
            } else {
                insertLoopNodes(loop);
            }
            Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After handling of loop %s", loop.header);
        }

        logIrreducibleLoops();
        Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After loop detection");
    }

    private List<Loop> findLoops() {
        /* Mapping from the loop header node to additional loop information. */
        Map<MergeNode, Loop> unorderedLoops = new HashMap<>();
        /* Loops in reverse order of, i.e., inner loops before outer loops. */
        List<Loop> orderedLoops = new ArrayList<>();

        /*
         * Ensure we have an outermost loop that we can use to eliminate irreducible loops. This
         * loop can remain empty (no ends), in which case it is ignored.
         */
        irreducibleLoopHandler = findOrCreateLoop(unorderedLoops, methodScope.loopExplosionHead);

        NodeBitMap visited = methodScope.graph.createNodeBitMap();
        NodeBitMap active = methodScope.graph.createNodeBitMap();
        Deque<Node> stack = new ArrayDeque<>();
        visited.mark(startInstruction);
        stack.push(startInstruction);

        while (!stack.isEmpty()) {
            Node current = stack.peek();
            assert visited.isMarked(current);

            if (active.isMarked(current)) {
                /* We are back-tracking, i.e., all successor nodes have been processed. */
                stack.pop();
                active.clear(current);

                Loop loop = unorderedLoops.get(current);
                if (loop != null) {
                    /*
                     * Since nodes are popped in reverse order that they were pushed, we add inner
                     * loops before outer loops here.
                     */
                    assert !orderedLoops.contains(loop);
                    orderedLoops.add(loop);
                }

            } else {
                /*
                 * Process the node. Note that we do not remove the node from the stack, i.e., we
                 * will peek it again. But the next time the node is marked as active, so we do not
                 * execute this code again.
                 */
                active.mark(current);
                for (Node successor : current.cfgSuccessors()) {
                    if (active.isMarked(successor)) {
                        /* Detected a cycle, i.e., a backward branch of a loop. */
                        Loop loop = findOrCreateLoop(unorderedLoops, (MergeNode) successor);
                        assert !loop.ends.contains(current);
                        loop.ends.add((EndNode) current);

                    } else if (visited.isMarked(successor)) {
                        /* Forward merge into a branch we are already exploring. */

                    } else {
                        /* Forward branch to a node we have not seen yet. */
                        visited.mark(successor);
                        stack.push(successor);
                    }
                }
            }
        }
        return orderedLoops;
    }

    private Loop findOrCreateLoop(Map<MergeNode, Loop> unorderedLoops, MergeNode loopHeader) {
        assert methodScope.loopExplosionMerges.isMarkedAndGrow(loopHeader) : loopHeader;
        Loop loop = unorderedLoops.get(loopHeader);
        if (loop == null) {
            loop = new Loop();
            loop.header = loopHeader;
            unorderedLoops.put(loopHeader, loop);
        }
        return loop;
    }

    private void findLoopExits(Loop loop) {
        /*
         * Backward marking of loop nodes: Starting with the known loop ends, we mark all nodes that
         * are reachable until we hit the loop begin. All successors of loop nodes that are not
         * marked as loop nodes themselves are exits of the loop. We mark all successors, and then
         * subtract the loop nodes, to find the exits.
         */

        NodeBitMap possibleExits = methodScope.graph.createNodeBitMap();
        NodeBitMap visited = methodScope.graph.createNodeBitMap();
        Deque<Node> stack = new ArrayDeque<>();
        for (EndNode loopEnd : loop.ends) {
            stack.push(loopEnd);
            visited.mark(loopEnd);
        }

        while (!stack.isEmpty()) {
            Node current = stack.pop();
            if (current == loop.header) {
                continue;
            }
            if (!methodScope.graph.isNew(methodScope.methodStartMark, current)) {
                /*
                 * The current node is before the method that contains the exploded loop. The loop
                 * must have a second entry point, i.e., it is an irreducible loop.
                 */
                loop.irreducible = true;
                return;
            }

            for (Node predecessor : current.cfgPredecessors()) {
                if (predecessor instanceof LoopExitNode) {
                    /*
                     * Inner loop. We do not need to mark every node of it, instead we just continue
                     * marking at the loop header.
                     */
                    LoopBeginNode innerLoopBegin = ((LoopExitNode) predecessor).loopBegin();
                    if (!visited.isMarked(innerLoopBegin)) {
                        stack.push(innerLoopBegin);
                        visited.mark(innerLoopBegin);

                        /*
                         * All loop exits of the inner loop possibly need a LoopExit of our loop.
                         * Because we are processing inner loops first, we are guaranteed to already
                         * have all exits of the inner loop.
                         */
                        for (LoopExitNode exit : innerLoopBegin.loopExits()) {
                            possibleExits.mark(exit);
                        }
                    }

                } else if (!visited.isMarked(predecessor)) {
                    stack.push(predecessor);
                    visited.mark(predecessor);

                    if (predecessor instanceof ControlSplitNode) {
                        for (Node succ : predecessor.cfgSuccessors()) {
                            /*
                             * We would not need to mark the current node, and would not need to
                             * mark visited nodes. But it is easier to just mark everything, since
                             * we subtract all visited nodes in the end anyway. Note that at this
                             * point we do not have the complete visited information, so we would
                             * always mark too many possible exits.
                             */
                            possibleExits.mark(succ);
                        }
                    }
                }
            }
        }

        /* All visited nodes are not exits of our loop. */
        possibleExits.subtract(visited);

        /*
         * Now we know all the actual loop exits. Ideally, we would insert LoopExit nodes for them.
         * However, a LoopExit needs a valid FrameState that captures the state at the point where
         * we exit the loop. During graph decoding, we create a FrameState for every exploded loop
         * iteration. We need to do a forward marking until we hit the next such point. This puts
         * some nodes into the loop that are actually not part of the loop.
         *
         * In some cases, we did not create a FrameState during graph decoding: when there was no
         * LoopExit in the original loop that we exploded. This happens for code paths that lead
         * immediately to a DeoptimizeNode.
         *
         * Both cases mimic the behavior of the BytecodeParser, which also puts more nodes than
         * necessary into a loop because it computes loop information based on bytecodes, before the
         * actual parsing.
         */

        for (Node succ : possibleExits) {
            stack.push(succ);
            visited.mark(succ);
            assert !methodScope.loopExplosionMerges.isMarkedAndGrow(succ);
        }

        while (!stack.isEmpty()) {
            Node current = stack.pop();
            assert visited.isMarked(current);
            assert current instanceof ControlSinkNode || current instanceof LoopEndNode || current.cfgSuccessors().iterator().hasNext() : "Must not reach a node that has not been decoded yet";

            for (Node successor : current.cfgSuccessors()) {
                if (visited.isMarked(successor)) {
                    /* Already processed this successor. */

                } else if (methodScope.loopExplosionMerges.isMarkedAndGrow(successor)) {
                    /*
                     * We have a FrameState for the successor. The LoopExit will be inserted between
                     * the current node and the successor node. Since the successor node is a
                     * MergeNode, the current node mus be a AbstractEndNode with only that MergeNode
                     * as the successor.
                     */
                    assert successor instanceof MergeNode;
                    assert !loop.exits.contains(current);
                    loop.exits.add((AbstractEndNode) current);

                } else {
                    /* Node we have not seen yet. */
                    visited.mark(successor);
                    stack.push(successor);
                }
            }
        }
    }

    private void insertLoopNodes(Loop loop) {
        MergeNode merge = loop.header;
        FrameState stateAfter = merge.stateAfter().duplicate();
        FixedNode afterMerge = merge.next();
        merge.setNext(null);
        EndNode preLoopEnd = methodScope.graph.add(new EndNode());
        LoopBeginNode loopBegin = methodScope.graph.add(new LoopBeginNode());

        merge.setNext(preLoopEnd);
        /* Add the single non-loop predecessor of the loop header. */
        loopBegin.addForwardEnd(preLoopEnd);
        loopBegin.setNext(afterMerge);
        loopBegin.setStateAfter(stateAfter);

        /*
         * Phi functions of the original merge need to be split: inputs that come from forward edges
         * remain with the original phi function; inputs that come from backward edges are added to
         * new phi functions.
         */
        List<PhiNode> mergePhis = merge.phis().snapshot();
        List<PhiNode> loopBeginPhis = new ArrayList<>(mergePhis.size());
        for (int i = 0; i < mergePhis.size(); i++) {
            PhiNode mergePhi = mergePhis.get(i);
            PhiNode loopBeginPhi = methodScope.graph.addWithoutUnique(new ValuePhiNode(mergePhi.stamp(), loopBegin));
            mergePhi.replaceAtUsages(loopBeginPhi);
            /*
             * The first input of the new phi function is the original phi function, for the one
             * forward edge of the LoopBeginNode.
             */
            loopBeginPhi.addInput(mergePhi);
            loopBeginPhis.add(loopBeginPhi);
        }

        for (EndNode endNode : loop.ends) {
            for (int i = 0; i < mergePhis.size(); i++) {
                PhiNode mergePhi = mergePhis.get(i);
                PhiNode loopBeginPhi = loopBeginPhis.get(i);
                loopBeginPhi.addInput(mergePhi.valueAt(endNode));
            }

            merge.removeEnd(endNode);
            LoopEndNode loopEnd = methodScope.graph.add(new LoopEndNode(loopBegin));
            endNode.replaceAndDelete(loopEnd);
        }

        /*
         * Insert the LoopExit nodes (the easy part) and compute the FrameState for the new exits
         * (the difficult part).
         */
        for (AbstractEndNode exit : loop.exits) {
            AbstractMergeNode loopExplosionMerge = exit.merge();
            assert methodScope.loopExplosionMerges.isMarkedAndGrow(loopExplosionMerge);

            LoopExitNode loopExit = methodScope.graph.add(new LoopExitNode(loopBegin));
            exit.replaceAtPredecessor(loopExit);
            loopExit.setNext(exit);
            assignLoopExitState(loopExit, loopExplosionMerge, exit);
        }
    }

    /**
     * During graph decoding, we create a FrameState for every exploded loop iteration. This is
     * mostly the state that we want, we only need to tweak it a little bit: we need to insert the
     * appropriate ProxyNodes for all values that are created inside the loop and that flow out of
     * the loop.
     */
    private void assignLoopExitState(LoopExitNode loopExit, AbstractMergeNode loopExplosionMerge, AbstractEndNode loopExplosionEnd) {
        FrameState oldState = loopExplosionMerge.stateAfter();

        /* Collect all nodes that are in the FrameState at the LoopBegin. */
        NodeBitMap loopBeginValues = new NodeBitMap(methodScope.graph);
        for (FrameState state = loopExit.loopBegin().stateAfter(); state != null; state = state.outerFrameState()) {
            for (ValueNode value : state.values()) {
                if (value != null && !value.isConstant() && !loopExit.loopBegin().isPhiAtMerge(value)) {
                    loopBeginValues.mark(ProxyPlaceholder.unwrap(value));
                }
            }
        }

        List<ValueNode> newValues = new ArrayList<>(oldState.values().size());
        for (ValueNode v : oldState.values()) {
            ValueNode value = v;
            ValueNode realValue = ProxyPlaceholder.unwrap(value);

            /*
             * The LoopExit is inserted before the existing merge, i.e., separately for every branch
             * that leads to the merge. So for phi functions of the merge, we need to take the input
             * that corresponds to our branch.
             */
            if (realValue instanceof PhiNode && loopExplosionMerge.isPhiAtMerge(realValue)) {
                value = ((PhiNode) realValue).valueAt(loopExplosionEnd);
                realValue = ProxyPlaceholder.unwrap(value);
            }

            if (realValue == null || realValue.isConstant() || loopBeginValues.contains(realValue) || !methodScope.graph.isNew(methodScope.methodStartMark, realValue)) {
                newValues.add(realValue);
            } else {
                /*
                 * The node is not in the FrameState of the LoopBegin, i.e., it is a value computed
                 * inside the loop.
                 */
                GraalError.guarantee(value instanceof ProxyPlaceholder && ((ProxyPlaceholder) value).proxyPoint == loopExplosionMerge,
                                "Value flowing out of loop, but we are not prepared to insert a ProxyNode");

                ProxyPlaceholder proxyPlaceholder = (ProxyPlaceholder) value;
                ValueProxyNode proxy = ProxyNode.forValue(proxyPlaceholder.value, loopExit, methodScope.graph);
                proxyPlaceholder.setValue(proxy);
                newValues.add(proxy);
            }
        }

        FrameState newState = new FrameState(oldState.outerFrameState(), oldState.getCode(), oldState.bci, newValues, oldState.localsSize(), oldState.stackSize(), oldState.rethrowException(),
                        oldState.duringCall(), oldState.monitorIds(), oldState.virtualObjectMappings());

        assert loopExit.stateAfter() == null;
        loopExit.setStateAfter(methodScope.graph.add(newState));
    }

    /**
     * Graal does not support irreducible loops (loops with more than one entry point). There are
     * two ways to make them reducible: 1) duplicate nodes (peel a loop iteration starting at the
     * second entry point until we reach the first entry point), or 2) insert a big outer loop
     * covering the whole method and build a state machine for the different loop entry points.
     * Since node duplication can lead to an exponential explosion of nodes in the worst case, we
     * use the second approach.
     *
     * We already did some preparations to insert a big outer loop:
     * {@link MethodScope#loopExplosionHead} is the loop header for the outer loop, and we ensured
     * that we have a {@link Loop} data object for it in {@link #irreducibleLoopHandler}.
     *
     * Now we need to insert the state machine. We have several implementation restrictions to make
     * that efficient:
     * <ul>
     * <li>There must be only one loop variable, i.e., one value that is different in the
     * {@link FrameState} of the different loop headers.</li>
     * <li>The loop variable must use the primitive {@code int} type, because Graal only has a
     * {@link IntegerSwitchNode switch node} for {@code int}.</li>
     * <li>The values of the loop variable that are merged are {@link PrimitiveConstant compile time
     * constants}.</li>
     * </ul>
     */
    private void handleIrreducibleLoop(Loop loop) {
        assert loop != irreducibleLoopHandler;

        FrameState loopState = loop.header.stateAfter();
        FrameState explosionHeadState = irreducibleLoopHandler.header.stateAfter();
        assert loopState.outerFrameState() == explosionHeadState.outerFrameState();
        NodeInputList<ValueNode> loopValues = loopState.values();
        NodeInputList<ValueNode> explosionHeadValues = explosionHeadState.values();
        assert loopValues.size() == explosionHeadValues.size();

        /*
         * Find the loop variable, and the value of the loop variable for our loop and the outermost
         * loop. There must be exactly one loop variable.
         */
        int loopVariableIndex = -1;
        ValueNode loopValue = null;
        ValueNode explosionHeadValue = null;
        for (int i = 0; i < loopValues.size(); i++) {
            ValueNode curLoopValue = loopValues.get(i);
            ValueNode curExplosionHeadValue = explosionHeadValues.get(i);

            if (curLoopValue != curExplosionHeadValue) {
                if (loopVariableIndex != -1) {
                    throw bailout("must have only one variable that is changed in loop. " + loopValue + " != " + explosionHeadValue + " and " + curLoopValue + " != " + curExplosionHeadValue);
                }

                loopVariableIndex = i;
                loopValue = curLoopValue;
                explosionHeadValue = curExplosionHeadValue;
            }
        }
        assert loopVariableIndex != -1;

        ValuePhiNode loopVariablePhi;
        SortedMap<Integer, AbstractBeginNode> dispatchTable = new TreeMap<>();
        AbstractBeginNode unreachableDefaultSuccessor;
        if (irreducibleLoopSwitch == null) {
            /*
             * This is the first irreducible loop. We need to build the initial state machine
             * (dispatch for the loop header of the outermost loop).
             */
            assert !irreducibleLoopHandler.header.isPhiAtMerge(explosionHeadValue);
            assert irreducibleLoopHandler.header.phis().isEmpty();

            /* The new phi function for the loop variable. */
            loopVariablePhi = methodScope.graph.addWithoutUnique(new ValuePhiNode(explosionHeadValue.stamp().unrestricted(), irreducibleLoopHandler.header));
            for (int i = 0; i < irreducibleLoopHandler.header.phiPredecessorCount(); i++) {
                loopVariablePhi.addInput(explosionHeadValue);
            }

            /*
             * Build the new FrameState for the loop header. There is only once change in comparison
             * to the old FrameState: the loop variable is replaced with the phi function.
             */
            FrameState oldFrameState = explosionHeadState;
            List<ValueNode> newFrameStateValues = new ArrayList<>();
            for (int i = 0; i < explosionHeadValues.size(); i++) {
                if (i == loopVariableIndex) {
                    newFrameStateValues.add(loopVariablePhi);
                } else {
                    newFrameStateValues.add(explosionHeadValues.get(i));
                }
            }
            FrameState newFrameState = methodScope.graph.add(
                            new FrameState(oldFrameState.outerFrameState(), oldFrameState.getCode(), oldFrameState.bci, newFrameStateValues, oldFrameState.localsSize(),
                                            oldFrameState.stackSize(), oldFrameState.rethrowException(), oldFrameState.duringCall(), oldFrameState.monitorIds(),
                                            oldFrameState.virtualObjectMappings()));
            oldFrameState.replaceAtUsages(newFrameState);

            /*
             * Disconnect the outermost loop header from its loop body, so that we can later on
             * insert the switch node. Collect dispatch information for the outermost loop.
             */
            FixedNode handlerNext = irreducibleLoopHandler.header.next();
            irreducibleLoopHandler.header.setNext(null);
            BeginNode handlerBegin = methodScope.graph.add(new BeginNode());
            handlerBegin.setNext(handlerNext);
            dispatchTable.put(asInt(explosionHeadValue), handlerBegin);

            /*
             * We know that there will always be a matching key in the switch. But Graal always
             * wants a default successor, so we build a dummy block that just deoptimizes.
             */
            unreachableDefaultSuccessor = methodScope.graph.add(new BeginNode());
            DeoptimizeNode deopt = methodScope.graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.UnreachedCode));
            unreachableDefaultSuccessor.setNext(deopt);

        } else {
            /*
             * This is the second or a subsequent irreducible loop, i.e., we already inserted a
             * switch node before. We re-create the dispatch state machine of that switch, so that
             * we can extend it with one more branch.
             */
            assert irreducibleLoopHandler.header.isPhiAtMerge(explosionHeadValue);
            assert irreducibleLoopHandler.header.phis().count() == 1 && irreducibleLoopHandler.header.phis().first() == explosionHeadValue;
            assert irreducibleLoopSwitch.value() == explosionHeadValue;

            /* We can modify the phi function used by the old switch node. */
            loopVariablePhi = (ValuePhiNode) explosionHeadValue;

            /*
             * We cannot modify the old switch node. Insert all information from the old switch node
             * into our temporary data structures for the new, larger, switch node.
             */
            for (int i = 0; i < irreducibleLoopSwitch.keyCount(); i++) {
                int key = irreducibleLoopSwitch.keyAt(i).asInt();
                dispatchTable.put(key, irreducibleLoopSwitch.successorAtKey(key));
            }
            unreachableDefaultSuccessor = irreducibleLoopSwitch.defaultSuccessor();

            /* Unlink and delete the old switch node, we do not need it anymore. */
            assert irreducibleLoopHandler.header.next() == irreducibleLoopSwitch;
            irreducibleLoopHandler.header.setNext(null);
            irreducibleLoopSwitch.clearSuccessors();
            irreducibleLoopSwitch.safeDelete();
        }

        /* Insert our loop into the dispatch state machine. */
        assert loop.header.phis().isEmpty();
        BeginNode dispatchBegin = methodScope.graph.add(new BeginNode());
        EndNode dispatchEnd = methodScope.graph.add(new EndNode());
        dispatchBegin.setNext(dispatchEnd);
        loop.header.addForwardEnd(dispatchEnd);
        int intLoopValue = asInt(loopValue);
        assert !dispatchTable.containsKey(intLoopValue);
        dispatchTable.put(intLoopValue, dispatchBegin);

        /* Disconnect the ends of our loop and re-connect them to the outermost loop header. */
        for (EndNode end : loop.ends) {
            loop.header.removeEnd(end);
            irreducibleLoopHandler.ends.add(end);
            irreducibleLoopHandler.header.addForwardEnd(end);
            loopVariablePhi.addInput(loopValue);
        }

        /* Build and insert the switch node. */
        irreducibleLoopSwitch = methodScope.graph.add(createSwitch(loopVariablePhi, dispatchTable, unreachableDefaultSuccessor));
        irreducibleLoopHandler.header.setNext(irreducibleLoopSwitch);
    }

    private static int asInt(ValueNode node) {
        if (!node.isConstant() || node.asJavaConstant().getJavaKind() != JavaKind.Int) {
            throw bailout("must have a loop variable of type int. " + node);
        }
        return node.asJavaConstant().asInt();
    }

    private static RuntimeException bailout(String msg) {
        throw new PermanentBailoutException("Graal implementation restriction: Method with %s loop explosion %s", LoopExplosionKind.MERGE_EXPLODE, msg);
    }

    private static IntegerSwitchNode createSwitch(ValuePhiNode switchedValue, SortedMap<Integer, AbstractBeginNode> dispatchTable, AbstractBeginNode defaultSuccessor) {
        int numKeys = dispatchTable.size();
        int numSuccessors = numKeys + 1;

        AbstractBeginNode[] switchSuccessors = new AbstractBeginNode[numSuccessors];
        int[] switchKeys = new int[numKeys];
        double[] switchKeyProbabilities = new double[numSuccessors];
        int[] switchKeySuccessors = new int[numSuccessors];

        int idx = 0;
        for (Map.Entry<Integer, AbstractBeginNode> entry : dispatchTable.entrySet()) {
            switchSuccessors[idx] = entry.getValue();
            switchKeys[idx] = entry.getKey();
            switchKeyProbabilities[idx] = 1d / numKeys;
            switchKeySuccessors[idx] = idx;
            idx++;
        }
        switchSuccessors[idx] = defaultSuccessor;
        /* We know the default branch is never going to be executed. */
        switchKeyProbabilities[idx] = 0;
        switchKeySuccessors[idx] = idx;

        return new IntegerSwitchNode(switchedValue, switchSuccessors, switchKeys, switchKeyProbabilities, switchKeySuccessors);
    }

    /**
     * Print information about irreducible loops, when enabled with -Dgraal.Log=IrreducibleLoops.
     */
    @SuppressWarnings("try")
    private void logIrreducibleLoops() {
        try (Debug.Scope s = Debug.scope("IrreducibleLoops")) {
            if (Debug.isLogEnabled(Debug.BASIC_LOG_LEVEL) && irreducibleLoopSwitch != null) {
                StringBuilder msg = new StringBuilder("Inserted state machine to remove irreducible loops. Dispatching to the following states: ");
                String sep = "";
                for (int i = 0; i < irreducibleLoopSwitch.keyCount(); i++) {
                    msg.append(sep).append(irreducibleLoopSwitch.keyAt(i).asInt());
                    sep = ", ";
                }
                Debug.log(Debug.BASIC_LOG_LEVEL, "%s", msg);
            }
        }
    }
}