# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1358207472 -3600
# Node ID 44012c5c6783327fc386f4eec27aa08e75fdb251
# Parent  6d65e368bb8156733137ceafce2d7cafebc5cf5a
New experiment with LSRA order. Remove old block order calculation.

diff -r 6d65e368bb81 -r 44012c5c6783 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	Mon Jan 14 16:56:54 2013 +0100
+++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java	Tue Jan 15 00:51:12 2013 +0100
@@ -35,15 +35,8 @@
  * and the machine code generator.
  */
 public final class ComputeBlockOrder {
-    private int blockCount;
     private List<Block> linearScanOrder;
     private List<Block> codeEmittingOrder;
-    private final BitSet visitedBlocks; // used for recursive processing of blocks
-    private final BitSet activeBlocks; // used for recursive processing of blocks
-    private final int[] forwardBranches; // number of incoming forward branches for each block
-    private final List<Block> workList; // temporary list (used in markLoops and computeOrder)
-    private final List<Block> loopHeaders;
-    private final boolean reorderLoops;
 
     private Comparator<Block> blockComparator = new Comparator<Block>() {
         @Override
@@ -63,18 +56,6 @@
         }};
 
     public ComputeBlockOrder(int maxBlockId, int loopCount, Block startBlock, boolean reorderLoops) {
-        loopHeaders = new ArrayList<>(loopCount);
-        while (loopHeaders.size() < loopCount) {
-            loopHeaders.add(null);
-        }
-        visitedBlocks = new BitSet(maxBlockId);
-        activeBlocks = new BitSet(maxBlockId);
-        forwardBranches = new int[maxBlockId];
-        workList = new ArrayList<>(8);
-        this.reorderLoops = reorderLoops;
-
-        countEdges(startBlock, null);
-        computeOrder(startBlock);
 
         List<Block> newLinearScanOrder = new ArrayList<>();
         List<Block> order = new ArrayList<>();
@@ -82,21 +63,81 @@
         BitSet orderedBlocks = new BitSet(maxBlockId);
         orderedBlocks.set(startBlock.getId());
         worklist.add(startBlock);
-        computeCodeEmittingOrder(order, newLinearScanOrder, worklist, orderedBlocks);
-        assert codeEmittingOrder.size() == order.size();
+        computeCodeEmittingOrder(order, worklist, orderedBlocks);
         codeEmittingOrder = order;
 
+        orderedBlocks.clear();
+        orderedBlocks.set(startBlock.getId());
+        worklist.add(startBlock);
+        computeNewLinearScanOrder(newLinearScanOrder, worklist, orderedBlocks);
+
+        assert order.size() == newLinearScanOrder.size() : codeEmittingOrder.size() + " vs " + newLinearScanOrder.size();
         linearScanOrder = newLinearScanOrder;
     }
 
-    private void computeCodeEmittingOrder(List<Block> order, List<Block> newLinearScanOrder, PriorityQueue<Block> worklist, BitSet orderedBlocks) {
+    private void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) {
         while (!worklist.isEmpty()) {
             Block nextImportantPath = worklist.poll();
-            addImportantPath(nextImportantPath, order, newLinearScanOrder, worklist, orderedBlocks);
+            addImportantPath(nextImportantPath, order, worklist, orderedBlocks);
+        }
+    }
+
+    private void computeNewLinearScanOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) {
+        while (!worklist.isEmpty()) {
+            Block nextImportantPath = worklist.poll();
+            addImportantLinearScanOrderPath(nextImportantPath, order, worklist, orderedBlocks);
         }
     }
 
