Bug 678377: IonMonkey: LICM: Use explicit stack to mark blocks in a loop, r=bhackett
authorHannes Verschore <hv1989@gmail.com>
Mon, 29 Apr 2013 10:35:44 +0200
changeset 130198 082445b83eba1134f01a1e6d1110c68b41987a5b
parent 130197 ea5490a3bca7f8119595e045aec896b8168def53
child 130199 9edc1d55aff547ddf47604dd7a76839616ccb7fb
push idunknown
push userunknown
push dateunknown
reviewersbhackett
bugs678377
milestone23.0a1
Bug 678377: IonMonkey: LICM: Use explicit stack to mark blocks in a loop, r=bhackett
js/src/ion/LICM.cpp
js/src/ion/LICM.h
--- a/js/src/ion/LICM.cpp
+++ b/js/src/ion/LICM.cpp
@@ -30,17 +30,17 @@ LICM::analyze()
     for (ReversePostorderIterator i(graph.rpoBegin()); i != graph.rpoEnd(); i++) {
         MBasicBlock *header = *i;
 
         // Skip non-headers and self-loops.
         if (!header->isLoopHeader() || header->numPredecessors() < 2)
             continue;
 
         // Attempt to optimize loop.
-        Loop loop(mir, header->backedge(), header);
+        Loop loop(mir, header);
 
         Loop::LoopReturn lr = loop.init();
         if (lr == Loop::LoopReturn_Error)
             return false;
         if (lr == Loop::LoopReturn_Skip) {
             graph.unmarkBlocks();
             continue;
         }
@@ -49,76 +49,83 @@ LICM::analyze()
             return false;
 
         graph.unmarkBlocks();
     }
 
     return true;
 }
 
-Loop::Loop(MIRGenerator *mir, MBasicBlock *footer, MBasicBlock *header)
+Loop::Loop(MIRGenerator *mir, MBasicBlock *header)
   : mir(mir),
-    footer_(footer),
     header_(header)
 {
     preLoop_ = header_->getPredecessor(0);
 }
 
 Loop::LoopReturn
 Loop::init()
 {
     IonSpew(IonSpew_LICM, "Loop identified, headed by block %d", header_->id());
-    IonSpew(IonSpew_LICM, "footer is block %d", footer_->id());
+    IonSpew(IonSpew_LICM, "footer is block %d", header_->backedge()->id());
 
     // The first predecessor of the loop header must dominate the header.
     JS_ASSERT(header_->id() > header_->getPredecessor(0)->id());
 
-    LoopReturn lr = iterateLoopBlocks(footer_);
-    if (lr == LoopReturn_Error)
+    // Loops from backedge to header and marks all visited blocks
+    // as part of the loop. At the same time add all hoistable instructions
+    // (in RPO order) to the instruction worklist.
+    Vector<MBasicBlock *, 1, IonAllocPolicy> inlooplist;
+    if (!inlooplist.append(header_->backedge()))
         return LoopReturn_Error;
+    header_->backedge()->mark();
 
-    return lr;
-}
+    while (!inlooplist.empty()) {
+        MBasicBlock *block = inlooplist.back();
 
-Loop::LoopReturn
-Loop::iterateLoopBlocks(MBasicBlock *current)
-{
-    // Visited.
-    current->mark();
+        // Hoisting requires more finesse if the loop contains a block that
+        // self-dominates: there exists control flow that may enter the loop
+        // without passing through the loop preheader.
+        //
+        // Rather than perform a complicated analysis of the dominance graph,
+        // just return a soft error to ignore this loop.
+        if (block->immediateDominator() == block)
+            return LoopReturn_Skip;
 
-    // Hoisting requires more finesse if the loop contains a block that
-    // self-dominates: there exists control flow that may enter the loop
-    // without passing through the loop preheader.
-    //
-    // Rather than perform a complicated analysis of the dominance graph,
-    // just return a soft error to ignore this loop.
-    if (current->immediateDominator() == current)
-        return LoopReturn_Skip;
+        // Add not yet visited predecessors to the inlooplist.
+        if (block != header_) {
+            for (size_t i = 0; i < block->numPredecessors(); i--) {
+                MBasicBlock *pred = block->getPredecessor(i);
+                if (pred->isMarked())
+                    continue;
+
+                if (!inlooplist.append(pred))
+                    return LoopReturn_Error;
+                pred->mark();
+            }
+        }
 
-    // If we haven't reached the loop header yet, recursively explore predecessors
-    // if we haven't seen them already.
-    if (current != header_) {
-        for (size_t i = 0; i < current->numPredecessors(); i++) {
-            if (current->getPredecessor(i)->isMarked())
-                continue;
-            LoopReturn lr = iterateLoopBlocks(current->getPredecessor(i));
-            if (lr != LoopReturn_Success)
-                return lr;
+        // If any block was added, process them first.
+        if (block != inlooplist.back())
+            continue;
+
+        // Add all instructions in this block (but the control instruction) to the worklist
+        for (MInstructionIterator i = block->begin(); i != block->end(); i++) {
+            MInstruction *ins = *i;
+
+            if (ins->isMovable() && !ins->isEffectful()) {
+                if (!insertInWorklist(ins))
+                    return LoopReturn_Error;
+            }
         }
+
+        // All successors of this block are visited.
+        inlooplist.popBack();
     }
 
-    // Add all instructions in this block (but the control instruction) to the worklist
-    for (MInstructionIterator i = current->begin(); i != current->end(); i++) {
-        MInstruction *ins = *i;
-
-        if (ins->isMovable() && !ins->isEffectful()) {
-            if (!insertInWorklist(ins))
-                return LoopReturn_Error;
-        }
-    }
     return LoopReturn_Success;
 }
 
 bool
 Loop::optimize()
 {
     InstructionQueue invariantInstructions;
 
--- a/js/src/ion/LICM.h
+++ b/js/src/ion/LICM.h
@@ -41,39 +41,32 @@ class Loop
     enum LoopReturn {
         LoopReturn_Success,
         LoopReturn_Error, // Compilation failure.
         LoopReturn_Skip   // The loop is not suitable for LICM, but there is no error.
     };
 
   public:
     // A loop is constructed on a backedge found in the control flow graph.
-    Loop(MIRGenerator *mir, MBasicBlock *header, MBasicBlock *footer);
+    Loop(MIRGenerator *mir, MBasicBlock *footer);
 
     // Initializes the loop, finds all blocks and instructions contained in the loop.
     LoopReturn init();
 
     // Identifies hoistable loop invariant instructions and moves them out of the loop.
     bool optimize();
 
   private:
-    // These blocks define the loop.  header_ points to the loop header, and footer_
-    // points to the basic block that has a backedge back to the loop header.
-    MBasicBlock *footer_;
+    // These blocks define the loop.  header_ points to the loop header
     MBasicBlock *header_;
 
     // The pre-loop block is the first predecessor of the loop header.  It is where
     // the loop is first entered and where hoisted instructions will be placed.
     MBasicBlock* preLoop_;
 
-    // This method recursively traverses the graph from the loop footer back through
-    // predecessor edges and stops when it reaches the loop header.
-    // Along the way it adds instructions to the worklist for invariance testing.
-    LoopReturn iterateLoopBlocks(MBasicBlock *current);
-
     bool hoistInstructions(InstructionQueue &toHoist);
 
     // Utility methods for invariance testing and instruction hoisting.
     bool isInLoop(MDefinition *ins);
     bool isBeforeLoop(MDefinition *ins);
     bool isLoopInvariant(MInstruction *ins);
     bool isLoopInvariant(MDefinition *ins);