# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1309945951 -7200
# Node ID bdc1a456a6e0ea271d23aecc6977d82ebca28db8
# Parent  d197ba8959c96b65fd0c6c50d4950e5a1cff9f94
Added calculation of loop depth and loop index to scheduler.

diff -r d197ba8959c9 -r bdc1a456a6e0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Tue Jul 05 19:49:35 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Wed Jul 06 11:52:31 2011 +0200
@@ -122,6 +122,7 @@
 
         IdentifyBlocksPhase schedule = new IdentifyBlocksPhase(true);
         schedule.apply(graph);
+        compilation.stats.loopCount = schedule.loopCount();
 
 
         List<Block> blocks = schedule.getBlocks();
@@ -132,6 +133,8 @@
             map.put(b, block);
             block.setInstructions(b.getInstructions());
             block.setLinearScanNumber(b.blockID());
+            block.setLoopDepth(b.loopDepth());
+            block.setLoopIndex(b.loopIndex());
 
             block.setFirstInstruction(b.firstNode());
             block.setLastInstruction(b.lastNode());
@@ -166,7 +169,6 @@
 
         ComputeLinearScanOrder clso = new ComputeLinearScanOrder(lirBlocks.size(), startBlock);
         orderedBlocks = clso.linearScanOrder();
-        this.compilation.stats.loopCount = clso.numLoops();
 
         int z = 0;
         for (LIRBlock b : orderedBlocks) {
diff -r d197ba8959c9 -r bdc1a456a6e0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ArrayLength.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ArrayLength.java	Tue Jul 05 19:49:35 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ArrayLength.java	Wed Jul 06 11:52:31 2011 +0200
@@ -95,8 +95,7 @@
 
     @Override
     public Node copy(Graph into) {
-        ArrayLength x = new ArrayLength(null, into);
-        return x;
+        return new ArrayLength(null, into);
     }
 
     @SuppressWarnings("unchecked")
diff -r d197ba8959c9 -r bdc1a456a6e0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java	Tue Jul 05 19:49:35 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java	Wed Jul 06 11:52:31 2011 +0200
@@ -30,7 +30,6 @@
 import com.oracle.max.graal.compiler.lir.*;
 import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.graph.*;
-import com.sun.cri.ci.*;
 
 public final class ComputeLinearScanOrder {
 
@@ -124,9 +123,11 @@
         countEdges(startBlock, null);
 
         if (numLoops > 0) {
-            markLoops();
-            clearNonNaturalLoops(startBlock);
-            assignLoopDepth(startBlock);
+            TTY.println("num loops " + numLoops);
+            throw new IllegalStateException();
+//            markLoops();
+//            clearNonNaturalLoops(startBlock);
+//            assignLoopDepth(startBlock);
         }
 
         computeOrder(startBlock);
@@ -193,15 +194,15 @@
         // 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 (GraalOptions.TraceLinearScanLevel >= 3) {
-                TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops);
-            }
-
-            cur.setLoopIndex(numLoops);
-            numLoops++;
-        }
+//        if (cur.isLinearScanLoopHeader()) {
+//            assert cur.loopIndex() == -1 : "cannot set loop-index twice";
+//            if (GraalOptions.TraceLinearScanLevel >= 3) {
+//                TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops);
+//            }
+//
+//            cur.setLoopIndex(numLoops);
+//            numLoops++;
+//        }
 
         if (GraalOptions.TraceLinearScanLevel >= 3) {
             TTY.println("Finished counting edges for block B%d", cur.blockID());
@@ -329,10 +330,10 @@
         // 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--;
+//        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.
@@ -360,10 +361,10 @@
 //        curBit--;
 
         // exceptions handlers are added as late as possible
-//        if (!cur.isExceptionEntry()) {
-//            weight |= 1 << curBit;
-//        }
-//        curBit--;
+        if (!cur.isExceptionEntry()) {
+            weight |= 1 << curBit;
+        }
+        curBit--;
 
         // guarantee that weight is > 0
         weight |= 1;
@@ -434,29 +435,22 @@
         linearScanOrder.add(cur);
     }
 