-    private void addImportantPath(Block block, List<Block> order, List<Block> newLinearScanOrder, PriorityQueue<Block> worklist, BitSet orderedBlocks) {
+    private void addImportantLinearScanOrderPath(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) {
+        order.add(block);
+
+        Block bestSucc = null;
+        double bestSuccProb = 0;
+
+        for (Block succ : block.getSuccessors()) {
+            if (!orderedBlocks.get(succ.getId()) && succ.getLoopDepth() >= block.getLoopDepth()) {
+                double curProb = succ.getBeginNode().probability();
+                if (curProb >= bestSuccProb) {
+                    bestSuccProb = curProb;
+                    bestSucc = succ;
+                }
+                assert curProb >= 0 : curProb;
+            }
+        }
+
+        for (Block succ : block.getSuccessors()) {
+            if (!orderedBlocks.get(succ.getId())) {
+                if (succ != bestSucc) {
+                    orderedBlocks.set(succ.getId());
+                    worklist.add(succ);
+                }
+            }
+        }
+
+        if (bestSucc != null) {
+            if (!bestSucc.isLoopHeader() && bestSucc.getPredecessors().size() > 1) {
+                // We are at a merge. Check probabilities of predecessors that are not yet scheduled.
+                double unscheduledSum = 0.0;
+                double scheduledSum = 0.0;
+                for (Block pred : bestSucc.getPredecessors()) {
+                    if (!orderedBlocks.get(pred.getId())) {
+                        unscheduledSum += pred.getBeginNode().probability();
+                    } else {
+                        scheduledSum += pred.getBeginNode().probability();
+                    }
+                }
+
+                if (unscheduledSum > 0.0 && unscheduledSum > scheduledSum / 10) {
+                    return;
+                }
+            }
+            orderedBlocks.set(bestSucc.getId());
+            addImportantLinearScanOrderPath(bestSucc, order, worklist, orderedBlocks);
+        }
+    }
+
+    private void addImportantPath(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) {
         if (!skipLoopHeader(block)) {
             if (block.isLoopHeader()) {
                 block.align = true;
@@ -111,7 +152,6 @@
                 }
             }
         }
-        newLinearScanOrder.add(block);
         Block bestSucc = null;
         double bestSuccProb = 0;
 
@@ -137,12 +177,12 @@
 
         if (bestSucc != null) {
             orderedBlocks.set(bestSucc.getId());
-            addImportantPath(bestSucc, order, newLinearScanOrder, worklist, orderedBlocks);
+            addImportantPath(bestSucc, order, worklist, orderedBlocks);
         }
     }
 
