author | Nicholas D. Matsakis <nmatsakis@mozilla.com> |
Thu, 11 Jul 2013 12:55:47 -0400 | |
changeset 138326 | 42a9972a1667793929cebfef885b1b60bad4b466 |
parent 138325 | 1c4f15e06065a9e82596a2bf69c21a5943ea05f4 |
child 138327 | e97532f5fd86d8218f9f741c5a94dc321b738277 |
push id | 30932 |
push user | nmatsakis@mozilla.com |
push date | Fri, 12 Jul 2013 16:50:23 +0000 |
treeherder | mozilla-inbound@42a9972a1667 [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | bhackett |
bugs | 880377 |
milestone | 25.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
|
js/src/ion/UnreachableCodeElimination.cpp | file | annotate | diff | comparison | revisions | |
js/src/ion/UnreachableCodeElimination.h | file | annotate | diff | comparison | revisions |
--- 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) {}