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