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