diff -r 000000000000 -r 6474c204b198 js/src/jit/UnreachableCodeElimination.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/jit/UnreachableCodeElimination.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,298 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "jit/UnreachableCodeElimination.h" + +#include "jit/AliasAnalysis.h" +#include "jit/IonAnalysis.h" +#include "jit/MIRGenerator.h" +#include "jit/ValueNumbering.h" + +using namespace js; +using namespace jit; + +bool +UnreachableCodeElimination::analyze() +{ + // The goal of this routine is to eliminate code that is + // unreachable, either because there is no path from the entry + // block to the code, or because the path traverses a conditional + // branch where the condition is a constant (e.g., "if (false) { + // ... }"). The latter can either appear in the source form or + // arise due to optimizations. + // + // The stategy is straightforward. The pass begins with a + // depth-first search. We set a bit on each basic block that + // is visited. If a block terminates in a conditional branch + // predicated on a constant, we rewrite the block to an unconditional + // jump and do not visit the now irrelevant basic block. + // + // Once the initial DFS is complete, we do a second pass over the + // blocks to find those that were not reached. Those blocks are + // simply removed wholesale. We must also correct any phis that + // may be affected.. + + // Pass 1: Identify unreachable blocks (if any). + if (!prunePointlessBranchesAndMarkReachableBlocks()) + return false; + + return removeUnmarkedBlocksAndCleanup(); +} + +bool +UnreachableCodeElimination::removeUnmarkedBlocks(size_t marked) +{ + marked_ = marked; + return removeUnmarkedBlocksAndCleanup(); +} + +bool +UnreachableCodeElimination::removeUnmarkedBlocksAndCleanup() +{ + // Everything is reachable, no work required. + JS_ASSERT(marked_ <= graph_.numBlocks()); + if (marked_ == graph_.numBlocks()) { + graph_.unmarkBlocks(); + return true; + } + + // Pass 2: Remove unmarked blocks (see analyze() above). + if (!removeUnmarkedBlocksAndClearDominators()) + return false; + graph_.unmarkBlocks(); + + AssertGraphCoherency(graph_); + + IonSpewPass("UCE-mid-point"); + + // Pass 3: Recompute dominators and tweak phis. + BuildDominatorTree(graph_); + if (redundantPhis_ && !EliminatePhis(mir_, graph_, ConservativeObservability)) + return false; + + // Pass 4: Rerun alias analysis + if (rerunAliasAnalysis_) { + AliasAnalysis analysis(mir_, graph_); + if (!analysis.analyze()) + return false; + } + + // Pass 5: It's important for optimizations to re-run GVN (and in + // turn alias analysis) after UCE if we eliminated branches. + if (rerunAliasAnalysis_ && mir_->optimizationInfo().gvnEnabled()) { + ValueNumberer gvn(mir_, graph_, mir_->optimizationInfo().gvnKind() == GVN_Optimistic); + if (!gvn.clear() || !gvn.analyze()) + return false; + IonSpewPass("GVN-after-UCE"); + AssertExtendedGraphCoherency(graph_); + + 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 nullptr. + + MControlInstruction *ins = block->lastIns(); + if (!ins->isTest()) + return nullptr; + + MTest *testIns = ins->toTest(); + MDefinition *v = testIns->getOperand(0); + if (!v->isConstant()) + return nullptr; + + BranchDirection bdir = v->toConstant()->valueToBoolean() ? TRUE_BRANCH : FALSE_BRANCH; + return testIns->branchSuccessor(bdir); +} + +bool +UnreachableCodeElimination::prunePointlessBranchesAndMarkReachableBlocks() +{ + BlockList worklist, optimizableBlocks; + + // 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(); + + // 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(graph_.alloc(), succ); + block->discardLastIns(); + block->end(gotoIns); + MBasicBlock *successorWithPhis = block->successorWithPhis(); + if (successorWithPhis && successorWithPhis != succ) + block->setSuccessorWithPhis(nullptr, 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. + if (!disableAliasAnalysis_ && instr->dependency() && !instr->dependency()->block()->isMarked()) + rerunAliasAnalysis_ = true; + + for (MUseIterator iter(instr->usesBegin()); iter != instr->usesEnd(); ) { + if (!iter->consumer()->block()->isMarked()) { + instr->setUseRemovedUnchecked(); + iter = instr->removeUse(iter); + } else { + iter++; + } + } +} + +bool +UnreachableCodeElimination::removeUnmarkedBlocksAndClearDominators() +{ + // Removes blocks that are not marked from the graph. For blocks + // that *are* marked, clears the mark and adjusts the id to its + // new value. Also adds blocks that are immediately reachable + // from an unmarked block to the frontier. + + size_t id = marked_; + for (PostorderIterator iter(graph_.poBegin()); iter != graph_.poEnd();) { + if (mir_->shouldCancel("Eliminate Unreachable Code")) + return false; + + MBasicBlock *block = *iter; + iter++; + + // Unconditionally clear the dominators. It's somewhat complex to + // adjust the values and relatively fast to just recompute. + block->clearDominatorInfo(); + + if (block->isMarked()) { + block->setId(--id); + for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd(); iter++) + checkDependencyAndRemoveUsesFromUnmarkedBlocks(*iter); + for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) + checkDependencyAndRemoveUsesFromUnmarkedBlocks(*iter); + } else { + if (block->numPredecessors() > 1) { + // If this block had phis, then any reachable + // predecessors need to have the successorWithPhis + // flag cleared. + for (size_t i = 0; i < block->numPredecessors(); i++) + block->getPredecessor(i)->setSuccessorWithPhis(nullptr, 0); + } + + if (block->isLoopBackedge()) { + // NB. We have to update the loop header if we + // eliminate the backedge. At first I thought this + // check would be insufficient, because it would be + // possible to have code like this: + // + // while (true) { + // ...; + // if (1 == 1) break; + // } + // + // in which the backedge is removed as part of + // rewriting the condition, but no actual blocks are + // removed. However, in all such cases, the backedge + // would be a critical edge and hence the critical + // edge block is being removed. + block->loopHeaderOfBackedge()->clearLoopHeader(); + } + + for (size_t i = 0, c = block->numSuccessors(); i < c; i++) { + MBasicBlock *succ = block->getSuccessor(i); + if (succ->isMarked()) { + // succ is on the frontier of blocks to be removed: + succ->removePredecessor(block); + + if (!redundantPhis_) { + for (MPhiIterator iter(succ->phisBegin()); iter != succ->phisEnd(); iter++) { + if (iter->operandIfRedundant()) { + redundantPhis_ = true; + break; + } + } + } + } + } + + graph_.removeBlock(block); + } + } + + JS_ASSERT(id == 0); + + return true; +}