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 id24605
push userkwierso@gmail.com
push dateMon, 29 Apr 2013 21:47:00 +0000
treeherdermozilla-central@dd0c611a0a27 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett
bugs678377
milestone23.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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);