# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1306501135 -7200
# Node ID e3a0630a1dab7ba6a27da18565b86d26b537f518
# Parent  58e65eb6bb5d54d7a9ccec498bf8e849c8309fb7
added code for computing dominators.

diff -r 58e65eb6bb5d -r e3a0630a1dab graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Fri May 27 14:20:30 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Fri May 27 14:58:55 2011 +0200
@@ -32,13 +32,26 @@
     private int blockID;
     private final List<Block> successors = new ArrayList<Block>();
     private final List<Block> predecessors = new ArrayList<Block>();
-    private final List<Instruction> instructions = new ArrayList<Instruction>();
+    private List<Instruction> instructions = new ArrayList<Instruction>();
     private boolean exceptionEntry;
+    private Block dominator;
+    private final List<Block> dominators = new ArrayList<Block>();
 
     public List<Block> getSuccessors() {
         return Collections.unmodifiableList(successors);
     }
 
+    public void setDominator(Block dominator) {
+        assert this.dominator == null;
+        assert dominator != null;
+        this.dominator = dominator;
+        dominator.dominators.add(this);
+    }
+
+    public List<Block> getDominators() {
+        return Collections.unmodifiableList(dominators);
+    }
+
     public List<Instruction> getInstructions() {
         return instructions;
     }
@@ -97,4 +110,12 @@
     public String toString() {
         return "B" + blockID;
     }
+
+    public Block dominator() {
+        return dominator;
+    }
+
+    public void setInstructions(List<Instruction> instructions) {
+        this.instructions = instructions;
+    }
 }
diff -r 58e65eb6bb5d -r e3a0630a1dab graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 27 14:20:30 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 27 14:58:55 2011 +0200
@@ -27,6 +27,8 @@
 import com.oracle.graal.graph.*;
 import com.sun.c1x.debug.*;
 import com.sun.c1x.ir.*;
+import com.sun.cri.ci.*;
+import com.sun.jmx.remote.util.*;
 
 
 public class Schedule {
@@ -149,20 +151,94 @@
             }
         }
 
-        orderBlocks();
+        //computeDominators();
+        //sortNodesWithinBlocks();
         //print();
     }
 
-    private void orderBlocks() {
-       /* List<Block> orderedBlocks = new ArrayList<Block>();
-        Block startBlock = nodeToBlock.get(graph.start().start());
-        List<Block> toSchedule = new ArrayList<Block>();
-        toSchedule.add(startBlock);
+    private void sortNodesWithinBlocks() {
+        for (Block b : blocks) {
+            sortNodesWithinBlocks(b);
+        }
+    }
+
+    private void sortNodesWithinBlocks(Block b) {
+        List<Instruction> instructions = b.getInstructions();
+        Collections.shuffle(instructions);
+
+        List<Instruction> sortedInstructions = new ArrayList<Instruction>();
+        sortedInstructions.addAll(instructions);
+        b.setInstructions(sortedInstructions);
+    }
+
+    private void computeDominators() {
+        Block dominatorRoot = nodeToBlock.get(graph.start());
+        assert dominatorRoot.getPredecessors().size() == 0;
+        CiBitMap visited = new CiBitMap(blocks.size());
+        visited.set(dominatorRoot.blockID());
+        LinkedList<Block> workList = new LinkedList<Block>();
+        workList.add(dominatorRoot);
+
+        while (!workList.isEmpty()) {
+            Block b = workList.remove();
+
+            TTY.println("processing" + b);
+            List<Block> predecessors = b.getPredecessors();
+            if (predecessors.size() == 1) {
+                b.setDominator(predecessors.get(0));
+            } else if (predecessors.size() > 0) {
+                boolean delay = false;
+                for (Block pred : predecessors) {
+                    if (pred != dominatorRoot && pred.dominator() == null) {
+                        delay = true;
+                        break;
+                    }
+                }
 
-        while (toSchedule.size() != 0) {
+                if (delay) {
+                    workList.add(b);
+                    continue;
+                }
+
+                Block dominator = null;
+                for (Block pred : predecessors) {
+                    if (dominator == null) {
+                        dominator = pred;
+                    } else {
+                        dominator = commonDominator(dominator, pred);
+                    }
+                }
+                b.setDominator(dominator);
+            }
 
+            for (Block succ : b.getSuccessors()) {
+                if (!visited.get(succ.blockID())) {
+                    visited.set(succ.blockID());
+                    workList.add(succ);
+                }
+            }
+        }
+    }
 
-        }*/
+    public Block commonDominator(Block a, Block b) {
+        CiBitMap bitMap = new CiBitMap(blocks.size());
+        Block cur = a;
+        while (cur != null) {
+            bitMap.set(cur.blockID());
+            cur = cur.dominator();
+        }
+
+        cur = b;
+        while (cur != null) {
+            if (bitMap.get(cur.blockID())) {
+                return cur;
+            }
+            cur = cur.dominator();
+        }
+
+        print();
+        assert false : "no common dominator between " + a + " and " + b;
+        return null;
     }
 
     private void print() {
@@ -185,6 +261,10 @@
            for (Block pred : b.getPredecessors()) {
                TTY.print(pred + ";");
            }
+
+           if (b.dominator() != null) {
+               TTY.print(" dom=" + b.dominator());
+           }
            TTY.println();
 
            if (b.getInstructions().size() > 0) {
diff -r 58e65eb6bb5d -r e3a0630a1dab graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java	Fri May 27 14:20:30 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java	Fri May 27 14:58:55 2011 +0200
@@ -95,18 +95,22 @@
         builder.append(" [");
 
         builder.append("]");
-        //if (end() != null) {
-            builder.append(" -> ");
-            boolean hasSucc = false;
-            for (Node s : this.successors()) {
-                if (hasSucc) {
-                    builder.append(", ");
-                }
-                builder.append("#");
+
+        builder.append(" -> ");
+        boolean hasSucc = false;
+        for (Node s : this.successors()) {
+            if (hasSucc) {
+                builder.append(", ");
+            }
+            builder.append("#");
+            if (s != null) {
                 builder.append(s.id());
-                hasSucc = true;
+            } else {
+                builder.append("null");
             }
-        //}
+            hasSucc = true;
+        }
+
         return builder.toString();
     }