# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1306265985 -7200
# Node ID 2ac7b30b729011e37a00b0ab88b46dbe8879bc61
# Parent  3e4d992fd31265bb81e932822db1f1da7e2b61af
Enabled new block finding algorithm.

diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Tue May 24 21:39:45 2011 +0200
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.sun.c1x.debug.*;
 import com.sun.c1x.ir.*;
 
 
@@ -33,6 +34,7 @@
     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 boolean exceptionEntry;
 
     public List<Block> getSuccessors() {
         return Collections.unmodifiableList(successors);
@@ -59,8 +61,28 @@
         return blockID;
     }
 
+    public void setExceptionEntry(boolean b) {
+        exceptionEntry = b;
+    }
+
+    public boolean isExceptionEntry() {
+        return exceptionEntry;
+    }
+
     @Override
     public String toString() {
         return "B" + blockID;
     }
+
+    public void removeExceptionSuccessors() {
+        for (int i = 0; i < successors.size(); ++i) {
+            TTY.println("checking succ");
+            if (successors.get(i).isExceptionEntry()) {
+                TTY.println("removing successor " + i);
+                successors.remove(i);
+                i--;
+            }
+        }
+
+    }
 }
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Tue May 24 21:39:45 2011 +0200
@@ -55,6 +55,7 @@
     }
 
     private Block assignBlock(Node n) {
+        assert n instanceof BlockBegin : n;
         Block curBlock = nodeToBlock.get(n);
         if (curBlock == null) {
             curBlock = createBlock();
@@ -111,13 +112,27 @@
                             successorCount++;
                             if (successorCount > 1) {
                                 // Our predecessor is a split => we need a new block.
-                                assignBlock(n);
+                                if (singlePred instanceof ExceptionEdgeInstruction) {
+                                    ExceptionEdgeInstruction e = (ExceptionEdgeInstruction) singlePred;
+                                    if (e.exceptionEdge() != n) {
+                                        break;
+                                    }
+                                }
+                                Block b = assignBlock(n);
+                                b.setExceptionEntry(singlePred instanceof ExceptionEdgeInstruction);
                                 blockBeginNodes.add(n);
                                 return true;
                             }
                         }
                     }
-                    assignBlock(n, nodeToBlock.get(singlePred));
+
+                    if (singlePred instanceof BlockEnd) {
+                        Block b = assignBlock(n);
+                        b.setExceptionEntry(singlePred instanceof Throw);
+                        blockBeginNodes.add(n);
+                    } else {
+                        assignBlock(n, nodeToBlock.get(singlePred));
+                    }
                 }
                 return true;
             }}
@@ -134,14 +149,32 @@
             }
         }
 
+        orderBlocks();
         //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);
+
+        while (toSchedule.size() != 0) {
+
+
+        }*/
+    }
+
     private void print() {
         TTY.println("============================================");
         TTY.println("%d blocks", blocks.size());
+
         for (Block b : blocks) {
+           TTY.println();
            TTY.print(b.toString());
+           if (b.isExceptionEntry()) {
+               TTY.print(" (ex)");
+           }
 
            TTY.print(" succs=");
            for (Block succ : b.getSuccessors()) {
@@ -153,9 +186,11 @@
                TTY.print(pred + ";");
            }
            TTY.println();
+           TTY.print("first instr: " + b.getInstructions().get(0));
+           TTY.print("last instr: " + b.getInstructions().get(b.getInstructions().size() - 1));
         }
 
-
+/*
         TTY.println("============================================");
         TTY.println("%d nodes", nodeToBlock.size());
         for (Node n : graph.getNodes()) {
@@ -167,6 +202,6 @@
                 }
                 TTY.println();
             }
-        }
+        }*/
     }
 }
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/alloc/ControlFlowOptimizer.java
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/ControlFlowOptimizer.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/ControlFlowOptimizer.java	Tue May 24 21:39:45 2011 +0200
@@ -103,7 +103,7 @@
 
         assert instructions.size() >= 2 : "block must have label and branch";
         assert instructions.get(0).code == LIROpcode.Label : "first instruction must always be a label";
