# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1309946366 -7200
# Node ID f855f0e93791a51a9c0291ae67924e5cf249553f
# Parent  bdc1a456a6e0ea271d23aecc6977d82ebca28db8
simplified compute linear scan order.

diff -r bdc1a456a6e0 -r f855f0e93791 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java	Wed Jul 06 11:52:31 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ComputeLinearScanOrder.java	Wed Jul 06 11:59:26 2011 +0200
@@ -28,15 +28,12 @@
 import com.oracle.max.graal.compiler.*;
 import com.oracle.max.graal.compiler.debug.*;
 import com.oracle.max.graal.compiler.lir.*;
-import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.graph.*;
 
 public final class ComputeLinearScanOrder {
 
     private final int maxBlockId; // the highest blockId of a block
     private int numBlocks; // total number of blocks (smaller than maxBlockId)
-    private int numLoops; // total number of loops
-    private boolean iterativeDominators; // method requires iterative computation of dominators
 
     List<LIRBlock> linearScanOrder; // the resulting list of blocks in correct order
 
@@ -44,8 +41,6 @@
     final BitMap activeBlocks; // used for recursive processing of blocks
     final BitMap dominatorBlocks; // temporary BitMap used for computation of dominator
     final int[] forwardBranches; // number of incoming forward branches for each block
-    final List<LIRBlock> loopEndBlocks; // list of all loop end blocks collected during countEdges
-    BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop
     final List<LIRBlock> workList; // temporary list (used in markLoops and computeOrder)
 
     // accessors for visitedBlocks and activeBlocks
@@ -86,28 +81,11 @@
         return --forwardBranches[b.blockID()];
     }
 
-    // accessors for loopMap
-    boolean isBlockInLoop(int loopIdx, LIRBlock b) {
-        return loopMap.at(loopIdx, b.blockID());
-    }
-
-    void setBlockInLoop(int loopIdx, LIRBlock b) {
-        loopMap.setBit(loopIdx, b.blockID());
-    }
-
-    void clearBlockInLoop(int loopIdx, int blockId) {
-        loopMap.clearBit(loopIdx, blockId);
-    }
-
     // accessors for final result
     public List<LIRBlock> linearScanOrder() {
         return linearScanOrder;
     }
 