-    void computeOrder(LIRBlock startBlock) {
+    private void computeOrder(LIRBlock startBlock) {
         if (GraalOptions.TraceLinearScanLevel >= 3) {
             TTY.println("----- computing final block order");
         }
 
         // the start block is always the first block in the linear scan order
         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(stdEntry)) {
-            sortIntoWorkList(stdEntry);
-        } else {
-            throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)");
-        }
+        assert readyForProcessing(startBlock);
+        sortIntoWorkList(startBlock);
 
         do {
             LIRBlock cur = workList.remove(workList.size() - 1);
-
             appendBlock(cur);
 
             int i;
diff -r d197ba8959c9 -r bdc1a456a6e0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java	Tue Jul 05 19:49:35 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java	Wed Jul 06 11:52:31 2011 +0200
@@ -27,6 +27,7 @@
 import com.oracle.max.asm.*;
 import com.oracle.max.graal.compiler.alloc.*;
 import com.oracle.max.graal.compiler.debug.*;
+import com.oracle.max.graal.compiler.ir.*;
 import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.compiler.value.*;
 import com.oracle.max.graal.graph.*;
@@ -174,8 +175,7 @@
     }
 
     public int loopDepth() {
-        // TODO(tw): Set correct loop depth.
-        return 0;
+        return loopDepth;
     }
 
     public int loopIndex() {
@@ -284,4 +284,8 @@
         LIROpcode code = lirInstruction.code;
         return code == LIROpcode.Branch || code == LIROpcode.TableSwitch;
     }
+
+    public boolean isExceptionEntry() {
+        return firstInstruction() instanceof ExceptionObject;
+    }
 }
diff -r d197ba8959c9 -r bdc1a456a6e0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Tue Jul 05 19:49:35 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Wed Jul 06 11:52:31 2011 +0200
@@ -116,9 +116,11 @@
      * @param graph
      */
     public GraphBuilderPhase(GraalCompilation compilation, RiMethod method, boolean inline) {
-        super(inline ? "BuildInlineGraph " + method.holder().name() + "." + method.name() + method.signature().asString() : "BuildGraph");
+        super(inline ? "BuildInlineGraph" : "BuildGraph");
         this.compilation = compilation;
 
+        setDetailedName(getName() + " " + method.holder().name() + "." + method.name() + method.signature().asString());
+
         this.runtime = compilation.runtime;
         this.method = method;
         this.stats = compilation.stats;
diff -r d197ba8959c9 -r bdc1a456a6e0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java	Tue Jul 05 19:49:35 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java	Wed Jul 06 11:52:31 2011 +0200
@@ -30,12 +30,14 @@
 public abstract class Phase {
 
     private final String name;
+    private String detailedName;
     private static final ThreadLocal<Phase> currentPhase = new ThreadLocal<Phase>();
     private final boolean shouldVerify;
 
     public Phase() {
         this.name = this.getClass().getSimpleName();
         this.shouldVerify = true;
+        this.detailedName = name;
     }
 
     public Phase(String name) {
@@ -45,6 +47,11 @@
     public Phase(String name, boolean shouldVerify) {
         this.name = name;
         this.shouldVerify = shouldVerify;
+        this.detailedName = name;
+    }
+
+    protected void setDetailedName(String detailedName) {
+        this.detailedName = detailedName;
     }
 
     public final void apply(Graph graph) {
@@ -71,13 +78,13 @@
         } catch (AssertionError t) {
             GraalCompilation compilation = GraalCompilation.compilation();
             if (compilation.compiler.isObserved() && plotOnError) {
-                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "AssertionError in " + getName(), graph, true, false, true));
+                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "AssertionError in " + detailedName, graph, true, false, true));
             }
             throw t;
         } catch (RuntimeException t) {
             GraalCompilation compilation = GraalCompilation.compilation();
             if (compilation.compiler.isObserved() && plotOnError) {
-                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "RuntimeException in " + getName(), graph, true, false, true));
+                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "RuntimeException in " + detailedName, graph, true, false, true));
             }
             throw t;
         }
@@ -98,7 +105,7 @@
         }
         GraalCompilation compilation = GraalCompilation.compilation();
         if (compilation.compiler.isObserved() && this.getClass() != IdentifyBlocksPhase.class) {
-            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After " + getName(), graph, true, false));
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After " + detailedName, graph, true, false));
         }
 
         assert !shouldVerify || graph.verify();
diff -r d197ba8959c9 -r bdc1a456a6e0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Tue Jul 05 19:49:35 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Wed Jul 06 11:52:31 2011 +0200
@@ -38,6 +38,8 @@
     private Block javaBlock;
     private final List<Block> dominators = new ArrayList<Block>();
     private Anchor anchor;
+    private int loopDepth = 0;
+    private int loopIndex = -1;
 
     private Node firstNode;
     private Node lastNode;
@@ -63,6 +65,22 @@
         return lastNode;
     }
 
