# HG changeset patch
# User Gilles Duboscq <gilles.duboscq@oracle.com>
# Date 1312187633 -7200
# Node ID 13579dfa8a3c41a08cc573826381ad66d654b121
# Parent  6d32b38ef241e9fa0c625ba28e3e36c60831962e
Fix for scheduleOutOfLoops : scehdule in the latest block possible even when scheduling out of loops

diff -r 6d32b38ef241 -r 13579dfa8a3c graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Fri Jul 29 17:39:14 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Mon Aug 01 10:33:53 2011 +0200
@@ -169,7 +169,7 @@
     public static boolean SplitMaterialization               = ____;
     public static boolean OptCanonicalizer                   = true;
     public static boolean OptLoops                           = ____;
-    public static boolean ScheduleOutOfLoops                 = ____;
+    public static boolean ScheduleOutOfLoops                 = true;
     public static boolean OptReorderLoops                    = ____;
     public static boolean LoopPeeling                        = ____;
     public static boolean LoopInversion                      = ____;
diff -r 6d32b38ef241 -r 13579dfa8a3c 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	Fri Jul 29 17:39:14 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Mon Aug 01 10:33:53 2011 +0200
@@ -335,6 +335,10 @@
                 block = earliestBlock(n);
             } else if (GraalOptions.ScheduleOutOfLoops) {
                 block = scheduleOutOfLoops(n, latestBlock, earliestBlock(n));
+                Block b2 = scheduleOutOfLoops(n, latestBlock);
+                if (block != b2) {
+                    TTY.println(":> scheduleOutOfLoops disagreement for " + n + " : " + block + " vs. " + b2);
+                }
             } else {
                 block = latestBlock;
             }
@@ -503,10 +507,15 @@
     private Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) {
         assert latestBlock != null : "no latest : " + n;
         Block cur = latestBlock;
+        Block prevDepth = latestBlock;
         while (cur.loopDepth() != 0 && cur != earliest && cur.dominator() != null && cur.dominator().loopDepth() <= cur.loopDepth()) {
-            cur = cur.dominator();
+            Block dom = cur.dominator();
+            if (dom.loopDepth() < prevDepth.loopDepth()) {
+                prevDepth = dom;
+            }
+            cur = dom;
         }
-        return cur;
+        return prevDepth;
     }
 
     private void blocksForUsage(Node node, Node usage, BlockClosure closure) {
@@ -850,4 +859,62 @@
         }
         return i;
     }
+
+    private Block scheduleOutOfLoops(Node n, Block latestBlock) {
+        Block cur = latestBlock;
+        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);
+                    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;
+    }
+
+    private boolean canSchedule(Node n, Block block) {
+        Set<Block> allowedBlocks = new HashSet<Block>();
+        Block cur = block;
+        while (cur != null) {
+            allowedBlocks.add(cur);
+            cur = cur.dominator();
+        }
+        // Now we know the allowed blocks for inputs and predecessors.
+        return checkNodesAbove(allowedBlocks, n);
+    }
+
+    private boolean checkNodesAbove(Set<Block> allowedBlocks, Node n) {
+        if (n == null) {
+            return true;
+        }
+
+        if (nodeToBlock.get(n) != null) {
+            return allowedBlocks.contains(nodeToBlock.get(n));
+        } else {
+            assert !(n instanceof Phi) : ((Phi) n).merge();
+            for (Node input : n.inputs()) {
+                if (!checkNodesAbove(allowedBlocks, input)) {
+                    return false;
+                }
+            }
+            for (Node pred : n.predecessors()) {
+                if (!checkNodesAbove(allowedBlocks, pred)) {
+                    return false;
+                }
+            }
+            return true;
+        }
+    }
 }