# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1362953052 -3600
# Node ID 317b004fc74141fca407eed685777849df0c58ad
# Parent  bf1c9ae737751f8227df6cfb7f65baadf11c5dbd
Use sum of unscheduled blocks at merge point.

diff -r bf1c9ae73775 -r 317b004fc741 graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java	Sun Mar 10 23:02:48 2013 +0100
+++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java	Sun Mar 10 23:04:12 2013 +0100
@@ -55,6 +55,13 @@
     private static final int INITIAL_WORKLIST_CAPACITY = 10;
 
     /**
+     * Divisor used for degrading the probability of the current path versus unscheduled paths at a
+     * merge node when calculating the linear scan order. A high value means that predecessors of
+     * merge nodes are more likely to be scheduled before the merge node.
+     */
+    private static final int PENALTY_VERSUS_UNSCHEDULED = 10;
+
+    /**
      * Computes the block order used for the linear scan register allocator.
      * 
      * @return sorted list of blocks
@@ -122,13 +129,20 @@
         enqueueSuccessors(block, worklist, visitedBlocks);
         if (mostLikelySuccessor != null) {
             if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) {
-                // We are at a merge. Check that predecessors are scheduled.
+                // We are at a merge. Check probabilities of predecessors that are not yet
+                // scheduled.
+                double unscheduledSum = 0.0;
                 for (Block pred : mostLikelySuccessor.getPredecessors()) {
-                    if (pred.getLinearScanNumber() == -1) {
-                        visitedBlocks.clear(mostLikelySuccessor.getId());
-                        return;
+                    if (!visitedBlocks.get(pred.getId())) {
+                        unscheduledSum += pred.getBeginNode().probability();
                     }
                 }
+
+                if (unscheduledSum > block.getProbability() / PENALTY_VERSUS_UNSCHEDULED) {
+                    // Add this merge only after at least one additional predecessor gets scheduled.
+                    visitedBlocks.clear(mostLikelySuccessor.getId());
+                    return;
+                }
             }
             addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks);
         }