-        assert instructions.get(instructions.size() - 1) instanceof LIRBranch : "last instruction must always be a branch";
+        assert instructions.get(instructions.size() - 1) instanceof LIRBranch : "last instruction must always be a branch but is " + instructions.get(instructions.size() - 1);
         assert ((LIRBranch) instructions.get(instructions.size() - 1)).cond() == Condition.TRUE : "branch must be unconditional";
         assert ((LIRBranch) instructions.get(instructions.size() - 1)).block() == block.suxAt(0) : "branch target must be the successor";
 
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java	Tue May 24 21:39:45 2011 +0200
@@ -126,6 +126,8 @@
         // setup a list with the LIR instructions of all predecessors
         for (int i = 0; i < numPreds; i++) {
             LIRBlock pred = block.predAt(i);
+            assert pred != null;
+            assert pred.lir() != null;
             List<LIRInstruction> predInstructions = pred.lir().instructionsList();
 
             if (pred.numberOfSux() != 1) {
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java	Tue May 24 21:39:45 2011 +0200
@@ -27,6 +27,7 @@
 
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.sun.c1x.*;
 import com.sun.c1x.alloc.Interval.*;
 import com.sun.c1x.debug.*;
@@ -1159,6 +1160,14 @@
             final int blockFrom = block.firstLirInstructionId();
             int blockTo = block.lastLirInstructionId();
 
+            // (tw) Destroy all registers on exception handler entry.
+            if (block.isExceptionEntry()) {
+                for (CiRegister r : callerSaveRegs) {
+                    if (attributes(r).isAllocatable) {
+                        addTemp(r.asValue(), block.firstLirInstructionId(), RegisterPriority.None, CiKind.Illegal);
+                    }
+                }
+            }
             assert blockFrom == instructions.get(0).id;
             assert blockTo == instructions.get(instructions.size() - 1).id;
 
@@ -1263,6 +1272,22 @@
 
             } // end of instruction iteration
 
+
+            // (tw) TODO: Check if this matters..
+            // (tw) Make sure that no spill store optimization is applied for phi instructions that flow into exception handlers.
+//            if (block.isExceptionEntry()) {
+//                Instruction firstInstruction = block.getInstructions().get(0);
+//                for (Node n : firstInstruction.usages()) {
+//                    if (n instanceof Phi) {
+//                        Phi phi = (Phi) n;
+//                        Interval interval = intervalFor(phi.operand());
+//                        if (interval != null) {
+//                            interval.setSpillState(SpillState.NoOptimization);
+//                        }
+//                    }
+//                }
+//            }
+
         } // end of block iteration
 
         // add the range [0, 1] to all fixed intervals.
@@ -1589,7 +1614,7 @@
             if (block.numberOfPreds() == 1 && block.numberOfSux() == 1) {
                 List<LIRInstruction> instructions = block.lir().instructionsList();
                 assert instructions.get(0).code == LIROpcode.Label : "block must start with label";
-                assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successors must end with branch";
+                assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successors must end with branch (" + block + "), " + instructions.get(instructions.size() - 1);
                 assert ((LIRBranch) instructions.get(instructions.size() - 1)).cond() == Condition.TRUE : "block with successor must end with unconditional branch";
 
                 // check if block is empty (only label and branch)
@@ -2065,8 +2090,8 @@
         }
 
         printLir("After register number assignment", true);
-        EdgeMoveOptimizer.optimize(ir.linearScanOrder());
-        ControlFlowOptimizer.optimize(ir);
+        //EdgeMoveOptimizer.optimize(ir.linearScanOrder());
+        //ControlFlowOptimizer.optimize(ir);
         printLir("After control flow optimization", false);
     }
 
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java
--- a/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java	Tue May 24 21:39:45 2011 +0200
@@ -175,6 +175,9 @@
         begin("states");
 
         FrameState state = block.stateBefore();
+        if (state == null) {
+            return;
+        }
         int stackSize = state.stackSize();
         if (stackSize > 0) {
             begin("stack");
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java
--- a/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java	Tue May 24 21:39:45 2011 +0200
@@ -392,8 +392,8 @@
 
         // emit phi-instruction moves after safepoint since this simplifies
         // describing the state at the safepoint.
-        moveToPhi(x.stateAfter());
 
+        moveToPhi();
         lir.jump(getLIRBlock(x.defaultSuccessor()));
     }
 
@@ -1266,11 +1266,6 @@
         }
     }
 
