# HG changeset patch
# User Gilles Duboscq <gilles.duboscq@oracle.com>
# Date 1311953954 -7200
# Node ID 6d32b38ef241e9fa0c625ba28e3e36c60831962e
# Parent  6c5242cd893025281ec1d99a04f3f8328938e517
Optimization for the scheduler changes

diff -r 6c5242cd8930 -r 6d32b38ef241 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 16:36:53 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Fri Jul 29 17:39:14 2011 +0200
@@ -169,7 +169,7 @@
     public static boolean SplitMaterialization               = ____;
     public static boolean OptCanonicalizer                   = true;
     public static boolean OptLoops                           = ____;
-    public static boolean OptOptimisticSchedule              = ____;
+    public static boolean ScheduleOutOfLoops                 = ____;
     public static boolean OptReorderLoops                    = ____;
     public static boolean LoopPeeling                        = ____;
     public static boolean LoopInversion                      = ____;
diff -r 6c5242cd8930 -r 6d32b38ef241 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 16:36:53 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Fri Jul 29 17:39:14 2011 +0200
@@ -39,6 +39,7 @@
 
     private final List<Block> blocks = new ArrayList<Block>();
     private NodeMap<Block> nodeToBlock;
+    private NodeMap<Block> earliestCache;
     private Graph graph;
     private boolean scheduleAllNodes;
     private boolean splitMaterialization;
@@ -63,6 +64,7 @@
     protected void run(Graph graph) {
         this.graph = graph;
         nodeToBlock = graph.createNodeMap();
+        earliestCache = graph.createNodeMap();
         identifyBlocks();
     }
 
@@ -321,28 +323,28 @@
         if (prevBlock != null) {
             return;
         }
-
-        Block earliest = earliestBlock(n);
         //TTY.println("Earliest for " + n + " : " + earliest);
         // if in CFG, schedule at the latest position possible in the outermost loop possible
         // if floating, use rematerialization to place the node, it tries to compute the value only when it will be used,
         // in the block with the smallest probability (outside of loops), while minimizing live ranges
-        int suxCount = 0;
-        for (Node sux : n.successors()) {
-            if (sux != null) {
-                suxCount++;
+        if (!splitMaterialization || noRematerialization(n) || n.predecessors().size() > 0 || nonNullSuccessorCount(n) > 0) {
+            Block latestBlock = latestBlock(n);
+            //TTY.println("Latest for " + n + " : " + latestBlock);
+            Block block;
+            if (latestBlock == null) {
+                block = earliestBlock(n);
+            } else if (GraalOptions.ScheduleOutOfLoops) {
+                block = scheduleOutOfLoops(n, latestBlock, earliestBlock(n));
+            } else {
+                block = latestBlock;
             }
-        }
-        if (!splitMaterialization || noRematerialization(n) || n.predecessors().size() > 0 || suxCount > 0) {
-            Block latestBlock = latestBlock(n);
-            if (latestBlock == null) {
-                latestBlock = earliest;
-            }
-            //TTY.println("Latest for " + n + " : " + latestBlock);
-            Block block = scheduleOutOfLoops(n, latestBlock, earliest);
             nodeToBlock.set(n, block);
             block.getInstructions().add(n);
         } else {
+            GraalTimers timer = GraalTimers.get("earliest");
+            timer.start();
+            Block earliest = earliestBlock(n);
+            timer.stop();
             Map<Block, Set<Usage>> usages = computeUsages(n, earliest);
             if (usages.isEmpty()) {
                 nodeToBlock.set(n, earliest);
@@ -353,6 +355,16 @@
         }
     }
 
+    private int nonNullSuccessorCount(Node n) {
+        int suxCount = 0;
+        for (Node sux : n.successors()) {
+            if (sux != null) {
+                suxCount++;
+            }
+        }
+        return suxCount;
+    }
+
     private BitMap usagesBitMap(Set<Usage> usages) {
         BitMap usagesBitMap = new BitMap(blocks.size());
         for (Usage u : usages) {
@@ -434,12 +446,22 @@
             block = getCommonDominator(block, nodeToBlock.get(succ));
         }
         ensureScheduledUsages(n);
+        CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(block);
         for (Node usage : n.usages()) {
-            for (Block usageBlock : blocksForUsage(n, usage)) {
-                block = getCommonDominator(block, usageBlock);
-            }
+            blocksForUsage(n, usage, cdbc);
         }
-        return block;
+        return cdbc.block;
+    }
+
+    private class CommonDominatorBlockClosure implements BlockClosure {
+        public Block block;
+        public CommonDominatorBlockClosure(Block block) {
+            this.block = block;
+        }
+        @Override
+        public void apply(Block block) {
+            this.block = getCommonDominator(this.block, block);
+        }
     }
 
     private Block earliestBlock(Node n) {
@@ -447,6 +469,10 @@
         if (earliest != null) {
             return earliest;
         }
+        earliest = earliestCache.get(n);
+        if (earliest != null) {
+            return earliest;
+        }
         BitMap bits = new BitMap(blocks.size());
         ArrayList<Node> before = new ArrayList<Node>(n.predecessors().size() + n.inputs().size());
         before.addAll(n.predecessors());
@@ -469,6 +495,7 @@
             assert start != null;
             return start;
         }
+        earliestCache.set(n, earliest);
         return earliest;
     }
 
@@ -482,9 +509,7 @@
         return cur;
     }
 
