001/*
002 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.nodes;
024
025import static jdk.internal.jvmci.common.JVMCIError.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030import com.oracle.graal.debug.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.compiler.common.*;
034import com.oracle.graal.compiler.common.util.*;
035import com.oracle.graal.graph.*;
036
037/**
038 * Decoder for {@link EncodedGraph encoded graphs} produced by {@link GraphEncoder}. Support for
039 * loop explosion during decoding is built into this class, because it requires many interactions
040 * with the decoding process. Subclasses can provide canonicalization and simplification of nodes
041 * during decoding, as well as method inlining during decoding.
042 */
043public class GraphDecoder {
044
045    public enum LoopExplosionKind {
046        /**
047         * No loop explosion.
048         */
049        NONE,
050        /**
051         * Fully unroll all loops. The loops must have a known finite number of iterations. If a
052         * loop has multiple loop ends, they are merged so that the subsequent loop iteration is
053         * processed only once. For example, a loop with 4 iterations and 2 loop ends leads to
054         * 1+1+1+1 = 4 copies of the loop body. The merge can introduce phi functions.
055         */
056        FULL_UNROLL,
057        /**
058         * Fully explode all loops. The loops must have a known finite number of iterations. If a
059         * loop has multiple loop ends, they are not merged so that subsequent loop iterations are
060         * processed multiple times. For example, a loop with 4 iterations and 2 loop ends leads to
061         * 1+2+4+8 = 15 copies of the loop body.
062         */
063        FULL_EXPLODE,
064        /**
065         * like {@link #FULL_EXPLODE}, but copies of the loop body that have the exact same state
066         * are merged. This reduces the number of copies necessary, but can introduce loops again.
067         */
068        MERGE_EXPLODE
069    }
070
071    /** Decoding state maintained for each encoded graph. */
072    protected class MethodScope {
073        /** The target graph where decoded nodes are added to. */
074        public final StructuredGraph graph;
075        /** The encode graph that is decoded. */
076        public final EncodedGraph encodedGraph;
077        /** Access to the encoded graph. */
078        public final TypeReader reader;
079        /** The kind of loop explosion to be performed during decoding. */
080        public final LoopExplosionKind loopExplosion;
081
082        /** All return nodes encountered during decoding. */
083        public final List<ReturnNode> returnNodes;
084        /** The exception unwind node encountered during decoding, or null. */
085        public UnwindNode unwindNode;
086
087        protected MethodScope(StructuredGraph graph, EncodedGraph encodedGraph, LoopExplosionKind loopExplosion) {
088            this.graph = graph;
089            this.encodedGraph = encodedGraph;
090            this.loopExplosion = loopExplosion;
091            this.returnNodes = new ArrayList<>();
092
093            if (encodedGraph != null) {
094                reader = UnsafeArrayTypeReader.create(encodedGraph.getEncoding(), encodedGraph.getStartOffset(), architecture.supportsUnalignedMemoryAccess());
095                if (encodedGraph.nodeStartOffsets == null) {
096                    int nodeCount = reader.getUVInt();
097                    long[] nodeStartOffsets = new long[nodeCount];
098                    for (int i = 0; i < nodeCount; i++) {
099                        nodeStartOffsets[i] = encodedGraph.getStartOffset() - reader.getUV();
100                    }
101                    encodedGraph.nodeStartOffsets = nodeStartOffsets;
102                }
103            } else {
104                reader = null;
105            }
106        }
107    }
108
109    /** Decoding state maintained for each loop in the encoded graph. */
110    protected static class LoopScope {
111        public final LoopScope outer;
112        public final int loopDepth;
113        public final int loopIteration;
114        /**
115         * Upcoming loop iterations during loop explosions that have not been processed yet. Only
116         * used when {@link MethodScope#loopExplosion} is not {@link LoopExplosionKind#NONE}.
117         */
118        public Deque<LoopScope> nextIterations;
119        /**
120         * Information about already processed loop iterations for state merging during loop
121         * explosion. Only used when {@link MethodScope#loopExplosion} is
122         * {@link LoopExplosionKind#MERGE_EXPLODE}.
123         */
124        public final Map<LoopExplosionState, LoopExplosionState> iterationStates;
125        public final int loopBeginOrderId;
126        /**
127         * The worklist of fixed nodes to process. Since we already the correct processing order
128         * from the orderId, we just set the orderId bit in the bitset when a node is ready for
129         * processing. The lowest set bit is the next node to process.
130         */
131        public final BitSet nodesToProcess;
132        /** Nodes that have been created, indexed by the orderId. */
133        public final Node[] createdNodes;
134        /**
135         * Nodes that have been created in outer loop scopes and existed before starting to process
136         * this loop, indexed by the orderId.
137         */
138        public final Node[] initialCreatedNodes;
139
140        protected LoopScope(MethodScope methodScope) {
141            this.outer = null;
142            this.nextIterations = null;
143            this.loopDepth = 0;
144            this.loopIteration = 0;
145            this.iterationStates = null;
146            this.loopBeginOrderId = -1;
147
148            int nodeCount = methodScope.encodedGraph.nodeStartOffsets.length;
149            this.nodesToProcess = new BitSet(nodeCount);
150            this.initialCreatedNodes = new Node[nodeCount];
151            this.createdNodes = new Node[nodeCount];
152        }
153
154        protected LoopScope(LoopScope outer, int loopDepth, int loopIteration, int loopBeginOrderId, Node[] initialCreatedNodes, Deque<LoopScope> nextIterations,
155                        Map<LoopExplosionState, LoopExplosionState> iterationStates) {
156            this.outer = outer;
157            this.loopDepth = loopDepth;
158            this.loopIteration = loopIteration;
159            this.nextIterations = nextIterations;
160            this.iterationStates = iterationStates;
161            this.loopBeginOrderId = loopBeginOrderId;
162            this.nodesToProcess = new BitSet(initialCreatedNodes.length);
163            this.initialCreatedNodes = initialCreatedNodes;
164            this.createdNodes = Arrays.copyOf(initialCreatedNodes, initialCreatedNodes.length);
165        }
166
167        @Override
168        public String toString() {
169            return loopDepth + "," + loopIteration + (loopBeginOrderId == -1 ? "" : "#" + loopBeginOrderId);
170        }
171    }
172
173    protected static class LoopExplosionState {
174        public final FrameState state;
175        public final MergeNode merge;
176        public final int hashCode;
177
178        protected LoopExplosionState(FrameState state, MergeNode merge) {
179            this.state = state;
180            this.merge = merge;
181
182            int h = 0;
183            for (ValueNode value : state.values()) {
184                if (value == null) {
185                    h = h * 31 + 1234;
186                } else {
187                    h = h * 31 + value.hashCode();
188                }
189            }
190            this.hashCode = h;
191        }
192
193        @Override
194        public boolean equals(Object obj) {
195            if (!(obj instanceof LoopExplosionState)) {
196                return false;
197            }
198
199            FrameState otherState = ((LoopExplosionState) obj).state;
200            FrameState thisState = state;
201            assert thisState.outerFrameState() == otherState.outerFrameState();
202
203            Iterator<ValueNode> thisIter = thisState.values().iterator();
204            Iterator<ValueNode> otherIter = otherState.values().iterator();
205            while (thisIter.hasNext() && otherIter.hasNext()) {
206                ValueNode thisValue = thisIter.next();
207                ValueNode otherValue = otherIter.next();
208                if (thisValue != otherValue) {
209                    return false;
210                }
211            }
212            return thisIter.hasNext() == otherIter.hasNext();
213        }
214
215        @Override
216        public int hashCode() {
217            return hashCode;
218        }
219    }
220
221    /**
222     * Additional information encoded for {@link Invoke} nodes to allow method inlining without
223     * decoding the frame state and successors beforehand.
224     */
225    protected static class InvokeData {
226        public final Invoke invoke;
227        public final ResolvedJavaType contextType;
228        public final int invokeOrderId;
229        public final int callTargetOrderId;
230        public final int stateAfterOrderId;
231        public final int nextOrderId;
232
233        public final int nextNextOrderId;
234        public final int exceptionOrderId;
235        public final int exceptionStateOrderId;
236        public final int exceptionNextOrderId;
237
238        protected InvokeData(Invoke invoke, ResolvedJavaType contextType, int invokeOrderId, int callTargetOrderId, int stateAfterOrderId, int nextOrderId, int nextNextOrderId, int exceptionOrderId,
239                        int exceptionStateOrderId, int exceptionNextOrderId) {
240            this.invoke = invoke;
241            this.contextType = contextType;
242            this.invokeOrderId = invokeOrderId;
243            this.callTargetOrderId = callTargetOrderId;
244            this.stateAfterOrderId = stateAfterOrderId;
245            this.nextOrderId = nextOrderId;
246            this.nextNextOrderId = nextNextOrderId;
247            this.exceptionOrderId = exceptionOrderId;
248            this.exceptionStateOrderId = exceptionStateOrderId;
249            this.exceptionNextOrderId = exceptionNextOrderId;
250        }
251    }
252
253    protected final Architecture architecture;
254
255    public GraphDecoder(Architecture architecture) {
256        this.architecture = architecture;
257    }
258
259    public final void decode(StructuredGraph graph, EncodedGraph encodedGraph) {
260        try (Debug.Scope scope = Debug.scope("GraphDecoder", graph)) {
261            MethodScope methodScope = new MethodScope(graph, encodedGraph, LoopExplosionKind.NONE);
262            decode(methodScope, null);
263            cleanupGraph(methodScope, null);
264            methodScope.graph.verify();
265        } catch (Throwable ex) {
266            Debug.handle(ex);
267        }
268    }
269
270    protected final void decode(MethodScope methodScope, FixedWithNextNode startNode) {
271        Graph.Mark start = methodScope.graph.getMark();
272        LoopScope loopScope = new LoopScope(methodScope);
273        FixedNode firstNode;
274        if (startNode != null) {
275            /*
276             * The start node of a graph can be referenced as the guard for a GuardedNode. We
277             * register the previous block node, so that such guards are correctly anchored when
278             * doing inlining during graph decoding.
279             */
280            registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, AbstractBeginNode.prevBegin(startNode), false, false);
281
282            firstNode = makeStubNode(methodScope, loopScope, GraphEncoder.FIRST_NODE_ORDER_ID);
283            startNode.setNext(firstNode);
284            loopScope.nodesToProcess.set(GraphEncoder.FIRST_NODE_ORDER_ID);
285        } else {
286            firstNode = methodScope.graph.start();
287            registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, firstNode, false, false);
288            loopScope.nodesToProcess.set(GraphEncoder.START_NODE_ORDER_ID);
289        }
290
291        while (loopScope != null) {
292            while (!loopScope.nodesToProcess.isEmpty()) {
293                loopScope = processNextNode(methodScope, loopScope);
294            }
295
296            if (loopScope.nextIterations != null && !loopScope.nextIterations.isEmpty()) {
297                /* Loop explosion: process the loop iteration. */
298                assert loopScope.nextIterations.peekFirst().loopIteration == loopScope.loopIteration + 1;
299                loopScope = loopScope.nextIterations.removeFirst();
300            } else {
301                propagateCreatedNodes(loopScope);
302                loopScope = loopScope.outer;
303            }
304        }
305
306        if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
307            /*
308             * The startNode can get deleted during graph cleanup, so we use its predecessor (if
309             * available) as the starting point for loop detection.
310             */
311            FixedNode detectLoopsStart = startNode.predecessor() != null ? (FixedNode) startNode.predecessor() : startNode;
312            cleanupGraph(methodScope, start);
313            detectLoops(methodScope.graph, detectLoopsStart);
314        }
315    }
316
317    private static void propagateCreatedNodes(LoopScope loopScope) {
318        if (loopScope.outer == null) {
319            return;
320        }
321
322        /* Register nodes that were created while decoding the loop to the outside scope. */
323        for (int i = 0; i < loopScope.createdNodes.length; i++) {
324            if (loopScope.outer.createdNodes[i] == null) {
325                loopScope.outer.createdNodes[i] = loopScope.createdNodes[i];
326            }
327        }
328    }
329
330    protected LoopScope processNextNode(MethodScope methodScope, LoopScope loopScope) {
331        int nodeOrderId = loopScope.nodesToProcess.nextSetBit(0);
332        loopScope.nodesToProcess.clear(nodeOrderId);
333
334        FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId);
335        if (node.isDeleted()) {
336            return loopScope;
337        }
338
339        if ((node instanceof MergeNode || (node instanceof LoopBeginNode && (methodScope.loopExplosion == LoopExplosionKind.FULL_UNROLL || methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE))) &&
340                        ((AbstractMergeNode) node).forwardEndCount() == 1) {
341            AbstractMergeNode merge = (AbstractMergeNode) node;
342            EndNode singleEnd = merge.forwardEndAt(0);
343
344            /* Nodes that would use this merge as the guard need to use the previous block. */
345            registerNode(loopScope, nodeOrderId, AbstractBeginNode.prevBegin(singleEnd), true, false);
346
347            FixedNode next = makeStubNode(methodScope, loopScope, nodeOrderId + GraphEncoder.BEGIN_NEXT_ORDER_ID_OFFSET);
348            singleEnd.replaceAtPredecessor(next);
349
350            merge.safeDelete();
351            singleEnd.safeDelete();
352            return loopScope;
353        }
354
355        LoopScope successorAddScope = loopScope;
356        boolean updatePredecessors = true;
357        if (node instanceof LoopExitNode) {
358            successorAddScope = loopScope.outer;
359            updatePredecessors = methodScope.loopExplosion == LoopExplosionKind.NONE;
360        }
361
362        methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
363        int typeId = methodScope.reader.getUVInt();
364        assert node.getNodeClass() == methodScope.encodedGraph.getNodeClasses()[typeId];
365        readProperties(methodScope, node);
366        makeSuccessorStubs(methodScope, successorAddScope, node, updatePredecessors);
367        makeInputNodes(methodScope, loopScope, node, true);
368
369        LoopScope resultScope = loopScope;
370        if (node instanceof LoopBeginNode) {
371            if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
372                handleLoopExplosionBegin(methodScope, loopScope, (LoopBeginNode) node);
373            }
374
375        } else if (node instanceof LoopExitNode) {
376            if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
377                handleLoopExplosionProxyNodes(methodScope, loopScope, (LoopExitNode) node, nodeOrderId);
378            } else {
379                handleProxyNodes(methodScope, loopScope, (LoopExitNode) node);
380            }
381
382        } else if (node instanceof AbstractEndNode) {
383            LoopScope phiInputScope = loopScope;
384            LoopScope phiNodeScope = loopScope;
385
386            if (methodScope.loopExplosion != LoopExplosionKind.NONE && node instanceof LoopEndNode) {
387                node = handleLoopExplosionEnd(methodScope, loopScope, (LoopEndNode) node);
388                phiNodeScope = loopScope.nextIterations.getLast();
389            }
390
391            int mergeOrderId = readOrderId(methodScope);
392            AbstractMergeNode merge = (AbstractMergeNode) lookupNode(phiNodeScope, mergeOrderId);
393            if (merge == null) {
394                merge = (AbstractMergeNode) makeStubNode(methodScope, phiNodeScope, mergeOrderId);
395
396                if (merge instanceof LoopBeginNode) {
397                    assert phiNodeScope == phiInputScope && phiNodeScope == loopScope;
398                    resultScope = new LoopScope(loopScope, loopScope.loopDepth + 1, 0, mergeOrderId, Arrays.copyOf(loopScope.createdNodes, loopScope.createdNodes.length), //
399                                    methodScope.loopExplosion != LoopExplosionKind.NONE ? new ArrayDeque<>() : null, //
400                                    methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE ? new HashMap<>() : null);
401                    phiInputScope = resultScope;
402                    phiNodeScope = resultScope;
403
404                    registerNode(loopScope, mergeOrderId, null, true, true);
405                    loopScope.nodesToProcess.clear(mergeOrderId);
406                    resultScope.nodesToProcess.set(mergeOrderId);
407                }
408            }
409
410            handlePhiFunctions(methodScope, phiInputScope, phiNodeScope, (AbstractEndNode) node, merge);
411
412        } else if (node instanceof Invoke) {
413            InvokeData invokeData = readInvokeData(methodScope, nodeOrderId, (Invoke) node);
414            handleInvoke(methodScope, loopScope, invokeData);
415
416        } else if (node instanceof ReturnNode) {
417            methodScope.returnNodes.add((ReturnNode) node);
418        } else if (node instanceof UnwindNode) {
419            assert methodScope.unwindNode == null : "graph can have only one UnwindNode";
420            methodScope.unwindNode = (UnwindNode) node;
421
422        } else {
423            handleFixedNode(methodScope, loopScope, nodeOrderId, node);
424        }
425
426        return resultScope;
427    }
428
429    private InvokeData readInvokeData(MethodScope methodScope, int invokeOrderId, Invoke invoke) {
430        ResolvedJavaType contextType = (ResolvedJavaType) readObject(methodScope);
431        int callTargetOrderId = readOrderId(methodScope);
432        int stateAfterOrderId = readOrderId(methodScope);
433        int nextOrderId = readOrderId(methodScope);
434
435        if (invoke instanceof InvokeWithExceptionNode) {
436            int nextNextOrderId = readOrderId(methodScope);
437            int exceptionOrderId = readOrderId(methodScope);
438            int exceptionStateOrderId = readOrderId(methodScope);
439            int exceptionNextOrderId = readOrderId(methodScope);
440            return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, nextNextOrderId, exceptionOrderId, exceptionStateOrderId, exceptionNextOrderId);
441        } else {
442            return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, -1, -1, -1, -1);
443        }
444    }
445
446    /**
447     * {@link Invoke} nodes do not have the {@link CallTargetNode}, {@link FrameState}, and
448     * successors encoded. Instead, this information is provided separately to allow method inlining
449     * without decoding and adding them to the graph upfront. For non-inlined methods, this method
450     * restores the normal state. Subclasses can override it to perform method inlining.
451     */
452    protected void handleInvoke(MethodScope methodScope, LoopScope loopScope, InvokeData invokeData) {
453        assert invokeData.invoke.callTarget() == null : "callTarget edge is ignored during decoding of Invoke";
454        CallTargetNode callTarget = (CallTargetNode) ensureNodeCreated(methodScope, loopScope, invokeData.callTargetOrderId);
455        if (invokeData.invoke instanceof InvokeWithExceptionNode) {
456            ((InvokeWithExceptionNode) invokeData.invoke).setCallTarget(callTarget);
457        } else {
458            ((InvokeNode) invokeData.invoke).setCallTarget(callTarget);
459        }
460
461        assert invokeData.invoke.stateAfter() == null && invokeData.invoke.stateDuring() == null : "FrameState edges are ignored during decoding of Invoke";
462        invokeData.invoke.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, invokeData.stateAfterOrderId));
463
464        invokeData.invoke.setNext(makeStubNode(methodScope, loopScope, invokeData.nextOrderId));
465        if (invokeData.invoke instanceof InvokeWithExceptionNode) {
466            ((InvokeWithExceptionNode) invokeData.invoke).setExceptionEdge((AbstractBeginNode) makeStubNode(methodScope, loopScope, invokeData.exceptionOrderId));
467        }
468    }
469
470    protected void handleLoopExplosionBegin(MethodScope methodScope, LoopScope loopScope, LoopBeginNode loopBegin) {
471        checkLoopExplosionIteration(methodScope, loopScope);
472
473        List<EndNode> predecessors = loopBegin.forwardEnds().snapshot();
474        FixedNode successor = loopBegin.next();
475        FrameState frameState = loopBegin.stateAfter();
476
477        if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
478            LoopExplosionState queryState = new LoopExplosionState(frameState, null);
479            LoopExplosionState existingState = loopScope.iterationStates.get(queryState);
480            if (existingState != null) {
481                loopBegin.replaceAtUsages(existingState.merge);
482                loopBegin.safeDelete();
483                successor.safeDelete();
484                for (EndNode predecessor : predecessors) {
485                    existingState.merge.addForwardEnd(predecessor);
486                }
487                return;
488            }
489        }
490
491        MergeNode merge = methodScope.graph.add(new MergeNode());
492        loopBegin.replaceAtUsages(merge);
493        loopBegin.safeDelete();
494        merge.setStateAfter(frameState);
495        merge.setNext(successor);
496        for (EndNode predecessor : predecessors) {
497            merge.addForwardEnd(predecessor);
498        }
499
500        if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
501            LoopExplosionState explosionState = new LoopExplosionState(frameState, merge);
502            loopScope.iterationStates.put(explosionState, explosionState);
503        }
504    }
505
506    /**
507     * Hook for subclasses.
508     *
509     * @param methodScope The current method.
510     * @param loopScope The current loop.
511     */
512    protected void checkLoopExplosionIteration(MethodScope methodScope, LoopScope loopScope) {
513        throw shouldNotReachHere("when subclass uses loop explosion, it needs to implement this method");
514    }
515
516    protected FixedNode handleLoopExplosionEnd(MethodScope methodScope, LoopScope loopScope, LoopEndNode loopEnd) {
517        EndNode replacementNode = methodScope.graph.add(new EndNode());
518        loopEnd.replaceAtPredecessor(replacementNode);
519        loopEnd.safeDelete();
520
521        assert methodScope.loopExplosion != LoopExplosionKind.NONE;
522        if (methodScope.loopExplosion != LoopExplosionKind.FULL_UNROLL || loopScope.nextIterations.isEmpty()) {
523            int nextIterationNumber = loopScope.nextIterations.isEmpty() ? loopScope.loopIteration + 1 : loopScope.nextIterations.getLast().loopIteration + 1;
524            LoopScope nextIterationScope = new LoopScope(loopScope.outer, loopScope.loopDepth, nextIterationNumber, loopScope.loopBeginOrderId, loopScope.initialCreatedNodes,
525                            loopScope.nextIterations, loopScope.iterationStates);
526            loopScope.nextIterations.addLast(nextIterationScope);
527            registerNode(nextIterationScope, loopScope.loopBeginOrderId, null, true, true);
528            makeStubNode(methodScope, nextIterationScope, loopScope.loopBeginOrderId);
529        }
530        return replacementNode;
531    }
532
533    /**
534     * Hook for subclasses.
535     *
536     * @param methodScope The current method.
537     * @param loopScope The current loop.
538     * @param nodeOrderId The orderId of the node.
539     * @param node The node to be simplified.
540     */
541    protected void handleFixedNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId, FixedNode node) {
542    }
543
544    protected void handleProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopExitNode loopExit) {
545        assert loopExit.stateAfter() == null;
546        int stateAfterOrderId = readOrderId(methodScope);
547        loopExit.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, stateAfterOrderId));
548
549        int numProxies = methodScope.reader.getUVInt();
550        for (int i = 0; i < numProxies; i++) {
551            int proxyOrderId = readOrderId(methodScope);
552            ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId);
553            /*
554             * The ProxyNode transports a value from the loop to the outer scope. We therefore
555             * register it in the outer scope.
556             */
557            registerNode(loopScope.outer, proxyOrderId, proxy, false, false);
558        }
559    }
560
561    protected void handleLoopExplosionProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopExitNode loopExit, int loopExitOrderId) {
562        assert loopExit.stateAfter() == null;
563        int stateAfterOrderId = readOrderId(methodScope);
564
565        BeginNode begin = methodScope.graph.add(new BeginNode());
566
567        FixedNode loopExitSuccessor = loopExit.next();
568        loopExit.replaceAtPredecessor(begin);
569
570        /*
571         * In the original graph, the loop exit is not a merge node. Multiple exploded loop
572         * iterations now take the same loop exit, so we have to introduce a new merge node to
573         * handle the merge.
574         */
575        MergeNode merge = null;
576        Node existingExit = lookupNode(loopScope.outer, loopExitOrderId);
577        if (existingExit == null) {
578            /* First loop iteration that exits. No merge necessary yet. */
579            registerNode(loopScope.outer, loopExitOrderId, begin, false, false);
580            begin.setNext(loopExitSuccessor);
581
582        } else if (existingExit instanceof BeginNode) {
583            /* Second loop iteration that exits. Create the merge. */
584            merge = methodScope.graph.add(new MergeNode());
585            registerNode(loopScope.outer, loopExitOrderId, merge, true, false);
586            /* Add the first iteration. */
587            EndNode firstEnd = methodScope.graph.add(new EndNode());
588            ((BeginNode) existingExit).setNext(firstEnd);
589            merge.addForwardEnd(firstEnd);
590            merge.setNext(loopExitSuccessor);
591
592        } else {
593            /* Subsequent loop iteration. Merge already created. */
594            merge = (MergeNode) existingExit;
595        }
596
597        if (merge != null) {
598            EndNode end = methodScope.graph.add(new EndNode());
599            begin.setNext(end);
600            merge.addForwardEnd(end);
601        }
602
603        /*
604         * Possibly create phi nodes for the original proxy nodes that flow out of the loop. Note
605         * that we definitely do not need a proxy node itself anymore, since the loop was exploded
606         * and is no longer present.
607         */
608        int numProxies = methodScope.reader.getUVInt();
609        boolean phiCreated = false;
610        for (int i = 0; i < numProxies; i++) {
611            int proxyOrderId = readOrderId(methodScope);
612            ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId);
613            ValueNode phiInput = proxy.value();
614            ValueNode replacement;
615
616            ValueNode existing = (ValueNode) loopScope.outer.createdNodes[proxyOrderId];
617            if (existing == null || existing == phiInput) {
618                /*
619                 * We are at the first loop exit, or the proxy carries the same value for all exits.
620                 * We do not need a phi node yet.
621                 */
622                registerNode(loopScope.outer, proxyOrderId, phiInput, true, false);
623                replacement = phiInput;
624
625            } else if (!merge.isPhiAtMerge(existing)) {
626                /* Now we have two different values, so we need to create a phi node. */
627                PhiNode phi = methodScope.graph.addWithoutUnique(new ValuePhiNode(proxy.stamp(), merge));
628                /* Add the inputs from all previous exits. */
629                for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) {
630                    phi.addInput(existing);
631                }
632                /* Add the input from this exit. */
633                phi.addInput(phiInput);
634                registerNode(loopScope.outer, proxyOrderId, phi, true, false);
635                replacement = phi;
636                phiCreated = true;
637
638            } else {
639                /* Phi node has been created before, so just add the new input. */
640                PhiNode phi = (PhiNode) existing;
641                phi.addInput(phiInput);
642                replacement = phi;
643            }
644
645            methodScope.graph.replaceFloating(proxy, replacement);
646        }
647
648        if (merge != null && (merge.stateAfter() == null || phiCreated)) {
649            FrameState oldStateAfter = merge.stateAfter();
650            registerNode(loopScope.outer, stateAfterOrderId, null, true, true);
651            merge.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope.outer, stateAfterOrderId));
652            if (oldStateAfter != null) {
653                oldStateAfter.safeDelete();
654            }
655        }
656
657        loopExit.safeDelete();
658        assert loopExitSuccessor.predecessor() == null;
659        if (merge != null) {
660            merge.getNodeClass().getSuccessorEdges().update(merge, null, loopExitSuccessor);
661        } else {
662            begin.getNodeClass().getSuccessorEdges().update(begin, null, loopExitSuccessor);
663        }
664    }
665
666    protected void handlePhiFunctions(MethodScope methodScope, LoopScope phiInputScope, LoopScope phiNodeScope, AbstractEndNode end, AbstractMergeNode merge) {
667
668        if (end instanceof LoopEndNode) {
669            /*
670             * Fix the loop end index and the number of loop ends. When we do canonicalization
671             * during decoding, we can end up with fewer ends than the encoded graph had. And the
672             * order of loop ends can be different.
673             */
674            int numEnds = ((LoopBeginNode) merge).loopEnds().count();
675            ((LoopBeginNode) merge).nextEndIndex = numEnds;
676            ((LoopEndNode) end).endIndex = numEnds - 1;
677
678        } else {
679            if (merge.ends == null) {
680                merge.ends = new NodeInputList<>(merge);
681            }
682            merge.addForwardEnd((EndNode) end);
683        }
684
685        /*
686         * We create most phi functions lazily. Canonicalization and simplification during decoding
687         * can lead to dead branches that are not decoded, so we might not need all phi functions
688         * that the original graph contained. Since we process all predecessors before actually
689         * processing the merge node, we have the final phi function when processing the merge node.
690         * The only exception are loop headers of non-exploded loops: since backward branches are
691         * not processed yet when processing the loop body, we need to create all phi functions
692         * upfront.
693         */
694        boolean lazyPhi = allowLazyPhis() && (!(merge instanceof LoopBeginNode) || methodScope.loopExplosion != LoopExplosionKind.NONE);
695        int numPhis = methodScope.reader.getUVInt();
696        for (int i = 0; i < numPhis; i++) {
697            int phiInputOrderId = readOrderId(methodScope);
698            int phiNodeOrderId = readOrderId(methodScope);
699
700            ValueNode phiInput = (ValueNode) ensureNodeCreated(methodScope, phiInputScope, phiInputOrderId);
701
702            ValueNode existing = (ValueNode) lookupNode(phiNodeScope, phiNodeOrderId);
703            if (lazyPhi && (existing == null || existing == phiInput)) {
704                /* Phi function not yet necessary. */
705                registerNode(phiNodeScope, phiNodeOrderId, phiInput, true, false);
706
707            } else if (!merge.isPhiAtMerge(existing)) {
708                /*
709                 * Phi function is necessary. Create it and fill it with existing inputs as well as
710                 * the new input.
711                 */
712                registerNode(phiNodeScope, phiNodeOrderId, null, true, true);
713                PhiNode phi = (PhiNode) ensureNodeCreated(methodScope, phiNodeScope, phiNodeOrderId);
714
715                phi.setMerge(merge);
716                for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) {
717                    phi.addInput(existing);
718                }
719                phi.addInput(phiInput);
720
721            } else {
722                /* Phi node has been created before, so just add the new input. */
723                PhiNode phi = (PhiNode) existing;
724                phi.addInput(phiInput);
725            }
726        }
727    }
728
729    protected boolean allowLazyPhis() {
730        /* We need to exactly reproduce the encoded graph, including unnecessary phi functions. */
731        return false;
732    }
733
734    protected Node instantiateNode(MethodScope methodScope, int nodeOrderId) {
735        methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
736        NodeClass<?> nodeClass = methodScope.encodedGraph.getNodeClasses()[methodScope.reader.getUVInt()];
737        return nodeClass.allocateInstance();
738    }
739
740    protected void readProperties(MethodScope methodScope, Node node) {
741        Fields fields = node.getNodeClass().getData();
742        for (int pos = 0; pos < fields.getCount(); pos++) {
743            if (fields.getType(pos).isPrimitive()) {
744                long primitive = methodScope.reader.getSV();
745                fields.setRawPrimitive(node, pos, primitive);
746            } else {
747                Object value = readObject(methodScope);
748                fields.set(node, pos, value);
749            }
750        }
751    }
752
753    /**
754     * Process the input edges of a node. Input nodes that have not yet been created must be
755     * non-fixed nodes (because fixed nodes are processed in reverse postorder. Such non-fixed nodes
756     * are created on demand (recursively since they can themselves reference not yet created
757     * nodes).
758     */
759    protected void makeInputNodes(MethodScope methodScope, LoopScope loopScope, Node node, boolean updateUsages) {
760        Edges edges = node.getNodeClass().getEdges(Edges.Type.Inputs);
761        for (int index = 0; index < edges.getDirectCount(); index++) {
762            if (skipEdge(node, edges, index, true, true)) {
763                continue;
764            }
765            int orderId = readOrderId(methodScope);
766            Node value = ensureNodeCreated(methodScope, loopScope, orderId);
767            Edges.initializeNode(node, edges.getOffsets(), index, value);
768            if (updateUsages && value != null && !value.isDeleted()) {
769                edges.update(node, null, value);
770
771            }
772        }
773        for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
774            if (skipEdge(node, edges, index, false, true)) {
775                continue;
776            }
777            int size = methodScope.reader.getSVInt();
778            if (size != -1) {
779                NodeList<Node> nodeList = new NodeInputList<>(node, size);
780                Edges.initializeList(node, edges.getOffsets(), index, nodeList);
781                for (int idx = 0; idx < size; idx++) {
782                    int orderId = readOrderId(methodScope);
783                    Node value = ensureNodeCreated(methodScope, loopScope, orderId);
784                    nodeList.initialize(idx, value);
785                    if (updateUsages && value != null && !value.isDeleted()) {
786                        edges.update(node, null, value);
787                    }
788                }
789            }
790        }
791    }
792
793    protected Node ensureNodeCreated(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
794        if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
795            return null;
796        }
797        Node node = lookupNode(loopScope, nodeOrderId);
798        if (node != null) {
799            return node;
800        }
801
802        node = decodeFloatingNode(methodScope, loopScope, nodeOrderId);
803
804        if (node instanceof ProxyNode || node instanceof PhiNode) {
805            /*
806             * We need these nodes as they were in the original graph, without any canonicalization
807             * or value numbering.
808             */
809            node = methodScope.graph.addWithoutUnique(node);
810
811        } else {
812            /* Allow subclasses to canonicalize and intercept nodes. */
813            node = handleFloatingNodeBeforeAdd(methodScope, loopScope, node);
814            if (!node.isAlive()) {
815                node = addFloatingNode(methodScope, node);
816            }
817            node = handleFloatingNodeAfterAdd(methodScope, loopScope, node);
818        }
819        registerNode(loopScope, nodeOrderId, node, false, false);
820        return node;
821    }
822
823    protected Node addFloatingNode(MethodScope methodScope, Node node) {
824        /*
825         * We want to exactly reproduce the encoded graph. Even though nodes should be unique in the
826         * encoded graph, this is not always guaranteed.
827         */
828        return methodScope.graph.addWithoutUnique(node);
829    }
830
831    /**
832     * Decodes a non-fixed node, but does not do any post-processing and does not register it.
833     */
834    protected Node decodeFloatingNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
835        long readerByteIndex = methodScope.reader.getByteIndex();
836        Node node = instantiateNode(methodScope, nodeOrderId);
837        if (node instanceof FixedNode) {
838            /*
839             * This is a severe error that will lead to a corrupted graph, so it is better not to
840             * continue decoding at all.
841             */
842            throw shouldNotReachHere("Not a floating node: " + node.getClass().getName());
843        }
844
845        /* Read the properties of the node. */
846        readProperties(methodScope, node);
847        /* There must not be any successors to read, since it is a non-fixed node. */
848        assert node.getNodeClass().getEdges(Edges.Type.Successors).getCount() == 0;
849        /* Read the inputs of the node, possibly creating them recursively. */
850        makeInputNodes(methodScope, loopScope, node, false);
851        methodScope.reader.setByteIndex(readerByteIndex);
852        return node;
853    }
854
855    /**
856     * Hook for subclasses to process a non-fixed node before it is added to the graph.
857     *
858     * @param methodScope The current method.
859     * @param loopScope The current loop.
860     * @param node The node to be canonicalized.
861     * @return The replacement for the node, or the node itself.
862     */
863    protected Node handleFloatingNodeBeforeAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
864        return node;
865    }
866
867    /**
868     * Hook for subclasses to process a non-fixed node after it is added to the graph.
869     *
870     * @param methodScope The current method.
871     * @param loopScope The current loop.
872     * @param node The node to be canonicalized.
873     * @return The replacement for the node, or the node itself.
874     */
875    protected Node handleFloatingNodeAfterAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
876        return node;
877    }
878
879    /**
880     * Process successor edges of a node. We create the successor nodes so that we can fill the
881     * successor list, but no properties or edges are loaded yet. That is done when the successor is
882     * on top of the worklist in {@link #processNextNode}.
883     */
884    protected void makeSuccessorStubs(MethodScope methodScope, LoopScope loopScope, Node node, boolean updatePredecessors) {
885        Edges edges = node.getNodeClass().getEdges(Edges.Type.Successors);
886        for (int index = 0; index < edges.getDirectCount(); index++) {
887            if (skipEdge(node, edges, index, true, true)) {
888                continue;
889            }
890            int orderId = readOrderId(methodScope);
891            Node value = makeStubNode(methodScope, loopScope, orderId);
892            Edges.initializeNode(node, edges.getOffsets(), index, value);
893            if (updatePredecessors && value != null) {
894                edges.update(node, null, value);
895            }
896        }
897        for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
898            if (skipEdge(node, edges, index, false, true)) {
899                continue;
900            }
901            int size = methodScope.reader.getSVInt();
902            if (size != -1) {
903                NodeList<Node> nodeList = new NodeSuccessorList<>(node, size);
904                Edges.initializeList(node, edges.getOffsets(), index, nodeList);
905                for (int idx = 0; idx < size; idx++) {
906                    int orderId = readOrderId(methodScope);
907                    Node value = makeStubNode(methodScope, loopScope, orderId);
908                    nodeList.initialize(idx, value);
909                    if (updatePredecessors && value != null) {
910                        edges.update(node, null, value);
911                    }
912                }
913            }
914        }
915    }
916
917    protected FixedNode makeStubNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
918        if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
919            return null;
920        }
921        FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId);
922        if (node != null) {
923            return node;
924        }
925
926        long readerByteIndex = methodScope.reader.getByteIndex();
927        node = (FixedNode) methodScope.graph.add(instantiateNode(methodScope, nodeOrderId));
928        /* Properties and edges are not filled yet, the node remains uninitialized. */
929        methodScope.reader.setByteIndex(readerByteIndex);
930
931        registerNode(loopScope, nodeOrderId, node, false, false);
932        loopScope.nodesToProcess.set(nodeOrderId);
933        return node;
934    }
935
936    /**
937     * Returns false for {@link Edges} that are not necessary in the encoded graph because they are
938     * reconstructed using other sources of information.
939     */
940    protected static boolean skipEdge(Node node, Edges edges, int index, boolean direct, boolean decode) {
941        if (node instanceof PhiNode) {
942            /* The inputs of phi functions are filled manually when the end nodes are processed. */
943            assert edges.type() == Edges.Type.Inputs;
944            if (direct) {
945                assert index == edges.getDirectCount() - 1 : "PhiNode has one direct input (the MergeNode)";
946            } else {
947                assert index == edges.getCount() - 1 : "PhiNode has one variable size input (the values)";
948                if (decode) {
949                    /* The values must not be null, so initialize with an empty list. */
950                    Edges.initializeList(node, edges.getOffsets(), index, new NodeInputList<>(node));
951                }
952            }
953            return true;
954
955        } else if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs && !direct) {
956            /* The ends of merge nodes are filled manually when the ends are processed. */
957            assert index == edges.getCount() - 1 : "MergeNode has one variable size input (the ends)";
958            assert Edges.getNodeList(node, edges.getOffsets(), index) != null : "Input list must have been already created";
959            return true;
960
961        } else if (node instanceof LoopExitNode && edges.type() == Edges.Type.Inputs && edges.getType(index) == FrameState.class) {
962            /* The stateAfter of the loop exit is filled manually. */
963            return true;
964
965        } else if (node instanceof Invoke) {
966            assert node instanceof InvokeNode || node instanceof InvokeWithExceptionNode : "The only two Invoke node classes. Got " + node.getClass();
967            assert direct : "Invoke and InvokeWithException only have direct successor and input edges";
968            if (edges.type() == Edges.Type.Successors) {
969                assert edges.getCount() == (node instanceof InvokeWithExceptionNode ? 2 : 1) : "InvokeNode has one successor (next); InvokeWithExceptionNode has two successors (next, exceptionEdge)";
970                return true;
971            } else {
972                assert edges.type() == Edges.Type.Inputs;
973                if (edges.getType(index) == CallTargetNode.class) {
974                    return true;
975                } else if (edges.getType(index) == FrameState.class) {
976                    assert edges.get(node, index) == null || edges.get(node, index) == ((Invoke) node).stateAfter() : "Only stateAfter can be a FrameState during encoding";
977                    return true;
978                }
979            }
980        }
981        return false;
982    }
983
984    protected Node lookupNode(LoopScope loopScope, int nodeOrderId) {
985        return loopScope.createdNodes[nodeOrderId];
986    }
987
988    protected void registerNode(LoopScope loopScope, int nodeOrderId, Node node, boolean allowOverwrite, boolean allowNull) {
989        assert node == null || node.isAlive();
990        assert allowNull || node != null;
991        assert allowOverwrite || lookupNode(loopScope, nodeOrderId) == null;
992        loopScope.createdNodes[nodeOrderId] = node;
993    }
994
995    protected int readOrderId(MethodScope methodScope) {
996        return methodScope.reader.getUVInt();
997    }
998
999    protected Object readObject(MethodScope methodScope) {
1000        return methodScope.encodedGraph.getObjects()[methodScope.reader.getUVInt()];
1001    }
1002
1003    /*
1004     * The following methods are a literal copy from GraphBuilderPhase.
1005     */
1006
1007    protected void detectLoops(StructuredGraph currentGraph, FixedNode startInstruction) {
1008        NodeBitMap visited = currentGraph.createNodeBitMap();
1009        NodeBitMap active = currentGraph.createNodeBitMap();
1010        Deque<Node> stack = new ArrayDeque<>();
1011        stack.add(startInstruction);
1012        visited.mark(startInstruction);
1013        while (!stack.isEmpty()) {
1014            Node next = stack.peek();
1015            assert next.isDeleted() || visited.isMarked(next);
1016            if (next.isDeleted() || active.isMarked(next)) {
1017                stack.pop();
1018                if (!next.isDeleted()) {
1019                    active.clear(next);
1020                }
1021            } else {
1022                active.mark(next);
1023                for (Node n : next.cfgSuccessors()) {
1024                    if (active.contains(n)) {
1025                        // Detected cycle.
1026                        assert n instanceof MergeNode;
1027                        assert next instanceof EndNode;
1028                        MergeNode merge = (MergeNode) n;
1029                        EndNode endNode = (EndNode) next;
1030                        merge.removeEnd(endNode);
1031                        FixedNode afterMerge = merge.next();
1032                        if (!(afterMerge instanceof EndNode) || !(((EndNode) afterMerge).merge() instanceof LoopBeginNode)) {
1033                            FrameState stateAfter = merge.stateAfter();
1034                            merge.setNext(null);
1035                            merge.setStateAfter(null);
1036                            LoopBeginNode newLoopBegin = appendLoopBegin(currentGraph, merge);
1037                            newLoopBegin.setNext(afterMerge);
1038                            newLoopBegin.setStateAfter(stateAfter);
1039                        }
1040                        LoopBeginNode loopBegin = (LoopBeginNode) ((EndNode) merge.next()).merge();
1041                        LoopEndNode loopEnd = currentGraph.add(new LoopEndNode(loopBegin));
1042                        endNode.replaceAndDelete(loopEnd);
1043                    } else if (visited.contains(n)) {
1044                        // Normal merge into a branch we are already exploring.
1045                    } else {
1046                        visited.mark(n);
1047                        stack.push(n);
1048                    }
1049                }
1050            }
1051        }
1052
1053        insertLoopEnds(currentGraph, startInstruction);
1054    }
1055
1056    private static LoopBeginNode appendLoopBegin(StructuredGraph currentGraph, FixedWithNextNode fixedWithNext) {
1057        EndNode preLoopEnd = currentGraph.add(new EndNode());
1058        LoopBeginNode loopBegin = currentGraph.add(new LoopBeginNode());
1059        fixedWithNext.setNext(preLoopEnd);
1060        // Add the single non-loop predecessor of the loop header.
1061        loopBegin.addForwardEnd(preLoopEnd);
1062        return loopBegin;
1063    }
1064
1065    private static void insertLoopEnds(StructuredGraph currentGraph, FixedNode startInstruction) {
1066        NodeBitMap visited = currentGraph.createNodeBitMap();
1067        Deque<Node> stack = new ArrayDeque<>();
1068        stack.add(startInstruction);
1069        visited.mark(startInstruction);
1070        List<LoopBeginNode> loopBegins = new ArrayList<>();
1071        while (!stack.isEmpty()) {
1072            Node next = stack.pop();
1073            assert visited.isMarked(next);
1074            if (next instanceof LoopBeginNode) {
1075                loopBegins.add((LoopBeginNode) next);
1076            }
1077            for (Node n : next.cfgSuccessors()) {
1078                if (visited.contains(n)) {
1079                    // Nothing to do.
1080                } else {
1081                    visited.mark(n);
1082                    stack.push(n);
1083                }
1084            }
1085        }
1086
1087        IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap = new IdentityHashMap<>();
1088        for (int i = loopBegins.size() - 1; i >= 0; --i) {
1089            LoopBeginNode loopBegin = loopBegins.get(i);
1090            insertLoopExits(currentGraph, loopBegin, innerLoopsMap);
1091        }
1092
1093        // Remove degenerated merges with only one predecessor.
1094        for (LoopBeginNode loopBegin : loopBegins) {
1095            Node pred = loopBegin.forwardEnd().predecessor();
1096            if (pred instanceof MergeNode) {
1097                MergeNode.removeMergeIfDegenerated((MergeNode) pred);
1098            }
1099        }
1100    }
1101
1102    private static void insertLoopExits(StructuredGraph currentGraph, LoopBeginNode loopBegin, IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap) {
1103        NodeBitMap visited = currentGraph.createNodeBitMap();
1104        Deque<Node> stack = new ArrayDeque<>();
1105        for (LoopEndNode loopEnd : loopBegin.loopEnds()) {
1106            stack.push(loopEnd);
1107            visited.mark(loopEnd);
1108        }
1109
1110        List<ControlSplitNode> controlSplits = new ArrayList<>();
1111        List<LoopBeginNode> innerLoopBegins = new ArrayList<>();
1112
1113        while (!stack.isEmpty()) {
1114            Node current = stack.pop();
1115            if (current == loopBegin) {
1116                continue;
1117            }
1118            for (Node pred : current.cfgPredecessors()) {
1119                if (!visited.isMarked(pred)) {
1120                    visited.mark(pred);
1121                    if (pred instanceof LoopExitNode) {
1122                        // Inner loop
1123                        LoopExitNode loopExitNode = (LoopExitNode) pred;
1124                        LoopBeginNode innerLoopBegin = loopExitNode.loopBegin();
1125                        if (!visited.isMarked(innerLoopBegin)) {
1126                            stack.push(innerLoopBegin);
1127                            visited.mark(innerLoopBegin);
1128                            innerLoopBegins.add(innerLoopBegin);
1129                        }
1130                    } else {
1131                        if (pred instanceof ControlSplitNode) {
1132                            ControlSplitNode controlSplitNode = (ControlSplitNode) pred;
1133                            controlSplits.add(controlSplitNode);
1134                        }
1135                        stack.push(pred);
1136                    }
1137                }
1138            }
1139        }
1140
1141        for (ControlSplitNode controlSplit : controlSplits) {
1142            for (Node succ : controlSplit.cfgSuccessors()) {
1143                if (!visited.isMarked(succ)) {
1144                    LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin));
1145                    FixedNode next = ((FixedWithNextNode) succ).next();
1146                    next.replaceAtPredecessor(loopExit);
1147                    loopExit.setNext(next);
1148                }
1149            }
1150        }
1151
1152        for (LoopBeginNode inner : innerLoopBegins) {
1153            addLoopExits(currentGraph, loopBegin, inner, innerLoopsMap, visited);
1154        }
1155
1156        innerLoopsMap.put(loopBegin, innerLoopBegins);
1157    }
1158
1159    private static void addLoopExits(StructuredGraph currentGraph, LoopBeginNode loopBegin, LoopBeginNode inner, IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap, NodeBitMap visited) {
1160        for (LoopExitNode exit : inner.loopExits()) {
1161            if (!visited.isMarked(exit)) {
1162                LoopExitNode newLoopExit = currentGraph.add(new LoopExitNode(loopBegin));
1163                FixedNode next = exit.next();
1164                next.replaceAtPredecessor(newLoopExit);
1165                newLoopExit.setNext(next);
1166            }
1167        }
1168
1169        for (LoopBeginNode innerInner : innerLoopsMap.get(inner)) {
1170            addLoopExits(currentGraph, loopBegin, innerInner, innerLoopsMap, visited);
1171        }
1172    }
1173
1174    /**
1175     * Removes unnecessary nodes from the graph after decoding.
1176     *
1177     * @param methodScope The current method.
1178     * @param start Marker for the begin of the current method in the graph.
1179     */
1180    protected void cleanupGraph(MethodScope methodScope, Graph.Mark start) {
1181        assert verifyEdges(methodScope);
1182    }
1183
1184    protected boolean verifyEdges(MethodScope methodScope) {
1185        for (Node node : methodScope.graph.getNodes()) {
1186            assert node.isAlive();
1187            node.acceptInputs((n, i) -> {
1188                assert i.isAlive();
1189                assert i.usages().contains(n);
1190            });
1191            node.acceptSuccessors((n, s) -> {
1192                assert s.isAlive();
1193                assert s.predecessor() == n;
1194            });
1195
1196            for (Node usage : node.usages()) {
1197                assert usage.isAlive();
1198                assert usage.inputs().contains(node);
1199            }
1200            if (node.predecessor() != null) {
1201                assert node.predecessor().isAlive();
1202                assert node.predecessor().successors().contains(node);
1203            }
1204        }
1205        return true;
1206    }
1207}