# HG changeset patch # User Lukas Stadler # Date 1394788924 -3600 # Node ID ccf090d3be477b6a62c88ebab5debe56d175e87c # Parent e5235120893cae2246c5bbd19fee31fb4d969398 new graph ordering assertion mechanism diff -r e5235120893c -r ccf090d3be47 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Fri Mar 14 10:21:46 2014 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Fri Mar 14 10:22:04 2014 +0100 @@ -292,7 +292,7 @@ } private void printSchedule(String desc) { - if (Debug.isEnabled()) { + if (Debug.isLogEnabled()) { Debug.printf("=== %s / %s / %s (%s) ===\n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, memsched, desc); for (Block b : getCFG().getBlocks()) { Debug.printf("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth()); @@ -388,8 +388,7 @@ private void assignBlockToNode(ScheduledNode node, SchedulingStrategy strategy) { assert !node.isDeleted(); - Block prevBlock = cfg.getNodeToBlock().get(node); - if (prevBlock != null) { + if (cfg.getNodeToBlock().containsKey(node)) { return; } // PhiNodes, ProxyNodes and FixedNodes should already have been placed in blocks by @@ -418,6 +417,7 @@ block = latestBlock(node, strategy); } if (block == null) { + // handle nodes without usages block = earliestBlock; } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) { // schedule at the latest position possible in the outermost loop possible @@ -752,10 +752,14 @@ if (!(usage instanceof FrameState)) { throw new SchedulingError(usage.toString()); } - // If a FrameState belongs to a BeginNode then it's inputs will be placed at the - // common dominator of all EndNodes. - for (Node pred : unscheduledUsage.cfgPredecessors()) { - closure.apply(cfg.getNodeToBlock().get(pred)); + if (unscheduledUsage instanceof StartNode) { + closure.apply(cfg.getNodeToBlock().get(unscheduledUsage)); + } else { + // If a FrameState belongs to a BeginNode then it's inputs will be placed at + // the common dominator of all EndNodes. + for (Node pred : unscheduledUsage.cfgPredecessors()) { + closure.apply(cfg.getNodeToBlock().get(pred)); + } } } else { // For the time being, FrameStates can only be connected to NodeWithState. diff -r e5235120893c -r ccf090d3be47 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Fri Mar 14 10:21:46 2014 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Fri Mar 14 10:22:04 2014 +0100 @@ -26,7 +26,12 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.VirtualState.NodeClosure; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.graph.*; +import com.oracle.graal.phases.graph.ReentrantBlockIterator.*; +import com.oracle.graal.phases.schedule.*; +import com.oracle.graal.phases.schedule.SchedulePhase.*; public final class GraphOrder { @@ -34,9 +39,9 @@ } /** - * Asserts that there are no (invalid) cycles in the given graph. First, an ordered list of all - * nodes in the graph (a total ordering) is created. A second run over this list checks whether - * inputs are scheduled before their usages. + * Quick (and imprecise) assertion that there are no (invalid) cycles in the given graph. First, + * an ordered list of all nodes in the graph (a total ordering) is created. A second run over + * this list checks whether inputs are scheduled before their usages. * * @param graph the graph to be checked. * @throws AssertionError if a cycle was detected. @@ -62,7 +67,6 @@ } visited.mark(node); } - return true; } @@ -80,34 +84,161 @@ } private static void visitForward(ArrayList nodes, NodeBitMap visited, Node node, boolean floatingOnly) { - if (node != null && !visited.isMarked(node)) { - assert !floatingOnly || !(node instanceof FixedNode) : "unexpected reference to fixed node: " + node + " (this indicates an unexpected cycle)"; - visited.mark(node); - FrameState stateAfter = null; - if (node instanceof StateSplit) { - stateAfter = ((StateSplit) node).stateAfter(); - } - for (Node input : node.inputs()) { - if (input != stateAfter) { - visitForward(nodes, visited, input, true); + try { + assert node.isAlive() : node + " not alive"; + if (node != null && !visited.isMarked(node)) { + if (floatingOnly && node instanceof FixedNode) { + throw new GraalInternalError("unexpected reference to fixed node: %s (this indicates an unexpected cycle)", node); + } + visited.mark(node); + FrameState stateAfter = null; + if (node instanceof StateSplit) { + stateAfter = ((StateSplit) node).stateAfter(); + } + for (Node input : node.inputs()) { + if (input != stateAfter) { + visitForward(nodes, visited, input, true); + } + } + if (node instanceof EndNode) { + EndNode end = (EndNode) node; + for (PhiNode phi : end.merge().phis()) { + visitForward(nodes, visited, phi.valueAt(end), true); + } + } + nodes.add(node); + if (node instanceof MergeNode) { + for (PhiNode phi : ((MergeNode) node).phis()) { + visited.mark(phi); + nodes.add(phi); + } + } + if (stateAfter != null) { + visitForward(nodes, visited, stateAfter, true); } } - if (node instanceof EndNode) { - EndNode end = (EndNode) node; - for (PhiNode phi : end.merge().phis()) { - visitForward(nodes, visited, phi.valueAt(end), true); - } - } - nodes.add(node); - if (node instanceof MergeNode) { - for (PhiNode phi : ((MergeNode) node).phis()) { - visited.mark(phi); - nodes.add(phi); - } - } - if (stateAfter != null) { - visitForward(nodes, visited, stateAfter, true); - } + } catch (GraalInternalError e) { + e.addContext(node); + throw e; } } + + /** + * This method schedules the graph and makes sure that, for every node, all inputs are available + * at the position where it is scheduled. This is a very expensive assertion. + * + * Also, this phase assumes ProxyNodes to exist at LoopExitNodes, so that it cannot be run after + * phases that remove loop proxies or move proxies to BeginNodes. + */ + public static boolean assertSchedulableGraph(final StructuredGraph graph) { + try { + final SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS, MemoryScheduling.NONE); + final IdentityHashMap loopEntryStates = new IdentityHashMap<>(); + schedule.apply(graph, false); + + BlockIteratorClosure closure = new BlockIteratorClosure() { + + @Override + protected List processLoop(Loop loop, NodeBitMap initialState) { + return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates; + } + + @Override + protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) { + final List list = schedule.getBlockToNodesMap().get(block); + + /* + * A stateAfter is not valid directly after its associated state split, but + * right before the next fixed node. Therefore a pending stateAfter is kept that + * will be checked at the correct position. + */ + FrameState pendingStateAfter = null; + for (final ScheduledNode node : list) { + FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null; + + if (pendingStateAfter != null && node instanceof FixedNode) { + pendingStateAfter.applyToNonVirtual(new NodeClosure() { + public void apply(Node usage, Node nonVirtualNode) { + assert currentState.isMarked(nonVirtualNode) : nonVirtualNode + " not available at virtualstate " + usage + " before " + node + " in block " + block + " \n" + list; + } + }); + pendingStateAfter = null; + } + + if (node instanceof MergeNode) { + // phis aren't scheduled, so they need to be added explicitly + currentState.markAll(((MergeNode) node).phis()); + if (node instanceof LoopBeginNode) { + // remember the state at the loop entry, it's restored at exits + loopEntryStates.put((LoopBeginNode) node, currentState.copy()); + } + } else if (node instanceof ProxyNode) { + for (Node input : node.inputs()) { + if (input != ((ProxyNode) node).proxyPoint()) { + assert currentState.isMarked(input) : input + " not available at " + node + " in block " + block + "\n" + list; + } + } + } else if (node instanceof LoopExitNode) { + // the contents of the loop are only accessible via proxies at the exit + currentState.clearAll(); + currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin())); + // Loop proxies aren't scheduled, so they need to be added explicitly + currentState.markAll(((LoopExitNode) node).proxies()); + } else { + for (Node input : node.inputs()) { + if (input != stateAfter) { + assert currentState.isMarked(input) : input + " not available at " + node + " in block " + block + "\n" + list; + } + } + } + if (node instanceof AbstractEndNode) { + MergeNode merge = ((AbstractEndNode) node).merge(); + for (PhiNode phi : merge.phis()) { + assert currentState.isMarked(phi.valueAt((AbstractEndNode) node)) : phi.valueAt((AbstractEndNode) node) + " not available at phi " + phi + " / end " + node + + " in block " + block; + } + } + if (stateAfter != null) { + assert pendingStateAfter == null; + pendingStateAfter = stateAfter; + } + currentState.mark(node); + } + if (pendingStateAfter != null) { + pendingStateAfter.applyToNonVirtual(new NodeClosure() { + public void apply(Node usage, Node nonVirtualNode) { + assert currentState.isMarked(nonVirtualNode) : nonVirtualNode + " not available at virtualstate " + usage + " at end of block " + block + " \n" + list; + } + }); + } + return currentState; + } + + @Override + protected NodeBitMap merge(Block merge, List states) { + NodeBitMap result = states.get(0); + for (int i = 1; i < states.size(); i++) { + result.intersect(states.get(i)); + } + return result; + } + + @Override + protected NodeBitMap getInitialState() { + return graph.createNodeBitMap(); + } + + @Override + protected NodeBitMap cloneState(NodeBitMap oldState) { + return oldState.copy(); + } + }; + + ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock()); + + } catch (Throwable t) { + throw new AssertionError("unschedulable graph", t); + } + return true; + } }