-    private boolean skipLoopHeader(Block bestSucc) {
-        return (reorderLoops && bestSucc.isLoopHeader() && !bestSucc.isLoopEnd() && bestSucc.getLoop().loopBegin().loopEnds().count() == 1);
+    private static boolean skipLoopHeader(Block bestSucc) {
+        return (bestSucc.isLoopHeader() && !bestSucc.isLoopEnd() && bestSucc.getLoop().loopBegin().loopEnds().count() == 1);
     }
 
     /**
@@ -160,226 +200,4 @@
     public List<Block> codeEmittingOrder() {
         return codeEmittingOrder;
     }
-
-    private boolean isVisited(Block b) {
-        return visitedBlocks.get(b.getId());
-    }
-
-    private boolean isActive(Block b) {
-        return activeBlocks.get(b.getId());
-    }
-
-    private void setVisited(Block b) {
-        assert !isVisited(b);
-        visitedBlocks.set(b.getId());
-    }
-
-    private void setActive(Block b) {
-        assert !isActive(b);
-        activeBlocks.set(b.getId());
-    }
-
-    private void clearActive(Block b) {
-        assert isActive(b);
-        activeBlocks.clear(b.getId());
-    }
-
-    private void incForwardBranches(Block b) {
-        forwardBranches[b.getId()]++;
-    }
-
-    private int decForwardBranches(Block b) {
-        return --forwardBranches[b.getId()];
-    }
-
-    /**
-     * Traverses the CFG to analyze block and edge info. The analysis performed is:
-     *
-     * 1. Count of total number of blocks.
-     * 2. Count of all incoming edges and backward incoming edges.
-     * 3. Number loop header blocks.
-     * 4. Create a list with all loop end blocks.
-     */
-    private void countEdges(Block cur, Block parent) {
-        Debug.log("Counting edges for block B%d%s", cur.getId(), parent == null ? "" : " coming from B" + parent.getId());
-
-        if (isActive(cur)) {
-            return;
-        }
-
-        // increment number of incoming forward branches
-        incForwardBranches(cur);
-
-        if (isVisited(cur)) {
-            return;
-        }
-
-        blockCount++;
-        setVisited(cur);
-        setActive(cur);
-
-        // recursive call for all successors
-        for (int i = cur.numberOfSux() - 1; i >= 0; i--) {
-            countEdges(cur.suxAt(i), cur);
-        }
-
-        clearActive(cur);
-
-        Debug.log("Finished counting edges for block B%d", cur.getId());
-    }
-
-    private static int computeWeight(Block cur) {
-
-        // limit loop-depth to 15 bit (only for security reason, it will never be so big)
-        int weight = (cur.getLoopDepth() & 0x7FFF) << 16;
-
-        int curBit = 15;
-
-        // loop end blocks (blocks that end with a backward branch) are added
-        // after all other blocks of the loop.
-        if (!cur.isLoopEnd()) {
-            weight |= 1 << curBit;
-        }
-        curBit--;
-
-        // exceptions handlers are added as late as possible
-        if (!cur.isExceptionEntry()) {
-            weight |= 1 << curBit;
-        }
-        curBit--;
-
-        if (cur.getBeginNode().probability() > 0.5) {
-            weight |= 1 << curBit;
-        }
-        curBit--;
-
-        if (cur.getBeginNode().probability() > 0.05) {
-            weight |= 1 << curBit;
-        }
-        curBit--;
-
-        // guarantee that weight is > 0
-        weight |= 1;
-
-        assert curBit >= 0 : "too many flags";
-        assert weight > 0 : "weight cannot become negative";
-
-        return weight;
-    }
-
-    private boolean readyForProcessing(Block cur) {
-        // Discount the edge just traveled.
-        // When the number drops to zero, all forward branches were processed
-        if (decForwardBranches(cur) != 0) {
-            return false;
-        }
-
-        assert !linearScanOrder.contains(cur) : "block already processed (block can be ready only once)";
-        assert !workList.contains(cur) : "block already in work-list (block can be ready only once)";
-        return true;
-    }
-
-    private void sortIntoWorkList(Block cur) {
-        assert !workList.contains(cur) : "block already in work list";
-
-        int curWeight = computeWeight(cur);
-
-        // the linearScanNumber is used to cache the weight of a block
-        cur.linearScanNumber = curWeight;
-
-        workList.add(null); // provide space for new element
-
-        int insertIdx = workList.size() - 1;
-        while (insertIdx > 0 && workList.get(insertIdx - 1).linearScanNumber > curWeight) {
-            workList.set(insertIdx, workList.get(insertIdx - 1));
-            insertIdx--;
-        }
-        workList.set(insertIdx, cur);
-
-        if (Debug.isLogEnabled()) {
-            Debug.log("Sorted B%d into worklist. new worklist:", cur.getId());
-            for (int i = 0; i < workList.size(); i++) {
-                Debug.log(String.format("%8d B%02d  weight:%6x", i, workList.get(i).getId(), workList.get(i).linearScanNumber));
-            }
-        }
-
-        for (int i = 0; i < workList.size(); i++) {
-            assert workList.get(i).linearScanNumber > 0 : "weight not set";
-            assert i == 0 || workList.get(i - 1).linearScanNumber <= workList.get(i).linearScanNumber : "incorrect order in worklist";
-        }
-    }
-
-    private void appendBlock(Block cur) {
-        Debug.log("appending block B%d (weight 0x%06x) to linear-scan order", cur.getId(), cur.linearScanNumber);
-        assert !linearScanOrder.contains(cur) : "cannot add the same block twice";
-
-        cur.linearScanNumber = linearScanOrder.size();
-        linearScanOrder.add(cur);
-
-        if (cur.isLoopEnd() && cur.isLoopHeader()) {
-            //cur.align = true;
-            codeEmittingOrder.add(cur);
-        } else {
-            if (!cur.isLoopHeader() || ((LoopBeginNode) cur.getBeginNode()).loopEnds().count() > 1 || !reorderLoops) {
-                if (cur.isLoopHeader()) {
-                   // cur.align = true;
-                }
-                codeEmittingOrder.add(cur);
-
-                if (cur.isLoopEnd() && reorderLoops) {
-                    Block loopHeader = loopHeaders.get(cur.getLoop().index);
-                    if (loopHeader != null) {
-                        codeEmittingOrder.add(loopHeader);
-
-                        for (int i = 0; i < loopHeader.numberOfSux(); i++) {
-                            Block succ = loopHeader.suxAt(i);
-                            if (succ.getLoopDepth() == loopHeader.getLoopDepth()) {
-                              //  succ.align = true;
-                            }
-                        }
-                    }
-                }
-            } else {
-                loopHeaders.set(cur.getLoop().index, cur);
-            }
-        }
-    }
-
-    private void checkAndSortIntoWorkList(Block b) {
-        if (readyForProcessing(b)) {
-            sortIntoWorkList(b);
-        }
-    }
-
-    private void computeOrder(Block startBlock) {
-        // the start block is always the first block in the linear scan order
-        linearScanOrder = new ArrayList<>(blockCount);
-
-        codeEmittingOrder = new ArrayList<>(blockCount);
-
-        // start processing with standard entry block
-        assert workList.isEmpty() : "list must be empty before processing";
-
-        sortIntoWorkList(startBlock);
-
-        do {
-            Block cur = workList.remove(workList.size() - 1);
-            processBlock(cur);
-        } while (workList.size() > 0);
-    }
-
-    private void processBlock(Block cur) {
-        appendBlock(cur);
-
-        Node endNode = cur.getEndNode();
-        if (endNode instanceof IfNode && ((IfNode) endNode).probability() < 0.5) {
-            assert cur.numberOfSux() == 2;
-            checkAndSortIntoWorkList(cur.suxAt(1));
-            checkAndSortIntoWorkList(cur.suxAt(0));
-        } else {
-            for (Block sux : cur.getSuccessors()) {
-                checkAndSortIntoWorkList(sux);
-            }
-        }
-    }
 }