| /* |
| * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| package org.graalvm.compiler.nodes; |
| |
| import static org.graalvm.compiler.debug.GraalError.shouldNotReachHere; |
| import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED; |
| import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED; |
| |
| import java.util.ArrayDeque; |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.BitSet; |
| import java.util.Deque; |
| import java.util.HashMap; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.SortedMap; |
| import java.util.TreeMap; |
| |
| import org.graalvm.compiler.common.PermanentBailoutException; |
| import org.graalvm.compiler.core.common.Fields; |
| import org.graalvm.compiler.core.common.util.TypeReader; |
| import org.graalvm.compiler.core.common.util.UnsafeArrayTypeReader; |
| import org.graalvm.compiler.debug.Debug; |
| import org.graalvm.compiler.debug.GraalError; |
| import org.graalvm.compiler.graph.Edges; |
| import org.graalvm.compiler.graph.Graph; |
| import org.graalvm.compiler.graph.Node; |
| import org.graalvm.compiler.graph.NodeBitMap; |
| import org.graalvm.compiler.graph.NodeClass; |
| import org.graalvm.compiler.graph.NodeInputList; |
| import org.graalvm.compiler.graph.NodeList; |
| import org.graalvm.compiler.graph.NodeSourcePosition; |
| import org.graalvm.compiler.graph.NodeSuccessorList; |
| import org.graalvm.compiler.graph.spi.Canonicalizable; |
| import org.graalvm.compiler.graph.spi.CanonicalizerTool; |
| import org.graalvm.compiler.nodeinfo.InputType; |
| import org.graalvm.compiler.nodeinfo.NodeInfo; |
| import org.graalvm.compiler.nodes.GraphDecoder.MethodScope; |
| import org.graalvm.compiler.nodes.GraphDecoder.ProxyPlaceholder; |
| import org.graalvm.compiler.nodes.calc.FloatingNode; |
| import org.graalvm.compiler.nodes.extended.IntegerSwitchNode; |
| import org.graalvm.compiler.nodes.graphbuilderconf.LoopExplosionPlugin.LoopExplosionKind; |
| |
| import jdk.vm.ci.code.Architecture; |
| import jdk.vm.ci.meta.DeoptimizationAction; |
| import jdk.vm.ci.meta.DeoptimizationReason; |
| import jdk.vm.ci.meta.JavaConstant; |
| import jdk.vm.ci.meta.JavaKind; |
| import jdk.vm.ci.meta.PrimitiveConstant; |
| import jdk.vm.ci.meta.ResolvedJavaType; |
| |
| /** |
| * Decoder for {@link EncodedGraph encoded graphs} produced by {@link GraphEncoder}. Support for |
| * loop explosion during decoding is built into this class, because it requires many interactions |
| * with the decoding process. Subclasses can provide canonicalization and simplification of nodes |
| * during decoding, as well as method inlining during decoding. |
| */ |
| public class GraphDecoder { |
| |
| /** Decoding state maintained for each encoded graph. */ |
| protected class MethodScope { |
| /** The loop that contains the call. Only non-null during method inlining. */ |
| public final LoopScope callerLoopScope; |
| /** The target graph where decoded nodes are added to. */ |
| public final StructuredGraph graph; |
| /** |
| * Mark for nodes that were present before the decoding of this method started. Note that |
| * nodes that were decoded after the mark can still be part of an outer method, since |
| * floating nodes of outer methods are decoded lazily. |
| */ |
| public final Graph.Mark methodStartMark; |
| /** The encode graph that is decoded. */ |
| public final EncodedGraph encodedGraph; |
| /** Access to the encoded graph. */ |
| public final TypeReader reader; |
| /** The kind of loop explosion to be performed during decoding. */ |
| public final LoopExplosionKind loopExplosion; |
| /** A list of tasks to run before the method scope is closed. */ |
| public final List<Runnable> cleanupTasks; |
| |
| /** All return nodes encountered during decoding. */ |
| public final List<ReturnNode> returnNodes; |
| /** The exception unwind node encountered during decoding, or null. */ |
| public final List<UnwindNode> unwindNodes; |
| |
| /** All merges created during loop explosion. */ |
| public final NodeBitMap loopExplosionMerges; |
| /** |
| * The start of explosion, and the merge point for when irreducible loops are detected. Only |
| * used when {@link MethodScope#loopExplosion} is {@link LoopExplosionKind#MERGE_EXPLODE}. |
| */ |
| public MergeNode loopExplosionHead; |
| |
| protected MethodScope(LoopScope callerLoopScope, StructuredGraph graph, EncodedGraph encodedGraph, LoopExplosionKind loopExplosion) { |
| this.callerLoopScope = callerLoopScope; |
| this.graph = graph; |
| this.methodStartMark = graph.getMark(); |
| this.encodedGraph = encodedGraph; |
| this.loopExplosion = loopExplosion; |
| this.cleanupTasks = new ArrayList<>(); |
| this.returnNodes = new ArrayList<>(); |
| this.unwindNodes = new ArrayList<>(); |
| |
| if (encodedGraph != null) { |
| reader = UnsafeArrayTypeReader.create(encodedGraph.getEncoding(), encodedGraph.getStartOffset(), architecture.supportsUnalignedMemoryAccess()); |
| if (encodedGraph.nodeStartOffsets == null) { |
| int nodeCount = reader.getUVInt(); |
| long[] nodeStartOffsets = new long[nodeCount]; |
| for (int i = 0; i < nodeCount; i++) { |
| nodeStartOffsets[i] = encodedGraph.getStartOffset() - reader.getUV(); |
| } |
| encodedGraph.nodeStartOffsets = nodeStartOffsets; |
| } |
| } else { |
| reader = null; |
| } |
| |
| if (loopExplosion != LoopExplosionKind.NONE) { |
| loopExplosionMerges = new NodeBitMap(graph); |
| } else { |
| loopExplosionMerges = null; |
| } |
| } |
| } |
| |
| /** Decoding state maintained for each loop in the encoded graph. */ |
| protected static class LoopScope { |
| public final MethodScope methodScope; |
| public final LoopScope outer; |
| public final int loopDepth; |
| public final int loopIteration; |
| /** |
| * Upcoming loop iterations during loop explosions that have not been processed yet. Only |
| * used when {@link MethodScope#loopExplosion} is not {@link LoopExplosionKind#NONE}. |
| */ |
| public Deque<LoopScope> nextIterations; |
| /** |
| * Information about already processed loop iterations for state merging during loop |
| * explosion. Only used when {@link MethodScope#loopExplosion} is |
| * {@link LoopExplosionKind#MERGE_EXPLODE}. |
| */ |
| public final Map<LoopExplosionState, LoopExplosionState> iterationStates; |
| public final int loopBeginOrderId; |
| /** |
| * The worklist of fixed nodes to process. Since we already the correct processing order |
| * from the orderId, we just set the orderId bit in the bitset when a node is ready for |
| * processing. The lowest set bit is the next node to process. |
| */ |
| public final BitSet nodesToProcess; |
| /** Nodes that have been created, indexed by the orderId. */ |
| public final Node[] createdNodes; |
| /** |
| * Nodes that have been created in outer loop scopes and existed before starting to process |
| * this loop, indexed by the orderId. |
| */ |
| public final Node[] initialCreatedNodes; |
| |
| protected LoopScope(MethodScope methodScope) { |
| this.methodScope = methodScope; |
| this.outer = null; |
| this.nextIterations = methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN ? new ArrayDeque<>() : null; |
| this.loopDepth = 0; |
| this.loopIteration = 0; |
| this.iterationStates = null; |
| this.loopBeginOrderId = -1; |
| |
| int nodeCount = methodScope.encodedGraph.nodeStartOffsets.length; |
| this.nodesToProcess = new BitSet(nodeCount); |
| this.initialCreatedNodes = new Node[nodeCount]; |
| this.createdNodes = new Node[nodeCount]; |
| } |
| |
| protected LoopScope(MethodScope methodScope, LoopScope outer, int loopDepth, int loopIteration, int loopBeginOrderId, Node[] initialCreatedNodes, Node[] createdNodes, |
| Deque<LoopScope> nextIterations, Map<LoopExplosionState, LoopExplosionState> iterationStates) { |
| this.methodScope = methodScope; |
| this.outer = outer; |
| this.loopDepth = loopDepth; |
| this.loopIteration = loopIteration; |
| this.nextIterations = nextIterations; |
| this.iterationStates = iterationStates; |
| this.loopBeginOrderId = loopBeginOrderId; |
| this.nodesToProcess = new BitSet(initialCreatedNodes.length); |
| this.initialCreatedNodes = initialCreatedNodes; |
| this.createdNodes = Arrays.copyOf(createdNodes, createdNodes.length); |
| } |
| |
| @Override |
| public String toString() { |
| return loopDepth + "," + loopIteration + (loopBeginOrderId == -1 ? "" : "#" + loopBeginOrderId); |
| } |
| } |
| |
| protected static class LoopExplosionState { |
| public final FrameState state; |
| public final MergeNode merge; |
| public final int hashCode; |
| |
| protected LoopExplosionState(FrameState state, MergeNode merge) { |
| this.state = state; |
| this.merge = merge; |
| |
| int h = 0; |
| for (ValueNode value : state.values()) { |
| if (value == null) { |
| h = h * 31 + 1234; |
| } else { |
| h = h * 31 + ProxyPlaceholder.unwrap(value).hashCode(); |
| } |
| } |
| this.hashCode = h; |
| } |
| |
| @Override |
| public boolean equals(Object obj) { |
| if (!(obj instanceof LoopExplosionState)) { |
| return false; |
| } |
| |
| FrameState otherState = ((LoopExplosionState) obj).state; |
| FrameState thisState = state; |
| assert thisState.outerFrameState() == otherState.outerFrameState(); |
| |
| Iterator<ValueNode> thisIter = thisState.values().iterator(); |
| Iterator<ValueNode> otherIter = otherState.values().iterator(); |
| while (thisIter.hasNext() && otherIter.hasNext()) { |
| ValueNode thisValue = ProxyPlaceholder.unwrap(thisIter.next()); |
| ValueNode otherValue = ProxyPlaceholder.unwrap(otherIter.next()); |
| if (thisValue != otherValue) { |
| return false; |
| } |
| } |
| return thisIter.hasNext() == otherIter.hasNext(); |
| } |
| |
| @Override |
| public int hashCode() { |
| return hashCode; |
| } |
| } |
| |
| /** |
| * Additional information encoded for {@link Invoke} nodes to allow method inlining without |
| * decoding the frame state and successors beforehand. |
| */ |
| protected static class InvokeData { |
| public final Invoke invoke; |
| public final ResolvedJavaType contextType; |
| public final int invokeOrderId; |
| public final int callTargetOrderId; |
| public final int stateAfterOrderId; |
| public final int nextOrderId; |
| |
| public final int nextNextOrderId; |
| public final int exceptionOrderId; |
| public final int exceptionStateOrderId; |
| public final int exceptionNextOrderId; |
| public JavaConstant constantReceiver; |
| |
| protected InvokeData(Invoke invoke, ResolvedJavaType contextType, int invokeOrderId, int callTargetOrderId, int stateAfterOrderId, int nextOrderId, int nextNextOrderId, int exceptionOrderId, |
| int exceptionStateOrderId, int exceptionNextOrderId) { |
| this.invoke = invoke; |
| this.contextType = contextType; |
| this.invokeOrderId = invokeOrderId; |
| this.callTargetOrderId = callTargetOrderId; |
| this.stateAfterOrderId = stateAfterOrderId; |
| this.nextOrderId = nextOrderId; |
| this.nextNextOrderId = nextNextOrderId; |
| this.exceptionOrderId = exceptionOrderId; |
| this.exceptionStateOrderId = exceptionStateOrderId; |
| this.exceptionNextOrderId = exceptionNextOrderId; |
| } |
| } |
| |
| /** |
| * A node that is created during {@link LoopExplosionKind#MERGE_EXPLODE loop explosion} that can |
| * later be replaced by a ProxyNode if {@link LoopDetector loop detection} finds out that the |
| * value is defined in the loop, but used outside the loop. |
| */ |
| @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED) |
| protected static final class ProxyPlaceholder extends FloatingNode implements Canonicalizable { |
| public static final NodeClass<ProxyPlaceholder> TYPE = NodeClass.create(ProxyPlaceholder.class); |
| |
| @Input ValueNode value; |
| @Input(InputType.Unchecked) Node proxyPoint; |
| |
| public ProxyPlaceholder(ValueNode value, MergeNode proxyPoint) { |
| super(TYPE, value.stamp()); |
| this.value = value; |
| this.proxyPoint = proxyPoint; |
| } |
| |
| void setValue(ValueNode value) { |
| updateUsages(this.value, value); |
| this.value = value; |
| } |
| |
| @Override |
| public Node canonical(CanonicalizerTool tool) { |
| if (tool.allUsagesAvailable()) { |
| /* The node is always unnecessary after graph decoding. */ |
| return value; |
| } else { |
| return this; |
| } |
| } |
| |
| public static ValueNode unwrap(ValueNode value) { |
| ValueNode result = value; |
| while (result instanceof ProxyPlaceholder) { |
| result = ((ProxyPlaceholder) result).value; |
| } |
| return result; |
| } |
| } |
| |
| protected final Architecture architecture; |
| |
| public GraphDecoder(Architecture architecture) { |
| this.architecture = architecture; |
| } |
| |
| @SuppressWarnings("try") |
| public final void decode(StructuredGraph graph, EncodedGraph encodedGraph) { |
| try (Debug.Scope scope = Debug.scope("GraphDecoder", graph)) { |
| MethodScope methodScope = new MethodScope(null, graph, encodedGraph, LoopExplosionKind.NONE); |
| decode(createInitialLoopScope(methodScope, null)); |
| cleanupGraph(methodScope); |
| assert methodScope.graph.verify(); |
| } catch (Throwable ex) { |
| Debug.handle(ex); |
| } |
| } |
| |
| protected final LoopScope createInitialLoopScope(MethodScope methodScope, FixedWithNextNode startNode) { |
| LoopScope loopScope = new LoopScope(methodScope); |
| FixedNode firstNode; |
| if (startNode != null) { |
| /* |
| * The start node of a graph can be referenced as the guard for a GuardedNode. We |
| * register the previous block node, so that such guards are correctly anchored when |
| * doing inlining during graph decoding. |
| */ |
| registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, AbstractBeginNode.prevBegin(startNode), false, false); |
| |
| firstNode = makeStubNode(methodScope, loopScope, GraphEncoder.FIRST_NODE_ORDER_ID); |
| startNode.setNext(firstNode); |
| loopScope.nodesToProcess.set(GraphEncoder.FIRST_NODE_ORDER_ID); |
| } else { |
| firstNode = methodScope.graph.start(); |
| registerNode(loopScope, GraphEncoder.START_NODE_ORDER_ID, firstNode, false, false); |
| loopScope.nodesToProcess.set(GraphEncoder.START_NODE_ORDER_ID); |
| } |
| |
| if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { |
| methodScope.cleanupTasks.add(new LoopDetector(methodScope, startNode)); |
| } |
| return loopScope; |
| } |
| |
| protected final void decode(LoopScope initialLoopScope) { |
| LoopScope loopScope = initialLoopScope; |
| /* Process inlined methods. */ |
| while (loopScope != null) { |
| MethodScope methodScope = loopScope.methodScope; |
| |
| /* Process loops of method. */ |
| while (loopScope != null) { |
| |
| /* Process nodes of loop. */ |
| while (!loopScope.nodesToProcess.isEmpty()) { |
| loopScope = processNextNode(methodScope, loopScope); |
| methodScope = loopScope.methodScope; |
| /* |
| * We can have entered a new loop, and we can have entered a new inlined method. |
| */ |
| } |
| |
| /* Finished with a loop. */ |
| if (loopScope.nextIterations != null && !loopScope.nextIterations.isEmpty()) { |
| /* Loop explosion: process the loop iteration. */ |
| assert loopScope.nextIterations.peekFirst().loopIteration == loopScope.loopIteration + 1; |
| loopScope = loopScope.nextIterations.removeFirst(); |
| } else { |
| propagateCreatedNodes(loopScope); |
| loopScope = loopScope.outer; |
| } |
| } |
| |
| /* |
| * Finished with an inlined method. Perform all registered end-of-method cleanup tasks |
| * and continue with loop that contained the call. |
| */ |
| for (Runnable task : methodScope.cleanupTasks) { |
| task.run(); |
| } |
| loopScope = methodScope.callerLoopScope; |
| } |
| } |
| |
| private static void propagateCreatedNodes(LoopScope loopScope) { |
| if (loopScope.outer == null) { |
| return; |
| } |
| |
| /* Register nodes that were created while decoding the loop to the outside scope. */ |
| for (int i = 0; i < loopScope.createdNodes.length; i++) { |
| if (loopScope.outer.createdNodes[i] == null) { |
| loopScope.outer.createdNodes[i] = loopScope.createdNodes[i]; |
| } |
| } |
| } |
| |
| protected LoopScope processNextNode(MethodScope methodScope, LoopScope loopScope) { |
| int nodeOrderId = loopScope.nodesToProcess.nextSetBit(0); |
| loopScope.nodesToProcess.clear(nodeOrderId); |
| |
| FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId); |
| if (node.isDeleted()) { |
| return loopScope; |
| } |
| |
| if ((node instanceof MergeNode || |
| (node instanceof LoopBeginNode && (methodScope.loopExplosion == LoopExplosionKind.FULL_UNROLL || methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE || |
| methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN))) && |
| ((AbstractMergeNode) node).forwardEndCount() == 1) { |
| AbstractMergeNode merge = (AbstractMergeNode) node; |
| EndNode singleEnd = merge.forwardEndAt(0); |
| |
| /* Nodes that would use this merge as the guard need to use the previous block. */ |
| registerNode(loopScope, nodeOrderId, AbstractBeginNode.prevBegin(singleEnd), true, false); |
| |
| FixedNode next = makeStubNode(methodScope, loopScope, nodeOrderId + GraphEncoder.BEGIN_NEXT_ORDER_ID_OFFSET); |
| singleEnd.replaceAtPredecessor(next); |
| |
| merge.safeDelete(); |
| singleEnd.safeDelete(); |
| return loopScope; |
| } |
| |
| LoopScope successorAddScope = loopScope; |
| boolean updatePredecessors = true; |
| if (node instanceof LoopExitNode) { |
| if (methodScope.loopExplosion == LoopExplosionKind.FULL_EXPLODE_UNTIL_RETURN || (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE && loopScope.loopDepth > 1)) { |
| /* |
| * We do not want to merge loop exits of inner loops. Instead, we want to keep |
| * exploding the outer loop separately for every loop exit and then merge the outer |
| * loop. Therefore, we create a new LoopScope of the outer loop for every loop exit |
| * of the inner loop. |
| */ |
| LoopScope outerScope = loopScope.outer; |
| int nextIterationNumber = outerScope.nextIterations.isEmpty() ? outerScope.loopIteration + 1 : outerScope.nextIterations.getLast().loopIteration + 1; |
| successorAddScope = new LoopScope(methodScope, outerScope.outer, outerScope.loopDepth, nextIterationNumber, outerScope.loopBeginOrderId, outerScope.initialCreatedNodes, |
| loopScope.initialCreatedNodes, outerScope.nextIterations, outerScope.iterationStates); |
| checkLoopExplosionIteration(methodScope, successorAddScope); |
| |
| /* |
| * Nodes that are still unprocessed in the outer scope might be merge nodes that are |
| * also reachable from the new exploded scope. Clearing them ensures that we do not |
| * merge, but instead keep exploding. |
| */ |
| for (int id = outerScope.nodesToProcess.nextSetBit(0); id >= 0; id = outerScope.nodesToProcess.nextSetBit(id + 1)) { |
| successorAddScope.createdNodes[id] = null; |
| } |
| |
| outerScope.nextIterations.addLast(successorAddScope); |
| } else { |
| successorAddScope = loopScope.outer; |
| } |
| updatePredecessors = methodScope.loopExplosion == LoopExplosionKind.NONE; |
| } |
| |
| methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]); |
| int typeId = methodScope.reader.getUVInt(); |
| assert node.getNodeClass() == methodScope.encodedGraph.getNodeClasses()[typeId]; |
| readProperties(methodScope, node); |
| makeSuccessorStubs(methodScope, successorAddScope, node, updatePredecessors); |
| makeInputNodes(methodScope, loopScope, node, true); |
| |
| LoopScope resultScope = loopScope; |
| if (node instanceof LoopBeginNode) { |
| if (methodScope.loopExplosion != LoopExplosionKind.NONE) { |
| handleLoopExplosionBegin(methodScope, loopScope, (LoopBeginNode) node); |
| } |
| |
| } else if (node instanceof LoopExitNode) { |
| if (methodScope.loopExplosion != LoopExplosionKind.NONE) { |
| handleLoopExplosionProxyNodes(methodScope, loopScope, successorAddScope, (LoopExitNode) node, nodeOrderId); |
| } else { |
| handleProxyNodes(methodScope, loopScope, (LoopExitNode) node); |
| } |
| |
| } else if (node instanceof MergeNode) { |
| handleMergeNode(((MergeNode) node)); |
| |
| } else if (node instanceof AbstractEndNode) { |
| LoopScope phiInputScope = loopScope; |
| LoopScope phiNodeScope = loopScope; |
| |
| if (methodScope.loopExplosion != LoopExplosionKind.NONE && node instanceof LoopEndNode) { |
| node = handleLoopExplosionEnd(methodScope, loopScope, (LoopEndNode) node); |
| phiNodeScope = loopScope.nextIterations.getLast(); |
| } |
| |
| int mergeOrderId = readOrderId(methodScope); |
| AbstractMergeNode merge = (AbstractMergeNode) lookupNode(phiNodeScope, mergeOrderId); |
| if (merge == null) { |
| merge = (AbstractMergeNode) makeStubNode(methodScope, phiNodeScope, mergeOrderId); |
| |
| if (merge instanceof LoopBeginNode) { |
| assert phiNodeScope == phiInputScope && phiNodeScope == loopScope; |
| resultScope = new LoopScope(methodScope, loopScope, loopScope.loopDepth + 1, 0, mergeOrderId, |
| Arrays.copyOf(loopScope.createdNodes, loopScope.createdNodes.length), loopScope.createdNodes, // |
| methodScope.loopExplosion != LoopExplosionKind.NONE ? new ArrayDeque<>() : null, // |
| methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE ? new HashMap<>() : null); |
| phiInputScope = resultScope; |
| phiNodeScope = resultScope; |
| |
| registerNode(loopScope, mergeOrderId, null, true, true); |
| loopScope.nodesToProcess.clear(mergeOrderId); |
| resultScope.nodesToProcess.set(mergeOrderId); |
| } |
| } |
| |
| handlePhiFunctions(methodScope, phiInputScope, phiNodeScope, (AbstractEndNode) node, merge); |
| |
| } else if (node instanceof Invoke) { |
| InvokeData invokeData = readInvokeData(methodScope, nodeOrderId, (Invoke) node); |
| resultScope = handleInvoke(methodScope, loopScope, invokeData); |
| |
| } else if (node instanceof ReturnNode) { |
| methodScope.returnNodes.add((ReturnNode) node); |
| } else if (node instanceof UnwindNode) { |
| methodScope.unwindNodes.add((UnwindNode) node); |
| |
| } else { |
| handleFixedNode(methodScope, loopScope, nodeOrderId, node); |
| } |
| |
| return resultScope; |
| } |
| |
| private InvokeData readInvokeData(MethodScope methodScope, int invokeOrderId, Invoke invoke) { |
| ResolvedJavaType contextType = (ResolvedJavaType) readObject(methodScope); |
| int callTargetOrderId = readOrderId(methodScope); |
| int stateAfterOrderId = readOrderId(methodScope); |
| int nextOrderId = readOrderId(methodScope); |
| |
| if (invoke instanceof InvokeWithExceptionNode) { |
| int nextNextOrderId = readOrderId(methodScope); |
| int exceptionOrderId = readOrderId(methodScope); |
| int exceptionStateOrderId = readOrderId(methodScope); |
| int exceptionNextOrderId = readOrderId(methodScope); |
| return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, nextNextOrderId, exceptionOrderId, exceptionStateOrderId, |
| exceptionNextOrderId); |
| } else { |
| return new InvokeData(invoke, contextType, invokeOrderId, callTargetOrderId, stateAfterOrderId, nextOrderId, -1, -1, -1, -1); |
| } |
| } |
| |
| /** |
| * {@link Invoke} nodes do not have the {@link CallTargetNode}, {@link FrameState}, and |
| * successors encoded. Instead, this information is provided separately to allow method inlining |
| * without decoding and adding them to the graph upfront. For non-inlined methods, this method |
| * restores the normal state. Subclasses can override it to perform method inlining. |
| * |
| * The return value is the loop scope where decoding should continue. When method inlining |
| * should be performed, the returned loop scope must be a new loop scope for the inlined method. |
| * Without inlining, the original loop scope must be returned. |
| */ |
| protected LoopScope handleInvoke(MethodScope methodScope, LoopScope loopScope, InvokeData invokeData) { |
| assert invokeData.invoke.callTarget() == null : "callTarget edge is ignored during decoding of Invoke"; |
| CallTargetNode callTarget = (CallTargetNode) ensureNodeCreated(methodScope, loopScope, invokeData.callTargetOrderId); |
| if (invokeData.invoke instanceof InvokeWithExceptionNode) { |
| ((InvokeWithExceptionNode) invokeData.invoke).setCallTarget(callTarget); |
| } else { |
| ((InvokeNode) invokeData.invoke).setCallTarget(callTarget); |
| } |
| |
| assert invokeData.invoke.stateAfter() == null && invokeData.invoke.stateDuring() == null : "FrameState edges are ignored during decoding of Invoke"; |
| invokeData.invoke.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, invokeData.stateAfterOrderId)); |
| |
| invokeData.invoke.setNext(makeStubNode(methodScope, loopScope, invokeData.nextOrderId)); |
| if (invokeData.invoke instanceof InvokeWithExceptionNode) { |
| ((InvokeWithExceptionNode) invokeData.invoke).setExceptionEdge((AbstractBeginNode) makeStubNode(methodScope, loopScope, invokeData.exceptionOrderId)); |
| } |
| return loopScope; |
| } |
| |
| /** |
| * Hook for subclasses to perform simplifications for a non-loop-header control flow merge. |
| * |
| * @param merge The control flow merge. |
| */ |
| protected void handleMergeNode(MergeNode merge) { |
| } |
| |
| protected void handleLoopExplosionBegin(MethodScope methodScope, LoopScope loopScope, LoopBeginNode loopBegin) { |
| checkLoopExplosionIteration(methodScope, loopScope); |
| |
| List<EndNode> predecessors = loopBegin.forwardEnds().snapshot(); |
| FixedNode successor = loopBegin.next(); |
| FrameState frameState = loopBegin.stateAfter(); |
| |
| if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { |
| LoopExplosionState queryState = new LoopExplosionState(frameState, null); |
| LoopExplosionState existingState = loopScope.iterationStates.get(queryState); |
| if (existingState != null) { |
| loopBegin.replaceAtUsagesAndDelete(existingState.merge); |
| successor.safeDelete(); |
| for (EndNode predecessor : predecessors) { |
| existingState.merge.addForwardEnd(predecessor); |
| } |
| return; |
| } |
| } |
| |
| MergeNode merge = methodScope.graph.add(new MergeNode()); |
| methodScope.loopExplosionMerges.markAndGrow(merge); |
| |
| if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { |
| if (loopScope.iterationStates.size() == 0 && loopScope.loopDepth == 1) { |
| if (methodScope.loopExplosionHead != null) { |
| throw new PermanentBailoutException("Graal implementation restriction: Method with %s loop explosion must not have more than one top-level loop", LoopExplosionKind.MERGE_EXPLODE); |
| } |
| methodScope.loopExplosionHead = merge; |
| } |
| |
| List<ValueNode> newFrameStateValues = new ArrayList<>(); |
| for (ValueNode frameStateValue : frameState.values) { |
| if (frameStateValue == null || frameStateValue.isConstant() || !methodScope.graph.isNew(methodScope.methodStartMark, frameStateValue)) { |
| newFrameStateValues.add(frameStateValue); |
| |
| } else { |
| ProxyPlaceholder newFrameStateValue = methodScope.graph.unique(new ProxyPlaceholder(frameStateValue, merge)); |
| newFrameStateValues.add(newFrameStateValue); |
| |
| /* |
| * We do not have the orderID of the value anymore, so we need to search through |
| * the complete list of nodes to find a match. |
| */ |
| for (int i = 0; i < loopScope.createdNodes.length; i++) { |
| if (loopScope.createdNodes[i] == frameStateValue) { |
| loopScope.createdNodes[i] = newFrameStateValue; |
| } |
| if (loopScope.initialCreatedNodes[i] == frameStateValue) { |
| loopScope.initialCreatedNodes[i] = newFrameStateValue; |
| } |
| } |
| } |
| } |
| |
| FrameState newFrameState = methodScope.graph.add(new FrameState(frameState.outerFrameState(), frameState.getCode(), frameState.bci, newFrameStateValues, frameState.localsSize(), |
| frameState.stackSize(), frameState.rethrowException(), frameState.duringCall(), frameState.monitorIds(), frameState.virtualObjectMappings())); |
| |
| frameState.replaceAtUsages(newFrameState); |
| frameState.safeDelete(); |
| frameState = newFrameState; |
| } |
| |
| loopBegin.replaceAtUsagesAndDelete(merge); |
| merge.setStateAfter(frameState); |
| merge.setNext(successor); |
| for (EndNode predecessor : predecessors) { |
| merge.addForwardEnd(predecessor); |
| } |
| |
| if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { |
| LoopExplosionState explosionState = new LoopExplosionState(frameState, merge); |
| loopScope.iterationStates.put(explosionState, explosionState); |
| } |
| } |
| |
| /** |
| * Hook for subclasses. |
| * |
| * @param methodScope The current method. |
| * @param loopScope The current loop. |
| */ |
| protected void checkLoopExplosionIteration(MethodScope methodScope, LoopScope loopScope) { |
| throw shouldNotReachHere("when subclass uses loop explosion, it needs to implement this method"); |
| } |
| |
| protected FixedNode handleLoopExplosionEnd(MethodScope methodScope, LoopScope loopScope, LoopEndNode loopEnd) { |
| EndNode replacementNode = methodScope.graph.add(new EndNode()); |
| loopEnd.replaceAtPredecessor(replacementNode); |
| loopEnd.safeDelete(); |
| |
| assert methodScope.loopExplosion != LoopExplosionKind.NONE; |
| if (methodScope.loopExplosion != LoopExplosionKind.FULL_UNROLL || loopScope.nextIterations.isEmpty()) { |
| int nextIterationNumber = loopScope.nextIterations.isEmpty() ? loopScope.loopIteration + 1 : loopScope.nextIterations.getLast().loopIteration + 1; |
| LoopScope nextIterationScope = new LoopScope(methodScope, loopScope.outer, loopScope.loopDepth, nextIterationNumber, loopScope.loopBeginOrderId, loopScope.initialCreatedNodes, |
| loopScope.initialCreatedNodes, loopScope.nextIterations, loopScope.iterationStates); |
| checkLoopExplosionIteration(methodScope, nextIterationScope); |
| loopScope.nextIterations.addLast(nextIterationScope); |
| registerNode(nextIterationScope, loopScope.loopBeginOrderId, null, true, true); |
| makeStubNode(methodScope, nextIterationScope, loopScope.loopBeginOrderId); |
| } |
| return replacementNode; |
| } |
| |
| /** |
| * Hook for subclasses. |
| * |
| * @param methodScope The current method. |
| * @param loopScope The current loop. |
| * @param nodeOrderId The orderId of the node. |
| * @param node The node to be simplified. |
| */ |
| protected void handleFixedNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId, FixedNode node) { |
| } |
| |
| protected void handleProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopExitNode loopExit) { |
| assert loopExit.stateAfter() == null; |
| int stateAfterOrderId = readOrderId(methodScope); |
| loopExit.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, stateAfterOrderId)); |
| |
| int numProxies = methodScope.reader.getUVInt(); |
| for (int i = 0; i < numProxies; i++) { |
| int proxyOrderId = readOrderId(methodScope); |
| ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId); |
| /* |
| * The ProxyNode transports a value from the loop to the outer scope. We therefore |
| * register it in the outer scope. |
| */ |
| registerNode(loopScope.outer, proxyOrderId, proxy, false, false); |
| } |
| } |
| |
| protected void handleLoopExplosionProxyNodes(MethodScope methodScope, LoopScope loopScope, LoopScope outerScope, LoopExitNode loopExit, int loopExitOrderId) { |
| assert loopExit.stateAfter() == null; |
| int stateAfterOrderId = readOrderId(methodScope); |
| |
| BeginNode begin = methodScope.graph.add(new BeginNode()); |
| |
| FixedNode loopExitSuccessor = loopExit.next(); |
| loopExit.replaceAtPredecessor(begin); |
| |
| MergeNode loopExitPlaceholder = null; |
| if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE && loopScope.loopDepth == 1) { |
| /* |
| * This exit might end up as a loop exit of a loop detected after partial evaluation. We |
| * need to be able to create a FrameState and the necessary proxy nodes in this case. |
| */ |
| loopExitPlaceholder = methodScope.graph.add(new MergeNode()); |
| methodScope.loopExplosionMerges.markAndGrow(loopExitPlaceholder); |
| |
| EndNode end = methodScope.graph.add(new EndNode()); |
| begin.setNext(end); |
| loopExitPlaceholder.addForwardEnd(end); |
| |
| begin = methodScope.graph.add(new BeginNode()); |
| loopExitPlaceholder.setNext(begin); |
| } |
| |
| /* |
| * In the original graph, the loop exit is not a merge node. Multiple exploded loop |
| * iterations now take the same loop exit, so we have to introduce a new merge node to |
| * handle the merge. |
| */ |
| MergeNode merge = null; |
| Node existingExit = lookupNode(outerScope, loopExitOrderId); |
| if (existingExit == null) { |
| /* First loop iteration that exits. No merge necessary yet. */ |
| registerNode(outerScope, loopExitOrderId, begin, false, false); |
| begin.setNext(loopExitSuccessor); |
| |
| } else if (existingExit instanceof BeginNode) { |
| /* Second loop iteration that exits. Create the merge. */ |
| merge = methodScope.graph.add(new MergeNode()); |
| registerNode(outerScope, loopExitOrderId, merge, true, false); |
| /* Add the first iteration. */ |
| EndNode firstEnd = methodScope.graph.add(new EndNode()); |
| ((BeginNode) existingExit).setNext(firstEnd); |
| merge.addForwardEnd(firstEnd); |
| merge.setNext(loopExitSuccessor); |
| |
| } else { |
| /* Subsequent loop iteration. Merge already created. */ |
| merge = (MergeNode) existingExit; |
| } |
| |
| if (merge != null) { |
| EndNode end = methodScope.graph.add(new EndNode()); |
| begin.setNext(end); |
| merge.addForwardEnd(end); |
| } |
| |
| /* |
| * Possibly create phi nodes for the original proxy nodes that flow out of the loop. Note |
| * that we definitely do not need a proxy node itself anymore, since the loop was exploded |
| * and is no longer present. |
| */ |
| int numProxies = methodScope.reader.getUVInt(); |
| boolean phiCreated = false; |
| for (int i = 0; i < numProxies; i++) { |
| int proxyOrderId = readOrderId(methodScope); |
| ProxyNode proxy = (ProxyNode) ensureNodeCreated(methodScope, loopScope, proxyOrderId); |
| ValueNode phiInput = proxy.value(); |
| |
| if (loopExitPlaceholder != null) { |
| if (!phiInput.isConstant()) { |
| phiInput = methodScope.graph.unique(new ProxyPlaceholder(phiInput, loopExitPlaceholder)); |
| } |
| registerNode(loopScope, proxyOrderId, phiInput, true, false); |
| } |
| |
| ValueNode replacement; |
| ValueNode existing = (ValueNode) outerScope.createdNodes[proxyOrderId]; |
| if (existing == null || existing == phiInput) { |
| /* |
| * We are at the first loop exit, or the proxy carries the same value for all exits. |
| * We do not need a phi node yet. |
| */ |
| registerNode(outerScope, proxyOrderId, phiInput, true, false); |
| replacement = phiInput; |
| |
| } else if (!merge.isPhiAtMerge(existing)) { |
| /* Now we have two different values, so we need to create a phi node. */ |
| PhiNode phi = methodScope.graph.addWithoutUnique(new ValuePhiNode(proxy.stamp(), merge)); |
| /* Add the inputs from all previous exits. */ |
| for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) { |
| phi.addInput(existing); |
| } |
| /* Add the input from this exit. */ |
| phi.addInput(phiInput); |
| registerNode(outerScope, proxyOrderId, phi, true, false); |
| replacement = phi; |
| phiCreated = true; |
| |
| } else { |
| /* Phi node has been created before, so just add the new input. */ |
| PhiNode phi = (PhiNode) existing; |
| phi.addInput(phiInput); |
| replacement = phi; |
| } |
| |
| proxy.replaceAtUsagesAndDelete(replacement); |
| } |
| |
| if (loopExitPlaceholder != null) { |
| registerNode(loopScope, stateAfterOrderId, null, true, true); |
| loopExitPlaceholder.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, stateAfterOrderId)); |
| } |
| |
| if (merge != null && (merge.stateAfter() == null || phiCreated)) { |
| FrameState oldStateAfter = merge.stateAfter(); |
| registerNode(outerScope, stateAfterOrderId, null, true, true); |
| merge.setStateAfter((FrameState) ensureNodeCreated(methodScope, outerScope, stateAfterOrderId)); |
| if (oldStateAfter != null) { |
| oldStateAfter.safeDelete(); |
| } |
| } |
| loopExit.safeDelete(); |
| assert loopExitSuccessor.predecessor() == null; |
| if (merge != null) { |
| merge.getNodeClass().getSuccessorEdges().update(merge, null, loopExitSuccessor); |
| } else { |
| begin.getNodeClass().getSuccessorEdges().update(begin, null, loopExitSuccessor); |
| } |
| } |
| |
| protected void handlePhiFunctions(MethodScope methodScope, LoopScope phiInputScope, LoopScope phiNodeScope, AbstractEndNode end, AbstractMergeNode merge) { |
| |
| if (end instanceof LoopEndNode) { |
| /* |
| * Fix the loop end index and the number of loop ends. When we do canonicalization |
| * during decoding, we can end up with fewer ends than the encoded graph had. And the |
| * order of loop ends can be different. |
| */ |
| int numEnds = ((LoopBeginNode) merge).loopEnds().count(); |
| ((LoopBeginNode) merge).nextEndIndex = numEnds; |
| ((LoopEndNode) end).endIndex = numEnds - 1; |
| |
| } else { |
| if (merge.ends == null) { |
| merge.ends = new NodeInputList<>(merge); |
| } |
| merge.addForwardEnd((EndNode) end); |
| } |
| |
| /* |
| * We create most phi functions lazily. Canonicalization and simplification during decoding |
| * can lead to dead branches that are not decoded, so we might not need all phi functions |
| * that the original graph contained. Since we process all predecessors before actually |
| * processing the merge node, we have the final phi function when processing the merge node. |
| * The only exception are loop headers of non-exploded loops: since backward branches are |
| * not processed yet when processing the loop body, we need to create all phi functions |
| * upfront. |
| */ |
| boolean lazyPhi = allowLazyPhis() && (!(merge instanceof LoopBeginNode) || methodScope.loopExplosion != LoopExplosionKind.NONE); |
| int numPhis = methodScope.reader.getUVInt(); |
| for (int i = 0; i < numPhis; i++) { |
| int phiInputOrderId = readOrderId(methodScope); |
| int phiNodeOrderId = readOrderId(methodScope); |
| |
| ValueNode phiInput = (ValueNode) ensureNodeCreated(methodScope, phiInputScope, phiInputOrderId); |
| |
| ValueNode existing = (ValueNode) lookupNode(phiNodeScope, phiNodeOrderId); |
| if (lazyPhi && (existing == null || existing == phiInput)) { |
| /* Phi function not yet necessary. */ |
| registerNode(phiNodeScope, phiNodeOrderId, phiInput, true, false); |
| |
| } else if (!merge.isPhiAtMerge(existing)) { |
| /* |
| * Phi function is necessary. Create it and fill it with existing inputs as well as |
| * the new input. |
| */ |
| registerNode(phiNodeScope, phiNodeOrderId, null, true, true); |
| PhiNode phi = (PhiNode) ensureNodeCreated(methodScope, phiNodeScope, phiNodeOrderId); |
| |
| phi.setMerge(merge); |
| for (int j = 0; j < merge.phiPredecessorCount() - 1; j++) { |
| phi.addInput(existing); |
| } |
| phi.addInput(phiInput); |
| |
| } else { |
| /* Phi node has been created before, so just add the new input. */ |
| PhiNode phi = (PhiNode) existing; |
| phi.addInput(phiInput); |
| } |
| } |
| } |
| |
| protected boolean allowLazyPhis() { |
| /* We need to exactly reproduce the encoded graph, including unnecessary phi functions. */ |
| return false; |
| } |
| |
| protected Node instantiateNode(MethodScope methodScope, int nodeOrderId) { |
| methodScope.reader.setByteIndex(methodScope.encodedGraph.nodeStartOffsets[nodeOrderId]); |
| NodeClass<?> nodeClass = methodScope.encodedGraph.getNodeClasses()[methodScope.reader.getUVInt()]; |
| return nodeClass.allocateInstance(); |
| } |
| |
| protected void readProperties(MethodScope methodScope, Node node) { |
| node.setNodeSourcePosition((NodeSourcePosition) readObject(methodScope)); |
| Fields fields = node.getNodeClass().getData(); |
| for (int pos = 0; pos < fields.getCount(); pos++) { |
| if (fields.getType(pos).isPrimitive()) { |
| long primitive = methodScope.reader.getSV(); |
| fields.setRawPrimitive(node, pos, primitive); |
| } else { |
| Object value = readObject(methodScope); |
| fields.set(node, pos, value); |
| } |
| } |
| } |
| |
| /** |
| * Process the input edges of a node. Input nodes that have not yet been created must be |
| * non-fixed nodes (because fixed nodes are processed in reverse postorder. Such non-fixed nodes |
| * are created on demand (recursively since they can themselves reference not yet created |
| * nodes). |
| */ |
| protected void makeInputNodes(MethodScope methodScope, LoopScope loopScope, Node node, boolean updateUsages) { |
| Edges edges = node.getNodeClass().getEdges(Edges.Type.Inputs); |
| for (int index = 0; index < edges.getDirectCount(); index++) { |
| if (skipEdge(node, edges, index, true, true)) { |
| continue; |
| } |
| int orderId = readOrderId(methodScope); |
| Node value = ensureNodeCreated(methodScope, loopScope, orderId); |
| edges.initializeNode(node, index, value); |
| if (updateUsages && value != null && !value.isDeleted()) { |
| edges.update(node, null, value); |
| |
| } |
| } |
| for (int index = edges.getDirectCount(); index < edges.getCount(); index++) { |
| if (skipEdge(node, edges, index, false, true)) { |
| continue; |
| } |
| int size = methodScope.reader.getSVInt(); |
| if (size != -1) { |
| NodeList<Node> nodeList = new NodeInputList<>(node, size); |
| edges.initializeList(node, index, nodeList); |
| for (int idx = 0; idx < size; idx++) { |
| int orderId = readOrderId(methodScope); |
| Node value = ensureNodeCreated(methodScope, loopScope, orderId); |
| nodeList.initialize(idx, value); |
| if (updateUsages && value != null && !value.isDeleted()) { |
| edges.update(node, null, value); |
| } |
| } |
| } |
| } |
| } |
| |
| protected Node ensureNodeCreated(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) { |
| if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) { |
| return null; |
| } |
| Node node = lookupNode(loopScope, nodeOrderId); |
| if (node != null) { |
| return node; |
| } |
| |
| node = decodeFloatingNode(methodScope, loopScope, nodeOrderId); |
| |
| if (node instanceof ProxyNode || node instanceof PhiNode) { |
| /* |
| * We need these nodes as they were in the original graph, without any canonicalization |
| * or value numbering. |
| */ |
| node = methodScope.graph.addWithoutUnique(node); |
| } else { |
| /* Allow subclasses to canonicalize and intercept nodes. */ |
| node = handleFloatingNodeBeforeAdd(methodScope, loopScope, node); |
| if (!node.isAlive()) { |
| node = addFloatingNode(methodScope, node); |
| } |
| node = handleFloatingNodeAfterAdd(methodScope, loopScope, node); |
| } |
| registerNode(loopScope, nodeOrderId, node, false, false); |
| return node; |
| } |
| |
| protected Node addFloatingNode(MethodScope methodScope, Node node) { |
| /* |
| * We want to exactly reproduce the encoded graph. Even though nodes should be unique in the |
| * encoded graph, this is not always guaranteed. |
| */ |
| return methodScope.graph.addWithoutUnique(node); |
| } |
| |
| /** |
| * Decodes a non-fixed node, but does not do any post-processing and does not register it. |
| */ |
| protected Node decodeFloatingNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) { |
| long readerByteIndex = methodScope.reader.getByteIndex(); |
| Node node = instantiateNode(methodScope, nodeOrderId); |
| if (node instanceof FixedNode) { |
| /* |
| * This is a severe error that will lead to a corrupted graph, so it is better not to |
| * continue decoding at all. |
| */ |
| throw shouldNotReachHere("Not a floating node: " + node.getClass().getName()); |
| } |
| |
| /* Read the properties of the node. */ |
| readProperties(methodScope, node); |
| /* There must not be any successors to read, since it is a non-fixed node. */ |
| assert node.getNodeClass().getEdges(Edges.Type.Successors).getCount() == 0; |
| /* Read the inputs of the node, possibly creating them recursively. */ |
| makeInputNodes(methodScope, loopScope, node, false); |
| methodScope.reader.setByteIndex(readerByteIndex); |
| return node; |
| } |
| |
| /** |
| * Hook for subclasses to process a non-fixed node before it is added to the graph. |
| * |
| * @param methodScope The current method. |
| * @param loopScope The current loop. |
| * @param node The node to be canonicalized. |
| * @return The replacement for the node, or the node itself. |
| */ |
| protected Node handleFloatingNodeBeforeAdd(MethodScope methodScope, LoopScope loopScope, Node node) { |
| return node; |
| } |
| |
| /** |
| * Hook for subclasses to process a non-fixed node after it is added to the graph. |
| * |
| * If this method replaces a node with another node, it must update its source position if the |
| * original node has the source position set. |
| * |
| * @param methodScope The current method. |
| * @param loopScope The current loop. |
| * @param node The node to be canonicalized. |
| * @return The replacement for the node, or the node itself. |
| */ |
| protected Node handleFloatingNodeAfterAdd(MethodScope methodScope, LoopScope loopScope, Node node) { |
| return node; |
| } |
| |
| /** |
| * Process successor edges of a node. We create the successor nodes so that we can fill the |
| * successor list, but no properties or edges are loaded yet. That is done when the successor is |
| * on top of the worklist in {@link #processNextNode}. |
| */ |
| protected void makeSuccessorStubs(MethodScope methodScope, LoopScope loopScope, Node node, boolean updatePredecessors) { |
| Edges edges = node.getNodeClass().getEdges(Edges.Type.Successors); |
| for (int index = 0; index < edges.getDirectCount(); index++) { |
| if (skipEdge(node, edges, index, true, true)) { |
| continue; |
| } |
| int orderId = readOrderId(methodScope); |
| Node value = makeStubNode(methodScope, loopScope, orderId); |
| edges.initializeNode(node, index, value); |
| if (updatePredecessors && value != null) { |
| edges.update(node, null, value); |
| } |
| } |
| for (int index = edges.getDirectCount(); index < edges.getCount(); index++) { |
| if (skipEdge(node, edges, index, false, true)) { |
| continue; |
| } |
| int size = methodScope.reader.getSVInt(); |
| if (size != -1) { |
| NodeList<Node> nodeList = new NodeSuccessorList<>(node, size); |
| edges.initializeList(node, index, nodeList); |
| for (int idx = 0; idx < size; idx++) { |
| int orderId = readOrderId(methodScope); |
| Node value = makeStubNode(methodScope, loopScope, orderId); |
| nodeList.initialize(idx, value); |
| if (updatePredecessors && value != null) { |
| edges.update(node, null, value); |
| } |
| } |
| } |
| } |
| } |
| |
| protected FixedNode makeStubNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId) { |
| if (nodeOrderId == GraphEncoder.NULL_ORDER_ID) { |
| return null; |
| } |
| FixedNode node = (FixedNode) lookupNode(loopScope, nodeOrderId); |
| if (node != null) { |
| return node; |
| } |
| |
| long readerByteIndex = methodScope.reader.getByteIndex(); |
| node = (FixedNode) methodScope.graph.add(instantiateNode(methodScope, nodeOrderId)); |
| /* Properties and edges are not filled yet, the node remains uninitialized. */ |
| methodScope.reader.setByteIndex(readerByteIndex); |
| |
| registerNode(loopScope, nodeOrderId, node, false, false); |
| loopScope.nodesToProcess.set(nodeOrderId); |
| return node; |
| } |
| |
| /** |
| * Returns false for {@link Edges} that are not necessary in the encoded graph because they are |
| * reconstructed using other sources of information. |
| */ |
| protected static boolean skipEdge(Node node, Edges edges, int index, boolean direct, boolean decode) { |
| if (node instanceof PhiNode) { |
| /* The inputs of phi functions are filled manually when the end nodes are processed. */ |
| assert edges.type() == Edges.Type.Inputs; |
| if (direct) { |
| assert index == edges.getDirectCount() - 1 : "PhiNode has one direct input (the MergeNode)"; |
| } else { |
| assert index == edges.getCount() - 1 : "PhiNode has one variable size input (the values)"; |
| if (decode) { |
| /* The values must not be null, so initialize with an empty list. */ |
| edges.initializeList(node, index, new NodeInputList<>(node)); |
| } |
| } |
| return true; |
| |
| } else if (node instanceof AbstractMergeNode && edges.type() == Edges.Type.Inputs && !direct) { |
| /* The ends of merge nodes are filled manually when the ends are processed. */ |
| assert index == edges.getCount() - 1 : "MergeNode has one variable size input (the ends)"; |
| assert Edges.getNodeList(node, edges.getOffsets(), index) != null : "Input list must have been already created"; |
| return true; |
| |
| } else if (node instanceof LoopExitNode && edges.type() == Edges.Type.Inputs && edges.getType(index) == FrameState.class) { |
| /* The stateAfter of the loop exit is filled manually. */ |
| return true; |
| |
| } else if (node instanceof Invoke) { |
| assert node instanceof InvokeNode || node instanceof InvokeWithExceptionNode : "The only two Invoke node classes. Got " + node.getClass(); |
| assert direct : "Invoke and InvokeWithException only have direct successor and input edges"; |
| if (edges.type() == Edges.Type.Successors) { |
| assert edges.getCount() == (node instanceof InvokeWithExceptionNode ? 2 : 1) : "InvokeNode has one successor (next); InvokeWithExceptionNode has two successors (next, exceptionEdge)"; |
| return true; |
| } else { |
| assert edges.type() == Edges.Type.Inputs; |
| if (edges.getType(index) == CallTargetNode.class) { |
| return true; |
| } else if (edges.getType(index) == FrameState.class) { |
| assert edges.get(node, index) == null || edges.get(node, index) == ((Invoke) node).stateAfter() : "Only stateAfter can be a FrameState during encoding"; |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| protected Node lookupNode(LoopScope loopScope, int nodeOrderId) { |
| return loopScope.createdNodes[nodeOrderId]; |
| } |
| |
| protected void registerNode(LoopScope loopScope, int nodeOrderId, Node node, boolean allowOverwrite, boolean allowNull) { |
| assert node == null || node.isAlive(); |
| assert allowNull || node != null; |
| assert allowOverwrite || lookupNode(loopScope, nodeOrderId) == null; |
| loopScope.createdNodes[nodeOrderId] = node; |
| } |
| |
| protected int readOrderId(MethodScope methodScope) { |
| return methodScope.reader.getUVInt(); |
| } |
| |
| protected Object readObject(MethodScope methodScope) { |
| return methodScope.encodedGraph.getObjects()[methodScope.reader.getUVInt()]; |
| } |
| |
| /** |
| * Removes unnecessary nodes from the graph after decoding. |
| * |
| * @param methodScope The current method. |
| */ |
| protected void cleanupGraph(MethodScope methodScope) { |
| assert verifyEdges(methodScope); |
| } |
| |
| protected boolean verifyEdges(MethodScope methodScope) { |
| for (Node node : methodScope.graph.getNodes()) { |
| assert node.isAlive(); |
| for (Node i : node.inputs()) { |
| assert i.isAlive(); |
| assert i.usages().contains(node); |
| } |
| for (Node s : node.successors()) { |
| assert s.isAlive(); |
| assert s.predecessor() == node; |
| } |
| |
| for (Node usage : node.usages()) { |
| assert usage.isAlive(); |
| assert usage.inputs().contains(node) : node + " / " + usage + " / " + usage.inputs().count(); |
| } |
| if (node.predecessor() != null) { |
| assert node.predecessor().isAlive(); |
| assert node.predecessor().successors().contains(node); |
| } |
| } |
| return true; |
| } |
| } |
| |
| class LoopDetector implements Runnable { |
| |
| /** |
| * Information about loops before the actual loop nodes are inserted. |
| */ |
| static class Loop { |
| /** |
| * The header, i.e., the target of backward branches. |
| */ |
| MergeNode header; |
| /** |
| * The ends, i.e., the source of backward branches. The {@link EndNode#successors successor} |
| * is the {@link #header loop header}. |
| */ |
| List<EndNode> ends = new ArrayList<>(); |
| /** |
| * Exits of the loop. The successor is a {@link MergeNode} marked in |
| * {@link MethodScope#loopExplosionMerges}. |
| */ |
| List<AbstractEndNode> exits = new ArrayList<>(); |
| /** |
| * Set to true when the loop is irreducible, i.e., has multiple entries. See |
| * {@link #handleIrreducibleLoop} for details on the handling. |
| */ |
| boolean irreducible; |
| } |
| |
| private final MethodScope methodScope; |
| private final FixedNode startInstruction; |
| |
| private Loop irreducibleLoopHandler; |
| private IntegerSwitchNode irreducibleLoopSwitch; |
| |
| protected LoopDetector(MethodScope methodScope, FixedNode startInstruction) { |
| this.methodScope = methodScope; |
| this.startInstruction = startInstruction; |
| } |
| |
| @Override |
| public void run() { |
| Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "Before loop detection"); |
| |
| List<Loop> orderedLoops = findLoops(); |
| assert orderedLoops.get(orderedLoops.size() - 1) == irreducibleLoopHandler : "outermost loop must be the last element in the list"; |
| |
| for (Loop loop : orderedLoops) { |
| if (loop.ends.isEmpty()) { |
| assert loop == irreducibleLoopHandler; |
| continue; |
| } |
| |
| /* |
| * The algorithm to find loop exits requires that inner loops have already been |
| * processed. Therefore, we need to iterate the loops in order (inner loops before outer |
| * loops), and we cannot find the exits for all loops before we start inserting nodes. |
| */ |
| findLoopExits(loop); |
| |
| if (loop.irreducible) { |
| handleIrreducibleLoop(loop); |
| } else { |
| insertLoopNodes(loop); |
| } |
| Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After handling of loop %s", loop.header); |
| } |
| |
| logIrreducibleLoops(); |
| Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After loop detection"); |
| } |
| |
| private List<Loop> findLoops() { |
| /* Mapping from the loop header node to additional loop information. */ |
| Map<MergeNode, Loop> unorderedLoops = new HashMap<>(); |
| /* Loops in reverse order of, i.e., inner loops before outer loops. */ |
| List<Loop> orderedLoops = new ArrayList<>(); |
| |
| /* |
| * Ensure we have an outermost loop that we can use to eliminate irreducible loops. This |
| * loop can remain empty (no ends), in which case it is ignored. |
| */ |
| irreducibleLoopHandler = findOrCreateLoop(unorderedLoops, methodScope.loopExplosionHead); |
| |
| NodeBitMap visited = methodScope.graph.createNodeBitMap(); |
| NodeBitMap active = methodScope.graph.createNodeBitMap(); |
| Deque<Node> stack = new ArrayDeque<>(); |
| visited.mark(startInstruction); |
| stack.push(startInstruction); |
| |
| while (!stack.isEmpty()) { |
| Node current = stack.peek(); |
| assert visited.isMarked(current); |
| |
| if (active.isMarked(current)) { |
| /* We are back-tracking, i.e., all successor nodes have been processed. */ |
| stack.pop(); |
| active.clear(current); |
| |
| Loop loop = unorderedLoops.get(current); |
| if (loop != null) { |
| /* |
| * Since nodes are popped in reverse order that they were pushed, we add inner |
| * loops before outer loops here. |
| */ |
| assert !orderedLoops.contains(loop); |
| orderedLoops.add(loop); |
| } |
| |
| } else { |
| /* |
| * Process the node. Note that we do not remove the node from the stack, i.e., we |
| * will peek it again. But the next time the node is marked as active, so we do not |
| * execute this code again. |
| */ |
| active.mark(current); |
| for (Node successor : current.cfgSuccessors()) { |
| if (active.isMarked(successor)) { |
| /* Detected a cycle, i.e., a backward branch of a loop. */ |
| Loop loop = findOrCreateLoop(unorderedLoops, (MergeNode) successor); |
| assert !loop.ends.contains(current); |
| loop.ends.add((EndNode) current); |
| |
| } else if (visited.isMarked(successor)) { |
| /* Forward merge into a branch we are already exploring. */ |
| |
| } else { |
| /* Forward branch to a node we have not seen yet. */ |
| visited.mark(successor); |
| stack.push(successor); |
| } |
| } |
| } |
| } |
| return orderedLoops; |
| } |
| |
| private Loop findOrCreateLoop(Map<MergeNode, Loop> unorderedLoops, MergeNode loopHeader) { |
| assert methodScope.loopExplosionMerges.isMarkedAndGrow(loopHeader) : loopHeader; |
| Loop loop = unorderedLoops.get(loopHeader); |
| if (loop == null) { |
| loop = new Loop(); |
| loop.header = loopHeader; |
| unorderedLoops.put(loopHeader, loop); |
| } |
| return loop; |
| } |
| |
| private void findLoopExits(Loop loop) { |
| /* |
| * Backward marking of loop nodes: Starting with the known loop ends, we mark all nodes that |
| * are reachable until we hit the loop begin. All successors of loop nodes that are not |
| * marked as loop nodes themselves are exits of the loop. We mark all successors, and then |
| * subtract the loop nodes, to find the exits. |
| */ |
| |
| NodeBitMap possibleExits = methodScope.graph.createNodeBitMap(); |
| NodeBitMap visited = methodScope.graph.createNodeBitMap(); |
| Deque<Node> stack = new ArrayDeque<>(); |
| for (EndNode loopEnd : loop.ends) { |
| stack.push(loopEnd); |
| visited.mark(loopEnd); |
| } |
| |
| while (!stack.isEmpty()) { |
| Node current = stack.pop(); |
| if (current == loop.header) { |
| continue; |
| } |
| if (!methodScope.graph.isNew(methodScope.methodStartMark, current)) { |
| /* |
| * The current node is before the method that contains the exploded loop. The loop |
| * must have a second entry point, i.e., it is an irreducible loop. |
| */ |
| loop.irreducible = true; |
| return; |
| } |
| |
| for (Node predecessor : current.cfgPredecessors()) { |
| if (predecessor instanceof LoopExitNode) { |
| /* |
| * Inner loop. We do not need to mark every node of it, instead we just continue |
| * marking at the loop header. |
| */ |
| LoopBeginNode innerLoopBegin = ((LoopExitNode) predecessor).loopBegin(); |
| if (!visited.isMarked(innerLoopBegin)) { |
| stack.push(innerLoopBegin); |
| visited.mark(innerLoopBegin); |
| |
| /* |
| * All loop exits of the inner loop possibly need a LoopExit of our loop. |
| * Because we are processing inner loops first, we are guaranteed to already |
| * have all exits of the inner loop. |
| */ |
| for (LoopExitNode exit : innerLoopBegin.loopExits()) { |
| possibleExits.mark(exit); |
| } |
| } |
| |
| } else if (!visited.isMarked(predecessor)) { |
| stack.push(predecessor); |
| visited.mark(predecessor); |
| |
| if (predecessor instanceof ControlSplitNode) { |
| for (Node succ : predecessor.cfgSuccessors()) { |
| /* |
| * We would not need to mark the current node, and would not need to |
| * mark visited nodes. But it is easier to just mark everything, since |
| * we subtract all visited nodes in the end anyway. Note that at this |
| * point we do not have the complete visited information, so we would |
| * always mark too many possible exits. |
| */ |
| possibleExits.mark(succ); |
| } |
| } |
| } |
| } |
| } |
| |
| /* All visited nodes are not exits of our loop. */ |
| possibleExits.subtract(visited); |
| |
| /* |
| * Now we know all the actual loop exits. Ideally, we would insert LoopExit nodes for them. |
| * However, a LoopExit needs a valid FrameState that captures the state at the point where |
| * we exit the loop. During graph decoding, we create a FrameState for every exploded loop |
| * iteration. We need to do a forward marking until we hit the next such point. This puts |
| * some nodes into the loop that are actually not part of the loop. |
| * |
| * In some cases, we did not create a FrameState during graph decoding: when there was no |
| * LoopExit in the original loop that we exploded. This happens for code paths that lead |
| * immediately to a DeoptimizeNode. |
| * |
| * Both cases mimic the behavior of the BytecodeParser, which also puts more nodes than |
| * necessary into a loop because it computes loop information based on bytecodes, before the |
| * actual parsing. |
| */ |
| |
| for (Node succ : possibleExits) { |
| stack.push(succ); |
| visited.mark(succ); |
| assert !methodScope.loopExplosionMerges.isMarkedAndGrow(succ); |
| } |
| |
| while (!stack.isEmpty()) { |
| Node current = stack.pop(); |
| assert visited.isMarked(current); |
| assert current instanceof ControlSinkNode || current instanceof LoopEndNode || current.cfgSuccessors().iterator().hasNext() : "Must not reach a node that has not been decoded yet"; |
| |
| for (Node successor : current.cfgSuccessors()) { |
| if (visited.isMarked(successor)) { |
| /* Already processed this successor. */ |
| |
| } else if (methodScope.loopExplosionMerges.isMarkedAndGrow(successor)) { |
| /* |
| * We have a FrameState for the successor. The LoopExit will be inserted between |
| * the current node and the successor node. Since the successor node is a |
| * MergeNode, the current node mus be a AbstractEndNode with only that MergeNode |
| * as the successor. |
| */ |
| assert successor instanceof MergeNode; |
| assert !loop.exits.contains(current); |
| loop.exits.add((AbstractEndNode) current); |
| |
| } else { |
| /* Node we have not seen yet. */ |
| visited.mark(successor); |
| stack.push(successor); |
| } |
| } |
| } |
| } |
| |
| private void insertLoopNodes(Loop loop) { |
| MergeNode merge = loop.header; |
| FrameState stateAfter = merge.stateAfter().duplicate(); |
| FixedNode afterMerge = merge.next(); |
| merge.setNext(null); |
| EndNode preLoopEnd = methodScope.graph.add(new EndNode()); |
| LoopBeginNode loopBegin = methodScope.graph.add(new LoopBeginNode()); |
| |
| merge.setNext(preLoopEnd); |
| /* Add the single non-loop predecessor of the loop header. */ |
| loopBegin.addForwardEnd(preLoopEnd); |
| loopBegin.setNext(afterMerge); |
| loopBegin.setStateAfter(stateAfter); |
| |
| /* |
| * Phi functions of the original merge need to be split: inputs that come from forward edges |
| * remain with the original phi function; inputs that come from backward edges are added to |
| * new phi functions. |
| */ |
| List<PhiNode> mergePhis = merge.phis().snapshot(); |
| List<PhiNode> loopBeginPhis = new ArrayList<>(mergePhis.size()); |
| for (int i = 0; i < mergePhis.size(); i++) { |
| PhiNode mergePhi = mergePhis.get(i); |
| PhiNode loopBeginPhi = methodScope.graph.addWithoutUnique(new ValuePhiNode(mergePhi.stamp(), loopBegin)); |
| mergePhi.replaceAtUsages(loopBeginPhi); |
| /* |
| * The first input of the new phi function is the original phi function, for the one |
| * forward edge of the LoopBeginNode. |
| */ |
| loopBeginPhi.addInput(mergePhi); |
| loopBeginPhis.add(loopBeginPhi); |
| } |
| |
| for (EndNode endNode : loop.ends) { |
| for (int i = 0; i < mergePhis.size(); i++) { |
| PhiNode mergePhi = mergePhis.get(i); |
| PhiNode loopBeginPhi = loopBeginPhis.get(i); |
| loopBeginPhi.addInput(mergePhi.valueAt(endNode)); |
| } |
| |
| merge.removeEnd(endNode); |
| LoopEndNode loopEnd = methodScope.graph.add(new LoopEndNode(loopBegin)); |
| endNode.replaceAndDelete(loopEnd); |
| } |
| |
| /* |
| * Insert the LoopExit nodes (the easy part) and compute the FrameState for the new exits |
| * (the difficult part). |
| */ |
| for (AbstractEndNode exit : loop.exits) { |
| AbstractMergeNode loopExplosionMerge = exit.merge(); |
| assert methodScope.loopExplosionMerges.isMarkedAndGrow(loopExplosionMerge); |
| |
| LoopExitNode loopExit = methodScope.graph.add(new LoopExitNode(loopBegin)); |
| exit.replaceAtPredecessor(loopExit); |
| loopExit.setNext(exit); |
| assignLoopExitState(loopExit, loopExplosionMerge, exit); |
| } |
| } |
| |
| /** |
| * During graph decoding, we create a FrameState for every exploded loop iteration. This is |
| * mostly the state that we want, we only need to tweak it a little bit: we need to insert the |
| * appropriate ProxyNodes for all values that are created inside the loop and that flow out of |
| * the loop. |
| */ |
| private void assignLoopExitState(LoopExitNode loopExit, AbstractMergeNode loopExplosionMerge, AbstractEndNode loopExplosionEnd) { |
| FrameState oldState = loopExplosionMerge.stateAfter(); |
| |
| /* Collect all nodes that are in the FrameState at the LoopBegin. */ |
| NodeBitMap loopBeginValues = new NodeBitMap(methodScope.graph); |
| for (FrameState state = loopExit.loopBegin().stateAfter(); state != null; state = state.outerFrameState()) { |
| for (ValueNode value : state.values()) { |
| if (value != null && !value.isConstant() && !loopExit.loopBegin().isPhiAtMerge(value)) { |
| loopBeginValues.mark(ProxyPlaceholder.unwrap(value)); |
| } |
| } |
| } |
| |
| List<ValueNode> newValues = new ArrayList<>(oldState.values().size()); |
| for (ValueNode v : oldState.values()) { |
| ValueNode value = v; |
| ValueNode realValue = ProxyPlaceholder.unwrap(value); |
| |
| /* |
| * The LoopExit is inserted before the existing merge, i.e., separately for every branch |
| * that leads to the merge. So for phi functions of the merge, we need to take the input |
| * that corresponds to our branch. |
| */ |
| if (realValue instanceof PhiNode && loopExplosionMerge.isPhiAtMerge(realValue)) { |
| value = ((PhiNode) realValue).valueAt(loopExplosionEnd); |
| realValue = ProxyPlaceholder.unwrap(value); |
| } |
| |
| if (realValue == null || realValue.isConstant() || loopBeginValues.contains(realValue) || !methodScope.graph.isNew(methodScope.methodStartMark, realValue)) { |
| newValues.add(realValue); |
| } else { |
| /* |
| * The node is not in the FrameState of the LoopBegin, i.e., it is a value computed |
| * inside the loop. |
| */ |
| GraalError.guarantee(value instanceof ProxyPlaceholder && ((ProxyPlaceholder) value).proxyPoint == loopExplosionMerge, |
| "Value flowing out of loop, but we are not prepared to insert a ProxyNode"); |
| |
| ProxyPlaceholder proxyPlaceholder = (ProxyPlaceholder) value; |
| ValueProxyNode proxy = ProxyNode.forValue(proxyPlaceholder.value, loopExit, methodScope.graph); |
| proxyPlaceholder.setValue(proxy); |
| newValues.add(proxy); |
| } |
| } |
| |
| FrameState newState = new FrameState(oldState.outerFrameState(), oldState.getCode(), oldState.bci, newValues, oldState.localsSize(), oldState.stackSize(), oldState.rethrowException(), |
| oldState.duringCall(), oldState.monitorIds(), oldState.virtualObjectMappings()); |
| |
| assert loopExit.stateAfter() == null; |
| loopExit.setStateAfter(methodScope.graph.add(newState)); |
| } |
| |
| /** |
| * Graal does not support irreducible loops (loops with more than one entry point). There are |
| * two ways to make them reducible: 1) duplicate nodes (peel a loop iteration starting at the |
| * second entry point until we reach the first entry point), or 2) insert a big outer loop |
| * covering the whole method and build a state machine for the different loop entry points. |
| * Since node duplication can lead to an exponential explosion of nodes in the worst case, we |
| * use the second approach. |
| * |
| * We already did some preparations to insert a big outer loop: |
| * {@link MethodScope#loopExplosionHead} is the loop header for the outer loop, and we ensured |
| * that we have a {@link Loop} data object for it in {@link #irreducibleLoopHandler}. |
| * |
| * Now we need to insert the state machine. We have several implementation restrictions to make |
| * that efficient: |
| * <ul> |
| * <li>There must be only one loop variable, i.e., one value that is different in the |
| * {@link FrameState} of the different loop headers.</li> |
| * <li>The loop variable must use the primitive {@code int} type, because Graal only has a |
| * {@link IntegerSwitchNode switch node} for {@code int}.</li> |
| * <li>The values of the loop variable that are merged are {@link PrimitiveConstant compile time |
| * constants}.</li> |
| * </ul> |
| */ |
| private void handleIrreducibleLoop(Loop loop) { |
| assert loop != irreducibleLoopHandler; |
| |
| FrameState loopState = loop.header.stateAfter(); |
| FrameState explosionHeadState = irreducibleLoopHandler.header.stateAfter(); |
| assert loopState.outerFrameState() == explosionHeadState.outerFrameState(); |
| NodeInputList<ValueNode> loopValues = loopState.values(); |
| NodeInputList<ValueNode> explosionHeadValues = explosionHeadState.values(); |
| assert loopValues.size() == explosionHeadValues.size(); |
| |
| /* |
| * Find the loop variable, and the value of the loop variable for our loop and the outermost |
| * loop. There must be exactly one loop variable. |
| */ |
| int loopVariableIndex = -1; |
| ValueNode loopValue = null; |
| ValueNode explosionHeadValue = null; |
| for (int i = 0; i < loopValues.size(); i++) { |
| ValueNode curLoopValue = loopValues.get(i); |
| ValueNode curExplosionHeadValue = explosionHeadValues.get(i); |
| |
| if (curLoopValue != curExplosionHeadValue) { |
| if (loopVariableIndex != -1) { |
| throw bailout("must have only one variable that is changed in loop. " + loopValue + " != " + explosionHeadValue + " and " + curLoopValue + " != " + curExplosionHeadValue); |
| } |
| |
| loopVariableIndex = i; |
| loopValue = curLoopValue; |
| explosionHeadValue = curExplosionHeadValue; |
| } |
| } |
| assert loopVariableIndex != -1; |
| |
| ValuePhiNode loopVariablePhi; |
| SortedMap<Integer, AbstractBeginNode> dispatchTable = new TreeMap<>(); |
| AbstractBeginNode unreachableDefaultSuccessor; |
| if (irreducibleLoopSwitch == null) { |
| /* |
| * This is the first irreducible loop. We need to build the initial state machine |
| * (dispatch for the loop header of the outermost loop). |
| */ |
| assert !irreducibleLoopHandler.header.isPhiAtMerge(explosionHeadValue); |
| assert irreducibleLoopHandler.header.phis().isEmpty(); |
| |
| /* The new phi function for the loop variable. */ |
| loopVariablePhi = methodScope.graph.addWithoutUnique(new ValuePhiNode(explosionHeadValue.stamp().unrestricted(), irreducibleLoopHandler.header)); |
| for (int i = 0; i < irreducibleLoopHandler.header.phiPredecessorCount(); i++) { |
| loopVariablePhi.addInput(explosionHeadValue); |
| } |
| |
| /* |
| * Build the new FrameState for the loop header. There is only once change in comparison |
| * to the old FrameState: the loop variable is replaced with the phi function. |
| */ |
| FrameState oldFrameState = explosionHeadState; |
| List<ValueNode> newFrameStateValues = new ArrayList<>(); |
| for (int i = 0; i < explosionHeadValues.size(); i++) { |
| if (i == loopVariableIndex) { |
| newFrameStateValues.add(loopVariablePhi); |
| } else { |
| newFrameStateValues.add(explosionHeadValues.get(i)); |
| } |
| } |
| FrameState newFrameState = methodScope.graph.add( |
| new FrameState(oldFrameState.outerFrameState(), oldFrameState.getCode(), oldFrameState.bci, newFrameStateValues, oldFrameState.localsSize(), |
| oldFrameState.stackSize(), oldFrameState.rethrowException(), oldFrameState.duringCall(), oldFrameState.monitorIds(), |
| oldFrameState.virtualObjectMappings())); |
| oldFrameState.replaceAtUsages(newFrameState); |
| |
| /* |
| * Disconnect the outermost loop header from its loop body, so that we can later on |
| * insert the switch node. Collect dispatch information for the outermost loop. |
| */ |
| FixedNode handlerNext = irreducibleLoopHandler.header.next(); |
| irreducibleLoopHandler.header.setNext(null); |
| BeginNode handlerBegin = methodScope.graph.add(new BeginNode()); |
| handlerBegin.setNext(handlerNext); |
| dispatchTable.put(asInt(explosionHeadValue), handlerBegin); |
| |
| /* |
| * We know that there will always be a matching key in the switch. But Graal always |
| * wants a default successor, so we build a dummy block that just deoptimizes. |
| */ |
| unreachableDefaultSuccessor = methodScope.graph.add(new BeginNode()); |
| DeoptimizeNode deopt = methodScope.graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.UnreachedCode)); |
| unreachableDefaultSuccessor.setNext(deopt); |
| |
| } else { |
| /* |
| * This is the second or a subsequent irreducible loop, i.e., we already inserted a |
| * switch node before. We re-create the dispatch state machine of that switch, so that |
| * we can extend it with one more branch. |
| */ |
| assert irreducibleLoopHandler.header.isPhiAtMerge(explosionHeadValue); |
| assert irreducibleLoopHandler.header.phis().count() == 1 && irreducibleLoopHandler.header.phis().first() == explosionHeadValue; |
| assert irreducibleLoopSwitch.value() == explosionHeadValue; |
| |
| /* We can modify the phi function used by the old switch node. */ |
| loopVariablePhi = (ValuePhiNode) explosionHeadValue; |
| |
| /* |
| * We cannot modify the old switch node. Insert all information from the old switch node |
| * into our temporary data structures for the new, larger, switch node. |
| */ |
| for (int i = 0; i < irreducibleLoopSwitch.keyCount(); i++) { |
| int key = irreducibleLoopSwitch.keyAt(i).asInt(); |
| dispatchTable.put(key, irreducibleLoopSwitch.successorAtKey(key)); |
| } |
| unreachableDefaultSuccessor = irreducibleLoopSwitch.defaultSuccessor(); |
| |
| /* Unlink and delete the old switch node, we do not need it anymore. */ |
| assert irreducibleLoopHandler.header.next() == irreducibleLoopSwitch; |
| irreducibleLoopHandler.header.setNext(null); |
| irreducibleLoopSwitch.clearSuccessors(); |
| irreducibleLoopSwitch.safeDelete(); |
| } |
| |
| /* Insert our loop into the dispatch state machine. */ |
| assert loop.header.phis().isEmpty(); |
| BeginNode dispatchBegin = methodScope.graph.add(new BeginNode()); |
| EndNode dispatchEnd = methodScope.graph.add(new EndNode()); |
| dispatchBegin.setNext(dispatchEnd); |
| loop.header.addForwardEnd(dispatchEnd); |
| int intLoopValue = asInt(loopValue); |
| assert !dispatchTable.containsKey(intLoopValue); |
| dispatchTable.put(intLoopValue, dispatchBegin); |
| |
| /* Disconnect the ends of our loop and re-connect them to the outermost loop header. */ |
| for (EndNode end : loop.ends) { |
| loop.header.removeEnd(end); |
| irreducibleLoopHandler.ends.add(end); |
| irreducibleLoopHandler.header.addForwardEnd(end); |
| loopVariablePhi.addInput(loopValue); |
| } |
| |
| /* Build and insert the switch node. */ |
| irreducibleLoopSwitch = methodScope.graph.add(createSwitch(loopVariablePhi, dispatchTable, unreachableDefaultSuccessor)); |
| irreducibleLoopHandler.header.setNext(irreducibleLoopSwitch); |
| } |
| |
| private static int asInt(ValueNode node) { |
| if (!node.isConstant() || node.asJavaConstant().getJavaKind() != JavaKind.Int) { |
| throw bailout("must have a loop variable of type int. " + node); |
| } |
| return node.asJavaConstant().asInt(); |
| } |
| |
| private static RuntimeException bailout(String msg) { |
| throw new PermanentBailoutException("Graal implementation restriction: Method with %s loop explosion %s", LoopExplosionKind.MERGE_EXPLODE, msg); |
| } |
| |
| private static IntegerSwitchNode createSwitch(ValuePhiNode switchedValue, SortedMap<Integer, AbstractBeginNode> dispatchTable, AbstractBeginNode defaultSuccessor) { |
| int numKeys = dispatchTable.size(); |
| int numSuccessors = numKeys + 1; |
| |
| AbstractBeginNode[] switchSuccessors = new AbstractBeginNode[numSuccessors]; |
| int[] switchKeys = new int[numKeys]; |
| double[] switchKeyProbabilities = new double[numSuccessors]; |
| int[] switchKeySuccessors = new int[numSuccessors]; |
| |
| int idx = 0; |
| for (Map.Entry<Integer, AbstractBeginNode> entry : dispatchTable.entrySet()) { |
| switchSuccessors[idx] = entry.getValue(); |
| switchKeys[idx] = entry.getKey(); |
| switchKeyProbabilities[idx] = 1d / numKeys; |
| switchKeySuccessors[idx] = idx; |
| idx++; |
| } |
| switchSuccessors[idx] = defaultSuccessor; |
| /* We know the default branch is never going to be executed. */ |
| switchKeyProbabilities[idx] = 0; |
| switchKeySuccessors[idx] = idx; |
| |
| return new IntegerSwitchNode(switchedValue, switchSuccessors, switchKeys, switchKeyProbabilities, switchKeySuccessors); |
| } |
| |
| /** |
| * Print information about irreducible loops, when enabled with -Dgraal.Log=IrreducibleLoops. |
| */ |
| @SuppressWarnings("try") |
| private void logIrreducibleLoops() { |
| try (Debug.Scope s = Debug.scope("IrreducibleLoops")) { |
| if (Debug.isLogEnabled(Debug.BASIC_LOG_LEVEL) && irreducibleLoopSwitch != null) { |
| StringBuilder msg = new StringBuilder("Inserted state machine to remove irreducible loops. Dispatching to the following states: "); |
| String sep = ""; |
| for (int i = 0; i < irreducibleLoopSwitch.keyCount(); i++) { |
| msg.append(sep).append(irreducibleLoopSwitch.keyAt(i).asInt()); |
| sep = ", "; |
| } |
| Debug.log(Debug.BASIC_LOG_LEVEL, "%s", msg); |
| } |
| } |
| } |
| } |
