--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Fri May 27 18:14:36 2011 +0200
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.sun.c1x.ir.*;
 
 
@@ -32,14 +33,27 @@
     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<Node> instructions = new ArrayList<Node>();
     private boolean exceptionEntry;
+    private Block dominator;
+    private final List<Block> dominators = new ArrayList<Block>();
 
     public List<Block> getSuccessors() {
         return Collections.unmodifiableList(successors);
     }
 
-    public List<Instruction> getInstructions() {
+    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<Node> getInstructions() {
         return instructions;
     }
 
@@ -97,4 +111,12 @@
     public String toString() {
         return "B" + blockID;
     }
+
+    public Block dominator() {
+        return dominator;
+    }
+
+    public void setInstructions(List<Node> instructions) {
+        this.instructions = instructions;
+    }
 }

--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 27 18:14:36 2011 +0200
@@ -27,6 +27,7 @@
 import com.oracle.graal.graph.*;
 import com.sun.c1x.debug.*;
 import com.sun.c1x.ir.*;
+import com.sun.cri.ci.*;
 
 
 public class Schedule {
@@ -66,9 +67,7 @@
     private Block assignBlock(Node n, Block b) {
         assert nodeToBlock.get(n) == null;
         nodeToBlock.set(n, b);
-        if (n != n.graph().start()) {
-            b.getInstructions().add((Instruction) n);
-        }
+        b.getInstructions().add(n);
         return b;
     }
 
@@ -161,20 +160,156 @@
             }
         }
 
-        orderBlocks();
-//        print();
+        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) {
+            sortNodesWithinBlocks(b, map);
+        }
+    }
+
+    private void sortNodesWithinBlocks(Block b, NodeBitMap map) {
+        List<Node> instructions = b.getInstructions();
+        Collections.shuffle(instructions);
+
+        List<Node> sortedInstructions = new ArrayList<Node>();
+        for (Node i : instructions) {
+            addToSorting(b, i, sortedInstructions, map);
+        }
+        b.setInstructions(sortedInstructions);
     }
 