-    protected void moveToPhi() {
-        assert lastState != null;
-        this.moveToPhi(lastState);
-    }
-
     private List<Phi> getPhis(LIRBlock block) {
         if (block.getInstructions().size() > 0) {
             Instruction i = block.getInstructions().get(0);
@@ -1287,7 +1282,7 @@
         return null;
     }
 
-    protected void moveToPhi(FrameState curState) {
+    protected void moveToPhi() {
         // Moves all stack values into their phi position
         LIRBlock bb = currentBlock;
         if (bb.numberOfSux() == 1) {
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/graph/IR.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Tue May 24 21:39:45 2011 +0200
@@ -86,33 +86,37 @@
 
         Schedule schedule = new Schedule(this.compilation.graph);
         List<Block> blocks = schedule.getBlocks();
-        NodeMap<Block> nodeToBlock = schedule.getNodeToBlock();
-       /* orderedBlocks = new ArrayList<LIRBlock>();
+        List<LIRBlock> lirBlocks = new ArrayList<LIRBlock>();
         Map<Block, LIRBlock> map = new HashMap<Block, LIRBlock>();
         for (Block b : blocks) {
             LIRBlock block = new LIRBlock(b.blockID());
+            block.setExceptionEntry(b.isExceptionEntry());
             map.put(b, block);
             block.setInstructions(b.getInstructions());
-            orderedBlocks.add(block);
+            block.setLinearScanNumber(b.blockID());
+            lirBlocks.add(block);
         }
 
         for (Block b : blocks) {
             for (Block succ : b.getSuccessors()) {
-                map.get(b).blockSuccessors().add(map.get(succ));
+                if (succ.isExceptionEntry()) {
+                    map.get(b).getExceptionHandlerSuccessors().add(map.get(succ));
+                } else {
+                    map.get(b).blockSuccessors().add(map.get(succ));
+                }
             }
 
             for (Block pred : b.getPredecessors()) {
                 map.get(b).blockPredecessors().add(map.get(pred));
             }
-        }*/
+        }
 
 
-        // TODO(tw): Schedule nodes within a block.
-
+     // TODO(tw): Schedule nodes within a block.
+        //computeLinearScanOrder();
 
-
-
-        computeLinearScanOrder();
+//        assert orderedBlocks.size() == lirBlocks.size();
+        orderedBlocks = lirBlocks;
 
 
         valueToBlock = new HashMap<Value, LIRBlock>();
@@ -125,6 +129,37 @@
         assert startBlock != null;
         verifyAndPrint("After linear scan order");
 
+        ComputeLinearScanOrder clso = new ComputeLinearScanOrder(lirBlocks.size(), startBlock);
+        orderedBlocks = clso.linearScanOrder();
+        this.compilation.stats.loopCount = clso.numLoops();
+
+        int z = 0;
+        for (LIRBlock b : orderedBlocks) {
+            b.setLinearScanNumber(z++);
+
+        /*    TTY.println();
+
+            for (Instruction i : b.getInstructions()) {
+                if (i instanceof BlockBegin) {
+                    TTY.println("BlockBegin #" + ((BlockBegin) i).blockID);
+
+                    TTY.print("    => succs: ");
+                    for (LIRBlock succBlock : b.blockSuccessors()) {
+                        TTY.print("B#" + ((BlockBegin) succBlock.getInstructions().get(0)).blockID);
+                    }
+                    TTY.print("    => ex: ");
+                    for (LIRBlock succBlock : b.getExceptionHandlerSuccessors()) {
+                        TTY.print("B#" + ((BlockBegin) succBlock.getInstructions().get(0)).blockID);
+                    }
+                    TTY.println();
+                } else {
+                    TTY.println(i.getClass().getSimpleName() + " #" + i.id());
+                }
+            }*/
+        }
+
+
+
         if (C1XOptions.PrintTimers) {
             C1XTimers.HIR_OPTIMIZE.stop();
         }
@@ -145,7 +180,7 @@
     }
 
     private Map<Value, LIRBlock> makeLinearScanOrder() {
-
+/*
         if (orderedBlocks == null) {
 
             Map<Value, LIRBlock> valueToBlock = new HashMap<Value, LIRBlock>();
@@ -160,7 +195,6 @@
                 valueToBlock.put(bb, lirBlock);
                 lirBlock.setLinearScanNumber(bb.linearScanNumber());
                 // TODO(tw): Initialize LIRBlock.linearScanLoopHeader and LIRBlock.linearScanLoopEnd
-                lirBlock.setStateBefore(bb.stateBefore());
                 orderedBlocks.add(lirBlock);
                 ++z;
             }
@@ -185,8 +219,9 @@
                 ++z;
             }
 
-        }
-        return valueToBlock;
+        }*/
+        return null;
+        //return valueToBlock;
     }
 
     /**
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java	Tue May 24 21:39:45 2011 +0200
@@ -27,6 +27,7 @@
 
 import com.sun.c1x.*;
 import com.sun.c1x.debug.*;
+import com.sun.c1x.lir.*;
 import com.sun.c1x.util.*;
 import com.sun.cri.ci.*;
 
@@ -35,69 +36,71 @@
     private final int maxBlockId; // the highest blockId of a block
     private int numBlocks; // total number of blocks (smaller than maxBlockId)
     private int numLoops; // total number of loops
+    private boolean iterativeDominators; // method requires iterative computation of dominators
 
-    List<BlockBegin> linearScanOrder; // the resulting list of blocks in correct order
+    List<LIRBlock> linearScanOrder; // the resulting list of blocks in correct order
 
     final CiBitMap visitedBlocks; // used for recursive processing of blocks
     final CiBitMap activeBlocks; // used for recursive processing of blocks
+    final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator
     final int[] forwardBranches; // number of incoming forward branches for each block
-    final List<BlockBegin> loopEndBlocks; // list of all loop end blocks collected during countEdges
+    final List<LIRBlock> loopEndBlocks; // list of all loop end blocks collected during countEdges
     BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop
-    final List<BlockBegin> workList; // temporary list (used in markLoops and computeOrder)
+    final List<LIRBlock> workList; // temporary list (used in markLoops and computeOrder)
 
     // accessors for visitedBlocks and activeBlocks
-    private void initVisited() {
+    void initVisited() {
         activeBlocks.clearAll();
         visitedBlocks.clearAll();
     }
 
-    private boolean isVisited(BlockBegin b) {
-        return visitedBlocks.get(b.blockID);
+    boolean isVisited(LIRBlock b) {
+        return visitedBlocks.get(b.blockID());
     }
 
-    private boolean isActive(BlockBegin b) {
-        return activeBlocks.get(b.blockID);
+    boolean isActive(LIRBlock b) {
+        return activeBlocks.get(b.blockID());
     }
 
-    private void setVisited(BlockBegin b) {
+    void setVisited(LIRBlock b) {
         assert !isVisited(b) : "already set";
-        visitedBlocks.set(b.blockID);
+        visitedBlocks.set(b.blockID());
     }
 
-    private void setActive(BlockBegin b) {
+    void setActive(LIRBlock b) {
         assert !isActive(b) : "already set";
-        activeBlocks.set(b.blockID);
+        activeBlocks.set(b.blockID());
     }
 
-    private void clearActive(BlockBegin b) {
+    void clearActive(LIRBlock b) {
         assert isActive(b) : "not already";
-        activeBlocks.clear(b.blockID);
+        activeBlocks.clear(b.blockID());
     }
 
     // accessors for forwardBranches
-    private void incForwardBranches(BlockBegin b) {
-        forwardBranches[b.blockID]++;
+    void incForwardBranches(LIRBlock b) {
+        forwardBranches[b.blockID()]++;
     }
 
-    private int decForwardBranches(BlockBegin b) {
-        return --forwardBranches[b.blockID];
+    int decForwardBranches(LIRBlock b) {
+        return --forwardBranches[b.blockID()];
     }
 
     // accessors for loopMap
-    private boolean isBlockInLoop(int loopIdx, BlockBegin b) {
-        return loopMap.at(loopIdx, b.blockID);
+    boolean isBlockInLoop(int loopIdx, LIRBlock b) {
+        return loopMap.at(loopIdx, b.blockID());
     }
 
-    private void setBlockInLoop(int loopIdx, BlockBegin b) {
-        loopMap.setBit(loopIdx, b.blockID);
+    void setBlockInLoop(int loopIdx, LIRBlock b) {
+        loopMap.setBit(loopIdx, b.blockID());
     }
 
-    private void clearBlockInLoop(int loopIdx, int blockId) {
+    void clearBlockInLoop(int loopIdx, int blockId) {
         loopMap.clearBit(loopIdx, blockId);
     }
 
     // accessors for final result
-    public List<BlockBegin> linearScanOrder() {
+    public List<LIRBlock> linearScanOrder() {
         return linearScanOrder;
     }
 
@@ -105,18 +108,34 @@
         return numLoops;
     }
 
-    public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) {
+    public ComputeLinearScanOrder(int maxBlockId, LIRBlock startBlock) {
 
         this.maxBlockId = maxBlockId;
         visitedBlocks = new CiBitMap(maxBlockId);
         activeBlocks = new CiBitMap(maxBlockId);
+        dominatorBlocks = new CiBitMap(maxBlockId);
         forwardBranches = new int[maxBlockId];
-        loopEndBlocks = new ArrayList<BlockBegin>(8);
-        workList = new ArrayList<BlockBegin>(8);
+        loopEndBlocks = new ArrayList<LIRBlock>(8);
+        workList = new ArrayList<LIRBlock>(8);
+
+        splitCriticalEdges();
 
         countEdges(startBlock, null);
 
+        if (numLoops > 0) {
+            markLoops();
+            clearNonNaturalLoops(startBlock);
+            assignLoopDepth(startBlock);
+        }
+
         computeOrder(startBlock);
+
+        printBlocks();
+        assert verify();
+    }
+
+    void splitCriticalEdges() {
+        // TODO: move critical edge splitting from IR to here
     }
 
     /**
@@ -127,9 +146,9 @@
      * 3. Number loop header blocks.
      * 4. Create a list with all loop end blocks.
      */
-    private void countEdges(final BlockBegin cur, BlockBegin parent) {
+    void countEdges(LIRBlock cur, LIRBlock parent) {
         if (C1XOptions.TraceLinearScanLevel >= 3) {
-            TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID);
+            TTY.println("Counting edges for block B%d%s", cur.blockID(), parent == null ? "" : " coming from B" + parent.blockID());
         }
 
         if (isActive(cur)) {
@@ -139,9 +158,19 @@
             assert isVisited(cur) : "block must be visited when block is active";
             assert parent != null : "must have parent";
 
-            //cur.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader);
+            cur.setLinearScanLoopHeader();
+            cur.setBackwardBranchTarget(true);
+            parent.setLinearScanLoopEnd();
 
-            //parent.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd);
+            // When a loop header is also the start of an exception handler, then the backward branch is
+            // an exception edge. Because such edges are usually critical edges which cannot be split, the
+            // loop must be excluded here from processing.
+            if (cur.isExceptionEntry()) {
+                // Make sure that dominators are correct in this weird situation
+                iterativeDominators = true;
+                return;
+            }
+//            assert parent.numberOfSux() == 1 && parent.suxAt(0) == cur : "loop end blocks must have one successor (critical edges are split)";
 
             loopEndBlocks.add(parent);
             return;
@@ -162,40 +191,197 @@
         setActive(cur);
 
         // recursive call for all successors
-        cur.allSuccessorsDo(true, new BlockClosure() {
-            public void apply(BlockBegin block) {
-                countEdges(block, cur);
-            }
-        });
+        int i;
+        for (i = cur.numberOfSux() - 1; i >= 0; i--) {
+            countEdges(cur.suxAt(i), cur);
+        }
+        for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) {
+            countEdges(ex, cur);
+        }
 
         clearActive(cur);
 
+        // Each loop has a unique number.
+        // When multiple loops are nested, assignLoopDepth assumes that the
+        // innermost loop has the lowest number. This is guaranteed by setting
+        // the loop number after the recursive calls for the successors above
+        // have returned.
+        if (cur.isLinearScanLoopHeader()) {
+            assert cur.loopIndex() == -1 : "cannot set loop-index twice";
+            if (C1XOptions.TraceLinearScanLevel >= 3) {
+                TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops);
+            }
+
+            cur.setLoopIndex(numLoops);
+            numLoops++;
+        }
+
         if (C1XOptions.TraceLinearScanLevel >= 3) {
-            TTY.println("Finished counting edges for block B%d", cur.blockID);
+            TTY.println("Finished counting edges for block B%d", cur.blockID());
+        }
+    }
+
+    void markLoops() {
+        if (C1XOptions.TraceLinearScanLevel >= 3) {
+            TTY.println("----- marking loops");
+        }
+
+        loopMap = new BitMap2D(numLoops, maxBlockId);
+
+        for (int i = loopEndBlocks.size() - 1; i >= 0; i--) {
+            LIRBlock loopEnd = loopEndBlocks.get(i);
+            LIRBlock loopStart = loopEnd.suxAt(0);
+            int loopIdx = loopStart.loopIndex();
+
+            if (C1XOptions.TraceLinearScanLevel >= 3) {
+                TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID(), loopEnd.blockID(), loopIdx);
+            }
+            assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set";
+//            assert loopEnd.numberOfSux() == 1 : "incorrect number of successors";
+            assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set";
+            assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
+            assert workList.isEmpty() : "work list must be empty before processing";
+
+            // add the end-block of the loop to the working list
+            workList.add(loopEnd);
+            setBlockInLoop(loopIdx, loopEnd);
+            do {
+                LIRBlock cur = workList.remove(workList.size() - 1);
+
+                if (C1XOptions.TraceLinearScanLevel >= 3) {
+                    TTY.println("    processing B%d", cur.blockID());
+                }
+                assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list";
+
+                // recursive processing of all predecessors ends when start block of loop is reached
+                if (cur != loopStart) {
+                    for (int j = cur.numberOfPreds() - 1; j >= 0; j--) {
+                        LIRBlock pred = cur.predAt(j);
+
+                        if (!isBlockInLoop(loopIdx, pred)) {
+                            // this predecessor has not been processed yet, so add it to work list
+                            if (C1XOptions.TraceLinearScanLevel >= 3) {
+                                TTY.println("    pushing B%d", pred.blockID());
+                            }
+                            workList.add(pred);
+                            setBlockInLoop(loopIdx, pred);
+                        }
+                    }
+                }
+            } while (!workList.isEmpty());
         }
     }
 
