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