-
-    private Set<Block> blocksForUsage(Node node, Node usage) {
-        Set<Block> blocks = new HashSet<Block>(2);
+    private void blocksForUsage(Node node, Node usage, BlockClosure closure) {
         if (usage instanceof Phi) {
             Phi phi = (Phi) usage;
             Merge merge = phi.merge();
@@ -499,7 +524,7 @@
                         TTY.println(phi.inputs().toString());
                         TTY.println("value count: " + phi.valueCount());
                     }
-                    blocks.add(mergeBlock.getPredecessors().get(i));
+                    closure.apply(mergeBlock.getPredecessors().get(i));
                 }
             }
         } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
@@ -508,19 +533,18 @@
             for (Node pred : merge.cfgPredecessors()) {
                 block = getCommonDominator(block, nodeToBlock.get(pred));
             }
-            blocks.add(block);
+            closure.apply(block);
         } else if (usage instanceof LoopCounter) {
             LoopCounter counter = (LoopCounter) usage;
             if (node == counter.init() || node == counter.stride()) {
                 LoopBegin loopBegin = counter.loopBegin();
                 Block mergeBlock = nodeToBlock.get(loopBegin);
-                blocks.add(mergeBlock.dominator());
+                closure.apply(mergeBlock.dominator());
             }
         } else {
             assignBlockToNode(usage);
-            blocks.add(nodeToBlock.get(usage));
+            closure.apply(nodeToBlock.get(usage));
         }
-        return blocks;
     }
 
     private void patch(Usage usage, Node original, Node patch) {
@@ -555,13 +579,16 @@
         // now true usages are ready
     }
 
-    private Map<Block, Set<Usage>> computeUsages(Node node, Block from) { //TODO use a List instead of a Set here ?
-        Map<Block, Set<Usage>> blockUsages = new HashMap<Block, Set<Usage>>();
+    private Map<Block, Set<Usage>> computeUsages(Node node, final Block from) { //TODO use a List instead of a Set here ?
+        final Map<Block, Set<Usage>> blockUsages = new HashMap<Block, Set<Usage>>();
         ensureScheduledUsages(node);
-        for (Node usage : node.dataUsages()) {
-            for (Block b : blocksForUsage(node, usage)) {
-                addUsageToTree(usage, b, from, blockUsages);
-            }
+        for (final Node usage : node.dataUsages()) {
+            blocksForUsage(node, usage, new BlockClosure() {
+                @Override
+                public void apply(Block block) {
+                    addUsageToTree(usage, block, from, blockUsages);
+                }
+            });
         }
         /*TTY.println("Usages for " + node + " from " + from);
         for (Entry<Block, Set<Usage>> entry : blockUsages.entrySet()) {
@@ -599,7 +626,7 @@
     }
 
     private boolean noRematerialization(Node n) {
-        return n instanceof Local || n instanceof LocationNode || n instanceof Constant || n instanceof StateSplit || n instanceof FrameState;
+        return n instanceof Local || n instanceof LocationNode || n instanceof Constant || n instanceof StateSplit || n instanceof FrameState || n instanceof CheckCast; //TODO why CheckCast ??
     }
 
     private static class Usage {