Bug 880377 - Make UCE abort if some blocks are only reachable from OSR entry point. r=bhackett, a=bajaj
authorNicholas D. Matsakis <nmatsakis@mozilla.com>
Thu, 11 Jul 2013 12:55:47 -0400
changeset 143559 7255bae7b63563a843e2dba520a791133fcee37d
parent 143558 a584507c3833325179005e3101d45d26972d081f
child 143560 218c4145c0667240c197f72b7a316c18d2d72a54
push id3995
push userryanvm@gmail.com
push dateWed, 17 Jul 2013 19:43:59 +0000
treeherdermozilla-aurora@602f5a2d621a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett, bajaj
bugs880377
milestone24.0a2
Bug 880377 - Make UCE abort if some blocks are only reachable from OSR entry point. r=bhackett, a=bajaj
js/src/ion/UnreachableCodeElimination.cpp
js/src/ion/UnreachableCodeElimination.h
--- a/js/src/ion/UnreachableCodeElimination.cpp
+++ b/js/src/ion/UnreachableCodeElimination.cpp
@@ -90,66 +90,116 @@ UnreachableCodeElimination::removeUnmark
         if (mir_->shouldCancel("GVN-after-UCE"))
             return false;
     }
 
     return true;
 }
 
 bool
+UnreachableCodeElimination::enqueue(MBasicBlock *block, BlockList &list)
+{
+    if (block->isMarked())
+        return true;
+
+    block->mark();
+    marked_++;
+    return list.append(block);
+}
+
+MBasicBlock *
+UnreachableCodeElimination::optimizableSuccessor(MBasicBlock *block)
+{
+    // If the last instruction in `block` is a test instruction of a
+    // constant value, returns the successor that the branch will
+    // always branch to at runtime. Otherwise, returns NULL.
+
+    MControlInstruction *ins = block->lastIns();
+    if (!ins->isTest())
+        return NULL;
+
+    MTest *testIns = ins->toTest();
+    MDefinition *v = testIns->getOperand(0);
+    if (!v->isConstant())
+        return NULL;
+
+    const Value &val = v->toConstant()->value();
+    BranchDirection bdir = ToBoolean(val) ? TRUE_BRANCH : FALSE_BRANCH;
+    return testIns->branchSuccessor(bdir);
+}
+
+bool
 UnreachableCodeElimination::prunePointlessBranchesAndMarkReachableBlocks()
 {
-    Vector<MBasicBlock *, 16, SystemAllocPolicy> worklist;
+    BlockList worklist, optimizableBlocks;
 
-    // Seed with the two entry points.
-    MBasicBlock *entries[] = { graph_.entryBlock(), graph_.osrBlock() };
-    for (size_t i = 0; i < sizeof(entries) / sizeof(entries[0]); i++) {
-        if (entries[i]) {
-            entries[i]->mark();
-            marked_++;
-            if (!worklist.append(entries[i]))
-                return false;
-        }
-    }
-
-    // Process everything reachable from there.
+    // Process everything reachable from the start block, ignoring any
+    // OSR block.
+    if (!enqueue(graph_.entryBlock(), worklist))
+        return false;
     while (!worklist.empty()) {
         if (mir_->shouldCancel("Eliminate Unreachable Code"))
             return false;
 
         MBasicBlock *block = worklist.popCopy();
-        MControlInstruction *ins = block->lastIns();
 
-        // Rewrite test false or test true to goto.
-        if (ins->isTest()) {
-            MTest *testIns = ins->toTest();
-            MDefinition *v = testIns->getOperand(0);
-            if (v->isConstant()) {
-                const Value &val = v->toConstant()->value();
-                BranchDirection bdir = ToBoolean(val) ? TRUE_BRANCH : FALSE_BRANCH;
-                MBasicBlock *succ = testIns->branchSuccessor(bdir);
-                MGoto *gotoIns = MGoto::New(succ);
-                block->discardLastIns();
-                block->end(gotoIns);
-                MBasicBlock *successorWithPhis = block->successorWithPhis();
-                if (successorWithPhis && successorWithPhis != succ)
-                    block->setSuccessorWithPhis(NULL, 0);
-            }
-        }
-
-        for (size_t i = 0; i < block->numSuccessors(); i++) {
-            MBasicBlock *succ = block->getSuccessor(i);
-            if (!succ->isMarked()) {
-                succ->mark();
-                marked_++;
-                if (!worklist.append(succ))
+        // If this block is a test on a constant operand, only enqueue
+        // the relevant successor. Also, remember the block for later.
+        if (MBasicBlock *succ = optimizableSuccessor(block)) {
+            if (!optimizableBlocks.append(block))
+                return false;
+            if (!enqueue(succ, worklist))
+                return false;
+        } else {
+            // Otherwise just visit all successors.
+            for (size_t i = 0; i < block->numSuccessors(); i++) {
+                MBasicBlock *succ = block->getSuccessor(i);
+                if (!enqueue(succ, worklist))
                     return false;
             }
         }
     }
+
+    // Now, if there is an OSR block, check that all of its successors
+    // were reachable (bug 880377). If not, we are in danger of
+    // creating a CFG with two disjoint parts, so simply mark all
+    // blocks as reachable. This generally occurs when the TI info for
+    // stack types is incorrect or incomplete, due to operations that
+    // have not yet executed in baseline.
+    if (graph_.osrBlock()) {
+        MBasicBlock *osrBlock = graph_.osrBlock();
+        JS_ASSERT(!osrBlock->isMarked());
+        if (!enqueue(osrBlock, worklist))
+            return false;
+        for (size_t i = 0; i < osrBlock->numSuccessors(); i++) {
+            if (!osrBlock->getSuccessor(i)->isMarked()) {
+                // OSR block has an otherwise unreachable successor, abort.
+                for (MBasicBlockIterator iter(graph_.begin()); iter != graph_.end(); iter++)
+                    iter->mark();
+                marked_ = graph_.numBlocks();
+                return true;
+            }
+        }
+    }
+
+    // Now that we know we will not abort due to OSR, go back and
+    // transform any tests on constant operands into gotos.
+    for (uint32_t i = 0; i < optimizableBlocks.length(); i++) {
+        MBasicBlock *block = optimizableBlocks[i];
+        MBasicBlock *succ = optimizableSuccessor(block);
+        JS_ASSERT(succ);
+
+        MGoto *gotoIns = MGoto::New(succ);
+        block->discardLastIns();
+        block->end(gotoIns);
+        MBasicBlock *successorWithPhis = block->successorWithPhis();
+        if (successorWithPhis && successorWithPhis != succ)
+            block->setSuccessorWithPhis(NULL, 0);
+    }
+
     return true;
 }
 
 void
 UnreachableCodeElimination::checkDependencyAndRemoveUsesFromUnmarkedBlocks(MDefinition *instr)
 {
     // When the instruction depends on removed block,
     // alias analysis needs to get rerun to have the right dependency.
--- a/js/src/ion/UnreachableCodeElimination.h
+++ b/js/src/ion/UnreachableCodeElimination.h
@@ -12,27 +12,32 @@
 
 namespace js {
 namespace ion {
 
 class MIRGraph;
 
 class UnreachableCodeElimination
 {
+    typedef Vector<MBasicBlock *, 16, SystemAllocPolicy> BlockList;
+
     MIRGenerator *mir_;
     MIRGraph &graph_;
     uint32_t marked_;
     bool redundantPhis_;
     bool rerunAliasAnalysis_;
 
     bool prunePointlessBranchesAndMarkReachableBlocks();
     void checkDependencyAndRemoveUsesFromUnmarkedBlocks(MDefinition *instr);
     bool removeUnmarkedBlocksAndClearDominators();
     bool removeUnmarkedBlocksAndCleanup();
 
+    bool enqueue(MBasicBlock *block, BlockList &list);
+    MBasicBlock *optimizableSuccessor(MBasicBlock *block);
+
   public:
     UnreachableCodeElimination(MIRGenerator *mir, MIRGraph &graph)
       : mir_(mir),
         graph_(graph),
         marked_(0),
         redundantPhis_(false),
         rerunAliasAnalysis_(false)
     {}