# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1306512794 -7200
# Node ID f57594d3cd788452fe306d90777ee9394f50b352
# Parent  2af109bec0c00d6d08cce2c59cc6e963cf2802b4
Added code for sorting the nodes withing a block.

diff -r 2af109bec0c0 -r f57594d3cd78 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java
--- 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() {
diff -r 2af109bec0c0 -r f57594d3cd78 graal/GraalCompiler/src/com/sun/c1x/ir/Value.java
--- 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();
     }