Mercurial > hg > graal-compiler
changeset 23310:ca8c504c32f7
GraphPE: provide a FrameState for LoopExit created by loop detection
author | Christian Wimmer <christian.wimmer@oracle.com> |
---|---|
date | Thu, 14 Jan 2016 15:06:16 -0800 |
parents | 94f855720119 |
children | 2cc28cd4b483 |
files | graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GraphDecoder.java |
diffstat | 1 files changed, 175 insertions(+), 20 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GraphDecoder.java Thu Jan 14 22:41:45 2016 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GraphDecoder.java Thu Jan 14 15:06:16 2016 -0800 @@ -37,6 +37,7 @@ import java.util.Set; import jdk.vm.ci.code.Architecture; +import jdk.vm.ci.common.JVMCIError; import jdk.vm.ci.meta.ResolvedJavaType; import com.oracle.graal.compiler.common.Fields; @@ -51,6 +52,11 @@ import com.oracle.graal.graph.NodeInputList; import com.oracle.graal.graph.NodeList; import com.oracle.graal.graph.NodeSuccessorList; +import com.oracle.graal.graph.spi.Canonicalizable; +import com.oracle.graal.graph.spi.CanonicalizerTool; +import com.oracle.graal.nodeinfo.InputType; +import com.oracle.graal.nodeinfo.NodeInfo; +import com.oracle.graal.nodes.calc.FloatingNode; /** * Decoder for {@link EncodedGraph encoded graphs} produced by {@link GraphEncoder}. Support for @@ -102,6 +108,9 @@ /** The exception unwind node encountered during decoding, or null. */ public UnwindNode unwindNode; + /** All merges created during loop explosion. */ + public final NodeBitMap loopExplosionMerges; + protected MethodScope(StructuredGraph graph, EncodedGraph encodedGraph, LoopExplosionKind loopExplosion) { this.graph = graph; this.encodedGraph = encodedGraph; @@ -121,6 +130,12 @@ } else { reader = null; } + + if (loopExplosion != LoopExplosionKind.NONE) { + loopExplosionMerges = new NodeBitMap(graph); + } else { + loopExplosionMerges = null; + } } } @@ -202,7 +217,7 @@ if (value == null) { h = h * 31 + 1234; } else { - h = h * 31 + value.hashCode(); + h = h * 31 + ProxyPlaceholder.unwrap(value).hashCode(); } } this.hashCode = h; @@ -221,8 +236,8 @@ Iterator<ValueNode> thisIter = thisState.values().iterator(); Iterator<ValueNode> otherIter = otherState.values().iterator(); while (thisIter.hasNext() && otherIter.hasNext()) { - ValueNode thisValue = thisIter.next(); - ValueNode otherValue = otherIter.next(); + ValueNode thisValue = ProxyPlaceholder.unwrap(thisIter.next()); + ValueNode otherValue = ProxyPlaceholder.unwrap(otherIter.next()); if (thisValue != otherValue) { return false; } @@ -268,6 +283,48 @@ } } + /** + * A node that is created during {@link LoopExplosionKind#MERGE_EXPLODE loop explosion} that can + * later be replaced by a ProxyNode if {@link GraphDecoder#detectLoops loop detection} finds out + * that the value is defined in the loop, but used outside the loop. + */ + @NodeInfo + protected static final class ProxyPlaceholder extends FloatingNode implements Canonicalizable { + public static final NodeClass<ProxyPlaceholder> TYPE = NodeClass.create(ProxyPlaceholder.class); + + @Input ValueNode value; + @Input(InputType.Association) 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) { @@ -321,7 +378,7 @@ } if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { - detectLoops(methodScope.graph, startNode); + detectLoops(methodScope, methodScope.graph, startNode); } } @@ -514,6 +571,41 @@ } MergeNode merge = methodScope.graph.add(new MergeNode()); + methodScope.loopExplosionMerges.markAndGrow(merge); + + if (methodScope.loopExplosion == LoopExplosionKind.MERGE_EXPLODE) { + List<ValueNode> newFrameStateValues = new ArrayList<>(); + for (ValueNode frameStateValue : frameState.values) { + if (frameStateValue == null || frameStateValue.isConstant()) { + 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.method(), 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); @@ -1030,7 +1122,7 @@ * The following methods are a literal copy from GraphBuilderPhase. */ - protected void detectLoops(StructuredGraph currentGraph, FixedNode startInstruction) { + protected void detectLoops(MethodScope methodScope, StructuredGraph currentGraph, FixedNode startInstruction) { Debug.dump(currentGraph, "Before detectLoops"); NodeBitMap visited = currentGraph.createNodeBitMap(); NodeBitMap active = currentGraph.createNodeBitMap(); @@ -1054,6 +1146,7 @@ assert n instanceof MergeNode; assert next instanceof EndNode; MergeNode merge = (MergeNode) n; + assert methodScope.loopExplosionMerges.contains(merge) : merge; EndNode endNode = (EndNode) next; merge.removeEnd(endNode); FixedNode afterMerge = merge.next(); @@ -1080,7 +1173,7 @@ } Debug.dump(currentGraph, "Before insertLoopEnds"); - insertLoopEnds(currentGraph, startInstruction, newLoopBegins); + insertLoopEnds(methodScope, currentGraph, startInstruction, newLoopBegins); Debug.dump(currentGraph, "After detectLoops"); } @@ -1093,7 +1186,7 @@ return loopBegin; } - private static void insertLoopEnds(StructuredGraph currentGraph, FixedNode startInstruction, Set<LoopBeginNode> newLoopBegins) { + private static void insertLoopEnds(MethodScope methodScope, StructuredGraph currentGraph, FixedNode startInstruction, Set<LoopBeginNode> newLoopBegins) { NodeBitMap visited = currentGraph.createNodeBitMap(); Deque<Node> stack = new ArrayDeque<>(); stack.add(startInstruction); @@ -1117,19 +1210,11 @@ for (int i = loopBegins.size() - 1; i >= 0; --i) { LoopBeginNode loopBegin = loopBegins.get(i); - insertLoopExits(currentGraph, loopBegin); - } - - // Remove degenerated merges with only one predecessor. - for (LoopBeginNode loopBegin : loopBegins) { - Node pred = loopBegin.forwardEnd().predecessor(); - if (pred instanceof MergeNode) { - MergeNode.removeMergeIfDegenerated((MergeNode) pred); - } + insertLoopExits(methodScope, currentGraph, loopBegin); } } - private static void insertLoopExits(StructuredGraph currentGraph, LoopBeginNode loopBegin) { + private static void insertLoopExits(MethodScope methodScope, StructuredGraph currentGraph, LoopBeginNode loopBegin) { NodeBitMap visited = currentGraph.createNodeBitMap(); Deque<Node> stack = new ArrayDeque<>(); for (LoopEndNode loopEnd : loopBegin.loopEnds()) { @@ -1192,14 +1277,84 @@ * initial check for isMarked when we added a node to the list. */ if (!visited.isMarked(succ)) { - LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin)); FixedNode next = ((FixedWithNextNode) succ).next(); - next.replaceAtPredecessor(loopExit); - loopExit.setNext(next); + /* Skip over unnecessary BeginNodes, which will be deleted only later on. */ + while (next instanceof BeginNode) { + next = ((BeginNode) next).next(); + } + + /* + * 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. 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. + * + * 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. Since the BytecodeParser does + * not insert a LoopExit in such cases, we also do not have to insert a LoopExit. + */ + if (next instanceof EndNode) { + AbstractMergeNode merge = ((EndNode) next).merge(); + if (methodScope.loopExplosionMerges.contains(merge)) { + /* + * If this guarantee fails, we need to handle phi functions of the merge, + * i.e., take the phi function input for our EndNode and put it into the + * LoopExit state. + */ + JVMCIError.guarantee(merge.cfgPredecessors().count() == 1, merge.toString()); + + LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin)); + next.replaceAtPredecessor(loopExit); + loopExit.setNext(next); + assignLoopExitState(methodScope, loopExit, merge); + } + } } } } + private static void assignLoopExitState(MethodScope methodScope, LoopExitNode loopExit, AbstractMergeNode loopExplosionMerge) { + FrameState oldState = loopExplosionMerge.stateAfter(); + JVMCIError.guarantee(loopExit.loopBegin().stateAfter().outerFrameState() == oldState.outerFrameState(), "LoopBegin and LoopExit must have the same outer frame state"); + + /* Collect all nodes that are in the FrameState at the LoopBegin. */ + NodeBitMap loopBeginValues = new NodeBitMap(methodScope.graph); + for (ValueNode value : loopExit.loopBegin().stateAfter().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 value : oldState.values()) { + ValueNode realValue = ProxyPlaceholder.unwrap(value); + + if (realValue == null || realValue.isConstant() || loopBeginValues.contains(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. + */ + JVMCIError.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.method(), 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)); + } + /** * Removes unnecessary nodes from the graph after decoding. *