# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1397673473 -7200
# Node ID fc7f2bbd4eddc9f92405056b167442b3c744dd2a
# Parent  009d945ddc39a6915c2ac41f1110b71f62b8c80c
Improve schedule phase to avoid allocation of a BitSet per scheduled node.

diff -r 009d945ddc39 -r fc7f2bbd4edd graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Wed Apr 16 19:47:22 2014 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Wed Apr 16 20:37:53 2014 +0200
@@ -650,12 +650,7 @@
          * implies that the inputs' blocks have a total ordering via their dominance relation. So in
          * order to find the earliest block placement for this node we need to find the input block
          * that is dominated by all other input blocks.
-         * 
-         * While iterating over the inputs a set of dominator blocks of the current earliest
-         * placement is maintained. When the block of an input is not within this set, it becomes
-         * the current earliest placement and the list of dominator blocks is updated.
          */
-        BitSet dominators = new BitSet(cfg.getBlocks().length);
 
         if (node.predecessor() != null) {
             throw new SchedulingError();
@@ -668,12 +663,24 @@
             } else {
                 inputEarliest = earliestBlock(input);
             }
-            if (!dominators.get(inputEarliest.getId())) {
+            if (earliest == null) {
                 earliest = inputEarliest;
-                do {
-                    dominators.set(inputEarliest.getId());
-                    inputEarliest = inputEarliest.getDominator();
-                } while (inputEarliest != null && !dominators.get(inputEarliest.getId()));
+            } else if (earliest != inputEarliest) {
+                // Find out whether earliest or inputEarliest is earlier.
+                Block a = earliest.getDominator();
+                Block b = inputEarliest;
+                while (true) {
+                    if (a == inputEarliest || b == null) {
+                        // Nothing to change, the previous earliest block is still earliest.
+                        break;
+                    } else if (b == earliest || a == null) {
+                        // New earliest is the earliest.
+                        earliest = inputEarliest;
+                        break;
+                    }
+                    a = a.getDominator();
+                    b = b.getDominator();
+                }
             }
         }
         if (earliest == null) {