-    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 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 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() {
+        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() {
@@ -197,6 +332,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) {

--- a/graal/GraalCompiler/src/com/sun/c1x/debug/BlockPrinter.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/BlockPrinter.java	Fri May 27 18:14:36 2011 +0200
@@ -22,6 +22,7 @@
  */
 package com.sun.c1x.debug;
 
+import com.oracle.graal.graph.*;
 import com.oracle.max.graal.schedule.*;
 import com.sun.c1x.graph.*;
 import com.sun.c1x.ir.*;
@@ -44,7 +45,7 @@
     public void apply(Block block) {
         if (cfgOnly) {
             if (block.getInstructions().size() > 0) {
-                ip.printInstruction(block.getInstructions().get(0));
+                ip.printInstruction((Instruction) block.getInstructions().get(0));
             } else {
                 ip.out().println("Empty block");
             }
@@ -60,8 +61,10 @@
 
         ip.printInstructionListingHeader();
 
-        for (Instruction i : block.getInstructions()) {
-            ip.printInstructionListing(i);
+        for (Node i : block.getInstructions()) {
+            if (i instanceof Instruction) {
+                ip.printInstructionListing((Instruction) i);
+            }
         }
         out.println();
 

--- a/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java	Fri May 27 18:14:36 2011 +0200
@@ -25,6 +25,7 @@
 import java.io.*;
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.oracle.max.graal.schedule.*;
 import com.sun.c1x.*;
 import com.sun.c1x.alloc.*;
@@ -407,8 +408,10 @@
         begin("IR");
         out.println("HIR");
         out.disableIndentation();
-        for (Instruction i : block.getInstructions()) {
-            printInstructionHIR(i);
+        for (Node i : block.getInstructions()) {
+            if (i instanceof Instruction) {
+                printInstructionHIR((Instruction) i);
+            }
         }
         out.enableIndentation();
         end("IR");

--- a/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java	Fri May 27 18:14:36 2011 +0200
@@ -224,8 +224,11 @@
             TTY.println("BEGIN Generating LIR for block B" + block.blockID());
         }
 
-        for (Instruction instr : block.getInstructions()) {
-            FrameState stateAfter = instr.stateAfter();
+        for (Node instr : block.getInstructions()) {
+            FrameState stateAfter = null;
+            if (instr instanceof Instruction) {
+                stateAfter = ((Instruction) instr).stateAfter();
+            }
             FrameState stateBefore = null;
             if (instr instanceof StateSplit && ((StateSplit) instr).stateBefore() != null) {
                 stateBefore = ((StateSplit) instr).stateBefore();
@@ -239,9 +242,9 @@
                     }
                 }
             }
-            if (!(instr instanceof Merge)) {
+            if (!(instr instanceof Merge) && instr != instr.graph().start()) {
                 walkState(instr, stateAfter);
-                doRoot(instr);
+                doRoot((Value) instr);
             }
             if (stateAfter != null) {
                 lastState = stateAfter;
@@ -1215,12 +1218,11 @@
         return res.toArray(new SwitchRange[res.size()]);
     }
 
-    void doRoot(Instruction instr) {
+    void doRoot(Value instr) {
         if (C1XOptions.TraceLIRGeneratorLevel >= 2) {
-            TTY.println("Emitting LIR for instruction " + instr.toString());
+            TTY.println("Emitting LIR for instruction " + instr);
         }
         currentInstruction = instr;
-        assert !instr.hasSubst() : "shouldn't have missed substitution";
 
         if (C1XOptions.TraceLIRVisit) {
             TTY.println("Visiting    " + instr);
@@ -1289,7 +1291,7 @@
 
     private List<Phi> getPhis(LIRBlock block) {
         if (block.getInstructions().size() > 0) {
-            Instruction i = block.getInstructions().get(0);
+            Node i = block.getInstructions().get(0);
             if (i instanceof Merge) {
                 List<Phi> result = new ArrayList<Phi>();
                 for (Node n : i.usages()) {
@@ -1431,7 +1433,7 @@
         }
     }
 
-    protected void walkState(Instruction x, FrameState state) {
+    protected void walkState(Node x, FrameState state) {
         if (state == null) {
             return;
         }
@@ -1453,7 +1455,6 @@
 
     private void walkStateValue(Value value) {
         if (value != null) {
-            assert !value.hasSubst() : "missed substitution on " + value.toString();
             if (value instanceof Phi && !value.isIllegal()) {
                 // phi's are special
                 operandForPhi((Phi) value);

--- a/graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java	Fri May 27 18:14:36 2011 +0200
@@ -105,8 +105,8 @@
 
         // This goto is not a safepoint.
         Anchor e = new Anchor(null, graph);
-        Instruction sourceInstruction = source.getInstructions().get(source.getInstructions().size() - 1);
-        Instruction targetInstruction = target.getInstructions().get(0);
+        Node sourceInstruction = source.getInstructions().get(source.getInstructions().size() - 1);
+        Node targetInstruction = target.getInstructions().get(0);
         int sourceInstructionPredIndex = targetInstruction.predecessors().indexOf(sourceInstruction);
         int replacedIndex = targetInstruction.predecessorsIndex().get(sourceInstructionPredIndex);
         assert replacedIndex != -1 && sourceInstruction.successors().get(replacedIndex) != null;

--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Fri May 27 18:14:36 2011 +0200
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.oracle.max.graal.schedule.*;
 import com.sun.c1x.*;
 import com.sun.c1x.debug.*;
@@ -62,7 +63,7 @@
         this.compilation = compilation;
     }
 
-    public Map<Value, LIRBlock> valueToBlock;
+    public Map<Node, LIRBlock> valueToBlock;
 
     /**
      * Builds the graph, optimizes it, and computes the linear scan block order.
@@ -116,9 +117,9 @@
 
         orderedBlocks = lirBlocks;
 
-        valueToBlock = new HashMap<Value, LIRBlock>();
+        valueToBlock = new HashMap<Node, LIRBlock>();
         for (LIRBlock b : orderedBlocks) {
-            for (Instruction i : b.getInstructions()) {
+            for (Node i : b.getInstructions()) {
                 valueToBlock.put(i, b);
             }
         }

--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java	Fri May 27 18:14:36 2011 +0200
@@ -81,20 +81,22 @@
         builder.append(" [");
 
         builder.append("]");
-        //if (end() != null) {
-            builder.append(" -> ");
-            boolean hasSucc = false;
-            for (Node s : this.successors()) {
-                if (s != null) {
-                    if (hasSucc) {
-                        builder.append(", ");
-                    }
-                    builder.append("#");
-                    builder.append(s.id());
-                    hasSucc = true;
-                }
+
+        builder.append(" -> ");
+        boolean hasSucc = false;
+        for (Node s : this.successors()) {
+            if (hasSucc) {
+                builder.append(", ");
             }
-        //}
+            builder.append("#");
+            if (s != null) {
+                builder.append(s.id());
+            } else {
+                builder.append("null");
+            }
+            hasSucc = true;
+        }
+
         return builder.toString();
     }
 
@@ -246,10 +248,11 @@
                 sb.append("] ");
             }
         }
-        if (value != null && value.hasSubst()) {
-            sb.append("alias ").append(Util.valueString(value.subst()));
-        }
         return sb.toString();
     }
 
+    @Override
+    public String shortName() {
+        return "Merge #" + id();
+    }
 }

--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Value.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Value.java	Fri May 27 18:14:36 2011 +0200
@@ -56,11 +56,6 @@
 
     protected CiValue operand = CiValue.IllegalValue;
 
-    /**
-     * Used by {@link InstructionSubstituter}.
-     */
-    public Value subst;
-
     public abstract Merge block();
 
     /**
@@ -89,30 +84,6 @@
         throw new CloneNotSupportedException();
     }
 
-    /////////////////
-
-    /**
-     * Gets the instruction that should be substituted for this one. Note that this
-     * method is recursive; if the substituted instruction has a substitution, then
-     * the final substituted instruction will be returned. If there is no substitution
-     * for this instruction, {@code this} will be returned.
-     * @return the substitution for this instruction
-     */
-    public final Value subst() {
-        if (subst == null) {
-            return this;
-        }
-        return subst.subst();
-    }
-
-    /**
-     * Checks whether this instruction has a substitute.
-     * @return {@code true} if this instruction has a substitution.
-     */
-    public final boolean hasSubst() {
-        return subst != null;
-    }
-
     /**
      * Check whether this instruction has the specified flag set.
      * @param flag the flag to test
@@ -274,6 +245,9 @@
         }
         builder.append(getClass().getSimpleName());
         builder.append(" [").append(flagsToString()).append("]");
+        for (Node input : inputs()) {
+            TTY.println("input: " + input);
+        }
         return builder.toString();
     }
 

--- a/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java	Fri May 27 17:48:28 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java	Fri May 27 18:14:36 2011 +0200
@@ -24,10 +24,10 @@
 
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.oracle.max.asm.*;
 import com.sun.c1x.alloc.*;
 import com.sun.c1x.debug.*;
-import com.sun.c1x.ir.*;
 import com.sun.c1x.util.*;
 import com.sun.c1x.value.*;
 import com.sun.cri.ci.*;
@@ -41,7 +41,7 @@
     private LIRList lir;
     private final int blockID;
     private FrameState lastState;
-    private List<Instruction> instructions = new ArrayList<Instruction>(4);
+    private List<Node> instructions = new ArrayList<Node>(4);
     private List<LIRBlock> predecessors = new ArrayList<LIRBlock>(4);
     private List<LIRBlock> successors = new ArrayList<LIRBlock>(4);
     private List<LIRBlock> exceptionHandlerSuccessors = new ArrayList<LIRBlock>(4);
@@ -89,7 +89,7 @@
         linearScanNumber = blockID;
     }
 
-    public List<Instruction> getInstructions() {
+    public List<Node> getInstructions() {
         return instructions;
     }
 
@@ -248,7 +248,7 @@
         predecessors.clear();
     }
 
-    public void setInstructions(List<Instruction> list) {
+    public void setInstructions(List<Node> list) {
         instructions = list;
     }