# HG changeset patch # User Lukas Stadler # Date 1339607354 -7200 # Node ID d52edd1af4c452609f5b30e3a0c456775818da2c # Parent c1d2cef3f2004eb02af2259f702da902774f322c SchedulePhase doesn't schedule FrameStates, added documentation, cleanups diff -r c1d2cef3f200 -r d52edd1af4c4 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Wed Jun 13 15:11:19 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Wed Jun 13 19:09:14 2012 +0200 @@ -381,7 +381,7 @@ lastState = fs; } - List nodes = lir.nodesFor(block); + List nodes = lir.nodesFor(block); for (int i = 0; i < nodes.size(); i++) { Node instr = nodes.get(i); diff -r c1d2cef3f200 -r d52edd1af4c4 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java Wed Jun 13 15:11:19 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java Wed Jun 13 19:09:14 2012 +0200 @@ -41,7 +41,7 @@ /** * Map from blocks to the nodes in each block. */ - private BlockMap> blockToNodesMap; + private BlockMap> blockToNodesMap; public SchedulePhase() { super("Schedule"); @@ -57,17 +57,20 @@ sortNodesWithinBlocks(graph); } + /** + * Sets {@link ScheduledNode#scheduledNext} on all scheduled nodes in all blocks using the scheduling built by @link {@link #run(StructuredGraph)}. + * This method should thus only be called when run has been successfully executed. + */ public void scheduleGraph() { + assert blockToNodesMap != null : "cannot set scheduledNext before run has been executed"; for (Block block : cfg.getBlocks()) { - List nodeList = blockToNodesMap.get(block); + List nodeList = blockToNodesMap.get(block); ScheduledNode last = null; - for (Node node : nodeList) { - if (!(node instanceof FrameState)) { - if (last != null) { - last.setScheduledNext((ScheduledNode) node); - } - last = (ScheduledNode) node; + for (ScheduledNode node : nodeList) { + if (last != null) { + last.setScheduledNext(node); } + last = node; } } } @@ -79,79 +82,86 @@ /** * Gets the map from each block to the nodes in the block. */ - public BlockMap> getBlockToNodesMap() { + public BlockMap> getBlockToNodesMap() { return blockToNodesMap; } /** * Gets the nodes in a given block. */ - public List nodesFor(Block block) { + public List nodesFor(Block block) { return blockToNodesMap.get(block); } private void assignBlockToNodes(StructuredGraph graph) { for (Block block : cfg.getBlocks()) { - List nodes = new ArrayList<>(); + List nodes = new ArrayList<>(); assert blockToNodesMap.get(block) == null; blockToNodesMap.put(block, nodes); - for (Node node : block.getNodes()) { + for (FixedNode node : block.getNodes()) { nodes.add(node); } } for (Node n : graph.getNodes()) { - assignBlockToNode(n); + if (n instanceof ScheduledNode) { + assignBlockToNode((ScheduledNode) n); + } } } - private void assignBlockToNode(Node n) { - if (n == null) { - return; - } + /** + * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are already assigned to a + * block, since they should already have been placed by {@link ControlFlowGraph#identifyBlocks()}. + * This method will also try to + */ + private void assignBlockToNode(ScheduledNode node) { + assert !node.isDeleted(); - assert !n.isDeleted(); - - Block prevBlock = cfg.getNodeToBlock().get(n); + Block prevBlock = cfg.getNodeToBlock().get(node); if (prevBlock != null) { return; } - assert !(n instanceof PhiNode) : n; - assert !(n instanceof MergeNode); + // PhiNodes and FixedNodes should already have been placed in blocks by ControlFlowGraph.identifyBlocks + assert !(node instanceof PhiNode) : node; + assert !(node instanceof FixedNode) : node; // if in CFG, schedule at the latest position possible in the outermost loop possible - Block latestBlock = latestBlock(n); + Block latestBlock = latestBlock(node); Block block; if (latestBlock == null) { - block = earliestBlock(n); - } else if (GraalOptions.ScheduleOutOfLoops && !(n instanceof VirtualObjectFieldNode) && !(n instanceof VirtualObjectNode)) { - Block earliestBlock = earliestBlock(n); - block = scheduleOutOfLoops(n, latestBlock, earliestBlock); - assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + n + " (" + earliestBlock + " needs to dominate " + block + ")"; + block = earliestBlock(node); + } else if (GraalOptions.ScheduleOutOfLoops && !(node instanceof VirtualObjectFieldNode) && !(node instanceof VirtualObjectNode)) { + Block earliestBlock = earliestBlock(node); + block = scheduleOutOfLoops(node, latestBlock, earliestBlock); + assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + node + " (" + earliestBlock + " needs to dominate " + block + ")"; } else { block = latestBlock; } - cfg.getNodeToBlock().set(n, block); - blockToNodesMap.get(block).add(n); + cfg.getNodeToBlock().set(node, block); + blockToNodesMap.get(block).add(node); } - private Block latestBlock(Node n) { - Block block = null; - for (Node succ : n.successors()) { - if (succ == null) { - continue; - } - assignBlockToNode(succ); - block = getCommonDominator(block, cfg.getNodeToBlock().get(succ)); + /** + * Calculates the last block that the given node could be scheduled in, i.e., the common dominator of all usages. + * To do so all usages are also assigned to blocks. + */ + private Block latestBlock(ScheduledNode node) { + CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null); + for (Node succ : node.successors().nonNull()) { + assert cfg.getNodeToBlock().get(succ) != null; + cdbc.apply(cfg.getNodeToBlock().get(succ)); } - ensureScheduledUsages(n); - CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(block); - for (Node usage : n.usages()) { - blocksForUsage(n, usage, cdbc); + ensureScheduledUsages(node); + for (Node usage : node.usages()) { + blocksForUsage(node, usage, cdbc); } return cdbc.block; } - private class CommonDominatorBlockClosure implements BlockClosure { + /** + * A closure that will calculate the common dominator of all blocks passed to its {@link #apply(Block)} method. + */ + private static class CommonDominatorBlockClosure implements BlockClosure { public Block block; public CommonDominatorBlockClosure(Block block) { this.block = block; @@ -162,42 +172,45 @@ } } - private Block earliestBlock(Node n) { - Block earliest = cfg.getNodeToBlock().get(n); + /** + * Determines the earliest block in which the given node can be scheduled. + */ + private Block earliestBlock(Node node) { + Block earliest = cfg.getNodeToBlock().get(node); if (earliest != null) { return earliest; } - earliest = earliestCache.get(n); + earliest = earliestCache.get(node); if (earliest != null) { return earliest; } - BitSet bits = new BitSet(cfg.getBlocks().length); - ArrayList before = new ArrayList<>(); - if (n.predecessor() != null) { - before.add(n.predecessor()); - } - for (Node input : n.inputs()) { - before.add(input); - } - for (Node pred : before) { - if (pred == null) { - continue; - } - Block b = earliestBlock(pred); - if (!bits.get(b.getId())) { - earliest = b; + /* + * All inputs must be in a dominating block, otherwise the graph cannot be scheduled. This implies that the + * inputs' blocks have a total ordering via their dominance relation. So in order to find the earliest block + * placement for this node we need to find the input block that is dominated by all other input blocks. + * + * While iterating over the inputs a set of dominator blocks of the current earliest placement is maintained. + * When the block of an input is not within this set, it becomes the current earliest placement and the list of + * dominator blocks is updated. + */ + BitSet dominators = new BitSet(cfg.getBlocks().length); + + assert node.predecessor() == null; + for (Node input : node.inputs().nonNull()) { + assert input instanceof ValueNode; + Block inputEarliest = earliestBlock(input); + if (!dominators.get(inputEarliest.getId())) { + earliest = inputEarliest; do { - bits.set(b.getId()); - b = b.getDominator(); - } while(b != null && !bits.get(b.getId())); + dominators.set(inputEarliest.getId()); + inputEarliest = inputEarliest.getDominator(); + } while(inputEarliest != null && !dominators.get(inputEarliest.getId())); } } if (earliest == null) { - Block start = cfg.getNodeToBlock().get(((StructuredGraph) n.graph()).start()); - assert start != null; - return start; + earliest = cfg.getStartBlock(); } - earliestCache.set(n, earliest); + earliestCache.set(node, earliest); return earliest; } @@ -224,8 +237,9 @@ * @param usage the usage whose blocks need to be considered * @param closure the closure that will be called for each block */ - private void blocksForUsage(Node node, Node usage, BlockClosure closure) { + private void blocksForUsage(ScheduledNode node, Node usage, BlockClosure closure) { assert !(node instanceof PhiNode); + if (usage instanceof PhiNode) { // An input to a PhiNode is used at the end of the predecessor block that corresponds to the PhiNode input. // One PhiNode can use an input multiple times, the closure will be called for each usage. @@ -246,26 +260,34 @@ closure.apply(mergeBlock.getPredecessors().get(i)); } } - } else if (usage instanceof FrameState && ((FrameState) usage).block() != null && !(node instanceof FrameState)) { - // If a FrameState belongs to a MergeNode then it's inputs will be placed at the common dominator of all EndNodes. - // BUT only if the input is neither a PhiNode (this method is never called for PhiNodes) nor a FrameState. - // A FrameState input is an outer FrameState. They should be placed into the same block as the usage, which is handled by the else. - MergeNode merge = ((FrameState) usage).block(); - Block block = null; - for (Node pred : merge.cfgPredecessors()) { - block = getCommonDominator(block, cfg.getNodeToBlock().get(pred)); + } else if (usage instanceof FrameState) { + // The following logic does not work if node is a PhiNode, but this method is never called for PhiNodes. + for (Node frameStateUsage : usage.usages()) { + if (frameStateUsage instanceof FrameState) { + // If a FrameState is an outer FrameState this method behaves as if the inner FrameState was the actual usage, by recursing. + blocksForUsage(node, frameStateUsage, closure); + } else if (frameStateUsage instanceof MergeNode) { + // If a FrameState belongs to a MergeNode then it's inputs will be placed at the common dominator of all EndNodes. + for (Node pred : frameStateUsage.cfgPredecessors()) { + closure.apply(cfg.getNodeToBlock().get(pred)); + } + } else { + // Otherwise: Put the input into the same block as the usage. + assert frameStateUsage instanceof StateSplit; + assignBlockToNode((ScheduledNode) frameStateUsage); + closure.apply(cfg.getNodeToBlock().get(frameStateUsage)); + } } - closure.apply(block); } else { - // All other types of usages: Just put the input into the same block as the usage. - assignBlockToNode(usage); + // All other types of usages: Put the input into the same block as the usage. + assignBlockToNode((ScheduledNode) usage); closure.apply(cfg.getNodeToBlock().get(usage)); } } private void ensureScheduledUsages(Node node) { - for (Node usage : node.usages().snapshot()) { - assignBlockToNode(usage); + for (Node usage : node.usages().filter(ScheduledNode.class)) { + assignBlockToNode((ScheduledNode) usage); } // now true usages are ready } @@ -281,21 +303,25 @@ } private void sortNodesWithinBlocks(StructuredGraph graph) { - NodeBitMap map = graph.createNodeBitMap(); + NodeBitMap visited = graph.createNodeBitMap(); for (Block b : cfg.getBlocks()) { - sortNodesWithinBlocks(b, map); + sortNodesWithinBlock(b, visited); } } - private void sortNodesWithinBlocks(Block b, NodeBitMap map) { - List instructions = blockToNodesMap.get(b); - List sortedInstructions = new ArrayList<>(instructions.size() + 2); + /** + * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over all inputs. + * This means that a node is added to the list after all its inputs have been processed. + */ + private void sortNodesWithinBlock(Block b, NodeBitMap visited) { + List instructions = blockToNodesMap.get(b); + List sortedInstructions = new ArrayList<>(instructions.size() + 2); - assert !map.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b; - assert !map.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b; + assert !visited.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b; + assert !visited.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b; - for (Node i : instructions) { - addToSorting(b, i, sortedInstructions, map); + for (ScheduledNode i : instructions) { + addToSorting(b, i, sortedInstructions, visited); } // Make sure that last node gets really last (i.e. when a frame state successor hangs off it). @@ -325,32 +351,44 @@ blockToNodesMap.put(b, sortedInstructions); } - private void addToSorting(Block b, Node i, List sortedInstructions, NodeBitMap map) { - if (i == null || map.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) { + private void addFrameStateToSorting(Block b, FrameState state, List sortedInstructions, NodeBitMap visited) { + if (state != null) { + assert !visited.isMarked(state); + + for (Node input : state.inputs()) { + if (input instanceof FrameState) { + addFrameStateToSorting(b, (FrameState) input, sortedInstructions, visited); + } else { + addToSorting(b, (ScheduledNode) input, sortedInstructions, visited); + } + } + } + } + + private void addToSorting(Block b, ScheduledNode i, List sortedInstructions, NodeBitMap visited) { + if (i == null || visited.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) { return; } FrameState state = null; - WriteNode writeNode = null; + WriteNode write = null; for (Node input : i.inputs()) { - if (input instanceof WriteNode && !map.isMarked(input) && cfg.getNodeToBlock().get(input) == b) { - writeNode = (WriteNode) input; + if (input instanceof WriteNode && !visited.isMarked(input) && cfg.getNodeToBlock().get(input) == b) { + assert write == null; + write = (WriteNode) input; } else if (input instanceof FrameState) { + assert state == null; state = (FrameState) input; } else { - addToSorting(b, input, sortedInstructions, map); + addToSorting(b, (ScheduledNode) input, sortedInstructions, visited); } } - if (i.predecessor() != null) { - addToSorting(b, i.predecessor(), sortedInstructions, map); - } - - map.mark(i); - - addToSorting(b, state, sortedInstructions, map); - assert writeNode == null || !map.isMarked(writeNode); - addToSorting(b, writeNode, sortedInstructions, map); + addToSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited); + visited.mark(i); + addFrameStateToSorting(b, state, sortedInstructions, visited); + assert write == null || !visited.isMarked(write); + addToSorting(b, write, sortedInstructions, visited); // Now predecessors and inputs are scheduled => we can add this node. sortedInstructions.add(i); diff -r c1d2cef3f200 -r d52edd1af4c4 graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java --- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java Wed Jun 13 15:11:19 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java Wed Jun 13 19:09:14 2012 +0200 @@ -30,7 +30,6 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.Verbosity; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.PhiNode.PhiType; diff -r c1d2cef3f200 -r d52edd1af4c4 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Wed Jun 13 15:11:19 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Wed Jun 13 19:09:14 2012 +0200 @@ -29,6 +29,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.lir.asm.*; import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; /** * This class implements the overall container for the LIR graph @@ -42,7 +43,7 @@ * The nodes for the blocks. * TODO: This should go away, we want all nodes connected with a next-pointer. */ - private final BlockMap> blockToNodesMap; + private final BlockMap> blockToNodesMap; /** * The linear-scan ordered list of blocks. @@ -87,7 +88,7 @@ * @param numLoops number of loops * @param compilation the compilation */ - public LIR(ControlFlowGraph cfg, BlockMap> blockToNodesMap, List linearScanOrder, List codeEmittingOrder) { + public LIR(ControlFlowGraph cfg, BlockMap> blockToNodesMap, List linearScanOrder, List codeEmittingOrder) { this.cfg = cfg; this.blockToNodesMap = blockToNodesMap; this.codeEmittingOrder = codeEmittingOrder; @@ -99,7 +100,7 @@ /** * Gets the nodes in a given block. */ - public List nodesFor(Block block) { + public List nodesFor(Block block) { return blockToNodesMap.get(block); } diff -r c1d2cef3f200 -r d52edd1af4c4 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Block.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Block.java Wed Jun 13 15:11:19 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Block.java Wed Jun 13 19:09:14 2012 +0200 @@ -24,7 +24,6 @@ import java.util.*; -import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; @@ -33,7 +32,7 @@ protected int id; protected BeginNode beginNode; - protected Node endNode; + protected FixedNode endNode; protected Loop loop; protected double probability; @@ -62,7 +61,7 @@ return beginNode; } - public Node getEndNode() { + public FixedNode getEndNode() { return endNode; } @@ -122,8 +121,8 @@ return postdominator; } - private class NodeIterator implements Iterator { - private Node cur; + private class NodeIterator implements Iterator { + private FixedNode cur; public NodeIterator() { cur = getBeginNode(); @@ -135,8 +134,8 @@ } @Override - public Node next() { - Node result = cur; + public FixedNode next() { + FixedNode result = cur; if (cur == getEndNode()) { cur = null; } else { @@ -152,10 +151,10 @@ } } - public Iterable getNodes() { - return new Iterable() { + public Iterable getNodes() { + return new Iterable() { @Override - public Iterator iterator() { + public Iterator iterator() { return new NodeIterator(); } }; diff -r c1d2cef3f200 -r d52edd1af4c4 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java Wed Jun 13 15:11:19 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java Wed Jun 13 19:09:14 2012 +0200 @@ -118,9 +118,9 @@ block.beginNode = (BeginNode) node; Node cur = node; + Node last; do { assert !cur.isDeleted(); - block.endNode = cur; assert nodeToBlock.get(cur) == null; nodeToBlock.set(cur, block); @@ -137,15 +137,11 @@ } } - Node next = null; - for (Node sux : cur.successors()) { - if (sux != null && !(sux instanceof BeginNode)) { - assert next == null; - next = sux; - } - } - cur = next; - } while (cur != null); + last = cur; + cur = cur.successors().first(); + } while (cur != null && !(cur instanceof BeginNode)); + + block.endNode = (FixedNode) last; } } diff -r c1d2cef3f200 -r d52edd1af4c4 graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraphScheduleTest.java --- a/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraphScheduleTest.java Wed Jun 13 15:11:19 2012 +0200 +++ b/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraphScheduleTest.java Wed Jun 13 19:09:14 2012 +0200 @@ -40,7 +40,7 @@ Block aBlock = nodeToBlock.get(a); if (bBlock == aBlock) { - List instructions = ibp.nodesFor(bBlock); + List instructions = ibp.nodesFor(bBlock); Assert.assertTrue(instructions.indexOf(b) > instructions.indexOf(a)); } else { Block block = bBlock;