-    private int computeWeight(BlockBegin cur) {
-        BlockBegin singleSux = null;
-        BlockEnd end = cur.end();
-        if (end.blockSuccessorCount() == 1) {
-            singleSux = end.blockSuccessor(0);
+    // check for non-natural loops (loops where the loop header does not dominate
+    // all other loop blocks = loops with multiple entries).
+    // such loops are ignored
+    void clearNonNaturalLoops(LIRBlock startBlock) {
+        for (int i = numLoops - 1; i >= 0; i--) {
+            if (isBlockInLoop(i, startBlock)) {
+                // loop i contains the entry block of the method.
+                // this is not a natural loop, so ignore it
+                if (C1XOptions.TraceLinearScanLevel >= 2) {
+                    TTY.println("Loop %d is non-natural, so it is ignored", i);
+                }
+
+                for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) {
+                    clearBlockInLoop(i, blockId);
+                }
+                iterativeDominators = true;
+            }
+        }
+    }
+
+    void assignLoopDepth(LIRBlock startBlock) {
+        if (C1XOptions.TraceLinearScanLevel >= 3) {
+            TTY.println("----- computing loop-depth and weight");
+        }
+        initVisited();
+
+        assert workList.isEmpty() : "work list must be empty before processing";
+        workList.add(startBlock);
+
+        do {
+            LIRBlock cur = workList.remove(workList.size() - 1);
+
+            if (!isVisited(cur)) {
+                setVisited(cur);
+                if (C1XOptions.TraceLinearScanLevel >= 4) {
+                    TTY.println("Computing loop depth for block B%d", cur.blockID());
+                }
+
+                // compute loop-depth and loop-index for the block
+                assert cur.loopDepth() == 0 : "cannot set loop-depth twice";
+                int i;
+                int loopDepth = 0;
+                int minLoopIdx = -1;
+                for (i = numLoops - 1; i >= 0; i--) {
+                    if (isBlockInLoop(i, cur)) {
+                        loopDepth++;
+                        minLoopIdx = i;
+                    }
+                }
+                cur.setLoopDepth(loopDepth);
+                cur.setLoopIndex(minLoopIdx);
+
+                // append all unvisited successors to work list
+                for (i = cur.numberOfSux() - 1; i >= 0; i--) {
+                    workList.add(cur.suxAt(i));
+                }
+                for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) {
+                    workList.add(ex);
+                }
+            }
+        } while (!workList.isEmpty());
+    }
+
+    int computeWeight(LIRBlock cur) {
+        LIRBlock singleSux = null;
+        if (cur.numberOfSux() == 1) {
+            singleSux = cur.suxAt(0);
         }
 
         // limit loop-depth to 15 bit (only for security reason, it will never be so big)
-        int loopDepth = 0; // TODO(tw): Assign loop depth
-        int weight = (loopDepth & 0x7FFF) << 16;
+        int weight = (cur.loopDepth() & 0x7FFF) << 16;
 
         int curBit = 15;
 
+        // this is necessary for the (very rare) case that two successive blocks have
+        // the same loop depth, but a different loop index (can happen for endless loops
+        // with exception handlers)
+        if (!cur.isLinearScanLoopHeader()) {
+            weight |= 1 << curBit;
+        }
+        curBit--;
+
+        // loop end blocks (blocks that end with a backward branch) are added
+        // after all other blocks of the loop.
+        if (!cur.isLinearScanLoopEnd()) {
+            weight |= 1 << curBit;
+        }
+        curBit--;
+
+        // critical edge split blocks are preferred because then they have a greater
+        // probability to be completely empty
+        //if (cur.isCriticalEdgeSplit()) {
+        //    weight |= 1 << curBit;
+        //}
+        //curBit--;
+
         // exceptions should not be thrown in normal control flow, so these blocks
         // are added as late as possible
-        if (!(cur.end() instanceof Throw) && (singleSux == null || !(singleSux.end() instanceof Throw))) {
-            weight |= (1 << curBit);
-        }
-        curBit--;
-        if (!(cur.end() instanceof Return) && (singleSux == null || !(singleSux.end() instanceof Return))) {
-            weight |= (1 << curBit);
+//        if (!(cur.end() instanceof Throw) && (singleSux == null || !(singleSux.end() instanceof Throw))) {
+//            weight |= 1 << curBit;
+//        }
+//        curBit--;
+//        if (!(cur.end() instanceof Return) && (singleSux == null || !(singleSux.end() instanceof Return))) {
+//            weight |= 1 << curBit;
+//        }
+//        curBit--;
+
+        // exceptions handlers are added as late as possible
+        if (!cur.isExceptionEntry()) {
+            weight |= 1 << curBit;
         }
         curBit--;
 
@@ -208,7 +394,7 @@
         return weight;
     }
 
-    private boolean readyForProcessing(BlockBegin cur) {
+    boolean readyForProcessing(LIRBlock cur) {
         // Discount the edge just traveled.
         // When the number drops to zero, all forward branches were processed
         if (decForwardBranches(cur) != 0) {
@@ -220,7 +406,7 @@
         return true;
     }
 
-    private void sortIntoWorkList(BlockBegin cur) {
+    void sortIntoWorkList(LIRBlock cur) {
         assert !workList.contains(cur) : "block already in work list";
 
         int curWeight = computeWeight(cur);
@@ -243,9 +429,9 @@
         workList.set(insertIdx, cur);
 
         if (C1XOptions.TraceLinearScanLevel >= 3) {
-            TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID);
+            TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID());
             for (int i = 0; i < workList.size(); i++) {
-                TTY.println(String.format("%8d B%02d  weight:%6x", i, workList.get(i).blockID, workList.get(i).linearScanNumber()));
+                TTY.println(String.format("%8d B%02d  weight:%6x", i, workList.get(i).blockID(), workList.get(i).linearScanNumber()));
             }
         }
 
@@ -255,9 +441,9 @@
         }
     }
 
-    private void appendBlock(BlockBegin cur) {
+    void appendBlock(LIRBlock cur) {
         if (C1XOptions.TraceLinearScanLevel >= 3) {
-            TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID, cur.linearScanNumber());
+            TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID(), cur.linearScanNumber());
         }
         assert !linearScanOrder.contains(cur) : "cannot add the same block twice";
 
@@ -268,34 +454,160 @@
         linearScanOrder.add(cur);
     }
 
