Mercurial > hg > truffle
changeset 2802:f57594d3cd78
Added code for sorting the nodes withing a block.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Fri, 27 May 2011 18:13:14 +0200 |
parents | 2af109bec0c0 |
children | 6a1e5d7e1f4e |
files | graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java graal/GraalCompiler/src/com/sun/c1x/ir/Value.java |
diffstat | 2 files changed, 64 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Fri May 27 15:11:34 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Fri May 27 18:13:14 2011 +0200 @@ -148,11 +148,50 @@ } } - //computeDominators(); - //sortNodesWithinBlocks(); + computeDominators(); + assignLatestPossibleBlockToNodes(); + sortNodesWithinBlocks(); //print(); } + private void assignLatestPossibleBlockToNodes() { + for (Node n : graph.getNodes()) { + assignLatestPossibleBlockToNode(n); + } + } + + private Block assignLatestPossibleBlockToNode(Node n) { + if (n == null) { + return null; + } + + Block prevBlock = nodeToBlock.get(n); + if (prevBlock != null) { + return prevBlock; + } + + Block block = null; + for (Node succ : n.successors()) { + block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ)); + } + for (Node usage : n.usages()) { + block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); + } + + nodeToBlock.set(n, block); + return block; + } + + private Block getCommonDominator(Block a, Block b) { + if (a == null) { + return b; + } + if (b == null) { + return a; + } + return commonDominator(a, b); + } + private void sortNodesWithinBlocks() { NodeBitMap map = graph.createNodeBitMap(); for (Block b : blocks) { @@ -165,14 +204,30 @@ Collections.shuffle(instructions); List<Node> sortedInstructions = new ArrayList<Node>(); - sortedInstructions.addAll(instructions); + for (Node i : instructions) { + addToSorting(b, i, sortedInstructions, map); + } b.setInstructions(sortedInstructions); + } + + private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) { + if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b) { + return; + } + TTY.println("addToSorting " + i.id() + " " + i.getClass().getName()); - for (Node i : instructions) { - if (!map.isMarked(i)) { + for (Node input : i.inputs()) { + if (input != null) TTY.println("visiting input " + input.id() + " " + input.getClass().getName()); + addToSorting(b, input, sortedInstructions, map); + } - } + for (Node pred : i.predecessors()) { + addToSorting(b, pred, sortedInstructions, map); } + + // Now predecessors and inputs are scheduled => we can add this node. + sortedInstructions.add(i); + map.mark(i); } private void computeDominators() {
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Value.java Fri May 27 15:11:34 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Value.java Fri May 27 18:13:14 2011 +0200 @@ -245,6 +245,9 @@ } builder.append(getClass().getSimpleName()); builder.append(" [").append(flagsToString()).append("]"); + for (Node input : inputs()) { + TTY.println("input: " + input); + } return builder.toString(); }