14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.nodes;
24
25 import static org.graalvm.compiler.debug.GraalError.shouldNotReachHere;
26 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
27 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
28
29 import java.util.ArrayDeque;
30 import java.util.ArrayList;
31 import java.util.Arrays;
32 import java.util.BitSet;
33 import java.util.Deque;
34 import java.util.HashMap;
35 import java.util.Iterator;
36 import java.util.List;
37 import java.util.Map;
38 import java.util.SortedMap;
39 import java.util.TreeMap;
40
41 import org.graalvm.compiler.common.PermanentBailoutException;
42 import org.graalvm.compiler.core.common.Fields;
43 import org.graalvm.compiler.core.common.util.TypeReader;
44 import org.graalvm.compiler.core.common.util.UnsafeArrayTypeReader;
45 import org.graalvm.compiler.debug.Debug;
46 import org.graalvm.compiler.debug.GraalError;
47 import org.graalvm.compiler.graph.Edges;
48 import org.graalvm.compiler.graph.Graph;
49 import org.graalvm.compiler.graph.Node;
50 import org.graalvm.compiler.graph.NodeBitMap;
51 import org.graalvm.compiler.graph.NodeClass;
52 import org.graalvm.compiler.graph.NodeInputList;
53 import org.graalvm.compiler.graph.NodeList;
54 import org.graalvm.compiler.graph.NodeSourcePosition;
55 import org.graalvm.compiler.graph.NodeSuccessorList;
56 import org.graalvm.compiler.graph.spi.Canonicalizable;
57 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
58 import org.graalvm.compiler.nodeinfo.InputType;
59 import org.graalvm.compiler.nodeinfo.NodeInfo;
60 import org.graalvm.compiler.nodes.GraphDecoder.MethodScope;
61 import org.graalvm.compiler.nodes.GraphDecoder.ProxyPlaceholder;
62 import org.graalvm.compiler.nodes.calc.FloatingNode;
63 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
64 import org.graalvm.compiler.nodes.graphbuilderconf.LoopExplosionPlugin.LoopExplosionKind;
65
66 import jdk.vm.ci.code.Architecture;
67 import jdk.vm.ci.meta.DeoptimizationAction;
68 import jdk.vm.ci.meta.DeoptimizationReason;
69 import jdk.vm.ci.meta.JavaConstant;
70 import jdk.vm.ci.meta.JavaKind;
71 import jdk.vm.ci.meta.PrimitiveConstant;
72 import jdk.vm.ci.meta.ResolvedJavaType;
73
74 /**
75 * Decoder for {@link EncodedGraph encoded graphs} produced by {@link GraphEncoder}. Support for
76 * loop explosion during decoding is built into this class, because it requires many interactions
77 * with the decoding process. Subclasses can provide canonicalization and simplification of nodes
78 * during decoding, as well as method inlining during decoding.
79 */
80 public class GraphDecoder {
81
82 /** Decoding state maintained for each encoded graph. */
83 protected class MethodScope {
84 /** The loop that contains the call. Only non-null during method inlining. */
89 * Mark for nodes that were present before the decoding of this method started. Note that
90 * nodes that were decoded after the mark can still be part of an outer method, since
91 * floating nodes of outer methods are decoded lazily.
92 */
93 public final Graph.Mark methodStartMark;
94 /** The encode graph that is decoded. */
95 public final EncodedGraph encodedGraph;
96 /** Access to the encoded graph. */
97 public final TypeReader reader;
98 /** The kind of loop explosion to be performed during decoding. */
99 public final LoopExplosionKind loopExplosion;
100 /** A list of tasks to run before the method scope is closed. */
101 public final List<Runnable> cleanupTasks;
102
103 /** All return nodes encountered during decoding. */
104 public final List<ReturnNode> returnNodes;
105 /** The exception unwind node encountered during decoding, or null. */
106 public final List<UnwindNode> unwindNodes;
107
108 /** All merges created during loop explosion. */
109 public final NodeBitMap loopExplosionMerges;
110 /**
111 * The start of explosion, and the merge point for when irreducible loops are detected. Only
112 * used when {@link MethodScope#loopExplosion} is {@link LoopExplosionKind#MERGE_EXPLODE}.
113 */
114 public MergeNode loopExplosionHead;
115
116 protected MethodScope(LoopScope callerLoopScope, StructuredGraph graph, EncodedGraph encodedGraph, LoopExplosionKind loopExplosion) {
117 this.callerLoopScope = callerLoopScope;
118 this.graph = graph;
119 this.methodStartMark = graph.getMark();
120 this.encodedGraph = encodedGraph;
121 this.loopExplosion = loopExplosion;
122 this.cleanupTasks = new ArrayList<>();
123 this.returnNodes = new ArrayList<>();
124 this.unwindNodes = new ArrayList<>();
125
126 if (encodedGraph != null) {
127 reader = UnsafeArrayTypeReader.create(encodedGraph.getEncoding(), encodedGraph.getStartOffset(), architecture.supportsUnalignedMemoryAccess());
128 if (encodedGraph.nodeStartOffsets == null) {
129 int nodeCount = reader.getUVInt();
130 long[] nodeStartOffsets = new long[nodeCount];
131 for (int i = 0; i < nodeCount; i++) {
132 nodeStartOffsets[i] = encodedGraph.getStartOffset() - reader.getUV();
133 }
134 encodedGraph.nodeStartOffsets = nodeStartOffsets;
135 }
136 } else {
137 reader = null;
138 }
139
140 if (loopExplosion != LoopExplosionKind.NONE) {
141 loopExplosionMerges = new NodeBitMap(graph);
142 } else {
143 loopExplosionMerges = null;
144 }
145 }
146 }
147
148 /** Decoding state maintained for each loop in the encoded graph. */
149 protected static class LoopScope {
150 public final MethodScope methodScope;
151 public final LoopScope outer;
152 public final int loopDepth;
153 public final int loopIteration;
154 /**
155 * Upcoming loop iterations during loop explosions that have not been processed yet. Only
156 * used when {@link MethodScope#loopExplosion} is not {@link LoopExplosionKind#NONE}.
157 */
158 public Deque<LoopScope> nextIterations;
159 /**
160 * Information about already processed loop iterations for state merging during loop
161 * explosion. Only used when {@link MethodScope#loopExplosion} is
162 * {@link LoopExplosionKind#MERGE_EXPLODE}.
163 */
164 public final Map<LoopExplosionState, LoopExplosionState> iterationStates;
165 public final int loopBeginOrderId;
166 /**
167 * The worklist of fixed nodes to process. Since we already the correct processing order
168 * from the orderId, we just set the orderId bit in the bitset when a node is ready for
169 * processing. The lowest set bit is the next node to process.
170 */
171 public final BitSet nodesToProcess;
172 /** Nodes that have been created, indexed by the orderId. */
173 public final Node[] createdNodes;
174 /**
175 * Nodes that have been created in outer loop scopes and existed before starting to process
176 * this loop, indexed by the orderId.
177 */
178 public final Node[] initialCreatedNodes;
179
180 protected LoopScope(MethodScope methodScope) {
181 this.methodScope = methodScope;
182 this.outer = null;
183 this.nextIterations = methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN ? new ArrayDeque<>() : null;
184 this.loopDepth = 0;
185 this.loopIteration = 0;
186 this.iterationStates = null;
187 this.loopBeginOrderId = -1;
188
189 int nodeCount = methodScope.encodedGraph.nodeStartOffsets.length;
190 this.nodesToProcess = new BitSet(nodeCount);
191 this.initialCreatedNodes = new Node[nodeCount];
192 this.createdNodes = new Node[nodeCount];
193 }
194
195 protected LoopScope(MethodScope methodScope, LoopScope outer, int loopDepth, int loopIteration, int loopBeginOrderId, Node[] initialCreatedNodes, Node[] createdNodes,
196 Deque<LoopScope> nextIterations, Map<LoopExplosionState, LoopExplosionState> iterationStates) {
197 this.methodScope = methodScope;
198 this.outer = outer;
199 this.loopDepth = loopDepth;
200 this.loopIteration = loopIteration;
201 this.nextIterations = nextIterations;
202 this.iterationStates = iterationStates;
203 this.loopBeginOrderId = loopBeginOrderId;
204 this.nodesToProcess = new BitSet(initialCreatedNodes.length);
205 this.initialCreatedNodes = initialCreatedNodes;
206 this.createdNodes = Arrays.copyOf(createdNodes, createdNodes.length);
207 }
208
209 @Override
210 public String toString() {
211 return loopDepth + "," + loopIteration + (loopBeginOrderId == -1 ? "" : "#" + loopBeginOrderId);
212 }
213 }
214
215 protected static class LoopExplosionState {
216 public final FrameState state;
364 */
365 registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, AbstractBeginNode.prevBegin(startNode), false, false);
366
367 firstNode = makeStubNode(methodScope, loopScope, GraphEncoder.FIRST_NODE_ORDER_ID);
368 startNode.setNext(firstNode);
369 loopScope.nodesToProcess.set(GraphEncoder.FIRST_NODE_ORDER_ID);
370 } else {
371 firstNode = methodScope.graph.start();
372 registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, firstNode, false, false);
373 loopScope.nodesToProcess.set(GraphEncoder.START_NODE_ORDER_ID);
374 }
375
376 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
377 methodScope.cleanupTasks.add(new LoopDetector(methodScope, startNode));
378 }
379 return loopScope;
380 }
381
382 protected final void decode(LoopScope initialLoopScope) {
383 LoopScope loopScope = initialLoopScope;
384 /* Process inlined methods. */
385 while (loopScope != null) {
386 MethodScope methodScope = loopScope.methodScope;
387
388 /* Process loops of method. */
389 while (loopScope != null) {
390
391 /* Process nodes of loop. */
392 while (!loopScope.nodesToProcess.isEmpty()) {
393 loopScope = processNextNode(methodScope, loopScope);
394 methodScope = loopScope.methodScope;
395 /*
396 * We can have entered a new loop, and we can have entered a new inlined method.
397 */
398 }
399
400 /* Finished with a loop. */
401 if (loopScope.nextIterations != null && !loopScope.nextIterations.isEmpty()) {
402 /* Loop explosion: process the loop iteration. */
403 assert loopScope.nextIterations.peekFirst().loopIteration == loopScope.loopIteration + 1;
404 loopScope = loopScope.nextIterations.removeFirst();
478 /*
479 * Nodes that are still unprocessed in the outer scope might be merge nodes that are
480 * also reachable from the new exploded scope. Clearing them ensures that we do not
481 * merge, but instead keep exploding.
482 */
483 for (int id = outerScope.nodesToProcess.nextSetBit(0); id >= 0; id = outerScope.nodesToProcess.nextSetBit(id + 1)) {
484 successorAddScope.createdNodes[id] = null;
485 }
486
487 outerScope.nextIterations.addLast(successorAddScope);
488 } else {
489 successorAddScope = loopScope.outer;
490 }
491 updatePredecessors = methodScope.loopExplosion == LoopExplosionKind.NONE;
492 }
493
494 methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
495 int typeId = methodScope.reader.getUVInt();
496 assert node.getNodeClass() == methodScope.encodedGraph.getNodeClasses()[typeId];
497 readProperties(methodScope, node);
498 makeSuccessorStubs(methodScope, successorAddScope, node, updatePredecessors);
499 makeInputNodes(methodScope, loopScope, node, true);
500
501 LoopScope resultScope = loopScope;
502 if (node instanceof LoopBeginNode) {
503 if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
504 handleLoopExplosionBegin(methodScope, loopScope, (LoopBeginNode) node);
505 }
506
507 } else if (node instanceof LoopExitNode) {
508 if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
509 handleLoopExplosionProxyNodes(methodScope, loopScope, successorAddScope, (LoopExitNode) node, nodeOrderId);
510 } else {
511 handleProxyNodes(methodScope, loopScope, (LoopExitNode) node);
512 }
513
514 } else if (node instanceof MergeNode) {
515 handleMergeNode(((MergeNode) node));
516
517 } else if (node instanceof AbstractEndNode) {
518 LoopScope phiInputScope = loopScope;
519 LoopScope phiNodeScope = loopScope;
520
521 if (methodScope.loopExplosion != LoopExplosionKind.NONE && node instanceof LoopEndNode) {
522 node = handleLoopExplosionEnd(methodScope, loopScope, (LoopEndNode) node);
523 phiNodeScope = loopScope.nextIterations.getLast();
524 }
525
526 int mergeOrderId = readOrderId(methodScope);
527 AbstractMergeNode merge = (AbstractMergeNode) lookupNode(phiNodeScope, mergeOrderId);
528 if (merge == null) {
529 merge = (AbstractMergeNode) makeStubNode(methodScope, phiNodeScope, mergeOrderId);
530
531 if (merge instanceof LoopBeginNode) {
532 assert phiNodeScope == phiInputScope && phiNodeScope == loopScope;
533 resultScope = new LoopScope(methodScope, loopScope, loopScope.loopDepth + 1, 0, mergeOrderId,
534 Arrays.copyOf(loopScope.createdNodes, loopScope.createdNodes.length), loopScope.createdNodes, //
535 methodScope.loopExplosion != LoopExplosionKind.NONE ? new ArrayDeque<>() : null, //
536 methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE ? new HashMap<>() : null);
537 phiInputScope = resultScope;
538 phiNodeScope = resultScope;
539
540 registerNode(loopScope, mergeOrderId, null, true, true);
541 loopScope.nodesToProcess.clear(mergeOrderId);
542 resultScope.nodesToProcess.set(mergeOrderId);
543 }
544 }
545
546 handlePhiFunctions(methodScope, phiInputScope, phiNodeScope, (AbstractEndNode) node, merge);
547
548 } else if (node instanceof Invoke) {
549 InvokeData invokeData = readInvokeData(methodScope, nodeOrderId, (Invoke) node);
550 resultScope = handleInvoke(methodScope, loopScope, invokeData);
551
552 } else if (node instanceof ReturnNode) {
553 methodScope.returnNodes.add((ReturnNode) node);
554 } else if (node instanceof UnwindNode) {
555 methodScope.unwindNodes.add((UnwindNode) node);
556
575 return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, nextNextOrderId, exceptionOrderId, exceptionStateOrderId,
576 exceptionNextOrderId);
577 } else {
578 return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, -1, -1, -1, -1);
579 }
580 }
581
582 /**
583 * {@link Invoke} nodes do not have the {@link CallTargetNode}, {@link FrameState}, and
584 * successors encoded. Instead, this information is provided separately to allow method inlining
585 * without decoding and adding them to the graph upfront. For non-inlined methods, this method
586 * restores the normal state. Subclasses can override it to perform method inlining.
587 *
588 * The return value is the loop scope where decoding should continue. When method inlining
589 * should be performed, the returned loop scope must be a new loop scope for the inlined method.
590 * Without inlining, the original loop scope must be returned.
591 */
592 protected LoopScope handleInvoke(MethodScope methodScope, LoopScope loopScope, InvokeData invokeData) {
593 assert invokeData.invoke.callTarget() == null : "callTarget edge is ignored during decoding of Invoke";
594 CallTargetNode callTarget = (CallTargetNode) ensureNodeCreated(methodScope, loopScope, invokeData.callTargetOrderId);
595 if (invokeData.invoke instanceof InvokeWithExceptionNode) {
596 ((InvokeWithExceptionNode) invokeData.invoke).setCallTarget(callTarget);
597 } else {
598 ((InvokeNode) invokeData.invoke).setCallTarget(callTarget);
599 }
600
601 assert invokeData.invoke.stateAfter() == null && invokeData.invoke.stateDuring() == null : "FrameState edges are ignored during decoding of Invoke";
602 invokeData.invoke.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, invokeData.stateAfterOrderId));
603
604 invokeData.invoke.setNext(makeStubNode(methodScope, loopScope, invokeData.nextOrderId));
605 if (invokeData.invoke instanceof InvokeWithExceptionNode) {
606 ((InvokeWithExceptionNode) invokeData.invoke).setExceptionEdge((AbstractBeginNode) makeStubNode(methodScope, loopScope, invokeData.exceptionOrderId));
607 }
608 return loopScope;
609 }
610
611 /**
612 * Hook for subclasses to perform simplifications for a non-loop-header control flow merge.
613 *
614 * @param merge The control flow merge.
615 */
616 protected void handleMergeNode(MergeNode merge) {
617 }
618
619 protected void handleLoopExplosionBegin(MethodScope methodScope, LoopScope loopScope, LoopBeginNode loopBegin) {
620 checkLoopExplosionIteration(methodScope, loopScope);
621
622 List<EndNode> predecessors = loopBegin.forwardEnds().snapshot();
623 FixedNode successor = loopBegin.next();
624 FrameState frameState = loopBegin.stateAfter();
625
626 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
627 LoopExplosionState queryState = new LoopExplosionState(frameState, null);
628 LoopExplosionState existingState = loopScope.iterationStates.get(queryState);
629 if (existingState != null) {
630 loopBegin.replaceAtUsagesAndDelete(existingState.merge);
631 successor.safeDelete();
632 for (EndNode predecessor : predecessors) {
633 existingState.merge.addForwardEnd(predecessor);
634 }
635 return;
636 }
637 }
638
639 MergeNode merge = methodScope.graph.add(new MergeNode());
640 methodScope.loopExplosionMerges.markAndGrow(merge);
641
642 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
643 if (loopScope.iterationStates.size() == 0 && loopScope.loopDepth == 1) {
644 if (methodScope.loopExplosionHead != null) {
645 throw new PermanentBailoutException("Graal implementation restriction: Method with %s loop explosion must not have more than one top-level loop", LoopExplosionKind.MERGE_EXPLODE);
646 }
647 methodScope.loopExplosionHead = merge;
648 }
649
650 List<ValueNode> newFrameStateValues = new ArrayList<>();
651 for (ValueNode frameStateValue : frameState.values) {
652 if (frameStateValue == null || frameStateValue.isConstant() || !methodScope.graph.isNew(methodScope.methodStartMark, frameStateValue)) {
653 newFrameStateValues.add(frameStateValue);
654
655 } else {
656 ProxyPlaceholder newFrameStateValue = methodScope.graph.unique(new ProxyPlaceholder(frameStateValue, merge));
657 newFrameStateValues.add(newFrameStateValue);
658
659 /*
660 * We do not have the orderID of the value anymore, so we need to search through
661 * the complete list of nodes to find a match.
662 */
663 for (int i = 0; i < loopScope.createdNodes.length; i++) {
664 if (loopScope.createdNodes[i] == frameStateValue) {
665 loopScope.createdNodes[i] = newFrameStateValue;
666 }
667 if (loopScope.initialCreatedNodes[i] == frameStateValue) {
668 loopScope.initialCreatedNodes[i] = newFrameStateValue;
669 }
670 }
671 }
672 }
673
674 FrameState newFrameState = methodScope.graph.add(new FrameState(frameState.outerFrameState(), frameState.getCode(), frameState.bci, newFrameStateValues, frameState.localsSize(),
675 frameState.stackSize(), frameState.rethrowException(), frameState.duringCall(), frameState.monitorIds(), frameState.virtualObjectMappings()));
676
677 frameState.replaceAtUsages(newFrameState);
678 frameState.safeDelete();
679 frameState = newFrameState;
680 }
681
682 loopBegin.replaceAtUsagesAndDelete(merge);
683 merge.setStateAfter(frameState);
684 merge.setNext(successor);
685 for (EndNode predecessor : predecessors) {
686 merge.addForwardEnd(predecessor);
687 }
688
689 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
690 LoopExplosionState explosionState = new LoopExplosionState(frameState, merge);
691 loopScope.iterationStates.put(explosionState, explosionState);
692 }
693 }
694
695 /**
696 * Hook for subclasses.
697 *
698 * @param methodScope The current method.
747 registerNode(loopScope.outer, proxyOrderId, proxy, false, false);
748 }
749 }
750
751 protected void handleLoopExplosionProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopScope outerScope, LoopExitNode loopExit, int loopExitOrderId) {
752 assert loopExit.stateAfter() == null;
753 int stateAfterOrderId = readOrderId(methodScope);
754
755 BeginNode begin = methodScope.graph.add(new BeginNode());
756
757 FixedNode loopExitSuccessor = loopExit.next();
758 loopExit.replaceAtPredecessor(begin);
759
760 MergeNode loopExitPlaceholder = null;
761 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE && loopScope.loopDepth == 1) {
762 /*
763 * This exit might end up as a loop exit of a loop detected after partial evaluation. We
764 * need to be able to create a FrameState and the necessary proxy nodes in this case.
765 */
766 loopExitPlaceholder = methodScope.graph.add(new MergeNode());
767 methodScope.loopExplosionMerges.markAndGrow(loopExitPlaceholder);
768
769 EndNode end = methodScope.graph.add(new EndNode());
770 begin.setNext(end);
771 loopExitPlaceholder.addForwardEnd(end);
772
773 begin = methodScope.graph.add(new BeginNode());
774 loopExitPlaceholder.setNext(begin);
775 }
776
777 /*
778 * In the original graph, the loop exit is not a merge node. Multiple exploded loop
779 * iterations now take the same loop exit, so we have to introduce a new merge node to
780 * handle the merge.
781 */
782 MergeNode merge = null;
783 Node existingExit = lookupNode(outerScope, loopExitOrderId);
784 if (existingExit == null) {
785 /* First loop iteration that exits. No merge necessary yet. */
786 registerNode(outerScope, loopExitOrderId, begin, false, false);
787 begin.setNext(loopExitSuccessor);
947 protected boolean allowLazyPhis() {
948 /* We need to exactly reproduce the encoded graph, including unnecessary phi functions. */
949 return false;
950 }
951
952 protected Node instantiateNode(MethodScope methodScope, int nodeOrderId) {
953 methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
954 NodeClass<?> nodeClass = methodScope.encodedGraph.getNodeClasses()[methodScope.reader.getUVInt()];
955 return nodeClass.allocateInstance();
956 }
957
958 protected void readProperties(MethodScope methodScope, Node node) {
959 node.setNodeSourcePosition((NodeSourcePosition) readObject(methodScope));
960 Fields fields = node.getNodeClass().getData();
961 for (int pos = 0; pos < fields.getCount(); pos++) {
962 if (fields.getType(pos).isPrimitive()) {
963 long primitive = methodScope.reader.getSV();
964 fields.setRawPrimitive(node, pos, primitive);
965 } else {
966 Object value = readObject(methodScope);
967 fields.set(node, pos, value);
968 }
969 }
970 }
971
972 /**
973 * Process the input edges of a node. Input nodes that have not yet been created must be
974 * non-fixed nodes (because fixed nodes are processed in reverse postorder. Such non-fixed nodes
975 * are created on demand (recursively since they can themselves reference not yet created
976 * nodes).
977 */
978 protected void makeInputNodes(MethodScope methodScope, LoopScope loopScope, Node node, boolean updateUsages) {
979 Edges edges = node.getNodeClass().getEdges(Edges.Type.Inputs);
980 for (int index = 0; index < edges.getDirectCount(); index++) {
981 if (skipEdge(node, edges, index, true, true)) {
982 continue;
983 }
984 int orderId = readOrderId(methodScope);
985 Node value = ensureNodeCreated(methodScope, loopScope, orderId);
986 edges.initializeNode(node, index, value);
987 if (updateUsages && value != null && !value.isDeleted()) {
988 edges.update(node, null, value);
989
990 }
991 }
992 for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
993 if (skipEdge(node, edges, index, false, true)) {
994 continue;
995 }
996 int size = methodScope.reader.getSVInt();
997 if (size != -1) {
998 NodeList<Node> nodeList = new NodeInputList<>(node, size);
999 edges.initializeList(node, index, nodeList);
1000 for (int idx = 0; idx < size; idx++) {
1001 int orderId = readOrderId(methodScope);
1002 Node value = ensureNodeCreated(methodScope, loopScope, orderId);
1003 nodeList.initialize(idx, value);
1004 if (updateUsages && value != null && !value.isDeleted()) {
1005 edges.update(node, null, value);
1006 }
1007 }
1008 }
1009 }
1010 }
1011
1012 protected Node ensureNodeCreated(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
1013 if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
1086 * Hook for subclasses to process a non-fixed node after it is added to the graph.
1087 *
1088 * If this method replaces a node with another node, it must update its source position if the
1089 * original node has the source position set.
1090 *
1091 * @param methodScope The current method.
1092 * @param loopScope The current loop.
1093 * @param node The node to be canonicalized.
1094 * @return The replacement for the node, or the node itself.
1095 */
1096 protected Node handleFloatingNodeAfterAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
1097 return node;
1098 }
1099
1100 /**
1101 * Process successor edges of a node. We create the successor nodes so that we can fill the
1102 * successor list, but no properties or edges are loaded yet. That is done when the successor is
1103 * on top of the worklist in {@link #processNextNode}.
1104 */
1105 protected void makeSuccessorStubs(MethodScope methodScope, LoopScope loopScope, Node node, boolean updatePredecessors) {
1106 Edges edges = node.getNodeClass().getEdges(Edges.Type.Successors);
1107 for (int index = 0; index < edges.getDirectCount(); index++) {
1108 if (skipEdge(node, edges, index, true, true)) {
1109 continue;
1110 }
1111 int orderId = readOrderId(methodScope);
1112 Node value = makeStubNode(methodScope, loopScope, orderId);
1113 edges.initializeNode(node, index, value);
1114 if (updatePredecessors && value != null) {
1115 edges.update(node, null, value);
1116 }
1117 }
1118 for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
1119 if (skipEdge(node, edges, index, false, true)) {
1120 continue;
1121 }
1122 int size = methodScope.reader.getSVInt();
1123 if (size != -1) {
1124 NodeList<Node> nodeList = new NodeSuccessorList<>(node, size);
1125 edges.initializeList(node, index, nodeList);
1126 for (int idx = 0; idx < size; idx++) {
1127 int orderId = readOrderId(methodScope);
1128 Node value = makeStubNode(methodScope, loopScope, orderId);
1129 nodeList.initialize(idx, value);
1130 if (updatePredecessors && value != null) {
1131 edges.update(node, null, value);
1132 }
1133 }
1134 }
1135 }
1136 }
1137
1138 protected FixedNode makeStubNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
1139 if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
1140 return null;
1141 }
1142 FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId);
1143 if (node != null) {
1144 return node;
1145 }
1146
1147 long readerByteIndex = methodScope.reader.getByteIndex();
1148 node = (FixedNode) methodScope.graph.add(instantiateNode(methodScope, nodeOrderId));
1149 /* Properties and edges are not filled yet, the node remains uninitialized. */
1150 methodScope.reader.setByteIndex(readerByteIndex);
1151
1152 registerNode(loopScope, nodeOrderId, node, false, false);
1153 loopScope.nodesToProcess.set(nodeOrderId);
1154 return node;
1155 }
1156
1157 /**
1158 * Returns false for {@link Edges} that are not necessary in the encoded graph because they are
1159 * reconstructed using other sources of information.
1160 */
1161 protected static boolean skipEdge(Node node, Edges edges, int index, boolean direct, boolean decode) {
1162 if (node instanceof PhiNode) {
1163 /* The inputs of phi functions are filled manually when the end nodes are processed. */
1164 assert edges.type() == Edges.Type.Inputs;
1165 if (direct) {
1166 assert index == edges.getDirectCount() - 1 : "PhiNode has one direct input (the MergeNode)";
1167 } else {
1168 assert index == edges.getCount() - 1 : "PhiNode has one variable size input (the values)";
1169 if (decode) {
1170 /* The values must not be null, so initialize with an empty list. */
1171 edges.initializeList(node, index, new NodeInputList<>(node));
1172 }
1173 }
1174 return true;
1175
1176 } else if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs && !direct) {
1177 /* The ends of merge nodes are filled manually when the ends are processed. */
1178 assert index == edges.getCount() - 1 : "MergeNode has one variable size input (the ends)";
1179 assert Edges.getNodeList(node, edges.getOffsets(), index) != null : "Input list must have been already created";
1180 return true;
1181
1182 } else if (node instanceof LoopExitNode && edges.type() == Edges.Type.Inputs && edges.getType(index) == FrameState.class) {
1183 /* The stateAfter of the loop exit is filled manually. */
1184 return true;
1185
1186 } else if (node instanceof Invoke) {
1187 assert node instanceof InvokeNode || node instanceof InvokeWithExceptionNode : "The only two Invoke node classes. Got " + node.getClass();
1188 assert direct : "Invoke and InvokeWithException only have direct successor and input edges";
1189 if (edges.type() == Edges.Type.Successors) {
1190 assert edges.getCount() == (node instanceof InvokeWithExceptionNode ? 2 : 1) : "InvokeNode has one successor (next); InvokeWithExceptionNode has two successors (next, exceptionEdge)";
1191 return true;
1192 } else {
1193 assert edges.type() == Edges.Type.Inputs;
1194 if (edges.getType(index) == CallTargetNode.class) {
1195 return true;
1196 } else if (edges.getType(index) == FrameState.class) {
1197 assert edges.get(node, index) == null || edges.get(node, index) == ((Invoke) node).stateAfter() : "Only stateAfter can be a FrameState during encoding";
1198 return true;
1199 }
1200 }
1201 }
1202 return false;
1203 }
1204
1205 protected Node lookupNode(LoopScope loopScope, int nodeOrderId) {
1206 return loopScope.createdNodes[nodeOrderId];
1207 }
1208
1209 protected void registerNode(LoopScope loopScope, int nodeOrderId, Node node, boolean allowOverwrite, boolean allowNull) {
1210 assert node == null || node.isAlive();
1211 assert allowNull || node != null;
1212 assert allowOverwrite || lookupNode(loopScope, nodeOrderId) == null;
1213 loopScope.createdNodes[nodeOrderId] = node;
1214 }
1215
1216 protected int readOrderId(MethodScope methodScope) {
1217 return methodScope.reader.getUVInt();
1218 }
1219
1220 protected Object readObject(MethodScope methodScope) {
1310 * The algorithm to find loop exits requires that inner loops have already been
1311 * processed. Therefore, we need to iterate the loops in order (inner loops before outer
1312 * loops), and we cannot find the exits for all loops before we start inserting nodes.
1313 */
1314 findLoopExits(loop);
1315
1316 if (loop.irreducible) {
1317 handleIrreducibleLoop(loop);
1318 } else {
1319 insertLoopNodes(loop);
1320 }
1321 Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After handling of loop %s", loop.header);
1322 }
1323
1324 logIrreducibleLoops();
1325 Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After loop detection");
1326 }
1327
1328 private List<Loop> findLoops() {
1329 /* Mapping from the loop header node to additional loop information. */
1330 Map<MergeNode, Loop> unorderedLoops = new HashMap<>();
1331 /* Loops in reverse order of, i.e., inner loops before outer loops. */
1332 List<Loop> orderedLoops = new ArrayList<>();
1333
1334 /*
1335 * Ensure we have an outermost loop that we can use to eliminate irreducible loops. This
1336 * loop can remain empty (no ends), in which case it is ignored.
1337 */
1338 irreducibleLoopHandler = findOrCreateLoop(unorderedLoops, methodScope.loopExplosionHead);
1339
1340 NodeBitMap visited = methodScope.graph.createNodeBitMap();
1341 NodeBitMap active = methodScope.graph.createNodeBitMap();
1342 Deque<Node> stack = new ArrayDeque<>();
1343 visited.mark(startInstruction);
1344 stack.push(startInstruction);
1345
1346 while (!stack.isEmpty()) {
1347 Node current = stack.peek();
1348 assert visited.isMarked(current);
1349
1350 if (active.isMarked(current)) {
1351 /* We are back-tracking, i.e., all successor nodes have been processed. */
1352 stack.pop();
1353 active.clear(current);
1354
1355 Loop loop = unorderedLoops.get(current);
1356 if (loop != null) {
1357 /*
1358 * Since nodes are popped in reverse order that they were pushed, we add inner
1359 * loops before outer loops here.
1360 */
1361 assert !orderedLoops.contains(loop);
1362 orderedLoops.add(loop);
1363 }
1364
1365 } else {
1366 /*
1367 * Process the node. Note that we do not remove the node from the stack, i.e., we
1368 * will peek it again. But the next time the node is marked as active, so we do not
1369 * execute this code again.
1370 */
1371 active.mark(current);
1372 for (Node successor : current.cfgSuccessors()) {
1373 if (active.isMarked(successor)) {
1374 /* Detected a cycle, i.e., a backward branch of a loop. */
1375 Loop loop = findOrCreateLoop(unorderedLoops, (MergeNode) successor);
1376 assert !loop.ends.contains(current);
1377 loop.ends.add((EndNode) current);
1378
1379 } else if (visited.isMarked(successor)) {
1380 /* Forward merge into a branch we are already exploring. */
1381
1382 } else {
1383 /* Forward branch to a node we have not seen yet. */
1384 visited.mark(successor);
1385 stack.push(successor);
1386 }
1387 }
1388 }
1389 }
1390 return orderedLoops;
1391 }
1392
1393 private Loop findOrCreateLoop(Map<MergeNode, Loop> unorderedLoops, MergeNode loopHeader) {
1394 assert methodScope.loopExplosionMerges.isMarkedAndGrow(loopHeader) : loopHeader;
1395 Loop loop = unorderedLoops.get(loopHeader);
1396 if (loop == null) {
1397 loop = new Loop();
1398 loop.header = loopHeader;
1399 unorderedLoops.put(loopHeader, loop);
1400 }
1401 return loop;
1402 }
1403
1404 private void findLoopExits(Loop loop) {
1405 /*
1406 * Backward marking of loop nodes: Starting with the known loop ends, we mark all nodes that
1407 * are reachable until we hit the loop begin. All successors of loop nodes that are not
1408 * marked as loop nodes themselves are exits of the loop. We mark all successors, and then
1409 * subtract the loop nodes, to find the exits.
1410 */
1411
1412 NodeBitMap possibleExits = methodScope.graph.createNodeBitMap();
1413 NodeBitMap visited = methodScope.graph.createNodeBitMap();
1414 Deque<Node> stack = new ArrayDeque<>();
1415 for (EndNode loopEnd : loop.ends) {
1416 stack.push(loopEnd);
1417 visited.mark(loopEnd);
1418 }
1419
1420 while (!stack.isEmpty()) {
1421 Node current = stack.pop();
1422 if (current == loop.header) {
1423 continue;
1424 }
1425 if (!methodScope.graph.isNew(methodScope.methodStartMark, current)) {
1426 /*
1427 * The current node is before the method that contains the exploded loop. The loop
1428 * must have a second entry point, i.e., it is an irreducible loop.
1429 */
1430 loop.irreducible = true;
1431 return;
1432 }
1433
1434 for (Node predecessor : current.cfgPredecessors()) {
1435 if (predecessor instanceof LoopExitNode) {
1436 /*
1437 * Inner loop. We do not need to mark every node of it, instead we just continue
1438 * marking at the loop header.
1439 */
1440 LoopBeginNode innerLoopBegin = ((LoopExitNode) predecessor).loopBegin();
1441 if (!visited.isMarked(innerLoopBegin)) {
1442 stack.push(innerLoopBegin);
1443 visited.mark(innerLoopBegin);
1444
1445 /*
1446 * All loop exits of the inner loop possibly need a LoopExit of our loop.
1447 * Because we are processing inner loops first, we are guaranteed to already
1448 * have all exits of the inner loop.
1449 */
1450 for (LoopExitNode exit : innerLoopBegin.loopExits()) {
1451 possibleExits.mark(exit);
1452 }
1453 }
1454
1455 } else if (!visited.isMarked(predecessor)) {
1456 stack.push(predecessor);
1457 visited.mark(predecessor);
1458
1459 if (predecessor instanceof ControlSplitNode) {
1460 for (Node succ : predecessor.cfgSuccessors()) {
1461 /*
1462 * We would not need to mark the current node, and would not need to
1463 * mark visited nodes. But it is easier to just mark everything, since
1464 * we subtract all visited nodes in the end anyway. Note that at this
1465 * point we do not have the complete visited information, so we would
1466 * always mark too many possible exits.
1467 */
1468 possibleExits.mark(succ);
1469 }
1470 }
1471 }
1472 }
1473 }
1474
1475 /* All visited nodes are not exits of our loop. */
1476 possibleExits.subtract(visited);
1477
1478 /*
1479 * Now we know all the actual loop exits. Ideally, we would insert LoopExit nodes for them.
1480 * However, a LoopExit needs a valid FrameState that captures the state at the point where
1481 * we exit the loop. During graph decoding, we create a FrameState for every exploded loop
1482 * iteration. We need to do a forward marking until we hit the next such point. This puts
1483 * some nodes into the loop that are actually not part of the loop.
1484 *
1485 * In some cases, we did not create a FrameState during graph decoding: when there was no
1486 * LoopExit in the original loop that we exploded. This happens for code paths that lead
1487 * immediately to a DeoptimizeNode.
1488 *
1489 * Both cases mimic the behavior of the BytecodeParser, which also puts more nodes than
1490 * necessary into a loop because it computes loop information based on bytecodes, before the
1491 * actual parsing.
1492 */
1493
1494 for (Node succ : possibleExits) {
1495 stack.push(succ);
1496 visited.mark(succ);
1497 assert !methodScope.loopExplosionMerges.isMarkedAndGrow(succ);
1498 }
1499
1500 while (!stack.isEmpty()) {
1501 Node current = stack.pop();
1502 assert visited.isMarked(current);
1503 assert current instanceof ControlSinkNode || current instanceof LoopEndNode || current.cfgSuccessors().iterator().hasNext() : "Must not reach a node that has not been decoded yet";
1504
1505 for (Node successor : current.cfgSuccessors()) {
1506 if (visited.isMarked(successor)) {
1507 /* Already processed this successor. */
1508
1509 } else if (methodScope.loopExplosionMerges.isMarkedAndGrow(successor)) {
1510 /*
1511 * We have a FrameState for the successor. The LoopExit will be inserted between
1512 * the current node and the successor node. Since the successor node is a
1513 * MergeNode, the current node mus be a AbstractEndNode with only that MergeNode
1514 * as the successor.
1515 */
1516 assert successor instanceof MergeNode;
1517 assert !loop.exits.contains(current);
1518 loop.exits.add((AbstractEndNode) current);
1519
1520 } else {
1521 /* Node we have not seen yet. */
1522 visited.mark(successor);
1523 stack.push(successor);
1524 }
1525 }
1526 }
1527 }
1528
1529 private void insertLoopNodes(Loop loop) {
1560 }
1561
1562 for (EndNode endNode : loop.ends) {
1563 for (int i = 0; i < mergePhis.size(); i++) {
1564 PhiNode mergePhi = mergePhis.get(i);
1565 PhiNode loopBeginPhi = loopBeginPhis.get(i);
1566 loopBeginPhi.addInput(mergePhi.valueAt(endNode));
1567 }
1568
1569 merge.removeEnd(endNode);
1570 LoopEndNode loopEnd = methodScope.graph.add(new LoopEndNode(loopBegin));
1571 endNode.replaceAndDelete(loopEnd);
1572 }
1573
1574 /*
1575 * Insert the LoopExit nodes (the easy part) and compute the FrameState for the new exits
1576 * (the difficult part).
1577 */
1578 for (AbstractEndNode exit : loop.exits) {
1579 AbstractMergeNode loopExplosionMerge = exit.merge();
1580 assert methodScope.loopExplosionMerges.isMarkedAndGrow(loopExplosionMerge);
1581
1582 LoopExitNode loopExit = methodScope.graph.add(new LoopExitNode(loopBegin));
1583 exit.replaceAtPredecessor(loopExit);
1584 loopExit.setNext(exit);
1585 assignLoopExitState(loopExit, loopExplosionMerge, exit);
1586 }
1587 }
1588
1589 /**
1590 * During graph decoding, we create a FrameState for every exploded loop iteration. This is
1591 * mostly the state that we want, we only need to tweak it a little bit: we need to insert the
1592 * appropriate ProxyNodes for all values that are created inside the loop and that flow out of
1593 * the loop.
1594 */
1595 private void assignLoopExitState(LoopExitNode loopExit, AbstractMergeNode loopExplosionMerge, AbstractEndNode loopExplosionEnd) {
1596 FrameState oldState = loopExplosionMerge.stateAfter();
1597
1598 /* Collect all nodes that are in the FrameState at the LoopBegin. */
1599 NodeBitMap loopBeginValues = new NodeBitMap(methodScope.graph);
1600 for (FrameState state = loopExit.loopBegin().stateAfter(); state != null; state = state.outerFrameState()) {
1601 for (ValueNode value : state.values()) {
1602 if (value != null && !value.isConstant() && !loopExit.loopBegin().isPhiAtMerge(value)) {
1603 loopBeginValues.mark(ProxyPlaceholder.unwrap(value));
1604 }
1605 }
1606 }
1607
1608 List<ValueNode> newValues = new ArrayList<>(oldState.values().size());
1609 for (ValueNode v : oldState.values()) {
1610 ValueNode value = v;
1611 ValueNode realValue = ProxyPlaceholder.unwrap(value);
1612
1613 /*
1614 * The LoopExit is inserted before the existing merge, i.e., separately for every branch
1615 * that leads to the merge. So for phi functions of the merge, we need to take the input
1616 * that corresponds to our branch.
1617 */
1618 if (realValue instanceof PhiNode && loopExplosionMerge.isPhiAtMerge(realValue)) {
1619 value = ((PhiNode) realValue).valueAt(loopExplosionEnd);
1620 realValue = ProxyPlaceholder.unwrap(value);
1621 }
1622
1623 if (realValue == null || realValue.isConstant() || loopBeginValues.contains(realValue) || !methodScope.graph.isNew(methodScope.methodStartMark, realValue)) {
|
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.PermanentBailoutException;
41 import org.graalvm.compiler.core.common.Fields;
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.Equivalence;
65 import org.graalvm.util.EconomicMap;
66 import org.graalvm.util.EconomicSet;
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. */
91 * Mark for nodes that were present before the decoding of this method started. Note that
92 * nodes that were decoded after the mark can still be part of an outer method, since
93 * floating nodes of outer methods are decoded lazily.
94 */
95 public final Graph.Mark methodStartMark;
96 /** The encode graph that is decoded. */
97 public final EncodedGraph encodedGraph;
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 /** A list of tasks to run before the method scope is closed. */
103 public final List<Runnable> cleanupTasks;
104
105 /** All return nodes encountered during decoding. */
106 public final List<ReturnNode> returnNodes;
107 /** The exception unwind node encountered during decoding, or null. */
108 public final List<UnwindNode> unwindNodes;
109
110 /** All merges created during loop explosion. */
111 public final EconomicSet<Node> loopExplosionMerges;
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.graph = graph;
121 this.methodStartMark = graph.getMark();
122 this.encodedGraph = encodedGraph;
123 this.loopExplosion = loopExplosion;
124 this.cleanupTasks = new ArrayList<>(2);
125 this.returnNodes = new ArrayList<>(1);
126 this.unwindNodes = new ArrayList<>(0);
127
128 if (encodedGraph != null) {
129 reader = UnsafeArrayTypeReader.create(encodedGraph.getEncoding(), encodedGraph.getStartOffset(), architecture.supportsUnalignedMemoryAccess());
130 if (encodedGraph.nodeStartOffsets == null) {
131 int nodeCount = reader.getUVInt();
132 int[] nodeStartOffsets = new int[nodeCount];
133 for (int i = 0; i < nodeCount; i++) {
134 nodeStartOffsets[i] = encodedGraph.getStartOffset() - reader.getUVInt();
135 }
136 encodedGraph.nodeStartOffsets = nodeStartOffsets;
137 }
138 } else {
139 reader = null;
140 }
141
142 if (loopExplosion != LoopExplosionKind.NONE) {
143 loopExplosionMerges = EconomicSet.create(Equivalence.IDENTITY);
144 } else {
145 loopExplosionMerges = null;
146 }
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.
179 */
180 public final Node[] initialCreatedNodes;
181
182 protected LoopScope(MethodScope methodScope) {
183 this.methodScope = methodScope;
184 this.outer = null;
185 this.nextIterations = methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN ? new ArrayDeque<>() : null;
186 this.loopDepth = 0;
187 this.loopIteration = 0;
188 this.iterationStates = null;
189 this.loopBeginOrderId = -1;
190
191 int nodeCount = methodScope.encodedGraph.nodeStartOffsets.length;
192 this.nodesToProcess = new BitSet(nodeCount);
193 this.initialCreatedNodes = new Node[nodeCount];
194 this.createdNodes = new Node[nodeCount];
195 }
196
197 protected LoopScope(MethodScope methodScope, LoopScope outer, int loopDepth, int loopIteration, int loopBeginOrderId, Node[] initialCreatedNodes, Node[] createdNodes,
198 Deque<LoopScope> nextIterations, EconomicMap<LoopExplosionState, LoopExplosionState> iterationStates) {
199 this.methodScope = methodScope;
200 this.outer = outer;
201 this.loopDepth = loopDepth;
202 this.loopIteration = loopIteration;
203 this.nextIterations = nextIterations;
204 this.iterationStates = iterationStates;
205 this.loopBeginOrderId = loopBeginOrderId;
206 this.nodesToProcess = new BitSet(initialCreatedNodes.length);
207 this.initialCreatedNodes = initialCreatedNodes;
208 this.createdNodes = Arrays.copyOf(createdNodes, createdNodes.length);
209 }
210
211 @Override
212 public String toString() {
213 return loopDepth + "," + loopIteration + (loopBeginOrderId == -1 ? "" : "#" + loopBeginOrderId);
214 }
215 }
216
217 protected static class LoopExplosionState {
218 public final FrameState state;
366 */
367 registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, AbstractBeginNode.prevBegin(startNode), false, false);
368
369 firstNode = makeStubNode(methodScope, loopScope, GraphEncoder.FIRST_NODE_ORDER_ID);
370 startNode.setNext(firstNode);
371 loopScope.nodesToProcess.set(GraphEncoder.FIRST_NODE_ORDER_ID);
372 } else {
373 firstNode = methodScope.graph.start();
374 registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, firstNode, false, false);
375 loopScope.nodesToProcess.set(GraphEncoder.START_NODE_ORDER_ID);
376 }
377
378 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
379 methodScope.cleanupTasks.add(new LoopDetector(methodScope, startNode));
380 }
381 return loopScope;
382 }
383
384 protected final void decode(LoopScope initialLoopScope) {
385 LoopScope loopScope = initialLoopScope;
386 /* Process (inlined) methods. */
387 while (loopScope != null) {
388 MethodScope methodScope = loopScope.methodScope;
389
390 /* Process loops of method. */
391 while (loopScope != null) {
392
393 /* Process nodes of loop. */
394 while (!loopScope.nodesToProcess.isEmpty()) {
395 loopScope = processNextNode(methodScope, loopScope);
396 methodScope = loopScope.methodScope;
397 /*
398 * We can have entered a new loop, and we can have entered a new inlined method.
399 */
400 }
401
402 /* Finished with a loop. */
403 if (loopScope.nextIterations != null && !loopScope.nextIterations.isEmpty()) {
404 /* Loop explosion: process the loop iteration. */
405 assert loopScope.nextIterations.peekFirst().loopIteration == loopScope.loopIteration + 1;
406 loopScope = loopScope.nextIterations.removeFirst();
480 /*
481 * Nodes that are still unprocessed in the outer scope might be merge nodes that are
482 * also reachable from the new exploded scope. Clearing them ensures that we do not
483 * merge, but instead keep exploding.
484 */
485 for (int id = outerScope.nodesToProcess.nextSetBit(0); id >= 0; id = outerScope.nodesToProcess.nextSetBit(id + 1)) {
486 successorAddScope.createdNodes[id] = null;
487 }
488
489 outerScope.nextIterations.addLast(successorAddScope);
490 } else {
491 successorAddScope = loopScope.outer;
492 }
493 updatePredecessors = methodScope.loopExplosion == LoopExplosionKind.NONE;
494 }
495
496 methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
497 int typeId = methodScope.reader.getUVInt();
498 assert node.getNodeClass() == methodScope.encodedGraph.getNodeClasses()[typeId];
499 readProperties(methodScope, node);
500 makeInputNodes(methodScope, loopScope, node, true);
501 makeSuccessorStubs(methodScope, successorAddScope, node, updatePredecessors);
502
503 LoopScope resultScope = loopScope;
504 if (node instanceof LoopBeginNode) {
505 if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
506 handleLoopExplosionBegin(methodScope, loopScope, (LoopBeginNode) node);
507 }
508
509 } else if (node instanceof LoopExitNode) {
510 if (methodScope.loopExplosion != LoopExplosionKind.NONE) {
511 handleLoopExplosionProxyNodes(methodScope, loopScope, successorAddScope, (LoopExitNode) node, nodeOrderId);
512 } else {
513 handleProxyNodes(methodScope, loopScope, (LoopExitNode) node);
514 }
515
516 } else if (node instanceof MergeNode) {
517 handleMergeNode(((MergeNode) node));
518
519 } else if (node instanceof AbstractEndNode) {
520 LoopScope phiInputScope = loopScope;
521 LoopScope phiNodeScope = loopScope;
522
523 if (methodScope.loopExplosion != LoopExplosionKind.NONE && node instanceof LoopEndNode) {
524 node = handleLoopExplosionEnd(methodScope, loopScope, (LoopEndNode) node);
525 phiNodeScope = loopScope.nextIterations.getLast();
526 }
527
528 int mergeOrderId = readOrderId(methodScope);
529 AbstractMergeNode merge = (AbstractMergeNode) lookupNode(phiNodeScope, mergeOrderId);
530 if (merge == null) {
531 merge = (AbstractMergeNode) makeStubNode(methodScope, phiNodeScope, mergeOrderId);
532
533 if (merge instanceof LoopBeginNode) {
534 assert phiNodeScope == phiInputScope && phiNodeScope == loopScope;
535 resultScope = new LoopScope(methodScope, loopScope, loopScope.loopDepth + 1, 0, mergeOrderId,
536 Arrays.copyOf(loopScope.createdNodes, loopScope.createdNodes.length), loopScope.createdNodes, //
537 methodScope.loopExplosion != LoopExplosionKind.NONE ? new ArrayDeque<>() : null, //
538 methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE ? EconomicMap.create(Equivalence.DEFAULT) : null);
539 phiInputScope = resultScope;
540 phiNodeScope = resultScope;
541
542 registerNode(loopScope, mergeOrderId, null, true, true);
543 loopScope.nodesToProcess.clear(mergeOrderId);
544 resultScope.nodesToProcess.set(mergeOrderId);
545 }
546 }
547
548 handlePhiFunctions(methodScope, phiInputScope, phiNodeScope, (AbstractEndNode) node, merge);
549
550 } else if (node instanceof Invoke) {
551 InvokeData invokeData = readInvokeData(methodScope, nodeOrderId, (Invoke) node);
552 resultScope = handleInvoke(methodScope, loopScope, invokeData);
553
554 } else if (node instanceof ReturnNode) {
555 methodScope.returnNodes.add((ReturnNode) node);
556 } else if (node instanceof UnwindNode) {
557 methodScope.unwindNodes.add((UnwindNode) node);
558
577 return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, nextNextOrderId, exceptionOrderId, exceptionStateOrderId,
578 exceptionNextOrderId);
579 } else {
580 return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, -1, -1, -1, -1);
581 }
582 }
583
584 /**
585 * {@link Invoke} nodes do not have the {@link CallTargetNode}, {@link FrameState}, and
586 * successors encoded. Instead, this information is provided separately to allow method inlining
587 * without decoding and adding them to the graph upfront. For non-inlined methods, this method
588 * restores the normal state. Subclasses can override it to perform method inlining.
589 *
590 * The return value is the loop scope where decoding should continue. When method inlining
591 * should be performed, the returned loop scope must be a new loop scope for the inlined method.
592 * Without inlining, the original loop scope must be returned.
593 */
594 protected LoopScope handleInvoke(MethodScope methodScope, LoopScope loopScope, InvokeData invokeData) {
595 assert invokeData.invoke.callTarget() == null : "callTarget edge is ignored during decoding of Invoke";
596 CallTargetNode callTarget = (CallTargetNode) ensureNodeCreated(methodScope, loopScope, invokeData.callTargetOrderId);
597 appendInvoke(methodScope, loopScope, invokeData, callTarget);
598 return loopScope;
599 }
600
601 protected void appendInvoke(MethodScope methodScope, LoopScope loopScope, InvokeData invokeData, CallTargetNode callTarget) {
602 if (invokeData.invoke instanceof InvokeWithExceptionNode) {
603 ((InvokeWithExceptionNode) invokeData.invoke).setCallTarget(callTarget);
604 } else {
605 ((InvokeNode) invokeData.invoke).setCallTarget(callTarget);
606 }
607
608 assert invokeData.invoke.stateAfter() == null && invokeData.invoke.stateDuring() == null : "FrameState edges are ignored during decoding of Invoke";
609 invokeData.invoke.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, invokeData.stateAfterOrderId));
610
611 invokeData.invoke.setNext(makeStubNode(methodScope, loopScope, invokeData.nextOrderId));
612 if (invokeData.invoke instanceof InvokeWithExceptionNode) {
613 ((InvokeWithExceptionNode) invokeData.invoke).setExceptionEdge((AbstractBeginNode) makeStubNode(methodScope, loopScope, invokeData.exceptionOrderId));
614 }
615 }
616
617 /**
618 * Hook for subclasses to perform simplifications for a non-loop-header control flow merge.
619 *
620 * @param merge The control flow merge.
621 */
622 protected void handleMergeNode(MergeNode merge) {
623 }
624
625 protected void handleLoopExplosionBegin(MethodScope methodScope, LoopScope loopScope, LoopBeginNode loopBegin) {
626 checkLoopExplosionIteration(methodScope, loopScope);
627
628 List<EndNode> predecessors = loopBegin.forwardEnds().snapshot();
629 FixedNode successor = loopBegin.next();
630 FrameState frameState = loopBegin.stateAfter();
631
632 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
633 LoopExplosionState queryState = new LoopExplosionState(frameState, null);
634 LoopExplosionState existingState = loopScope.iterationStates.get(queryState);
635 if (existingState != null) {
636 loopBegin.replaceAtUsagesAndDelete(existingState.merge);
637 successor.safeDelete();
638 for (EndNode predecessor : predecessors) {
639 existingState.merge.addForwardEnd(predecessor);
640 }
641 return;
642 }
643 }
644
645 MergeNode merge = methodScope.graph.add(new MergeNode());
646 methodScope.loopExplosionMerges.add(merge);
647
648 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
649 if (loopScope.iterationStates.size() == 0 && loopScope.loopDepth == 1) {
650 if (methodScope.loopExplosionHead != null) {
651 throw new PermanentBailoutException("Graal implementation restriction: Method with %s loop explosion must not have more than one top-level loop", LoopExplosionKind.MERGE_EXPLODE);
652 }
653 methodScope.loopExplosionHead = merge;
654 }
655
656 List<ValueNode> newFrameStateValues = new ArrayList<>();
657 for (ValueNode frameStateValue : frameState.values) {
658 if (frameStateValue == null || frameStateValue.isConstant() || !methodScope.graph.isNew(methodScope.methodStartMark, frameStateValue)) {
659 newFrameStateValues.add(frameStateValue);
660
661 } else {
662 ProxyPlaceholder newFrameStateValue = methodScope.graph.unique(new ProxyPlaceholder(frameStateValue, merge));
663 newFrameStateValues.add(newFrameStateValue);
664
665 /*
666 * We do not have the orderID of the value anymore, so we need to search through
667 * the complete list of nodes to find a match.
668 */
669 for (int i = 0; i < loopScope.createdNodes.length; i++) {
670 if (loopScope.createdNodes[i] == frameStateValue) {
671 loopScope.createdNodes[i] = newFrameStateValue;
672 }
673 if (loopScope.initialCreatedNodes[i] == frameStateValue) {
674 loopScope.initialCreatedNodes[i] = newFrameStateValue;
675 }
676 }
677 }
678 }
679
680 FrameState newFrameState = methodScope.graph.add(new FrameState(frameState.outerFrameState(), frameState.getCode(), frameState.bci, newFrameStateValues, frameState.localsSize(),
681 frameState.stackSize(), frameState.rethrowException(), frameState.duringCall(), frameState.monitorIds(), frameState.virtualObjectMappings()));
682
683 frameState.replaceAtUsagesAndDelete(newFrameState);
684 frameState = newFrameState;
685 }
686
687 loopBegin.replaceAtUsagesAndDelete(merge);
688 merge.setStateAfter(frameState);
689 merge.setNext(successor);
690 for (EndNode predecessor : predecessors) {
691 merge.addForwardEnd(predecessor);
692 }
693
694 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) {
695 LoopExplosionState explosionState = new LoopExplosionState(frameState, merge);
696 loopScope.iterationStates.put(explosionState, explosionState);
697 }
698 }
699
700 /**
701 * Hook for subclasses.
702 *
703 * @param methodScope The current method.
752 registerNode(loopScope.outer, proxyOrderId, proxy, false, false);
753 }
754 }
755
756 protected void handleLoopExplosionProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopScope outerScope, LoopExitNode loopExit, int loopExitOrderId) {
757 assert loopExit.stateAfter() == null;
758 int stateAfterOrderId = readOrderId(methodScope);
759
760 BeginNode begin = methodScope.graph.add(new BeginNode());
761
762 FixedNode loopExitSuccessor = loopExit.next();
763 loopExit.replaceAtPredecessor(begin);
764
765 MergeNode loopExitPlaceholder = null;
766 if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE && loopScope.loopDepth == 1) {
767 /*
768 * This exit might end up as a loop exit of a loop detected after partial evaluation. We
769 * need to be able to create a FrameState and the necessary proxy nodes in this case.
770 */
771 loopExitPlaceholder = methodScope.graph.add(new MergeNode());
772 methodScope.loopExplosionMerges.add(loopExitPlaceholder);
773
774 EndNode end = methodScope.graph.add(new EndNode());
775 begin.setNext(end);
776 loopExitPlaceholder.addForwardEnd(end);
777
778 begin = methodScope.graph.add(new BeginNode());
779 loopExitPlaceholder.setNext(begin);
780 }
781
782 /*
783 * In the original graph, the loop exit is not a merge node. Multiple exploded loop
784 * iterations now take the same loop exit, so we have to introduce a new merge node to
785 * handle the merge.
786 */
787 MergeNode merge = null;
788 Node existingExit = lookupNode(outerScope, loopExitOrderId);
789 if (existingExit == null) {
790 /* First loop iteration that exits. No merge necessary yet. */
791 registerNode(outerScope, loopExitOrderId, begin, false, false);
792 begin.setNext(loopExitSuccessor);
952 protected boolean allowLazyPhis() {
953 /* We need to exactly reproduce the encoded graph, including unnecessary phi functions. */
954 return false;
955 }
956
957 protected Node instantiateNode(MethodScope methodScope, int nodeOrderId) {
958 methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]);
959 NodeClass<?> nodeClass = methodScope.encodedGraph.getNodeClasses()[methodScope.reader.getUVInt()];
960 return nodeClass.allocateInstance();
961 }
962
963 protected void readProperties(MethodScope methodScope, Node node) {
964 node.setNodeSourcePosition((NodeSourcePosition) readObject(methodScope));
965 Fields fields = node.getNodeClass().getData();
966 for (int pos = 0; pos < fields.getCount(); pos++) {
967 if (fields.getType(pos).isPrimitive()) {
968 long primitive = methodScope.reader.getSV();
969 fields.setRawPrimitive(node, pos, primitive);
970 } else {
971 Object value = readObject(methodScope);
972 fields.putObject(node, pos, value);
973 }
974 }
975 }
976
977 /**
978 * Process the input edges of a node. Input nodes that have not yet been created must be
979 * non-fixed nodes (because fixed nodes are processed in reverse postorder. Such non-fixed nodes
980 * are created on demand (recursively since they can themselves reference not yet created
981 * nodes).
982 */
983 protected void makeInputNodes(MethodScope methodScope, LoopScope loopScope, Node node, boolean updateUsages) {
984 Edges edges = node.getNodeClass().getInputEdges();
985 for (int index = 0; index < edges.getDirectCount(); index++) {
986 if (skipDirectEdge(node, edges, index)) {
987 continue;
988 }
989 int orderId = readOrderId(methodScope);
990 Node value = ensureNodeCreated(methodScope, loopScope, orderId);
991 edges.initializeNode(node, index, value);
992 if (updateUsages && value != null && !value.isDeleted()) {
993 edges.update(node, null, value);
994
995 }
996 }
997 for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
998 if (skipIndirectEdge(node, edges, index, true)) {
999 continue;
1000 }
1001 int size = methodScope.reader.getSVInt();
1002 if (size != -1) {
1003 NodeList<Node> nodeList = new NodeInputList<>(node, size);
1004 edges.initializeList(node, index, nodeList);
1005 for (int idx = 0; idx < size; idx++) {
1006 int orderId = readOrderId(methodScope);
1007 Node value = ensureNodeCreated(methodScope, loopScope, orderId);
1008 nodeList.initialize(idx, value);
1009 if (updateUsages && value != null && !value.isDeleted()) {
1010 edges.update(node, null, value);
1011 }
1012 }
1013 }
1014 }
1015 }
1016
1017 protected Node ensureNodeCreated(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
1018 if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
1091 * Hook for subclasses to process a non-fixed node after it is added to the graph.
1092 *
1093 * If this method replaces a node with another node, it must update its source position if the
1094 * original node has the source position set.
1095 *
1096 * @param methodScope The current method.
1097 * @param loopScope The current loop.
1098 * @param node The node to be canonicalized.
1099 * @return The replacement for the node, or the node itself.
1100 */
1101 protected Node handleFloatingNodeAfterAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
1102 return node;
1103 }
1104
1105 /**
1106 * Process successor edges of a node. We create the successor nodes so that we can fill the
1107 * successor list, but no properties or edges are loaded yet. That is done when the successor is
1108 * on top of the worklist in {@link #processNextNode}.
1109 */
1110 protected void makeSuccessorStubs(MethodScope methodScope, LoopScope loopScope, Node node, boolean updatePredecessors) {
1111 Edges edges = node.getNodeClass().getSuccessorEdges();
1112 for (int index = 0; index < edges.getDirectCount(); index++) {
1113 if (skipDirectEdge(node, edges, index)) {
1114 continue;
1115 }
1116 int orderId = readOrderId(methodScope);
1117 Node value = makeStubNode(methodScope, loopScope, orderId);
1118 edges.initializeNode(node, index, value);
1119 if (updatePredecessors && value != null) {
1120 edges.update(node, null, value);
1121 }
1122 }
1123 for (int index = edges.getDirectCount(); index < edges.getCount(); index++) {
1124 if (skipIndirectEdge(node, edges, index, true)) {
1125 continue;
1126 }
1127 int size = methodScope.reader.getSVInt();
1128 if (size != -1) {
1129 NodeList<Node> nodeList = new NodeSuccessorList<>(node, size);
1130 edges.initializeList(node, index, nodeList);
1131 for (int idx = 0; idx < size; idx++) {
1132 int orderId = readOrderId(methodScope);
1133 Node value = makeStubNode(methodScope, loopScope, orderId);
1134 nodeList.initialize(idx, value);
1135 if (updatePredecessors && value != null) {
1136 edges.update(node, null, value);
1137 }
1138 }
1139 }
1140 }
1141 }
1142
1143 protected FixedNode makeStubNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) {
1144 if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) {
1145 return null;
1146 }
1147 FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId);
1148 if (node != null) {
1149 return node;
1150 }
1151
1152 long readerByteIndex = methodScope.reader.getByteIndex();
1153 node = (FixedNode) methodScope.graph.add(instantiateNode(methodScope, nodeOrderId));
1154 /* Properties and edges are not filled yet, the node remains uninitialized. */
1155 methodScope.reader.setByteIndex(readerByteIndex);
1156
1157 registerNode(loopScope, nodeOrderId, node, false, false);
1158 loopScope.nodesToProcess.set(nodeOrderId);
1159 return node;
1160 }
1161
1162 protected static boolean skipDirectEdge(Node node, Edges edges, int index) {
1163 if (node instanceof Invoke) {
1164 assert node instanceof InvokeNode || node instanceof InvokeWithExceptionNode : "The only two Invoke node classes. Got " + node.getClass();
1165 if (edges.type() == Edges.Type.Successors) {
1166 assert edges.getCount() == (node instanceof InvokeWithExceptionNode ? 2 : 1) : "InvokeNode has one successor (next); InvokeWithExceptionNode has two successors (next, exceptionEdge)";
1167 return true;
1168 } else {
1169 assert edges.type() == Edges.Type.Inputs;
1170 if (edges.getType(index) == CallTargetNode.class) {
1171 return true;
1172 } else if (edges.getType(index) == FrameState.class) {
1173 assert edges.get(node, index) == null || edges.get(node, index) == ((Invoke) node).stateAfter() : "Only stateAfter can be a FrameState during encoding";
1174 return true;
1175 }
1176 }
1177 } else if (node instanceof PhiNode) {
1178 /* The inputs of phi functions are filled manually when the end nodes are processed. */
1179 assert edges.type() == Edges.Type.Inputs;
1180 assert index == edges.getDirectCount() - 1 : "PhiNode has one direct input (the MergeNode)";
1181 return true;
1182
1183 } else if (node instanceof LoopExitNode && edges.type() == Edges.Type.Inputs && edges.getType(index) == FrameState.class) {
1184 /* The stateAfter of the loop exit is filled manually. */
1185 return true;
1186
1187 }
1188 return false;
1189 }
1190
1191 protected static boolean skipIndirectEdge(Node node, Edges edges, int index, boolean decode) {
1192 assert !(node instanceof Invoke);
1193 assert !(node instanceof LoopExitNode && edges.type() == Edges.Type.Inputs && edges.getType(index) == FrameState.class);
1194 if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs) {
1195 /* The ends of merge nodes are filled manually when the ends are processed. */
1196 assert index == edges.getCount() - 1 : "MergeNode has one variable size input (the ends)";
1197 assert Edges.getNodeList(node, edges.getOffsets(), index) != null : "Input list must have been already created";
1198 return true;
1199
1200 } else if (node instanceof PhiNode) {
1201 /* The inputs of phi functions are filled manually when the end nodes are processed. */
1202 assert edges.type() == Edges.Type.Inputs;
1203 assert index == edges.getCount() - 1 : "PhiNode has one variable size input (the values)";
1204 if (decode) {
1205 /* The values must not be null, so initialize with an empty list. */
1206 edges.initializeList(node, index, new NodeInputList<>(node));
1207 }
1208 return true;
1209
1210 }
1211 return false;
1212 }
1213
1214 protected Node lookupNode(LoopScope loopScope, int nodeOrderId) {
1215 return loopScope.createdNodes[nodeOrderId];
1216 }
1217
1218 protected void registerNode(LoopScope loopScope, int nodeOrderId, Node node, boolean allowOverwrite, boolean allowNull) {
1219 assert node == null || node.isAlive();
1220 assert allowNull || node != null;
1221 assert allowOverwrite || lookupNode(loopScope, nodeOrderId) == null;
1222 loopScope.createdNodes[nodeOrderId] = node;
1223 }
1224
1225 protected int readOrderId(MethodScope methodScope) {
1226 return methodScope.reader.getUVInt();
1227 }
1228
1229 protected Object readObject(MethodScope methodScope) {
1319 * The algorithm to find loop exits requires that inner loops have already been
1320 * processed. Therefore, we need to iterate the loops in order (inner loops before outer
1321 * loops), and we cannot find the exits for all loops before we start inserting nodes.
1322 */
1323 findLoopExits(loop);
1324
1325 if (loop.irreducible) {
1326 handleIrreducibleLoop(loop);
1327 } else {
1328 insertLoopNodes(loop);
1329 }
1330 Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After handling of loop %s", loop.header);
1331 }
1332
1333 logIrreducibleLoops();
1334 Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After loop detection");
1335 }
1336
1337 private List<Loop> findLoops() {
1338 /* Mapping from the loop header node to additional loop information. */
1339 EconomicMap<MergeNode, Loop> unorderedLoops = EconomicMap.create(Equivalence.IDENTITY);
1340 /* Loops in reverse order of, i.e., inner loops before outer loops. */
1341 List<Loop> orderedLoops = new ArrayList<>();
1342
1343 /*
1344 * Ensure we have an outermost loop that we can use to eliminate irreducible loops. This
1345 * loop can remain empty (no ends), in which case it is ignored.
1346 */
1347 irreducibleLoopHandler = findOrCreateLoop(unorderedLoops, methodScope.loopExplosionHead);
1348
1349 NodeBitMap visited = methodScope.graph.createNodeBitMap();
1350 NodeBitMap active = methodScope.graph.createNodeBitMap();
1351 Deque<Node> stack = new ArrayDeque<>();
1352 visited.mark(startInstruction);
1353 stack.push(startInstruction);
1354
1355 while (!stack.isEmpty()) {
1356 Node current = stack.peek();
1357 assert visited.isMarked(current);
1358
1359 if (active.isMarked(current)) {
1360 /* We are back-tracking, i.e., all successor nodes have been processed. */
1361 stack.pop();
1362 active.clear(current);
1363
1364 if (current instanceof MergeNode) {
1365 Loop loop = unorderedLoops.get((MergeNode) current);
1366 if (loop != null) {
1367 /*
1368 * Since nodes are popped in reverse order that they were pushed, we add
1369 * inner loops before outer loops here.
1370 */
1371 assert !orderedLoops.contains(loop);
1372 orderedLoops.add(loop);
1373 }
1374 }
1375
1376 } else {
1377 /*
1378 * Process the node. Note that we do not remove the node from the stack, i.e., we
1379 * will peek it again. But the next time the node is marked as active, so we do not
1380 * execute this code again.
1381 */
1382 active.mark(current);
1383 for (Node successor : current.cfgSuccessors()) {
1384 if (active.isMarked(successor)) {
1385 /* Detected a cycle, i.e., a backward branch of a loop. */
1386 Loop loop = findOrCreateLoop(unorderedLoops, (MergeNode) successor);
1387 assert !loop.ends.contains(current);
1388 loop.ends.add((EndNode) current);
1389
1390 } else if (visited.isMarked(successor)) {
1391 /* Forward merge into a branch we are already exploring. */
1392
1393 } else {
1394 /* Forward branch to a node we have not seen yet. */
1395 visited.mark(successor);
1396 stack.push(successor);
1397 }
1398 }
1399 }
1400 }
1401 return orderedLoops;
1402 }
1403
1404 private Loop findOrCreateLoop(EconomicMap<MergeNode, Loop> unorderedLoops, MergeNode loopHeader) {
1405 assert methodScope.loopExplosionMerges.contains(loopHeader) : loopHeader;
1406 Loop loop = unorderedLoops.get(loopHeader);
1407 if (loop == null) {
1408 loop = new Loop();
1409 loop.header = loopHeader;
1410 unorderedLoops.put(loopHeader, loop);
1411 }
1412 return loop;
1413 }
1414
1415 private void findLoopExits(Loop loop) {
1416 /*
1417 * Backward marking of loop nodes: Starting with the known loop ends, we mark all nodes that
1418 * are reachable until we hit the loop begin. All successors of loop nodes that are not
1419 * marked as loop nodes themselves are exits of the loop. We mark all successors, and then
1420 * subtract the loop nodes, to find the exits.
1421 */
1422
1423 List<Node> possibleExits = new ArrayList<>();
1424 NodeBitMap visited = methodScope.graph.createNodeBitMap();
1425 Deque<Node> stack = new ArrayDeque<>();
1426 for (EndNode loopEnd : loop.ends) {
1427 stack.push(loopEnd);
1428 visited.mark(loopEnd);
1429 }
1430
1431 while (!stack.isEmpty()) {
1432 Node current = stack.pop();
1433 if (current == loop.header) {
1434 continue;
1435 }
1436 if (!methodScope.graph.isNew(methodScope.methodStartMark, current)) {
1437 /*
1438 * The current node is before the method that contains the exploded loop. The loop
1439 * must have a second entry point, i.e., it is an irreducible loop.
1440 */
1441 loop.irreducible = true;
1442 return;
1443 }
1444
1445 for (Node predecessor : current.cfgPredecessors()) {
1446 if (predecessor instanceof LoopExitNode) {
1447 /*
1448 * Inner loop. We do not need to mark every node of it, instead we just continue
1449 * marking at the loop header.
1450 */
1451 LoopBeginNode innerLoopBegin = ((LoopExitNode) predecessor).loopBegin();
1452 if (!visited.isMarked(innerLoopBegin)) {
1453 stack.push(innerLoopBegin);
1454 visited.mark(innerLoopBegin);
1455
1456 /*
1457 * All loop exits of the inner loop possibly need a LoopExit of our loop.
1458 * Because we are processing inner loops first, we are guaranteed to already
1459 * have all exits of the inner loop.
1460 */
1461 for (LoopExitNode exit : innerLoopBegin.loopExits()) {
1462 possibleExits.add(exit);
1463 }
1464 }
1465
1466 } else if (!visited.isMarked(predecessor)) {
1467 stack.push(predecessor);
1468 visited.mark(predecessor);
1469
1470 if (predecessor instanceof ControlSplitNode) {
1471 for (Node succ : predecessor.cfgSuccessors()) {
1472 /*
1473 * We would not need to mark the current node, and would not need to
1474 * mark visited nodes. But it is easier to just mark everything, since
1475 * we subtract all visited nodes in the end anyway. Note that at this
1476 * point we do not have the complete visited information, so we would
1477 * always mark too many possible exits.
1478 */
1479 possibleExits.add(succ);
1480 }
1481 }
1482 }
1483 }
1484 }
1485
1486 /*
1487 * Now we know all the actual loop exits. Ideally, we would insert LoopExit nodes for them.
1488 * However, a LoopExit needs a valid FrameState that captures the state at the point where
1489 * we exit the loop. During graph decoding, we create a FrameState for every exploded loop
1490 * iteration. We need to do a forward marking until we hit the next such point. This puts
1491 * some nodes into the loop that are actually not part of the loop.
1492 *
1493 * In some cases, we did not create a FrameState during graph decoding: when there was no
1494 * LoopExit in the original loop that we exploded. This happens for code paths that lead
1495 * immediately to a DeoptimizeNode.
1496 *
1497 * Both cases mimic the behavior of the BytecodeParser, which also puts more nodes than
1498 * necessary into a loop because it computes loop information based on bytecodes, before the
1499 * actual parsing.
1500 */
1501
1502 for (Node succ : possibleExits) {
1503 if (!visited.contains(succ)) {
1504 stack.push(succ);
1505 visited.mark(succ);
1506 assert !methodScope.loopExplosionMerges.contains(succ);
1507 }
1508 }
1509
1510 while (!stack.isEmpty()) {
1511 Node current = stack.pop();
1512 assert visited.isMarked(current);
1513 assert current instanceof ControlSinkNode || current instanceof LoopEndNode || current.cfgSuccessors().iterator().hasNext() : "Must not reach a node that has not been decoded yet";
1514
1515 for (Node successor : current.cfgSuccessors()) {
1516 if (visited.isMarked(successor)) {
1517 /* Already processed this successor. */
1518
1519 } else if (methodScope.loopExplosionMerges.contains(successor)) {
1520 /*
1521 * We have a FrameState for the successor. The LoopExit will be inserted between
1522 * the current node and the successor node. Since the successor node is a
1523 * MergeNode, the current node mus be a AbstractEndNode with only that MergeNode
1524 * as the successor.
1525 */
1526 assert successor instanceof MergeNode;
1527 assert !loop.exits.contains(current);
1528 loop.exits.add((AbstractEndNode) current);
1529
1530 } else {
1531 /* Node we have not seen yet. */
1532 visited.mark(successor);
1533 stack.push(successor);
1534 }
1535 }
1536 }
1537 }
1538
1539 private void insertLoopNodes(Loop loop) {
1570 }
1571
1572 for (EndNode endNode : loop.ends) {
1573 for (int i = 0; i < mergePhis.size(); i++) {
1574 PhiNode mergePhi = mergePhis.get(i);
1575 PhiNode loopBeginPhi = loopBeginPhis.get(i);
1576 loopBeginPhi.addInput(mergePhi.valueAt(endNode));
1577 }
1578
1579 merge.removeEnd(endNode);
1580 LoopEndNode loopEnd = methodScope.graph.add(new LoopEndNode(loopBegin));
1581 endNode.replaceAndDelete(loopEnd);
1582 }
1583
1584 /*
1585 * Insert the LoopExit nodes (the easy part) and compute the FrameState for the new exits
1586 * (the difficult part).
1587 */
1588 for (AbstractEndNode exit : loop.exits) {
1589 AbstractMergeNode loopExplosionMerge = exit.merge();
1590 assert methodScope.loopExplosionMerges.contains(loopExplosionMerge);
1591
1592 LoopExitNode loopExit = methodScope.graph.add(new LoopExitNode(loopBegin));
1593 exit.replaceAtPredecessor(loopExit);
1594 loopExit.setNext(exit);
1595 assignLoopExitState(loopExit, loopExplosionMerge, exit);
1596 }
1597 }
1598
1599 /**
1600 * During graph decoding, we create a FrameState for every exploded loop iteration. This is
1601 * mostly the state that we want, we only need to tweak it a little bit: we need to insert the
1602 * appropriate ProxyNodes for all values that are created inside the loop and that flow out of
1603 * the loop.
1604 */
1605 private void assignLoopExitState(LoopExitNode loopExit, AbstractMergeNode loopExplosionMerge, AbstractEndNode loopExplosionEnd) {
1606 FrameState oldState = loopExplosionMerge.stateAfter();
1607
1608 /* Collect all nodes that are in the FrameState at the LoopBegin. */
1609 EconomicSet<Node> loopBeginValues = EconomicSet.create(Equivalence.IDENTITY);
1610 for (FrameState state = loopExit.loopBegin().stateAfter(); state != null; state = state.outerFrameState()) {
1611 for (ValueNode value : state.values()) {
1612 if (value != null && !value.isConstant() && !loopExit.loopBegin().isPhiAtMerge(value)) {
1613 loopBeginValues.add(ProxyPlaceholder.unwrap(value));
1614 }
1615 }
1616 }
1617
1618 List<ValueNode> newValues = new ArrayList<>(oldState.values().size());
1619 for (ValueNode v : oldState.values()) {
1620 ValueNode value = v;
1621 ValueNode realValue = ProxyPlaceholder.unwrap(value);
1622
1623 /*
1624 * The LoopExit is inserted before the existing merge, i.e., separately for every branch
1625 * that leads to the merge. So for phi functions of the merge, we need to take the input
1626 * that corresponds to our branch.
1627 */
1628 if (realValue instanceof PhiNode && loopExplosionMerge.isPhiAtMerge(realValue)) {
1629 value = ((PhiNode) realValue).valueAt(loopExplosionEnd);
1630 realValue = ProxyPlaceholder.unwrap(value);
1631 }
1632
1633 if (realValue == null || realValue.isConstant() || loopBeginValues.contains(realValue) || !methodScope.graph.isNew(methodScope.methodStartMark, realValue)) {
|