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