-    public int numLoops() {
-        return numLoops;
-    }
-
     public ComputeLinearScanOrder(int maxBlockId, LIRBlock startBlock) {
 
         this.maxBlockId = maxBlockId;
@@ -115,29 +93,11 @@
         activeBlocks = new BitMap(maxBlockId);
         dominatorBlocks = new BitMap(maxBlockId);
         forwardBranches = new int[maxBlockId];
-        loopEndBlocks = new ArrayList<LIRBlock>(8);
         workList = new ArrayList<LIRBlock>(8);
 
-        splitCriticalEdges();
-
         countEdges(startBlock, null);
-
-        if (numLoops > 0) {
-            TTY.println("num loops " + numLoops);
-            throw new IllegalStateException();
-//            markLoops();
-//            clearNonNaturalLoops(startBlock);
-//            assignLoopDepth(startBlock);
-        }
-
         computeOrder(startBlock);
-
         printBlocks();
-        assert verify();
-    }
-
-    void splitCriticalEdges() {
-        // TODO: move critical edge splitting from IR to here
     }
 
     /**
@@ -154,16 +114,6 @@
         }
 
         if (isActive(cur)) {
-            if (GraalOptions.TraceLinearScanLevel >= 3) {
-                TTY.println("backward branch");
-            }
-            assert isVisited(cur) : "block must be visited when block is active";
-            assert parent != null : "must have parent";
-
-            cur.setLinearScanLoopHeader();
-            parent.setLinearScanLoopEnd();
-
-            loopEndBlocks.add(parent);
             return;
         }
 
@@ -189,137 +139,11 @@
 
         clearActive(cur);
 
-        // Each loop has a unique number.
-        // When multiple loops are nested, assignLoopDepth assumes that the
-        // innermost loop has the lowest number. This is guaranteed by setting
-        // the loop number after the recursive calls for the successors above
-        // have returned.
-//        if (cur.isLinearScanLoopHeader()) {
-//            assert cur.loopIndex() == -1 : "cannot set loop-index twice";
-//            if (GraalOptions.TraceLinearScanLevel >= 3) {
-//                TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops);
-//            }
-//
-//            cur.setLoopIndex(numLoops);
-//            numLoops++;
-//        }
-
         if (GraalOptions.TraceLinearScanLevel >= 3) {
             TTY.println("Finished counting edges for block B%d", cur.blockID());
         }
     }
 
-    void markLoops() {
-        if (GraalOptions.TraceLinearScanLevel >= 3) {
-            TTY.println("----- marking loops");
-        }
-
-        loopMap = new BitMap2D(numLoops, maxBlockId);
-
-        for (int i = loopEndBlocks.size() - 1; i >= 0; i--) {
-            LIRBlock loopEnd = loopEndBlocks.get(i);
-            LIRBlock loopStart = loopEnd.suxAt(0);
-            int loopIdx = loopStart.loopIndex();
-
-            if (GraalOptions.TraceLinearScanLevel >= 3) {
-                TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID(), loopEnd.blockID(), loopIdx);
-            }
-            assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set";
-//            assert loopEnd.numberOfSux() == 1 : "incorrect number of successors";
-            assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set";
-            assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set";
-            assert workList.isEmpty() : "work list must be empty before processing";
-
-            // add the end-block of the loop to the working list
-            workList.add(loopEnd);
-            setBlockInLoop(loopIdx, loopEnd);
-            do {
-                LIRBlock cur = workList.remove(workList.size() - 1);
-
-                if (GraalOptions.TraceLinearScanLevel >= 3) {
-                    TTY.println("    processing B%d", cur.blockID());
-                }
-                assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list";
-
-                // recursive processing of all predecessors ends when start block of loop is reached
-                if (cur != loopStart) {
-                    for (int j = cur.numberOfPreds() - 1; j >= 0; j--) {
-                        LIRBlock pred = cur.predAt(j);
-
-                        if (!isBlockInLoop(loopIdx, pred)) {
-                            // this predecessor has not been processed yet, so add it to work list
-                            if (GraalOptions.TraceLinearScanLevel >= 3) {
-                                TTY.println("    pushing B%d", pred.blockID());
-                            }
-                            workList.add(pred);
-                            setBlockInLoop(loopIdx, pred);
-                        }
-                    }
-                }
-            } while (!workList.isEmpty());
-        }
-    }
-
-    // check for non-natural loops (loops where the loop header does not dominate
-    // all other loop blocks = loops with multiple entries).
-    // such loops are ignored
-    void clearNonNaturalLoops(LIRBlock startBlock) {
-        for (int i = numLoops - 1; i >= 0; i--) {
-            if (isBlockInLoop(i, startBlock)) {
-                // loop i contains the entry block of the method.
-                // this is not a natural loop, so ignore it
-                if (GraalOptions.TraceLinearScanLevel >= 2) {
-                    TTY.println("Loop %d is non-natural, so it is ignored", i);
-                }
-
-                for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) {
-                    clearBlockInLoop(i, blockId);
-                }
-                iterativeDominators = true;
-            }
-        }
-    }
-
-    void assignLoopDepth(LIRBlock startBlock) {
-        if (GraalOptions.TraceLinearScanLevel >= 3) {
-            TTY.println("----- computing loop-depth and weight");
-        }
-        initVisited();
-
-        assert workList.isEmpty() : "work list must be empty before processing";
-        workList.add(startBlock);
-
-        do {
-            LIRBlock cur = workList.remove(workList.size() - 1);
-
-            if (!isVisited(cur)) {
-                setVisited(cur);
-                if (GraalOptions.TraceLinearScanLevel >= 4) {
-                    TTY.println("Computing loop depth for block B%d", cur.blockID());
-                }
-
-                // compute loop-depth and loop-index for the block
-                assert cur.loopDepth() == 0 : "cannot set loop-depth twice";
-                int i;
-                int loopDepth = 0;
-                int minLoopIdx = -1;
-                for (i = numLoops - 1; i >= 0; i--) {
-                    if (isBlockInLoop(i, cur)) {
-                        loopDepth++;
-                        minLoopIdx = i;
-                    }
-                }
-                cur.setLoopDepth(loopDepth);
-                cur.setLoopIndex(minLoopIdx);
-
-                // append all unvisited successors to work list
-                for (i = cur.numberOfSux() - 1; i >= 0; i--) {
-                    workList.add(cur.suxAt(i));
-                }
-            }
-        } while (!workList.isEmpty());
-    }
-
     int computeWeight(LIRBlock cur) {
 
         // limit loop-depth to 15 bit (only for security reason, it will never be so big)
@@ -375,7 +199,7 @@
         return weight;
     }
 
-    boolean readyForProcessing(LIRBlock cur) {
+    private boolean readyForProcessing(LIRBlock cur) {
         // Discount the edge just traveled.
         // When the number drops to zero, all forward branches were processed
         if (decForwardBranches(cur) != 0) {
@@ -387,7 +211,7 @@
         return true;
     }
 
-    void sortIntoWorkList(LIRBlock cur) {
+    private void sortIntoWorkList(LIRBlock cur) {
         assert !workList.contains(cur) : "block already in work list";
 
         int curWeight = computeWeight(cur);
@@ -422,7 +246,7 @@
         }
     }
 
-    void appendBlock(LIRBlock cur) {
+    private void appendBlock(LIRBlock cur) {
         if (GraalOptions.TraceLinearScanLevel >= 3) {
             TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID(), cur.linearScanNumber());
         }
@@ -470,9 +294,6 @@
             TTY.println("----- loop information:");
             for (LIRBlock cur : linearScanOrder) {
                 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID()));
-                for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
-                    TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur)));
-                }
                 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth()));
             }
         }
@@ -506,76 +327,4 @@
             }
         }
     }
-
-    boolean verify() {
-       /* assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list";
-
-        if (GraalOptions.StressLinearScan) {
-            // blocks are scrambled when StressLinearScan is used
-            return true;
-        }
-
-        // check that all successors of a block have a higher linear-scan-number
-        // and that all predecessors of a block have a lower linear-scan-number
-        // (only backward branches of loops are ignored)
-        int i;
-        for (i = 0; i < linearScanOrder.size(); i++) {
-            BlockBegin cur = linearScanOrder.get(i);
-
-            assert cur.linearScanNumber() == i : "incorrect linearScanNumber";
-            assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber";
-
-            for (BlockBegin sux : cur.end().successors()) {
-                assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber";
-                if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) {
-                    assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order";
-                }
-                if (cur.loopDepth() == sux.loopDepth()) {
-                    assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
-                }
-            }
-
-            for (BlockBegin pred : cur.predecessors()) {
-                assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber";
-                if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) {
-                    assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order";
-                }
-                if (cur.loopDepth() == pred.loopDepth()) {
-                    assert cur.loopIndex() == pred.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index";
-                }
-
-                assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors";
-            }
-
-            // check dominator
-            if (i == 0) {
-                assert cur.dominator() == null : "first block has no dominator";
-            } else {
-                assert cur.dominator() != null : "all but first block must have dominator";
-            }
-            assert cur.numberOfPreds() != 1 || cur.dominator() == cur.predAt(0) || cur.isExceptionEntry() : "Single predecessor must also be dominator";
-        }
-
-        // check that all loops are continuous
-        for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) {
-            int blockIdx = 0;
-            assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop";
-
-            // skip blocks before the loop
-            while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
-                blockIdx++;
-            }
-            // skip blocks of loop
-            while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) {
-                blockIdx++;
-            }
-            // after the first non-loop block : there must not be another loop-block
-            while (blockIdx < numBlocks) {
-                assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order";
-                blockIdx++;
-            }
-        }
-*/
-        return true;
-    }
 }