Bug 880377 - Make UCE abort if some blocks are only reachable from OSR entry point r=bhackett
authorNicholas D. Matsakis <nmatsakis@mozilla.com>
Thu, 11 Jul 2013 12:55:47 -0400
changeset 138326 42a9972a1667793929cebfef885b1b60bad4b466
parent 138325 1c4f15e06065a9e82596a2bf69c21a5943ea05f4
child 138327 e97532f5fd86d8218f9f741c5a94dc321b738277
push id30932
push usernmatsakis@mozilla.com
push dateFri, 12 Jul 2013 16:50:23 +0000
treeherdermozilla-inbound@42a9972a1667 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett
bugs880377
milestone25.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 880377 - Make UCE abort if some blocks are only reachable from OSR entry point r=bhackett
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)
     {}