-    private void computeOrder(BlockBegin startBlock) {
+    void computeOrder(LIRBlock startBlock) {
         if (C1XOptions.TraceLinearScanLevel >= 3) {
             TTY.println("----- computing final block order");
         }
 
         // the start block is always the first block in the linear scan order
-        linearScanOrder = new ArrayList<BlockBegin>(numBlocks);
+        linearScanOrder = new ArrayList<LIRBlock>(numBlocks);
+        appendBlock(startBlock);
+
+        LIRBlock stdEntry = startBlock.suxAt(0);
 
         // start processing with standard entry block
         assert workList.isEmpty() : "list must be empty before processing";
 
-        if (readyForProcessing(startBlock)) {
-            sortIntoWorkList(startBlock);
+        if (readyForProcessing(stdEntry)) {
+            sortIntoWorkList(stdEntry);
         } else {
             throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)");
         }
 
         do {
-            final BlockBegin cur = workList.remove(workList.size() - 1);
+            LIRBlock cur = workList.remove(workList.size() - 1);
+
             appendBlock(cur);
 
-            cur.allSuccessorsDo(false, new BlockClosure() {
-                public void apply(BlockBegin block) {
-                    if (readyForProcessing(block)) {
-                        sortIntoWorkList(block);
+            int i;
+            int numSux = cur.numberOfSux();
+            // changed loop order to get "intuitive" order of if- and else-blocks
+            for (i = 0; i < numSux; i++) {
+                LIRBlock sux = cur.suxAt(i);
+                if (readyForProcessing(sux)) {
+                    sortIntoWorkList(sux);
+                }
+            }
+            for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) {
+                if (readyForProcessing(ex)) {
+                    sortIntoWorkList(ex);
+                }
+            }
+        } while (workList.size() > 0);
+    }
+
+    public void printBlocks() {
+        if (C1XOptions.TraceLinearScanLevel >= 2) {
+            TTY.println("----- loop information:");
+            for (LIRBlock cur : linearScanOrder) {
+                TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID()));
+                for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
+                    TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur)));
+                }
+                TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth()));
+            }
+        }
+
+        if (C1XOptions.TraceLinearScanLevel >= 1) {
+            TTY.println("----- linear-scan block order:");
+            for (LIRBlock cur : linearScanOrder) {
+                TTY.print(String.format("%4d: B%02d    loop: %2d  depth: %2d", cur.linearScanNumber(), cur.blockID(), cur.loopIndex(), cur.loopDepth()));
+
+                TTY.print(cur.isExceptionEntry() ? " ex" : "   ");
+                TTY.print(cur.isLinearScanLoopHeader() ? " lh" : "   ");
+                TTY.print(cur.isLinearScanLoopEnd() ? " le" : "   ");
+
+                TTY.print("    dom: null ");
+
+
+                if (cur.numberOfPreds() > 0) {
+                    TTY.print("    preds: ");
+                    for (int j = 0; j < cur.numberOfPreds(); j++) {
+                        LIRBlock pred = cur.predAt(j);
+                        TTY.print("B%d ", pred.blockID());
+                    }
+                }
+                if (cur.numberOfSux() > 0) {
+                    TTY.print("    sux: ");
+                    for (int j = 0; j < cur.numberOfSux(); j++) {
+                        LIRBlock sux = cur.suxAt(j);
+                        TTY.print("B%d ", sux.blockID());
                     }
                 }
-            });
-        } while (workList.size() > 0);
+                TTY.println();
+            }
+        }
+    }
+
+    boolean verify() {
+       /* assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list";
+
+        if (C1XOptions.StressLinearScan) {
+            // blocks are scrambled when StressLinearScan is used
+            return true;
+        }
+
+        // check that all successors of a block have a higher linear-scan-number
+        // and that all predecessors of a block have a lower linear-scan-number
+        // (only backward branches of loops are ignored)
+        int i;
+        for (i = 0; i < linearScanOrder.size(); i++) {
+            BlockBegin cur = linearScanOrder.get(i);
+
+            assert cur.linearScanNumber() == i : "incorrect linearScanNumber";
+            assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber";
+
+            for (BlockBegin sux : cur.end().successors()) {
+                assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber";
+                if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
+                    assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order";
+                }
+                if (cur.loopDepth() == sux.loopDepth()) {
+                    assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
+                }
+            }
+
+            for (BlockBegin pred : cur.predecessors()) {
+                assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber";
+                if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
+                    assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order";
+                }
+                if (cur.loopDepth() == pred.loopDepth()) {
+                    assert cur.loopIndex() == pred.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
+                }
+
+                assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors";
+            }
+
+            // check dominator
+            if (i == 0) {
+                assert cur.dominator() == null : "first block has no dominator";
+            } else {
+                assert cur.dominator() != null : "all but first block must have dominator";
+            }
+            assert cur.numberOfPreds() != 1 || cur.dominator() == cur.predAt(0) || cur.isExceptionEntry() : "Single predecessor must also be dominator";
+        }
+
+        // check that all loops are continuous
+        for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
+            int blockIdx = 0;
+            assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop";
+
+            // skip blocks before the loop
+            while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
+                blockIdx++;
+            }
+            // skip blocks of loop
+            while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
+                blockIdx++;
+            }
+            // after the first non-loop block : there must not be another loop-block
+            while (blockIdx < numBlocks) {
+                assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order";
+                blockIdx++;
+            }
+        }
+*/
+        return true;
     }
 }
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java
--- a/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java	Tue May 24 21:39:45 2011 +0200
@@ -29,7 +29,6 @@
 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.*;
 
 /**
@@ -43,7 +42,7 @@
     private List<Instruction> instructions = new ArrayList<Instruction>(4);
     private List<LIRBlock> predecessors = new ArrayList<LIRBlock>(4);
     private List<LIRBlock> successors = new ArrayList<LIRBlock>(4);
-    private List<Phi> phis = new ArrayList<Phi>(4);
+    private List<LIRBlock> exceptionHandlerSuccessors = new ArrayList<LIRBlock>(4);
 
     /**
      * Bit map specifying which {@linkplain OperandPool operands} are live upon entry to this block.
@@ -78,6 +77,10 @@
     private int lastLirInstructionID;
     public int blockEntryPco;
 
+    public List<LIRBlock> getExceptionHandlerSuccessors() {
+        return exceptionHandlerSuccessors;
+    }
+
     public LIRBlock(int blockID) {
         this.blockID = blockID;
         loopIndex = -1;
@@ -105,7 +108,6 @@
     }
 
     public int loopDepth;
-    public int loopIndex;
 
     public LIRList lir() {
         return lir;
@@ -151,6 +153,11 @@
         return successors;
     }
 
+    @Override
+    public String toString() {
+        return "B" + blockID();
+    }
+
     public List<LIRBlock> blockPredecessors() {
         return predecessors;
     }
@@ -161,10 +168,19 @@
     }
 
     public int loopIndex() {
-        // TODO(tw): Set correct loop index.
-        return -1;
+        return loopIndex;
+    }
+
+    public void setLoopIndex(int v) {
+        loopIndex = v;
     }
 
+    public void setLoopDepth(int v) {
+        this.loopDepth = v;
+    }
+
+    private int loopIndex;
+
     public Label label() {
         return label;
     }
@@ -172,7 +188,25 @@
     private int linearScanNumber = -1;
     private boolean linearScanLoopEnd;
     private boolean linearScanLoopHeader;
-    private FrameState stateBefore;
+    private boolean exceptionEntry;
+    private boolean backwardBranchTarget;
+
+
+    public void setExceptionEntry(boolean b) {
+        this.exceptionEntry = b;
+    }
+
+    public boolean isExceptionEntry() {
+        return exceptionEntry;
+    }
+
+    public void setBackwardBranchTarget(boolean b) {
+        this.backwardBranchTarget = b;
+    }
+
+    public boolean backwardBranchTarget() {
+        return backwardBranchTarget;
+    }
 
     public void setLinearScanNumber(int v) {
         linearScanNumber = v;
@@ -198,14 +232,6 @@
         return linearScanLoopHeader;
     }
 
-    public void setStateBefore(FrameState stateBefore) {
-        this.stateBefore = stateBefore;
-    }
-
-    public FrameState stateBefore() {
-        return stateBefore;
-    }
-
     public void replaceWith(LIRBlock other) {
         for (LIRBlock pred : predecessors) {
             Util.replaceAllInList(this, other, pred.successors);
diff -r 3e4d992fd312 -r 2ac7b30b7290 graal/GraalCompiler/src/com/sun/c1x/util/BitMap2D.java
--- a/graal/GraalCompiler/src/com/sun/c1x/util/BitMap2D.java	Tue May 24 14:40:47 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/util/BitMap2D.java	Tue May 24 21:39:45 2011 +0200
@@ -40,7 +40,8 @@
     }
 
     private boolean verifyBitWithinSlotIndex(int index)  {
-      return index < bitsPerSlot;
+      assert index < bitsPerSlot : "index " + index + " is out of bounds " + bitsPerSlot;
+      return true;
     }
 
     public BitMap2D(int sizeInSlots, int bitsPerSlot) {
diff -r 3e4d992fd312 -r 2ac7b30b7290 runtests.sh
--- a/runtests.sh	Tue May 24 14:40:47 2011 +0200
+++ b/runtests.sh	Tue May 24 21:39:45 2011 +0200
@@ -12,4 +12,4 @@
   exit 1;
 fi
 TESTDIR=${MAXINE}/com.oracle.max.vm/test
-${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -C1X:-PrintCFGToFile -XX:-TraceDeoptimization -XX:-TraceExceptions -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -C1X:-PrintAssembly -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $1 test.com.sun.max.vm.compiler.JavaTester -verbose=1 -gen-run-scheme=false -run-scheme-package=all ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads
+${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -C1X:PrintIdealGraphLevel=0 -C1X:-PrintCFGToFile -C1X:-PrintAssembly -XX:-TraceSignals -XX:-TraceDeoptimization -XX:-TraceExceptions -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $1 test.com.sun.max.vm.compiler.JavaTester -verbose=1 -gen-run-scheme=false -run-scheme-package=all ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads