1 /*
   2  * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.nodes;
  24 
  25 import static org.graalvm.compiler.debug.GraalError.shouldNotReachHere;
  26 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
  27 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
  28 
  29 import java.util.ArrayDeque;
  30 import java.util.ArrayList;
  31 import java.util.Arrays;
  32 import java.util.BitSet;
  33 import java.util.Deque;
  34 import java.util.Iterator;
  35 import java.util.List;
  36 import java.util.Map;
  37 import java.util.SortedMap;
  38 import java.util.TreeMap;
  39 
  40 import org.graalvm.compiler.core.common.Fields;
  41 import org.graalvm.compiler.core.common.PermanentBailoutException;
  42 import org.graalvm.compiler.core.common.util.TypeReader;
  43 import org.graalvm.compiler.core.common.util.UnsafeArrayTypeReader;
  44 import org.graalvm.compiler.debug.DebugContext;
  45 import org.graalvm.compiler.debug.GraalError;
  46 import org.graalvm.compiler.graph.Edges;
  47 import org.graalvm.compiler.graph.Graph;
  48 import org.graalvm.compiler.graph.Node;
  49 import org.graalvm.compiler.graph.NodeBitMap;
  50 import org.graalvm.compiler.graph.NodeClass;
  51 import org.graalvm.compiler.graph.NodeInputList;
  52 import org.graalvm.compiler.graph.NodeList;
  53 import org.graalvm.compiler.graph.NodeSourcePosition;
  54 import org.graalvm.compiler.graph.NodeSuccessorList;
  55 import org.graalvm.compiler.graph.spi.Canonicalizable;
  56 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
  57 import org.graalvm.compiler.nodeinfo.InputType;
  58 import org.graalvm.compiler.nodeinfo.NodeInfo;
  59 import org.graalvm.compiler.nodes.GraphDecoder.MethodScope;
  60 import org.graalvm.compiler.nodes.GraphDecoder.ProxyPlaceholder;
  61 import org.graalvm.compiler.nodes.calc.FloatingNode;
  62 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
  63 import org.graalvm.compiler.nodes.graphbuilderconf.LoopExplosionPlugin.LoopExplosionKind;
  64 import org.graalvm.compiler.options.OptionValues;
  65 import org.graalvm.util.EconomicMap;
  66 import org.graalvm.util.EconomicSet;
  67 import org.graalvm.util.Equivalence;
  68 
  69 import jdk.vm.ci.code.Architecture;
  70 import jdk.vm.ci.meta.DeoptimizationAction;
  71 import jdk.vm.ci.meta.DeoptimizationReason;
  72 import jdk.vm.ci.meta.JavaConstant;
  73 import jdk.vm.ci.meta.JavaKind;
  74 import jdk.vm.ci.meta.PrimitiveConstant;
  75 import jdk.vm.ci.meta.ResolvedJavaType;
  76 
  77 /**
  78  * Decoder for {@link EncodedGraph encoded graphs} produced by {@link GraphEncoder}. Support for
  79  * loop explosion during decoding is built into this class, because it requires many interactions
  80  * with the decoding process. Subclasses can provide canonicalization and simplification of nodes
  81  * during decoding, as well as method inlining during decoding.
  82  */
  83 public class GraphDecoder {
  84 
  85     /** Decoding state maintained for each encoded graph. */
  86     protected class MethodScope {
  87         /** The loop that contains the call. Only non-null during method inlining. */
  88         public final LoopScope callerLoopScope;
  89         /**
  90          * Mark for nodes that were present before the decoding of this method started. Note that
  91          * nodes that were decoded after the mark can still be part of an outer method, since
  92          * floating nodes of outer methods are decoded lazily.
  93          */
  94         public final Graph.Mark methodStartMark;
  95         /** The encode graph that is decoded. */
  96         public final EncodedGraph encodedGraph;
  97         /** The highest node order id that a fixed node has in the EncodedGraph. */
  98         public final int maxFixedNodeOrderId;
  99         /** Access to the encoded graph. */
 100         public final TypeReader reader;
 101         /** The kind of loop explosion to be performed during decoding. */
 102         public final LoopExplosionKind loopExplosion;
 103 
 104         /** All return nodes encountered during decoding. */
 105         public final List<ControlSinkNode> returnAndUnwindNodes;
 106 
 107         /** All merges created during loop explosion. */
 108         public final EconomicSet<Node> loopExplosionMerges;
 109 
 110         /**
 111          * The start of explosion, and the merge point for when irreducible loops are detected. Only
 112          * used when {@link MethodScope#loopExplosion} is {@link LoopExplosionKind#MERGE_EXPLODE}.
 113          */
 114         public MergeNode loopExplosionHead;
 115 
 116         protected MethodScope(LoopScope callerLoopScope, StructuredGraph graph, EncodedGraph encodedGraph, LoopExplosionKind loopExplosion) {
 117             this.callerLoopScope = callerLoopScope;
 118             this.methodStartMark = graph.getMark();
 119             this.encodedGraph = encodedGraph;
 120             this.loopExplosion = loopExplosion;
 121             this.returnAndUnwindNodes = new ArrayList<>(2);
 122 
 123             if (encodedGraph != null) {
 124                 reader = UnsafeArrayTypeReader.create(encodedGraph.getEncoding(), encodedGraph.getStartOffset(), architecture.supportsUnalignedMemoryAccess());
 125                 maxFixedNodeOrderId = reader.getUVInt();
 126                 if (encodedGraph.nodeStartOffsets == null) {
 127                     int nodeCount = reader.getUVInt();
 128                     int[] nodeStartOffsets = new int[nodeCount];
 129                     for (int i = 0; i < nodeCount; i++) {
 130                         nodeStartOffsets[i] = encodedGraph.getStartOffset() - reader.getUVInt();
 131                     }
 132                     encodedGraph.nodeStartOffsets = nodeStartOffsets;
 133                 }
 134             } else {
 135                 reader = null;
 136                 maxFixedNodeOrderId = 0;
 137             }
 138 
 139             if (loopExplosion != LoopExplosionKind.NONE) {
 140                 loopExplosionMerges = EconomicSet.create(Equivalence.IDENTITY);
 141             } else {
 142                 loopExplosionMerges = null;
 143             }
 144         }
 145 
 146         public boolean isInlinedMethod() {
 147             return false;
 148         }
 149     }
 150 
 151     /** Decoding state maintained for each loop in the encoded graph. */
 152     protected static class LoopScope {
 153         public final MethodScope methodScope;
 154         public final LoopScope outer;
 155         public final int loopDepth;
 156         public final int loopIteration;
 157         /**
 158          * Upcoming loop iterations during loop explosions that have not been processed yet. Only
 159          * used when {@link MethodScope#loopExplosion} is not {@link LoopExplosionKind#NONE}.
 160          */
 161         public Deque<LoopScope> nextIterations;
 162         /**
 163          * Information about already processed loop iterations for state merging during loop
 164          * explosion. Only used when {@link MethodScope#loopExplosion} is
 165          * {@link LoopExplosionKind#MERGE_EXPLODE}.
 166          */
 167         public final EconomicMap<LoopExplosionState, LoopExplosionState> iterationStates;
 168         public final int loopBeginOrderId;
 169         /**
 170          * The worklist of fixed nodes to process. Since we already the correct processing order
 171          * from the orderId, we just set the orderId bit in the bitset when a node is ready for
 172          * processing. The lowest set bit is the next node to process.
 173          */
 174         public final BitSet nodesToProcess;
 175         /** Nodes that have been created, indexed by the orderId. */
 176         public final Node[] createdNodes;
 177         /**
 178          * Nodes that have been created in outer loop scopes and existed before starting to process
 179          * this loop, indexed by the orderId. Only used when {@link MethodScope#loopExplosion} is
 180          * not {@link LoopExplosionKind#NONE}.
 181          */
 182         public final Node[] initialCreatedNodes;
 183 
 184         protected LoopScope(MethodScope methodScope) {
 185             this.methodScope = methodScope;
 186             this.outer = null;
 187             this.nextIterations = methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN ? new ArrayDeque<>(2) : null;
 188             this.loopDepth = 0;
 189             this.loopIteration = 0;
 190             this.iterationStates = null;
 191             this.loopBeginOrderId = -1;
 192 
 193             int nodeCount = methodScope.encodedGraph.nodeStartOffsets.length;
 194             this.nodesToProcess = new BitSet(methodScope.maxFixedNodeOrderId);
 195             this.createdNodes = new Node[nodeCount];
 196             this.initialCreatedNodes = null;
 197         }
 198 
 199         protected LoopScope(MethodScope methodScope, LoopScope outer, int loopDepth, int loopIteration, int loopBeginOrderId, Node[] initialCreatedNodes, Node[] createdNodes,
 200                         Deque<LoopScope> nextIterations, EconomicMap<LoopExplosionState, LoopExplosionState> iterationStates) {
 201             this.methodScope = methodScope;
 202             this.outer = outer;
 203             this.loopDepth = loopDepth;
 204             this.loopIteration = loopIteration;
 205             this.nextIterations = nextIterations;
 206             this.iterationStates = iterationStates;
 207             this.loopBeginOrderId = loopBeginOrderId;
 208             this.nodesToProcess = new BitSet(methodScope.maxFixedNodeOrderId);
 209             this.initialCreatedNodes = initialCreatedNodes;
 210             this.createdNodes = createdNodes;
 211         }
 212 
 213         @Override
 214         public String toString() {
 215             return loopDepth + "," + loopIteration + (loopBeginOrderId == -1 ? "" : "#" + loopBeginOrderId);
 216         }
 217     }
 218 
 219     protected static class LoopExplosionState {
 220         public final FrameState state;
 221         public final MergeNode merge;
 222         public final int hashCode;
 223 
 224         protected LoopExplosionState(FrameState state, MergeNode merge) {
 225             this.state = state;
 226             this.merge = merge;
 227 
 228             int h = 0;
 229             for (ValueNode value : state.values()) {
 230                 if (value == null) {
 231                     h = h * 31 + 1234;
 232                 } else {
 233                     h = h * 31 + ProxyPlaceholder.unwrap(value).hashCode();
 234                 }
 235             }
 236             this.hashCode = h;
 237         }
 238 
 239         @Override
 240         public boolean equals(Object obj) {
 241             if (!(obj instanceof LoopExplosionState)) {
 242                 return false;
 243             }
 244 
 245             FrameState otherState = ((LoopExplosionState) obj).state;
 246             FrameState thisState = state;
 247             assert thisState.outerFrameState() == otherState.outerFrameState();
 248 
 249             Iterator<ValueNode> thisIter = thisState.values().iterator();
 250             Iterator<ValueNode> otherIter = otherState.values().iterator();
 251             while (thisIter.hasNext() && otherIter.hasNext()) {
 252                 ValueNode thisValue = ProxyPlaceholder.unwrap(thisIter.next());
 253                 ValueNode otherValue = ProxyPlaceholder.unwrap(otherIter.next());
 254                 if (thisValue != otherValue) {
 255                     return false;
 256                 }
 257             }
 258             return thisIter.hasNext() == otherIter.hasNext();
 259         }
 260 
 261         @Override
 262         public int hashCode() {
 263             return hashCode;
 264         }
 265     }
 266 
 267     /**
 268      * Additional information encoded for {@link Invoke} nodes to allow method inlining without
 269      * decoding the frame state and successors beforehand.
 270      */
 271     protected static class InvokeData {
 272         public final Invoke invoke;
 273         public final ResolvedJavaType contextType;
 274         public final int invokeOrderId;
 275         public final int callTargetOrderId;
 276         public final int stateAfterOrderId;
 277         public final int nextOrderId;
 278 
 279         public final int nextNextOrderId;
 280         public final int exceptionOrderId;
 281         public final int exceptionStateOrderId;
 282         public final int exceptionNextOrderId;
 283         public JavaConstant constantReceiver;
 284 
 285         protected InvokeData(Invoke invoke, ResolvedJavaType contextType, int invokeOrderId, int callTargetOrderId, int stateAfterOrderId, int nextOrderId, int nextNextOrderId, int exceptionOrderId,
 286                         int exceptionStateOrderId, int exceptionNextOrderId) {
 287             this.invoke = invoke;
 288             this.contextType = contextType;
 289             this.invokeOrderId = invokeOrderId;
 290             this.callTargetOrderId = callTargetOrderId;
 291             this.stateAfterOrderId = stateAfterOrderId;
 292             this.nextOrderId = nextOrderId;
 293             this.nextNextOrderId = nextNextOrderId;
 294             this.exceptionOrderId = exceptionOrderId;
 295             this.exceptionStateOrderId = exceptionStateOrderId;
 296             this.exceptionNextOrderId = exceptionNextOrderId;
 297         }
 298     }
 299 
 300     /**
 301      * A node that is created during {@link LoopExplosionKind#MERGE_EXPLODE loop explosion} that can
 302      * later be replaced by a ProxyNode if {@link LoopDetector loop detection} finds out that the
 303      * value is defined in the loop, but used outside the loop.
 304      */
 305     @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
 306     protected static final class ProxyPlaceholder extends FloatingNode implements Canonicalizable {
 307         public static final NodeClass<ProxyPlaceholder> TYPE = NodeClass.create(ProxyPlaceholder.class);
 308 
 309         @Input ValueNode value;
 310         @Input(InputType.Unchecked) Node proxyPoint;
 311 
 312         public ProxyPlaceholder(ValueNode value, MergeNode proxyPoint) {
 313             super(TYPE, value.stamp());
 314             this.value = value;
 315             this.proxyPoint = proxyPoint;
 316         }
 317 
 318         void setValue(ValueNode value) {
 319             updateUsages(this.value, value);
 320             this.value = value;
 321         }
 322 
 323         @Override
 324         public Node canonical(CanonicalizerTool tool) {
 325             if (tool.allUsagesAvailable()) {
 326                 /* The node is always unnecessary after graph decoding. */
 327                 return value;
 328             } else {
 329                 return this;
 330             }
 331         }
 332 
 333         public static ValueNode unwrap(ValueNode value) {
 334             ValueNode result = value;
 335             while (result instanceof ProxyPlaceholder) {
 336                 result = ((ProxyPlaceholder) result).value;
 337             }
 338             return result;
 339         }
 340     }
 341 
 342     protected final Architecture architecture;
 343     /** The target graph where decoded nodes are added to. */
 344     protected final StructuredGraph graph;
 345     protected final OptionValues options;
 346     protected final DebugContext debug;
 347 
 348     private final EconomicMap<NodeClass<?>, ArrayDeque<Node>> reusableFloatingNodes;
 349 
 350     public GraphDecoder(Architecture architecture, StructuredGraph graph) {
 351         this.architecture = architecture;
 352         this.graph = graph;
 353         this.options = graph.getOptions();
 354         this.debug = graph.getDebug();
 355         reusableFloatingNodes = EconomicMap.create(Equivalence.IDENTITY);
 356     }
 357 
 358     @SuppressWarnings("try")
 359     public final void decode(EncodedGraph encodedGraph) {
 360         try (DebugContext.Scope scope = debug.scope("GraphDecoder", graph)) {
 361             MethodScope methodScope = new MethodScope(null, graph, encodedGraph, LoopExplosionKind.NONE);
 362             decode(createInitialLoopScope(methodScope, null));
 363             cleanupGraph(methodScope);
 364             assert graph.verify();
 365         } catch (Throwable ex) {
 366             debug.handle(ex);
 367         }
 368     }
 369 
 370     protected final LoopScope createInitialLoopScope(MethodScope methodScope, FixedWithNextNode startNode) {
 371         LoopScope loopScope = new LoopScope(methodScope);
 372         FixedNode firstNode;
 373         if (startNode != null) {
 374             /*
 375              * The start node of a graph can be referenced as the guard for a GuardedNode. We
 376              * register the previous block node, so that such guards are correctly anchored when
 377              * doing inlining during graph decoding.
 378              */
 379             registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, AbstractBeginNode.prevBegin(startNode), false, false);
 380 
 381             firstNode = makeStubNode(methodScope, loopScope, GraphEncoder.FIRST_NODE_ORDER_ID);
 382             startNode.setNext(firstNode);
 383             loopScope.nodesToProcess.set(GraphEncoder.FIRST_NODE_ORDER_ID);
 384         } else {
 385             firstNode = graph.start();
 386             registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, firstNode, false, false);
 387             loopScope.nodesToProcess.set(GraphEncoder.START_NODE_ORDER_ID);
 388         }
 389         return loopScope;
 390     }
 391 
 392     protected final void decode(LoopScope initialLoopScope) {
 393         LoopScope loopScope = initialLoopScope;
 394         /* Process (inlined) methods. */
 395         while (loopScope != null) {
 396             MethodScope methodScope = loopScope.methodScope;
 397 
 398             /* Process loops of method. */
 399             while (loopScope != null) {
 400 
 401                 /* Process nodes of loop. */
 402                 while (!loopScope.nodesToProcess.isEmpty()) {
 403                     loopScope = processNextNode(methodScope, loopScope);
 404                     methodScope = loopScope.methodScope;
 405                     /*
 406                      * We can have entered a new loop, and we can have entered a new inlined method.
 407                      */
 408                 }
 409 
 410                 /* Finished with a loop. */
 411                 if (loopScope.nextIterations != null && !loopScope.nextIterations.isEmpty()) {
 412                     /* Loop explosion: process the loop iteration. */
 413                     assert loopScope.nextIterations.peekFirst().loopIteration == loopScope.loopIteration + 1;
 414                     loopScope = loopScope.nextIterations.removeFirst();
 415                 } else {
 416                     propagateCreatedNodes(loopScope);
 417                     loopScope = loopScope.outer;
 418                 }
 419             }
 420 
 421             /*
 422              * Finished with an inlined method. Perform end-of-method cleanup tasks.
 423              */
 424             if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
 425                 LoopDetector loopDetector = new LoopDetector(graph, methodScope);
 426                 loopDetector.run();
 427             }
 428             if (methodScope.isInlinedMethod()) {
 429                 finishInlining(methodScope);
 430             }
 431 
 432             /* continue with the caller */
 433             loopScope = methodScope.callerLoopScope;
 434         }
 435     }
 436 
 437     protected void finishInlining(@SuppressWarnings("unused") MethodScope inlineScope) {
 438     }
 439 
 440     private static void propagateCreatedNodes(LoopScope loopScope) {
 441         if (loopScope.outer == null || loopScope.createdNodes != loopScope.outer.createdNodes) {
 442             return;
 443         }
 444 
 445         /* Register nodes that were created while decoding the loop to the outside scope. */
 446         for (int i = 0; i < loopScope.createdNodes.length; i++) {
 447             if (loopScope.outer.createdNodes[i] == null) {
 448                 loopScope.outer.createdNodes[i] = loopScope.createdNodes[i];
 449             }
 450         }
 451     }
 452 
 453     protected LoopScope processNextNode(MethodScope methodScope, LoopScope loopScope) {
 454         int nodeOrderId = loopScope.nodesToProcess.nextSetBit(0);
 455         loopScope.nodesToProcess.clear(nodeOrderId);
 456 
 457         FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId);
 458         if (node.isDeleted()) {
 459             return loopScope;
 460         }
 461 
 462         if ((node instanceof MergeNode ||
 463                         (node instanceof LoopBeginNode && (methodScope.loopExplosion == LoopExplosionKind.FULL_UNROLL || methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE ||
 464                                         methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN))) &&
 465                         ((AbstractMergeNode) node).forwardEndCount() == 1) {
 466             AbstractMergeNode merge = (AbstractMergeNode) node;
 467             EndNode singleEnd = merge.forwardEndAt(0);
 468 
 469             /*
 470              * In some corner cases, the MergeNode already has PhiNodes. Since there is a single
 471              * EndNode, each PhiNode can only have one input, and we can replace the PhiNode with
 472              * this single input.
 473              */
 474             for (PhiNode phi : merge.phis()) {
 475                 assert phi.inputs().count() == 1 : "input count must match end count";
 476                 Node singlePhiInput = phi.inputs().first();
 477 
 478                 /*
 479                  * We do not have the orderID of the PhiNode anymore, so we need to search through
 480                  * the complete list of nodes to find a match.
 481                  */
 482                 for (int i = 0; i < loopScope.createdNodes.length; i++) {
 483                     if (loopScope.createdNodes[i] == phi) {
 484                         loopScope.createdNodes[i] = singlePhiInput;
 485                     }
 486                 }
 487 
 488                 phi.replaceAndDelete(singlePhiInput);
 489             }
 490 
 491             /* Nodes that would use this merge as the guard need to use the previous block. */
 492             registerNode(loopScope, nodeOrderId, AbstractBeginNode.prevBegin(singleEnd), true, false);
 493 
 494             FixedNode next = makeStubNode(methodScope, loopScope, nodeOrderId + GraphEncoder.BEGIN_NEXT_ORDER_ID_OFFSET);
 495             singleEnd.replaceAtPredecessor(next);
 496 
 497             merge.safeDelete();
 498             singleEnd.safeDelete();
 499             return loopScope;
 500         }
 501 
 502         LoopScope successorAddScope = loopScope;
 503         boolean updatePredecessors = true;
 504         if (node instanceof LoopExitNode) {
 505             if (methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN || (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE && loopScope.loopDepth > 1)) {
 506                 /*
 507                  * We do not want to merge loop exits of inner loops. Instead, we want to keep
 508                  * exploding the outer loop separately for every loop exit and then merge the outer
 509                  * loop. Therefore, we create a new LoopScope of the outer loop for every loop exit
 510                  * of the inner loop.
 511                  */
 512                 LoopScope outerScope = loopScope.outer;
 513                 int nextIterationNumber = outerScope.nextIterations.isEmpty() ? outerScope.loopIteration + 1 : outerScope.nextIterations.getLast().loopIteration + 1;
 514                 successorAddScope = new LoopScope(methodScope, outerScope.outer, outerScope.loopDepth, nextIterationNumber, outerScope.loopBeginOrderId, outerScope.initialCreatedNodes,
 515                                 Arrays.copyOf(loopScope.initialCreatedNodes, loopScope.initialCreatedNodes.length), outerScope.nextIterations, outerScope.iterationStates);
 516                 checkLoopExplosionIteration(methodScope, successorAddScope);
 517 
 518                 /*
 519                  * Nodes that are still unprocessed in the outer scope might be merge nodes that are
 520                  * also reachable from the new exploded scope. Clearing them ensures that we do not
 521                  * merge, but instead keep exploding.
 522                  */
 523                 for (int id = outerScope.nodesToProcess.nextSetBit(0); id >= 0; id = outerScope.nodesToProcess.nextSetBit(id + 1)) {
 524                     successorAddScope.createdNodes[id] = null;
 525                 }
 526 
 527                 outerScope.nextIterations.addLast(successorAddScope);
 528             } else {
 529                 successorAddScope = loopScope.outer;
 530             }
 531             updatePredecessors = methodScope.loopExplosion == LoopExplosionKind.NONE;
 532         }
 533 
 534         methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
 535         int typeId = methodScope.reader.getUVInt();
 536         assert node.getNodeClass() == methodScope.encodedGraph.getNodeClasses()[typeId];
 537         makeFixedNodeInputs(methodScope, loopScope, node);
 538         readProperties(methodScope, node);
 539         makeSuccessorStubs(methodScope, successorAddScope, node, updatePredecessors);
 540 
 541         LoopScope resultScope = loopScope;
 542         if (node instanceof LoopBeginNode) {
 543             if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
 544                 handleLoopExplosionBegin(methodScope, loopScope, (LoopBeginNode) node);
 545             }
 546 
 547         } else if (node instanceof LoopExitNode) {
 548             if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
 549                 handleLoopExplosionProxyNodes(methodScope, loopScope, successorAddScope, (LoopExitNode) node, nodeOrderId);
 550             } else {
 551                 handleProxyNodes(methodScope, loopScope, (LoopExitNode) node);
 552             }
 553 
 554         } else if (node instanceof MergeNode) {
 555             handleMergeNode(((MergeNode) node));
 556 
 557         } else if (node instanceof AbstractEndNode) {
 558             LoopScope phiInputScope = loopScope;
 559             LoopScope phiNodeScope = loopScope;
 560 
 561             if (methodScope.loopExplosion != LoopExplosionKind.NONE && node instanceof LoopEndNode) {
 562                 node = handleLoopExplosionEnd(methodScope, loopScope, (LoopEndNode) node);
 563                 phiNodeScope = loopScope.nextIterations.getLast();
 564             }
 565 
 566             int mergeOrderId = readOrderId(methodScope);
 567             AbstractMergeNode merge = (AbstractMergeNode) lookupNode(phiNodeScope, mergeOrderId);
 568             if (merge == null) {
 569                 merge = (AbstractMergeNode) makeStubNode(methodScope, phiNodeScope, mergeOrderId);
 570 
 571                 if (merge instanceof LoopBeginNode) {
 572                     assert phiNodeScope == phiInputScope && phiNodeScope == loopScope;
 573                     resultScope = new LoopScope(methodScope, loopScope, loopScope.loopDepth + 1, 0, mergeOrderId,
 574                                     methodScope.loopExplosion != LoopExplosionKind.NONE ? Arrays.copyOf(loopScope.createdNodes, loopScope.createdNodes.length) : null,
 575                                     methodScope.loopExplosion != LoopExplosionKind.NONE ? Arrays.copyOf(loopScope.createdNodes, loopScope.createdNodes.length) : loopScope.createdNodes, //
 576                                     methodScope.loopExplosion != LoopExplosionKind.NONE ? new ArrayDeque<>(2) : null, //
 577                                     methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE ? EconomicMap.create(Equivalence.DEFAULT) : null);
 578                     phiInputScope = resultScope;
 579                     phiNodeScope = resultScope;
 580 
 581                     if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
 582                         registerNode(loopScope, mergeOrderId, null, true, true);
 583                     }
 584                     loopScope.nodesToProcess.clear(mergeOrderId);
 585                     resultScope.nodesToProcess.set(mergeOrderId);
 586                 }
 587             }
 588 
 589             handlePhiFunctions(methodScope, phiInputScope, phiNodeScope, (AbstractEndNode) node, merge);
 590 
 591         } else if (node instanceof Invoke) {
 592             InvokeData invokeData = readInvokeData(methodScope, nodeOrderId, (Invoke) node);
 593             resultScope = handleInvoke(methodScope, loopScope, invokeData);
 594 
 595         } else if (node instanceof ReturnNode || node instanceof UnwindNode) {
 596             methodScope.returnAndUnwindNodes.add((ControlSinkNode) node);
 597         } else {
 598             handleFixedNode(methodScope, loopScope, nodeOrderId, node);
 599         }
 600 
 601         return resultScope;
 602     }
 603 
 604     protected InvokeData readInvokeData(MethodScope methodScope, int invokeOrderId, Invoke invoke) {
 605         ResolvedJavaType contextType = (ResolvedJavaType) readObject(methodScope);
 606         int callTargetOrderId = readOrderId(methodScope);
 607         int stateAfterOrderId = readOrderId(methodScope);
 608         int nextOrderId = readOrderId(methodScope);
 609 
 610         if (invoke instanceof InvokeWithExceptionNode) {
 611             int nextNextOrderId = readOrderId(methodScope);
 612             int exceptionOrderId = readOrderId(methodScope);
 613             int exceptionStateOrderId = readOrderId(methodScope);
 614             int exceptionNextOrderId = readOrderId(methodScope);
 615             return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, nextNextOrderId, exceptionOrderId, exceptionStateOrderId,
 616                             exceptionNextOrderId);
 617         } else {
 618             return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, -1, -1, -1, -1);
 619         }
 620     }
 621 
 622     /**
 623      * {@link Invoke} nodes do not have the {@link CallTargetNode}, {@link FrameState}, and
 624      * successors encoded. Instead, this information is provided separately to allow method inlining
 625      * without decoding and adding them to the graph upfront. For non-inlined methods, this method
 626      * restores the normal state. Subclasses can override it to perform method inlining.
 627      *
 628      * The return value is the loop scope where decoding should continue. When method inlining
 629      * should be performed, the returned loop scope must be a new loop scope for the inlined method.
 630      * Without inlining, the original loop scope must be returned.
 631      */
 632     protected LoopScope handleInvoke(MethodScope methodScope, LoopScope loopScope, InvokeData invokeData) {
 633         assert invokeData.invoke.callTarget() == null : "callTarget edge is ignored during decoding of Invoke";
 634         CallTargetNode callTarget = (CallTargetNode) ensureNodeCreated(methodScope, loopScope, invokeData.callTargetOrderId);
 635         appendInvoke(methodScope, loopScope, invokeData, callTarget);
 636         return loopScope;
 637     }
 638 
 639     protected void appendInvoke(MethodScope methodScope, LoopScope loopScope, InvokeData invokeData, CallTargetNode callTarget) {
 640         if (invokeData.invoke instanceof InvokeWithExceptionNode) {
 641             ((InvokeWithExceptionNode) invokeData.invoke).setCallTarget(callTarget);
 642         } else {
 643             ((InvokeNode) invokeData.invoke).setCallTarget(callTarget);
 644         }
 645 
 646         assert invokeData.invoke.stateAfter() == null && invokeData.invoke.stateDuring() == null : "FrameState edges are ignored during decoding of Invoke";
 647         invokeData.invoke.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, invokeData.stateAfterOrderId));
 648 
 649         invokeData.invoke.setNext(makeStubNode(methodScope, loopScope, invokeData.nextOrderId));
 650         if (invokeData.invoke instanceof InvokeWithExceptionNode) {
 651             ((InvokeWithExceptionNode) invokeData.invoke).setExceptionEdge((AbstractBeginNode) makeStubNode(methodScope, loopScope, invokeData.exceptionOrderId));
 652         }
 653     }
 654 
 655     /**
 656      * Hook for subclasses to perform simplifications for a non-loop-header control flow merge.
 657      *
 658      * @param merge The control flow merge.
 659      */
 660     protected void handleMergeNode(MergeNode merge) {
 661     }
 662 
 663     protected void handleLoopExplosionBegin(MethodScope methodScope, LoopScope loopScope, LoopBeginNode loopBegin) {
 664         checkLoopExplosionIteration(methodScope, loopScope);
 665 
 666         List<EndNode> predecessors = loopBegin.forwardEnds().snapshot();
 667         FixedNode successor = loopBegin.next();
 668         FrameState frameState = loopBegin.stateAfter();
 669 
 670         if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
 671             LoopExplosionState queryState = new LoopExplosionState(frameState, null);
 672             LoopExplosionState existingState = loopScope.iterationStates.get(queryState);
 673             if (existingState != null) {
 674                 loopBegin.replaceAtUsagesAndDelete(existingState.merge);
 675                 successor.safeDelete();
 676                 for (EndNode predecessor : predecessors) {
 677                     existingState.merge.addForwardEnd(predecessor);
 678                 }
 679                 return;
 680             }
 681         }
 682 
 683         MergeNode merge = graph.add(new MergeNode());
 684         methodScope.loopExplosionMerges.add(merge);
 685 
 686         if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
 687             if (loopScope.iterationStates.size() == 0 && loopScope.loopDepth == 1) {
 688                 if (methodScope.loopExplosionHead != null) {
 689                     throw new PermanentBailoutException("Graal implementation restriction: Method with %s loop explosion must not have more than one top-level loop", LoopExplosionKind.MERGE_EXPLODE);
 690                 }
 691                 methodScope.loopExplosionHead = merge;
 692             }
 693 
 694             List<ValueNode> newFrameStateValues = new ArrayList<>();
 695             for (ValueNode frameStateValue : frameState.values) {
 696                 if (frameStateValue == null || frameStateValue.isConstant() || !graph.isNew(methodScope.methodStartMark, frameStateValue)) {
 697                     newFrameStateValues.add(frameStateValue);
 698 
 699                 } else {
 700                     ProxyPlaceholder newFrameStateValue = graph.unique(new ProxyPlaceholder(frameStateValue, merge));
 701                     newFrameStateValues.add(newFrameStateValue);
 702 
 703                     /*
 704                      * We do not have the orderID of the value anymore, so we need to search through
 705                      * the complete list of nodes to find a match.
 706                      */
 707                     for (int i = 0; i < loopScope.createdNodes.length; i++) {
 708                         if (loopScope.createdNodes[i] == frameStateValue) {
 709                             loopScope.createdNodes[i] = newFrameStateValue;
 710                         }
 711                     }
 712 
 713                     if (loopScope.initialCreatedNodes != null) {
 714                         for (int i = 0; i < loopScope.initialCreatedNodes.length; i++) {
 715                             if (loopScope.initialCreatedNodes[i] == frameStateValue) {
 716                                 loopScope.initialCreatedNodes[i] = newFrameStateValue;
 717                             }
 718                         }
 719                     }
 720                 }
 721             }
 722 
 723             FrameState newFrameState = graph.add(new FrameState(frameState.outerFrameState(), frameState.getCode(), frameState.bci, newFrameStateValues, frameState.localsSize(),
 724                             frameState.stackSize(), frameState.rethrowException(), frameState.duringCall(), frameState.monitorIds(), frameState.virtualObjectMappings()));
 725 
 726             frameState.replaceAtUsagesAndDelete(newFrameState);
 727             frameState = newFrameState;
 728         }
 729 
 730         loopBegin.replaceAtUsagesAndDelete(merge);
 731         merge.setStateAfter(frameState);
 732         merge.setNext(successor);
 733         for (EndNode predecessor : predecessors) {
 734             merge.addForwardEnd(predecessor);
 735         }
 736 
 737         if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
 738             LoopExplosionState explosionState = new LoopExplosionState(frameState, merge);
 739             loopScope.iterationStates.put(explosionState, explosionState);
 740         }
 741     }
 742 
 743     /**
 744      * Hook for subclasses.
 745      *
 746      * @param methodScope The current method.
 747      * @param loopScope The current loop.
 748      */
 749     protected void checkLoopExplosionIteration(MethodScope methodScope, LoopScope loopScope) {
 750         throw shouldNotReachHere("when subclass uses loop explosion, it needs to implement this method");
 751     }
 752 
 753     protected FixedNode handleLoopExplosionEnd(MethodScope methodScope, LoopScope loopScope, LoopEndNode loopEnd) {
 754         EndNode replacementNode = graph.add(new EndNode());
 755         loopEnd.replaceAtPredecessor(replacementNode);
 756         loopEnd.safeDelete();
 757 
 758         assert methodScope.loopExplosion != LoopExplosionKind.NONE;
 759         if (methodScope.loopExplosion != LoopExplosionKind.FULL_UNROLL || loopScope.nextIterations.isEmpty()) {
 760             int nextIterationNumber = loopScope.nextIterations.isEmpty() ? loopScope.loopIteration + 1 : loopScope.nextIterations.getLast().loopIteration + 1;
 761             LoopScope nextIterationScope = new LoopScope(methodScope, loopScope.outer, loopScope.loopDepth, nextIterationNumber, loopScope.loopBeginOrderId, loopScope.initialCreatedNodes,
 762                             Arrays.copyOf(loopScope.initialCreatedNodes, loopScope.initialCreatedNodes.length), loopScope.nextIterations, loopScope.iterationStates);
 763             checkLoopExplosionIteration(methodScope, nextIterationScope);
 764             loopScope.nextIterations.addLast(nextIterationScope);
 765             registerNode(nextIterationScope, loopScope.loopBeginOrderId, null, true, true);
 766             makeStubNode(methodScope, nextIterationScope, loopScope.loopBeginOrderId);
 767         }
 768         return replacementNode;
 769     }
 770 
 771     /**
 772      * Hook for subclasses.
 773      *
 774      * @param methodScope The current method.
 775      * @param loopScope The current loop.
 776      * @param nodeOrderId The orderId of the node.
 777      * @param node The node to be simplified.
 778      */
 779     protected void handleFixedNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId, FixedNode node) {
 780     }
 781 
 782     protected void handleProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopExitNode loopExit) {
 783         assert loopExit.stateAfter() == null;
 784         int stateAfterOrderId = readOrderId(methodScope);
 785         loopExit.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, stateAfterOrderId));
 786 
 787         int numProxies = methodScope.reader.getUVInt();
 788         for (int i = 0; i < numProxies; i++) {
 789             int proxyOrderId = readOrderId(methodScope);
 790             ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId);
 791             /*
 792              * The ProxyNode transports a value from the loop to the outer scope. We therefore
 793              * register it in the outer scope.
 794              */
 795             if (loopScope.outer.createdNodes != loopScope.createdNodes) {
 796                 registerNode(loopScope.outer, proxyOrderId, proxy, false, false);
 797             }
 798         }
 799     }
 800 
 801     protected void handleLoopExplosionProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopScope outerScope, LoopExitNode loopExit, int loopExitOrderId) {
 802         assert loopExit.stateAfter() == null;
 803         int stateAfterOrderId = readOrderId(methodScope);
 804 
 805         BeginNode begin = graph.add(new BeginNode());
 806 
 807         FixedNode loopExitSuccessor = loopExit.next();
 808         loopExit.replaceAtPredecessor(begin);
 809 
 810         MergeNode loopExitPlaceholder = null;
 811         if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE && loopScope.loopDepth == 1) {
 812             /*
 813              * This exit might end up as a loop exit of a loop detected after partial evaluation. We
 814              * need to be able to create a FrameState and the necessary proxy nodes in this case.
 815              */
 816             loopExitPlaceholder = graph.add(new MergeNode());
 817             methodScope.loopExplosionMerges.add(loopExitPlaceholder);
 818 
 819             EndNode end = graph.add(new EndNode());
 820             begin.setNext(end);
 821             loopExitPlaceholder.addForwardEnd(end);
 822 
 823             begin = graph.add(new BeginNode());
 824             loopExitPlaceholder.setNext(begin);
 825         }
 826 
 827         /*
 828          * In the original graph, the loop exit is not a merge node. Multiple exploded loop
 829          * iterations now take the same loop exit, so we have to introduce a new merge node to
 830          * handle the merge.
 831          */
 832         MergeNode merge = null;
 833         Node existingExit = lookupNode(outerScope, loopExitOrderId);
 834         if (existingExit == null) {
 835             /* First loop iteration that exits. No merge necessary yet. */
 836             registerNode(outerScope, loopExitOrderId, begin, false, false);
 837             begin.setNext(loopExitSuccessor);
 838 
 839         } else if (existingExit instanceof BeginNode) {
 840             /* Second loop iteration that exits. Create the merge. */
 841             merge = graph.add(new MergeNode());
 842             registerNode(outerScope, loopExitOrderId, merge, true, false);
 843             /* Add the first iteration. */
 844             EndNode firstEnd = graph.add(new EndNode());
 845             ((BeginNode) existingExit).setNext(firstEnd);
 846             merge.addForwardEnd(firstEnd);
 847             merge.setNext(loopExitSuccessor);
 848 
 849         } else {
 850             /* Subsequent loop iteration. Merge already created. */
 851             merge = (MergeNode) existingExit;
 852         }
 853 
 854         if (merge != null) {
 855             EndNode end = graph.add(new EndNode());
 856             begin.setNext(end);
 857             merge.addForwardEnd(end);
 858         }
 859 
 860         /*
 861          * Possibly create phi nodes for the original proxy nodes that flow out of the loop. Note
 862          * that we definitely do not need a proxy node itself anymore, since the loop was exploded
 863          * and is no longer present.
 864          */
 865         int numProxies = methodScope.reader.getUVInt();
 866         boolean phiCreated = false;
 867         for (int i = 0; i < numProxies; i++) {
 868             int proxyOrderId = readOrderId(methodScope);
 869             ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId);
 870             ValueNode phiInput = proxy.value();
 871 
 872             if (loopExitPlaceholder != null) {
 873                 if (!phiInput.isConstant()) {
 874                     phiInput = graph.unique(new ProxyPlaceholder(phiInput, loopExitPlaceholder));
 875                 }
 876                 registerNode(loopScope, proxyOrderId, phiInput, true, false);
 877             }
 878 
 879             ValueNode replacement;
 880             ValueNode existing = (ValueNode) outerScope.createdNodes[proxyOrderId];
 881             if (existing == null || existing == phiInput) {
 882                 /*
 883                  * We are at the first loop exit, or the proxy carries the same value for all exits.
 884                  * We do not need a phi node yet.
 885                  */
 886                 registerNode(outerScope, proxyOrderId, phiInput, true, false);
 887                 replacement = phiInput;
 888 
 889             } else if (!merge.isPhiAtMerge(existing)) {
 890                 /* Now we have two different values, so we need to create a phi node. */
 891                 PhiNode phi;
 892                 if (proxy instanceof ValueProxyNode) {
 893                     phi = graph.addWithoutUnique(new ValuePhiNode(proxy.stamp(), merge));
 894                 } else if (proxy instanceof GuardProxyNode) {
 895                     phi = graph.addWithoutUnique(new GuardPhiNode(merge));
 896                 } else {
 897                     throw GraalError.shouldNotReachHere();
 898                 }
 899                 /* Add the inputs from all previous exits. */
 900                 for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) {
 901                     phi.addInput(existing);
 902                 }
 903                 /* Add the input from this exit. */
 904                 phi.addInput(phiInput);
 905                 registerNode(outerScope, proxyOrderId, phi, true, false);
 906                 replacement = phi;
 907                 phiCreated = true;
 908 
 909             } else {
 910                 /* Phi node has been created before, so just add the new input. */
 911                 PhiNode phi = (PhiNode) existing;
 912                 phi.addInput(phiInput);
 913                 replacement = phi;
 914             }
 915 
 916             proxy.replaceAtUsagesAndDelete(replacement);
 917         }
 918 
 919         if (loopExitPlaceholder != null) {
 920             registerNode(loopScope, stateAfterOrderId, null, true, true);
 921             loopExitPlaceholder.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, stateAfterOrderId));
 922         }
 923 
 924         if (merge != null && (merge.stateAfter() == null || phiCreated)) {
 925             FrameState oldStateAfter = merge.stateAfter();
 926             registerNode(outerScope, stateAfterOrderId, null, true, true);
 927             merge.setStateAfter((FrameState) ensureNodeCreated(methodScope, outerScope, stateAfterOrderId));
 928             if (oldStateAfter != null) {
 929                 oldStateAfter.safeDelete();
 930             }
 931         }
 932         loopExit.safeDelete();
 933         assert loopExitSuccessor.predecessor() == null;
 934         if (merge != null) {
 935             merge.getNodeClass().getSuccessorEdges().update(merge, null, loopExitSuccessor);
 936         } else {
 937             begin.getNodeClass().getSuccessorEdges().update(begin, null, loopExitSuccessor);
 938         }
 939     }
 940 
 941     protected void handlePhiFunctions(MethodScope methodScope, LoopScope phiInputScope, LoopScope phiNodeScope, AbstractEndNode end, AbstractMergeNode merge) {
 942 
 943         if (end instanceof LoopEndNode) {
 944             /*
 945              * Fix the loop end index and the number of loop ends. When we do canonicalization
 946              * during decoding, we can end up with fewer ends than the encoded graph had. And the
 947              * order of loop ends can be different.
 948              */
 949             int numEnds = ((LoopBeginNode) merge).loopEnds().count();
 950             ((LoopBeginNode) merge).nextEndIndex = numEnds;
 951             ((LoopEndNode) end).endIndex = numEnds - 1;
 952 
 953         } else {
 954             if (merge.ends == null) {
 955                 merge.ends = new NodeInputList<>(merge);
 956             }
 957             merge.addForwardEnd((EndNode) end);
 958         }
 959 
 960         /*
 961          * We create most phi functions lazily. Canonicalization and simplification during decoding
 962          * can lead to dead branches that are not decoded, so we might not need all phi functions
 963          * that the original graph contained. Since we process all predecessors before actually
 964          * processing the merge node, we have the final phi function when processing the merge node.
 965          * The only exception are loop headers of non-exploded loops: since backward branches are
 966          * not processed yet when processing the loop body, we need to create all phi functions
 967          * upfront.
 968          */
 969         boolean lazyPhi = allowLazyPhis() && (!(merge instanceof LoopBeginNode) || methodScope.loopExplosion != LoopExplosionKind.NONE);
 970         int numPhis = methodScope.reader.getUVInt();
 971         for (int i = 0; i < numPhis; i++) {
 972             int phiInputOrderId = readOrderId(methodScope);
 973             int phiNodeOrderId = readOrderId(methodScope);
 974 
 975             ValueNode phiInput = (ValueNode) ensureNodeCreated(methodScope, phiInputScope, phiInputOrderId);
 976 
 977             ValueNode existing = (ValueNode) lookupNode(phiNodeScope, phiNodeOrderId);
 978             if (lazyPhi && (existing == null || existing == phiInput)) {
 979                 /* Phi function not yet necessary. */
 980                 registerNode(phiNodeScope, phiNodeOrderId, phiInput, true, false);
 981 
 982             } else if (!merge.isPhiAtMerge(existing)) {
 983                 /*
 984                  * Phi function is necessary. Create it and fill it with existing inputs as well as
 985                  * the new input.
 986                  */
 987                 registerNode(phiNodeScope, phiNodeOrderId, null, true, true);
 988                 PhiNode phi = (PhiNode) ensureNodeCreated(methodScope, phiNodeScope, phiNodeOrderId);
 989 
 990                 phi.setMerge(merge);
 991                 for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) {
 992                     phi.addInput(existing);
 993                 }
 994                 phi.addInput(phiInput);
 995 
 996             } else {
 997                 /* Phi node has been created before, so just add the new input. */
 998                 PhiNode phi = (PhiNode) existing;
 999                 phi.addInput(phiInput);
1000             }
1001         }
1002     }
1003 
1004     protected boolean allowLazyPhis() {
1005         /* We need to exactly reproduce the encoded graph, including unnecessary phi functions. */
1006         return false;
1007     }
1008 
1009     protected void readProperties(MethodScope methodScope, Node node) {
1010         node.setNodeSourcePosition((NodeSourcePosition) readObject(methodScope));
1011         Fields fields = node.getNodeClass().getData();
1012         for (int pos = 0; pos < fields.getCount(); pos++) {
1013             if (fields.getType(pos).isPrimitive()) {
1014                 long primitive = methodScope.reader.getSV();
1015                 fields.setRawPrimitive(node, pos, primitive);
1016             } else {
1017                 Object value = readObject(methodScope);
1018                 fields.putObject(node, pos, value);
1019             }
1020         }
1021     }
1022 
1023     /**
1024      * Process the input edges of a node. Input nodes that have not yet been created must be
1025      * non-fixed nodes (because fixed nodes are processed in reverse postorder. Such non-fixed nodes
1026      * are created on demand (recursively since they can themselves reference not yet created
1027      * nodes).
1028      */
1029     protected void makeFixedNodeInputs(MethodScope methodScope, LoopScope loopScope, Node node) {
1030         Edges edges = node.getNodeClass().getInputEdges();
1031         for (int index = 0; index < edges.getDirectCount(); index++) {
1032             if (skipDirectEdge(node, edges, index)) {
1033                 continue;
1034             }
1035             int orderId = readOrderId(methodScope);
1036             Node value = ensureNodeCreated(methodScope, loopScope, orderId);
1037             edges.initializeNode(node, index, value);
1038             if (value != null && !value.isDeleted()) {
1039                 edges.update(node, null, value);
1040 
1041             }
1042         }
1043 
1044         if (node instanceof AbstractMergeNode) {
1045             /* The ends of merge nodes are filled manually when the ends are processed. */
1046             assert edges.getCount() - edges.getDirectCount() == 1 : "MergeNode has one variable size input (the ends)";
1047             assert Edges.getNodeList(node, edges.getOffsets(), edges.getDirectCount()) != null : "Input list must have been already created";
1048         } else {
1049             for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
1050                 int size = methodScope.reader.getSVInt();
1051                 if (size != -1) {
1052                     NodeList<Node> nodeList = new NodeInputList<>(node, size);
1053                     edges.initializeList(node, index, nodeList);
1054                     for (int idx = 0; idx < size; idx++) {
1055                         int orderId = readOrderId(methodScope);
1056                         Node value = ensureNodeCreated(methodScope, loopScope, orderId);
1057                         nodeList.initialize(idx, value);
1058                         if (value != null && !value.isDeleted()) {
1059                             edges.update(node, null, value);
1060                         }
1061                     }
1062                 }
1063             }
1064         }
1065     }
1066 
1067     protected void makeFloatingNodeInputs(MethodScope methodScope, LoopScope loopScope, Node node) {
1068         Edges edges = node.getNodeClass().getInputEdges();
1069         if (node instanceof PhiNode) {
1070             /*
1071              * The inputs of phi functions are filled manually when the end nodes are processed.
1072              * However, the values must not be null, so initialize them with an empty list.
1073              */
1074             assert edges.getDirectCount() == 1 : "PhiNode has one direct input (the MergeNode)";
1075             assert edges.getCount() - edges.getDirectCount() == 1 : "PhiNode has one variable size input (the values)";
1076             edges.initializeList(node, edges.getDirectCount(), new NodeInputList<>(node));
1077         } else {
1078             for (int index = 0; index < edges.getDirectCount(); index++) {
1079                 int orderId = readOrderId(methodScope);
1080                 Node value = ensureNodeCreated(methodScope, loopScope, orderId);
1081                 edges.initializeNode(node, index, value);
1082             }
1083             for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
1084                 int size = methodScope.reader.getSVInt();
1085                 if (size != -1) {
1086                     NodeList<Node> nodeList = new NodeInputList<>(node, size);
1087                     edges.initializeList(node, index, nodeList);
1088                     for (int idx = 0; idx < size; idx++) {
1089                         int orderId = readOrderId(methodScope);
1090                         Node value = ensureNodeCreated(methodScope, loopScope, orderId);
1091                         nodeList.initialize(idx, value);
1092                     }
1093                 }
1094             }
1095         }
1096     }
1097 
1098     protected Node ensureNodeCreated(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
1099         if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
1100             return null;
1101         }
1102         Node node = lookupNode(loopScope, nodeOrderId);
1103         if (node != null) {
1104             return node;
1105         }
1106 
1107         node = decodeFloatingNode(methodScope, loopScope, nodeOrderId);
1108         if (node instanceof ProxyNode || node instanceof PhiNode) {
1109             /*
1110              * We need these nodes as they were in the original graph, without any canonicalization
1111              * or value numbering.
1112              */
1113             node = graph.addWithoutUnique(node);
1114         } else {
1115             /* Allow subclasses to canonicalize and intercept nodes. */
1116             Node newNode = handleFloatingNodeBeforeAdd(methodScope, loopScope, node);
1117             if (newNode != node) {
1118                 releaseFloatingNode(node);
1119             }
1120 
1121             if (!newNode.isAlive()) {
1122                 newNode = addFloatingNode(methodScope, newNode);
1123             }
1124             node = handleFloatingNodeAfterAdd(methodScope, loopScope, newNode);
1125         }
1126         registerNode(loopScope, nodeOrderId, node, false, false);
1127         return node;
1128     }
1129 
1130     protected Node addFloatingNode(@SuppressWarnings("unused") MethodScope methodScope, Node node) {
1131         /*
1132          * We want to exactly reproduce the encoded graph. Even though nodes should be unique in the
1133          * encoded graph, this is not always guaranteed.
1134          */
1135         return graph.addWithoutUnique(node);
1136     }
1137 
1138     /**
1139      * Decodes a non-fixed node, but does not do any post-processing and does not register it.
1140      */
1141     protected Node decodeFloatingNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
1142         long readerByteIndex = methodScope.reader.getByteIndex();
1143 
1144         methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
1145         NodeClass<?> nodeClass = methodScope.encodedGraph.getNodeClasses()[methodScope.reader.getUVInt()];
1146         Node node = allocateFloatingNode(nodeClass);
1147         if (node instanceof FixedNode) {
1148             /*
1149              * This is a severe error that will lead to a corrupted graph, so it is better not to
1150              * continue decoding at all.
1151              */
1152             throw shouldNotReachHere("Not a floating node: " + node.getClass().getName());
1153         }
1154 
1155         /* Read the inputs of the node, possibly creating them recursively. */
1156         makeFloatingNodeInputs(methodScope, loopScope, node);
1157 
1158         /* Read the properties of the node. */
1159         readProperties(methodScope, node);
1160         /* There must not be any successors to read, since it is a non-fixed node. */
1161         assert node.getNodeClass().getEdges(Edges.Type.Successors).getCount() == 0;
1162 
1163         methodScope.reader.setByteIndex(readerByteIndex);
1164         return node;
1165     }
1166 
1167     private Node allocateFloatingNode(NodeClass<?> nodeClass) {
1168         ArrayDeque<? extends Node> cachedNodes = reusableFloatingNodes.get(nodeClass);
1169         if (cachedNodes != null) {
1170             Node node = cachedNodes.poll();
1171             if (node != null) {
1172                 return node;
1173             }
1174         }
1175         return nodeClass.allocateInstance();
1176     }
1177 
1178     private void releaseFloatingNode(Node node) {
1179         ArrayDeque<Node> cachedNodes = reusableFloatingNodes.get(node.getNodeClass());
1180         if (cachedNodes == null) {
1181             cachedNodes = new ArrayDeque<>(2);
1182             reusableFloatingNodes.put(node.getNodeClass(), cachedNodes);
1183         }
1184         cachedNodes.push(node);
1185     }
1186 
1187     /**
1188      * Hook for subclasses to process a non-fixed node before it is added to the graph.
1189      *
1190      * @param methodScope The current method.
1191      * @param loopScope The current loop.
1192      * @param node The node to be canonicalized.
1193      * @return The replacement for the node, or the node itself.
1194      */
1195     protected Node handleFloatingNodeBeforeAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
1196         return node;
1197     }
1198 
1199     /**
1200      * Hook for subclasses to process a non-fixed node after it is added to the graph.
1201      *
1202      * If this method replaces a node with another node, it must update its source position if the
1203      * original node has the source position set.
1204      *
1205      * @param methodScope The current method.
1206      * @param loopScope The current loop.
1207      * @param node The node to be canonicalized.
1208      * @return The replacement for the node, or the node itself.
1209      */
1210     protected Node handleFloatingNodeAfterAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
1211         return node;
1212     }
1213 
1214     /**
1215      * Process successor edges of a node. We create the successor nodes so that we can fill the
1216      * successor list, but no properties or edges are loaded yet. That is done when the successor is
1217      * on top of the worklist in {@link #processNextNode}.
1218      */
1219     protected void makeSuccessorStubs(MethodScope methodScope, LoopScope loopScope, Node node, boolean updatePredecessors) {
1220         Edges edges = node.getNodeClass().getSuccessorEdges();
1221         for (int index = 0; index < edges.getDirectCount(); index++) {
1222             if (skipDirectEdge(node, edges, index)) {
1223                 continue;
1224             }
1225             int orderId = readOrderId(methodScope);
1226             Node value = makeStubNode(methodScope, loopScope, orderId);
1227             edges.initializeNode(node, index, value);
1228             if (updatePredecessors && value != null) {
1229                 edges.update(node, null, value);
1230             }
1231         }
1232         for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
1233             int size = methodScope.reader.getSVInt();
1234             if (size != -1) {
1235                 NodeList<Node> nodeList = new NodeSuccessorList<>(node, size);
1236                 edges.initializeList(node, index, nodeList);
1237                 for (int idx = 0; idx < size; idx++) {
1238                     int orderId = readOrderId(methodScope);
1239                     Node value = makeStubNode(methodScope, loopScope, orderId);
1240                     nodeList.initialize(idx, value);
1241                     if (updatePredecessors && value != null) {
1242                         edges.update(node, null, value);
1243                     }
1244                 }
1245             }
1246         }
1247     }
1248 
1249     protected FixedNode makeStubNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
1250         if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
1251             return null;
1252         }
1253         FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId);
1254         if (node != null) {
1255             return node;
1256         }
1257 
1258         long readerByteIndex = methodScope.reader.getByteIndex();
1259         methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
1260         NodeClass<?> nodeClass = methodScope.encodedGraph.getNodeClasses()[methodScope.reader.getUVInt()];
1261         node = (FixedNode) graph.add(nodeClass.allocateInstance());
1262         /* Properties and edges are not filled yet, the node remains uninitialized. */
1263         methodScope.reader.setByteIndex(readerByteIndex);
1264 
1265         registerNode(loopScope, nodeOrderId, node, false, false);
1266         loopScope.nodesToProcess.set(nodeOrderId);
1267         return node;
1268     }
1269 
1270     protected static boolean skipDirectEdge(Node node, Edges edges, int index) {
1271         if (node instanceof Invoke) {
1272             assert node instanceof InvokeNode || node instanceof InvokeWithExceptionNode : "The only two Invoke node classes. Got " + node.getClass();
1273             if (edges.type() == Edges.Type.Successors) {
1274                 assert edges.getCount() == (node instanceof InvokeWithExceptionNode ? 2 : 1) : "InvokeNode has one successor (next); InvokeWithExceptionNode has two successors (next, exceptionEdge)";
1275                 return true;
1276             } else {
1277                 assert edges.type() == Edges.Type.Inputs;
1278                 if (edges.getType(index) == CallTargetNode.class) {
1279                     return true;
1280                 } else if (edges.getType(index) == FrameState.class) {
1281                     assert edges.get(node, index) == null || edges.get(node, index) == ((Invoke) node).stateAfter() : "Only stateAfter can be a FrameState during encoding";
1282                     return true;
1283                 }
1284             }
1285         } else if (node instanceof LoopExitNode && edges.type() == Edges.Type.Inputs && edges.getType(index) == FrameState.class) {
1286             /* The stateAfter of the loop exit is filled manually. */
1287             return true;
1288 
1289         }
1290         return false;
1291     }
1292 
1293     protected Node lookupNode(LoopScope loopScope, int nodeOrderId) {
1294         return loopScope.createdNodes[nodeOrderId];
1295     }
1296 
1297     protected void registerNode(LoopScope loopScope, int nodeOrderId, Node node, boolean allowOverwrite, boolean allowNull) {
1298         assert node == null || node.isAlive();
1299         assert allowNull || node != null;
1300         assert allowOverwrite || lookupNode(loopScope, nodeOrderId) == null;
1301         loopScope.createdNodes[nodeOrderId] = node;
1302     }
1303 
1304     protected int readOrderId(MethodScope methodScope) {
1305         return methodScope.reader.getUVInt();
1306     }
1307 
1308     protected Object readObject(MethodScope methodScope) {
1309         return methodScope.encodedGraph.getObjects()[methodScope.reader.getUVInt()];
1310     }
1311 
1312     /**
1313      * Removes unnecessary nodes from the graph after decoding.
1314      *
1315      * @param methodScope The current method.
1316      */
1317     protected void cleanupGraph(MethodScope methodScope) {
1318         assert verifyEdges();
1319     }
1320 
1321     protected boolean verifyEdges() {
1322         for (Node node : graph.getNodes()) {
1323             assert node.isAlive();
1324             for (Node i : node.inputs()) {
1325                 assert i.isAlive();
1326                 assert i.usages().contains(node);
1327             }
1328             for (Node s : node.successors()) {
1329                 assert s.isAlive();
1330                 assert s.predecessor() == node;
1331             }
1332 
1333             for (Node usage : node.usages()) {
1334                 assert usage.isAlive();
1335                 assert usage.inputs().contains(node) : node + " / " + usage + " / " + usage.inputs().count();
1336             }
1337             if (node.predecessor() != null) {
1338                 assert node.predecessor().isAlive();
1339                 assert node.predecessor().successors().contains(node);
1340             }
1341         }
1342         return true;
1343     }
1344 }
1345 
1346 class LoopDetector implements Runnable {
1347 
1348     /**
1349      * Information about loops before the actual loop nodes are inserted.
1350      */
1351     static class Loop {
1352         /**
1353          * The header, i.e., the target of backward branches.
1354          */
1355         MergeNode header;
1356         /**
1357          * The ends, i.e., the source of backward branches. The {@link EndNode#successors successor}
1358          * is the {@link #header loop header}.
1359          */
1360         List<EndNode> ends = new ArrayList<>(2);
1361         /**
1362          * Exits of the loop. The successor is a {@link MergeNode} marked in
1363          * {@link MethodScope#loopExplosionMerges}.
1364          */
1365         List<AbstractEndNode> exits = new ArrayList<>();
1366         /**
1367          * Set to true when the loop is irreducible, i.e., has multiple entries. See
1368          * {@link #handleIrreducibleLoop} for details on the handling.
1369          */
1370         boolean irreducible;
1371     }
1372 
1373     private final StructuredGraph graph;
1374     private final MethodScope methodScope;
1375 
1376     private Loop irreducibleLoopHandler;
1377     private IntegerSwitchNode irreducibleLoopSwitch;
1378 
1379     protected LoopDetector(StructuredGraph graph, MethodScope methodScope) {
1380         this.graph = graph;
1381         this.methodScope = methodScope;
1382     }
1383 
1384     @Override
1385     public void run() {
1386         DebugContext debug = graph.getDebug();
1387         debug.dump(DebugContext.DETAILED_LEVEL, graph, "Before loop detection");
1388 
1389         List<Loop> orderedLoops = findLoops();
1390         assert orderedLoops.get(orderedLoops.size() - 1) == irreducibleLoopHandler : "outermost loop must be the last element in the list";
1391 
1392         for (Loop loop : orderedLoops) {
1393             if (loop.ends.isEmpty()) {
1394                 assert loop == irreducibleLoopHandler;
1395                 continue;
1396             }
1397 
1398             /*
1399              * The algorithm to find loop exits requires that inner loops have already been
1400              * processed. Therefore, we need to iterate the loops in order (inner loops before outer
1401              * loops), and we cannot find the exits for all loops before we start inserting nodes.
1402              */
1403             findLoopExits(loop);
1404 
1405             if (loop.irreducible) {
1406                 handleIrreducibleLoop(loop);
1407             } else {
1408                 insertLoopNodes(loop);
1409             }
1410             debug.dump(DebugContext.DETAILED_LEVEL, graph, "After handling of loop %s", loop.header);
1411         }
1412 
1413         logIrreducibleLoops();
1414         debug.dump(DebugContext.DETAILED_LEVEL, graph, "After loop detection");
1415     }
1416 
1417     private List<Loop> findLoops() {
1418         /* Mapping from the loop header node to additional loop information. */
1419         EconomicMap<MergeNode, Loop> unorderedLoops = EconomicMap.create(Equivalence.IDENTITY);
1420         /* Loops in reverse order of, i.e., inner loops before outer loops. */
1421         List<Loop> orderedLoops = new ArrayList<>();
1422 
1423         /*
1424          * Ensure we have an outermost loop that we can use to eliminate irreducible loops. This
1425          * loop can remain empty (no ends), in which case it is ignored.
1426          */
1427         irreducibleLoopHandler = findOrCreateLoop(unorderedLoops, methodScope.loopExplosionHead);
1428 
1429         NodeBitMap visited = graph.createNodeBitMap();
1430         NodeBitMap active = graph.createNodeBitMap();
1431         Deque<Node> stack = new ArrayDeque<>();
1432         visited.mark(methodScope.loopExplosionHead);
1433         stack.push(methodScope.loopExplosionHead);
1434 
1435         while (!stack.isEmpty()) {
1436             Node current = stack.peek();
1437             assert visited.isMarked(current);
1438 
1439             if (active.isMarked(current)) {
1440                 /* We are back-tracking, i.e., all successor nodes have been processed. */
1441                 stack.pop();
1442                 active.clear(current);
1443 
1444                 if (current instanceof MergeNode) {
1445                     Loop loop = unorderedLoops.get((MergeNode) current);
1446                     if (loop != null) {
1447                         /*
1448                          * Since nodes are popped in reverse order that they were pushed, we add
1449                          * inner loops before outer loops here.
1450                          */
1451                         assert !orderedLoops.contains(loop);
1452                         orderedLoops.add(loop);
1453                     }
1454                 }
1455 
1456             } else {
1457                 /*
1458                  * Process the node. Note that we do not remove the node from the stack, i.e., we
1459                  * will peek it again. But the next time the node is marked as active, so we do not
1460                  * execute this code again.
1461                  */
1462                 active.mark(current);
1463                 for (Node successor : current.cfgSuccessors()) {
1464                     if (active.isMarked(successor)) {
1465                         /* Detected a cycle, i.e., a backward branch of a loop. */
1466                         Loop loop = findOrCreateLoop(unorderedLoops, (MergeNode) successor);
1467                         assert !loop.ends.contains(current);
1468                         loop.ends.add((EndNode) current);
1469 
1470                     } else if (visited.isMarked(successor)) {
1471                         /* Forward merge into a branch we are already exploring. */
1472 
1473                     } else {
1474                         /* Forward branch to a node we have not seen yet. */
1475                         visited.mark(successor);
1476                         stack.push(successor);
1477                     }
1478                 }
1479             }
1480         }
1481         return orderedLoops;
1482     }
1483 
1484     private Loop findOrCreateLoop(EconomicMap<MergeNode, Loop> unorderedLoops, MergeNode loopHeader) {
1485         assert methodScope.loopExplosionMerges.contains(loopHeader) : loopHeader;
1486         Loop loop = unorderedLoops.get(loopHeader);
1487         if (loop == null) {
1488             loop = new Loop();
1489             loop.header = loopHeader;
1490             unorderedLoops.put(loopHeader, loop);
1491         }
1492         return loop;
1493     }
1494 
1495     private void findLoopExits(Loop loop) {
1496         /*
1497          * Backward marking of loop nodes: Starting with the known loop ends, we mark all nodes that
1498          * are reachable until we hit the loop begin. All successors of loop nodes that are not
1499          * marked as loop nodes themselves are exits of the loop. We mark all successors, and then
1500          * subtract the loop nodes, to find the exits.
1501          */
1502 
1503         List<Node> possibleExits = new ArrayList<>();
1504         NodeBitMap visited = graph.createNodeBitMap();
1505         Deque<Node> stack = new ArrayDeque<>();
1506         for (EndNode loopEnd : loop.ends) {
1507             stack.push(loopEnd);
1508             visited.mark(loopEnd);
1509         }
1510 
1511         while (!stack.isEmpty()) {
1512             Node current = stack.pop();
1513             if (current == loop.header) {
1514                 continue;
1515             }
1516             if (!graph.isNew(methodScope.methodStartMark, current)) {
1517                 /*
1518                  * The current node is before the method that contains the exploded loop. The loop
1519                  * must have a second entry point, i.e., it is an irreducible loop.
1520                  */
1521                 loop.irreducible = true;
1522                 return;
1523             }
1524 
1525             for (Node predecessor : current.cfgPredecessors()) {
1526                 if (predecessor instanceof LoopExitNode) {
1527                     /*
1528                      * Inner loop. We do not need to mark every node of it, instead we just continue
1529                      * marking at the loop header.
1530                      */
1531                     LoopBeginNode innerLoopBegin = ((LoopExitNode) predecessor).loopBegin();
1532                     if (!visited.isMarked(innerLoopBegin)) {
1533                         stack.push(innerLoopBegin);
1534                         visited.mark(innerLoopBegin);
1535 
1536                         /*
1537                          * All loop exits of the inner loop possibly need a LoopExit of our loop.
1538                          * Because we are processing inner loops first, we are guaranteed to already
1539                          * have all exits of the inner loop.
1540                          */
1541                         for (LoopExitNode exit : innerLoopBegin.loopExits()) {
1542                             possibleExits.add(exit);
1543                         }
1544                     }
1545 
1546                 } else if (!visited.isMarked(predecessor)) {
1547                     stack.push(predecessor);
1548                     visited.mark(predecessor);
1549 
1550                     if (predecessor instanceof ControlSplitNode) {
1551                         for (Node succ : predecessor.cfgSuccessors()) {
1552                             /*
1553                              * We would not need to mark the current node, and would not need to
1554                              * mark visited nodes. But it is easier to just mark everything, since
1555                              * we subtract all visited nodes in the end anyway. Note that at this
1556                              * point we do not have the complete visited information, so we would
1557                              * always mark too many possible exits.
1558                              */
1559                             possibleExits.add(succ);
1560                         }
1561                     }
1562                 }
1563             }
1564         }
1565 
1566         /*
1567          * Now we know all the actual loop exits. Ideally, we would insert LoopExit nodes for them.
1568          * However, a LoopExit needs a valid FrameState that captures the state at the point where
1569          * we exit the loop. During graph decoding, we create a FrameState for every exploded loop
1570          * iteration. We need to do a forward marking until we hit the next such point. This puts
1571          * some nodes into the loop that are actually not part of the loop.
1572          *
1573          * In some cases, we did not create a FrameState during graph decoding: when there was no
1574          * LoopExit in the original loop that we exploded. This happens for code paths that lead
1575          * immediately to a DeoptimizeNode.
1576          *
1577          * Both cases mimic the behavior of the BytecodeParser, which also puts more nodes than
1578          * necessary into a loop because it computes loop information based on bytecodes, before the
1579          * actual parsing.
1580          */
1581         for (Node succ : possibleExits) {
1582             if (!visited.contains(succ)) {
1583                 stack.push(succ);
1584                 visited.mark(succ);
1585                 assert !methodScope.loopExplosionMerges.contains(succ);
1586             }
1587         }
1588 
1589         while (!stack.isEmpty()) {
1590             Node current = stack.pop();
1591             assert visited.isMarked(current);
1592             assert current instanceof ControlSinkNode || current instanceof LoopEndNode || current.cfgSuccessors().iterator().hasNext() : "Must not reach a node that has not been decoded yet";
1593 
1594             for (Node successor : current.cfgSuccessors()) {
1595                 if (visited.isMarked(successor)) {
1596                     /* Already processed this successor. */
1597 
1598                 } else if (methodScope.loopExplosionMerges.contains(successor)) {
1599                     /*
1600                      * We have a FrameState for the successor. The LoopExit will be inserted between
1601                      * the current node and the successor node. Since the successor node is a
1602                      * MergeNode, the current node mus be a AbstractEndNode with only that MergeNode
1603                      * as the successor.
1604                      */
1605                     assert successor instanceof MergeNode;
1606                     assert !loop.exits.contains(current);
1607                     loop.exits.add((AbstractEndNode) current);
1608 
1609                 } else {
1610                     /* Node we have not seen yet. */
1611                     visited.mark(successor);
1612                     stack.push(successor);
1613                 }
1614             }
1615         }
1616     }
1617 
1618     private void insertLoopNodes(Loop loop) {
1619         MergeNode merge = loop.header;
1620         FrameState stateAfter = merge.stateAfter().duplicate();
1621         FixedNode afterMerge = merge.next();
1622         merge.setNext(null);
1623         EndNode preLoopEnd = graph.add(new EndNode());
1624         LoopBeginNode loopBegin = graph.add(new LoopBeginNode());
1625 
1626         merge.setNext(preLoopEnd);
1627         /* Add the single non-loop predecessor of the loop header. */
1628         loopBegin.addForwardEnd(preLoopEnd);
1629         loopBegin.setNext(afterMerge);
1630         loopBegin.setStateAfter(stateAfter);
1631 
1632         /*
1633          * Phi functions of the original merge need to be split: inputs that come from forward edges
1634          * remain with the original phi function; inputs that come from backward edges are added to
1635          * new phi functions.
1636          */
1637         List<PhiNode> mergePhis = merge.phis().snapshot();
1638         List<PhiNode> loopBeginPhis = new ArrayList<>(mergePhis.size());
1639         for (int i = 0; i < mergePhis.size(); i++) {
1640             PhiNode mergePhi = mergePhis.get(i);
1641             PhiNode loopBeginPhi = graph.addWithoutUnique(new ValuePhiNode(mergePhi.stamp(), loopBegin));
1642             mergePhi.replaceAtUsages(loopBeginPhi);
1643             /*
1644              * The first input of the new phi function is the original phi function, for the one
1645              * forward edge of the LoopBeginNode.
1646              */
1647             loopBeginPhi.addInput(mergePhi);
1648             loopBeginPhis.add(loopBeginPhi);
1649         }
1650 
1651         for (EndNode endNode : loop.ends) {
1652             for (int i = 0; i < mergePhis.size(); i++) {
1653                 PhiNode mergePhi = mergePhis.get(i);
1654                 PhiNode loopBeginPhi = loopBeginPhis.get(i);
1655                 loopBeginPhi.addInput(mergePhi.valueAt(endNode));
1656             }
1657 
1658             merge.removeEnd(endNode);
1659             LoopEndNode loopEnd = graph.add(new LoopEndNode(loopBegin));
1660             endNode.replaceAndDelete(loopEnd);
1661         }
1662 
1663         /*
1664          * Insert the LoopExit nodes (the easy part) and compute the FrameState for the new exits
1665          * (the difficult part).
1666          */
1667         for (AbstractEndNode exit : loop.exits) {
1668             AbstractMergeNode loopExplosionMerge = exit.merge();
1669             assert methodScope.loopExplosionMerges.contains(loopExplosionMerge);
1670 
1671             LoopExitNode loopExit = graph.add(new LoopExitNode(loopBegin));
1672             exit.replaceAtPredecessor(loopExit);
1673             loopExit.setNext(exit);
1674             assignLoopExitState(loopExit, loopExplosionMerge, exit);
1675         }
1676     }
1677 
1678     /**
1679      * During graph decoding, we create a FrameState for every exploded loop iteration. This is
1680      * mostly the state that we want, we only need to tweak it a little bit: we need to insert the
1681      * appropriate ProxyNodes for all values that are created inside the loop and that flow out of
1682      * the loop.
1683      */
1684     private void assignLoopExitState(LoopExitNode loopExit, AbstractMergeNode loopExplosionMerge, AbstractEndNode loopExplosionEnd) {
1685         FrameState oldState = loopExplosionMerge.stateAfter();
1686 
1687         /* Collect all nodes that are in the FrameState at the LoopBegin. */
1688         EconomicSet<Node> loopBeginValues = EconomicSet.create(Equivalence.IDENTITY);
1689         for (FrameState state = loopExit.loopBegin().stateAfter(); state != null; state = state.outerFrameState()) {
1690             for (ValueNode value : state.values()) {
1691                 if (value != null && !value.isConstant() && !loopExit.loopBegin().isPhiAtMerge(value)) {
1692                     loopBeginValues.add(ProxyPlaceholder.unwrap(value));
1693                 }
1694             }
1695         }
1696 
1697         List<ValueNode> newValues = new ArrayList<>(oldState.values().size());
1698         for (ValueNode v : oldState.values()) {
1699             ValueNode value = v;
1700             ValueNode realValue = ProxyPlaceholder.unwrap(value);
1701 
1702             /*
1703              * The LoopExit is inserted before the existing merge, i.e., separately for every branch
1704              * that leads to the merge. So for phi functions of the merge, we need to take the input
1705              * that corresponds to our branch.
1706              */
1707             if (realValue instanceof PhiNode && loopExplosionMerge.isPhiAtMerge(realValue)) {
1708                 value = ((PhiNode) realValue).valueAt(loopExplosionEnd);
1709                 realValue = ProxyPlaceholder.unwrap(value);
1710             }
1711 
1712             if (realValue == null || realValue.isConstant() || loopBeginValues.contains(realValue) || !graph.isNew(methodScope.methodStartMark, realValue)) {
1713                 newValues.add(realValue);
1714             } else {
1715                 /*
1716                  * The node is not in the FrameState of the LoopBegin, i.e., it is a value computed
1717                  * inside the loop.
1718                  */
1719                 GraalError.guarantee(value instanceof ProxyPlaceholder && ((ProxyPlaceholder) value).proxyPoint == loopExplosionMerge,
1720                                 "Value flowing out of loop, but we are not prepared to insert a ProxyNode");
1721 
1722                 ProxyPlaceholder proxyPlaceholder = (ProxyPlaceholder) value;
1723                 ValueProxyNode proxy = ProxyNode.forValue(proxyPlaceholder.value, loopExit, graph);
1724                 proxyPlaceholder.setValue(proxy);
1725                 newValues.add(proxy);
1726             }
1727         }
1728 
1729         FrameState newState = new FrameState(oldState.outerFrameState(), oldState.getCode(), oldState.bci, newValues, oldState.localsSize(), oldState.stackSize(), oldState.rethrowException(),
1730                         oldState.duringCall(), oldState.monitorIds(), oldState.virtualObjectMappings());
1731 
1732         assert loopExit.stateAfter() == null;
1733         loopExit.setStateAfter(graph.add(newState));
1734     }
1735 
1736     /**
1737      * Graal does not support irreducible loops (loops with more than one entry point). There are
1738      * two ways to make them reducible: 1) duplicate nodes (peel a loop iteration starting at the
1739      * second entry point until we reach the first entry point), or 2) insert a big outer loop
1740      * covering the whole method and build a state machine for the different loop entry points.
1741      * Since node duplication can lead to an exponential explosion of nodes in the worst case, we
1742      * use the second approach.
1743      *
1744      * We already did some preparations to insert a big outer loop:
1745      * {@link MethodScope#loopExplosionHead} is the loop header for the outer loop, and we ensured
1746      * that we have a {@link Loop} data object for it in {@link #irreducibleLoopHandler}.
1747      *
1748      * Now we need to insert the state machine. We have several implementation restrictions to make
1749      * that efficient:
1750      * <ul>
1751      * <li>There must be only one loop variable, i.e., one value that is different in the
1752      * {@link FrameState} of the different loop headers.</li>
1753      * <li>The loop variable must use the primitive {@code int} type, because Graal only has a
1754      * {@link IntegerSwitchNode switch node} for {@code int}.</li>
1755      * <li>The values of the loop variable that are merged are {@link PrimitiveConstant compile time
1756      * constants}.</li>
1757      * </ul>
1758      */
1759     private void handleIrreducibleLoop(Loop loop) {
1760         assert loop != irreducibleLoopHandler;
1761 
1762         FrameState loopState = loop.header.stateAfter();
1763         FrameState explosionHeadState = irreducibleLoopHandler.header.stateAfter();
1764         assert loopState.outerFrameState() == explosionHeadState.outerFrameState();
1765         NodeInputList<ValueNode> loopValues = loopState.values();
1766         NodeInputList<ValueNode> explosionHeadValues = explosionHeadState.values();
1767         assert loopValues.size() == explosionHeadValues.size();
1768 
1769         /*
1770          * Find the loop variable, and the value of the loop variable for our loop and the outermost
1771          * loop. There must be exactly one loop variable.
1772          */
1773         int loopVariableIndex = -1;
1774         ValueNode loopValue = null;
1775         ValueNode explosionHeadValue = null;
1776         for (int i = 0; i < loopValues.size(); i++) {
1777             ValueNode curLoopValue = loopValues.get(i);
1778             ValueNode curExplosionHeadValue = explosionHeadValues.get(i);
1779 
1780             if (curLoopValue != curExplosionHeadValue) {
1781                 if (loopVariableIndex != -1) {
1782                     throw bailout("must have only one variable that is changed in loop. " + loopValue + " != " + explosionHeadValue + " and " + curLoopValue + " != " + curExplosionHeadValue);
1783                 }
1784 
1785                 loopVariableIndex = i;
1786                 loopValue = curLoopValue;
1787                 explosionHeadValue = curExplosionHeadValue;
1788             }
1789         }
1790         assert loopVariableIndex != -1;
1791 
1792         ValuePhiNode loopVariablePhi;
1793         SortedMap<Integer, AbstractBeginNode> dispatchTable = new TreeMap<>();
1794         AbstractBeginNode unreachableDefaultSuccessor;
1795         if (irreducibleLoopSwitch == null) {
1796             /*
1797              * This is the first irreducible loop. We need to build the initial state machine
1798              * (dispatch for the loop header of the outermost loop).
1799              */
1800             assert !irreducibleLoopHandler.header.isPhiAtMerge(explosionHeadValue);
1801             assert irreducibleLoopHandler.header.phis().isEmpty();
1802 
1803             /* The new phi function for the loop variable. */
1804             loopVariablePhi = graph.addWithoutUnique(new ValuePhiNode(explosionHeadValue.stamp().unrestricted(), irreducibleLoopHandler.header));
1805             for (int i = 0; i < irreducibleLoopHandler.header.phiPredecessorCount(); i++) {
1806                 loopVariablePhi.addInput(explosionHeadValue);
1807             }
1808 
1809             /*
1810              * Build the new FrameState for the loop header. There is only once change in comparison
1811              * to the old FrameState: the loop variable is replaced with the phi function.
1812              */
1813             FrameState oldFrameState = explosionHeadState;
1814             List<ValueNode> newFrameStateValues = new ArrayList<>(explosionHeadValues.size());
1815             for (int i = 0; i < explosionHeadValues.size(); i++) {
1816                 if (i == loopVariableIndex) {
1817                     newFrameStateValues.add(loopVariablePhi);
1818                 } else {
1819                     newFrameStateValues.add(explosionHeadValues.get(i));
1820                 }
1821             }
1822 
1823             FrameState newFrameState = graph.add(
1824                             new FrameState(oldFrameState.outerFrameState(), oldFrameState.getCode(), oldFrameState.bci, newFrameStateValues, oldFrameState.localsSize(),
1825                                             oldFrameState.stackSize(), oldFrameState.rethrowException(), oldFrameState.duringCall(), oldFrameState.monitorIds(),
1826                                             oldFrameState.virtualObjectMappings()));
1827             oldFrameState.replaceAtUsages(newFrameState);
1828 
1829             /*
1830              * Disconnect the outermost loop header from its loop body, so that we can later on
1831              * insert the switch node. Collect dispatch information for the outermost loop.
1832              */
1833             FixedNode handlerNext = irreducibleLoopHandler.header.next();
1834             irreducibleLoopHandler.header.setNext(null);
1835             BeginNode handlerBegin = graph.add(new BeginNode());
1836             handlerBegin.setNext(handlerNext);
1837             dispatchTable.put(asInt(explosionHeadValue), handlerBegin);
1838 
1839             /*
1840              * We know that there will always be a matching key in the switch. But Graal always
1841              * wants a default successor, so we build a dummy block that just deoptimizes.
1842              */
1843             unreachableDefaultSuccessor = graph.add(new BeginNode());
1844             DeoptimizeNode deopt = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.UnreachedCode));
1845             unreachableDefaultSuccessor.setNext(deopt);
1846 
1847         } else {
1848             /*
1849              * This is the second or a subsequent irreducible loop, i.e., we already inserted a
1850              * switch node before. We re-create the dispatch state machine of that switch, so that
1851              * we can extend it with one more branch.
1852              */
1853             assert irreducibleLoopHandler.header.isPhiAtMerge(explosionHeadValue);
1854             assert irreducibleLoopHandler.header.phis().count() == 1 && irreducibleLoopHandler.header.phis().first() == explosionHeadValue;
1855             assert irreducibleLoopSwitch.value() == explosionHeadValue;
1856 
1857             /* We can modify the phi function used by the old switch node. */
1858             loopVariablePhi = (ValuePhiNode) explosionHeadValue;
1859 
1860             /*
1861              * We cannot modify the old switch node. Insert all information from the old switch node
1862              * into our temporary data structures for the new, larger, switch node.
1863              */
1864             for (int i = 0; i < irreducibleLoopSwitch.keyCount(); i++) {
1865                 int key = irreducibleLoopSwitch.keyAt(i).asInt();
1866                 dispatchTable.put(key, irreducibleLoopSwitch.successorAtKey(key));
1867             }
1868             unreachableDefaultSuccessor = irreducibleLoopSwitch.defaultSuccessor();
1869 
1870             /* Unlink and delete the old switch node, we do not need it anymore. */
1871             assert irreducibleLoopHandler.header.next() == irreducibleLoopSwitch;
1872             irreducibleLoopHandler.header.setNext(null);
1873             irreducibleLoopSwitch.clearSuccessors();
1874             irreducibleLoopSwitch.safeDelete();
1875         }
1876 
1877         /* Insert our loop into the dispatch state machine. */
1878         assert loop.header.phis().isEmpty();
1879         BeginNode dispatchBegin = graph.add(new BeginNode());
1880         EndNode dispatchEnd = graph.add(new EndNode());
1881         dispatchBegin.setNext(dispatchEnd);
1882         loop.header.addForwardEnd(dispatchEnd);
1883         int intLoopValue = asInt(loopValue);
1884         assert !dispatchTable.containsKey(intLoopValue);
1885         dispatchTable.put(intLoopValue, dispatchBegin);
1886 
1887         /* Disconnect the ends of our loop and re-connect them to the outermost loop header. */
1888         for (EndNode end : loop.ends) {
1889             loop.header.removeEnd(end);
1890             irreducibleLoopHandler.ends.add(end);
1891             irreducibleLoopHandler.header.addForwardEnd(end);
1892             loopVariablePhi.addInput(loopValue);
1893         }
1894 
1895         /* Build and insert the switch node. */
1896         irreducibleLoopSwitch = graph.add(createSwitch(loopVariablePhi, dispatchTable, unreachableDefaultSuccessor));
1897         irreducibleLoopHandler.header.setNext(irreducibleLoopSwitch);
1898     }
1899 
1900     private static int asInt(ValueNode node) {
1901         if (!node.isConstant() || node.asJavaConstant().getJavaKind() != JavaKind.Int) {
1902             throw bailout("must have a loop variable of type int. " + node);
1903         }
1904         return node.asJavaConstant().asInt();
1905     }
1906 
1907     private static RuntimeException bailout(String msg) {
1908         throw new PermanentBailoutException("Graal implementation restriction: Method with %s loop explosion %s", LoopExplosionKind.MERGE_EXPLODE, msg);
1909     }
1910 
1911     private static IntegerSwitchNode createSwitch(ValuePhiNode switchedValue, SortedMap<Integer, AbstractBeginNode> dispatchTable, AbstractBeginNode defaultSuccessor) {
1912         int numKeys = dispatchTable.size();
1913         int numSuccessors = numKeys + 1;
1914 
1915         AbstractBeginNode[] switchSuccessors = new AbstractBeginNode[numSuccessors];
1916         int[] switchKeys = new int[numKeys];
1917         double[] switchKeyProbabilities = new double[numSuccessors];
1918         int[] switchKeySuccessors = new int[numSuccessors];
1919 
1920         int idx = 0;
1921         for (Map.Entry<Integer, AbstractBeginNode> entry : dispatchTable.entrySet()) {
1922             switchSuccessors[idx] = entry.getValue();
1923             switchKeys[idx] = entry.getKey();
1924             switchKeyProbabilities[idx] = 1d / numKeys;
1925             switchKeySuccessors[idx] = idx;
1926             idx++;
1927         }
1928         switchSuccessors[idx] = defaultSuccessor;
1929         /* We know the default branch is never going to be executed. */
1930         switchKeyProbabilities[idx] = 0;
1931         switchKeySuccessors[idx] = idx;
1932 
1933         return new IntegerSwitchNode(switchedValue, switchSuccessors, switchKeys, switchKeyProbabilities, switchKeySuccessors);
1934     }
1935 
1936     /**
1937      * Print information about irreducible loops, when enabled with -Dgraal.Log=IrreducibleLoops.
1938      */
1939     @SuppressWarnings("try")
1940     private void logIrreducibleLoops() {
1941         DebugContext debug = graph.getDebug();
1942         try (DebugContext.Scope s = debug.scope("IrreducibleLoops")) {
1943             if (debug.isLogEnabled(DebugContext.BASIC_LEVEL) && irreducibleLoopSwitch != null) {
1944                 StringBuilder msg = new StringBuilder("Inserted state machine to remove irreducible loops. Dispatching to the following states: ");
1945                 String sep = "";
1946                 for (int i = 0; i < irreducibleLoopSwitch.keyCount(); i++) {
1947                     msg.append(sep).append(irreducibleLoopSwitch.keyAt(i).asInt());
1948                     sep = ", ";
1949                 }
1950                 debug.log(DebugContext.BASIC_LEVEL, "%s", msg);
1951             }
1952         }
1953     }
1954 }