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