+    public int loopDepth() {
+        return loopDepth;
+    }
+
+    public void setLoopDepth(int i) {
+        loopDepth = i;
+    }
+
+    public int loopIndex() {
+        return loopIndex;
+    }
+
+    public void setLoopIndex(int i) {
+        loopIndex = i;
+    }
+
     public Anchor createAnchor() {
         if (anchor == null) {
             if (firstNode instanceof Anchor) {
@@ -175,6 +193,10 @@
         return firstNode instanceof LoopBegin;
     }
 
+    public boolean isLoopEnd() {
+        return lastNode instanceof LoopEnd;
+    }
+
     public Block dominator() {
         return dominator;
     }
diff -r d197ba8959c9 -r bdc1a456a6e0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Tue Jul 05 19:49:35 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Wed Jul 06 11:52:31 2011 +0200
@@ -24,8 +24,6 @@
 
 import java.util.*;
 
-import javax.annotation.*;
-
 import com.oracle.max.graal.compiler.*;
 import com.oracle.max.graal.compiler.debug.*;
 import com.oracle.max.graal.compiler.ir.*;
@@ -39,6 +37,7 @@
     private NodeMap<Block> nodeToBlock;
     private Graph graph;
     private boolean scheduleAllNodes;
+    private int loopCount;
 
     public IdentifyBlocksPhase(boolean scheduleAllNodes) {
         super(scheduleAllNodes ? "FullSchedule" : "PartSchedule", false);
@@ -67,6 +66,10 @@
         return b;
     }
 
+    public int loopCount() {
+        return loopCount;
+    }
+
     private Block assignBlockNew(Node n, Block b) {
         if (b == null) {
             b = createBlock();
@@ -171,17 +174,7 @@
 
 
         if (scheduleAllNodes) {
-
-            // Add successors of loop end nodes. Makes the graph cyclic.
-            for (Block block : blocks) {
-                Node n = block.lastNode();
-                if (n instanceof LoopEnd) {
-                    LoopEnd loopEnd = (LoopEnd) n;
-                    assert loopEnd.loopBegin() != null;
-                    block.addSuccessor(nodeToBlock.get(loopEnd.loopBegin()));
-                }
-            }
-
+            computeLoopInformation(); // Will make the graph cyclic.
             assignLatestPossibleBlockToNodes();
             sortNodesWithinBlocks();
         } else {
@@ -189,6 +182,47 @@
         }
     }
 
+    private void computeLoopInformation() {
+
+        // Add successors of loop end nodes. Makes the graph cyclic.
+        for (Block block : blocks) {
+            Node n = block.lastNode();
+            if (n instanceof LoopEnd) {
+                LoopEnd loopEnd = (LoopEnd) n;
+                assert loopEnd.loopBegin() != null;
+                Block loopBeginBlock = nodeToBlock.get(loopEnd.loopBegin());
+                block.addSuccessor(loopBeginBlock);
+                BitMap map = new BitMap(blocks.size());
+                markBlocks(block, loopBeginBlock, map, loopCount++, block.loopDepth());
+            }
+        }
+
+//        for (Block block : blocks) {
+//            TTY.println("Block B" + block.blockID() + " loopIndex=" + block.loopIndex() + ", loopDepth=" + block.loopDepth());
+//        }
+    }
+
+    private void markBlocks(Block block, Block endBlock, BitMap map, int loopIndex, int initialDepth) {
+        if (map.get(block.blockID())) {
+            return;
+        }
+
+        map.set(block.blockID());
+        if (block.loopDepth() <= initialDepth) {
+            assert block.loopDepth() == initialDepth;
+            block.setLoopIndex(loopIndex);
+        }
+        block.setLoopDepth(block.loopDepth() + 1);
+
+        if (block == endBlock) {
+            return;
+        }
+
+        for (Block pred : block.getPredecessors()) {
+            markBlocks(pred, endBlock, map, loopIndex, initialDepth);
+        }
+    }
+
     private void computeJavaBlocks() {
 
         for (Block b : blocks) {
@@ -300,12 +334,12 @@
             }
         }
 
-        if (GraalOptions.OptOptimisticSchedule) {
-            block = scheduleOutOfLoops(n, block);
-        }
 
-        nodeToBlock.set(n, block);
         if (block != null) {
+            if (GraalOptions.OptOptimisticSchedule) {
+                block = scheduleOutOfLoops(n, block);
+            }
+            nodeToBlock.set(n, block);
             block.getInstructions().add(n);
         }
         return block;
@@ -313,15 +347,24 @@
 
     private Block scheduleOutOfLoops(Node n, Block latestBlock) {
         Block cur = latestBlock;
-        while (cur != null) {
+        while (cur.loopDepth() != 0) {
             if (cur.isLoopHeader()) {
                 assert cur.getPredecessors().size() == 2 : cur.getPredecessors().size();
                 if (canSchedule(n, cur.getPredecessors().get(0))) {
-                    TTY.println("can schedule out of loop!" + n);
+                   // TTY.println("can schedule out of loop!" + n);
                     return scheduleOutOfLoops(n, cur.getPredecessors().get(0));
+                } else {
+                    break;
                 }
             }
+            Block prev = cur;
             cur = cur.dominator();
+
+            // This must be a loop exit.
+            if (cur.loopDepth() > prev.loopDepth()) {
+//                TTY.println("break out because of different loop depth");
+                break;
+            }
         }
         return latestBlock;
     }