michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jit/UnreachableCodeElimination.h"
michael@0: 
michael@0: #include "jit/AliasAnalysis.h"
michael@0: #include "jit/IonAnalysis.h"
michael@0: #include "jit/MIRGenerator.h"
michael@0: #include "jit/ValueNumbering.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace jit;
michael@0: 
michael@0: bool
michael@0: UnreachableCodeElimination::analyze()
michael@0: {
michael@0:     // The goal of this routine is to eliminate code that is
michael@0:     // unreachable, either because there is no path from the entry
michael@0:     // block to the code, or because the path traverses a conditional
michael@0:     // branch where the condition is a constant (e.g., "if (false) {
michael@0:     // ... }").  The latter can either appear in the source form or
michael@0:     // arise due to optimizations.
michael@0:     //
michael@0:     // The stategy is straightforward.  The pass begins with a
michael@0:     // depth-first search.  We set a bit on each basic block that
michael@0:     // is visited.  If a block terminates in a conditional branch
michael@0:     // predicated on a constant, we rewrite the block to an unconditional
michael@0:     // jump and do not visit the now irrelevant basic block.
michael@0:     //
michael@0:     // Once the initial DFS is complete, we do a second pass over the
michael@0:     // blocks to find those that were not reached.  Those blocks are
michael@0:     // simply removed wholesale.  We must also correct any phis that
michael@0:     // may be affected..
michael@0: 
michael@0:     // Pass 1: Identify unreachable blocks (if any).
michael@0:     if (!prunePointlessBranchesAndMarkReachableBlocks())
michael@0:         return false;
michael@0: 
michael@0:     return removeUnmarkedBlocksAndCleanup();
michael@0: }
michael@0: 
michael@0: bool
michael@0: UnreachableCodeElimination::removeUnmarkedBlocks(size_t marked)
michael@0: {
michael@0:     marked_ = marked;
michael@0:     return removeUnmarkedBlocksAndCleanup();
michael@0: }
michael@0: 
michael@0: bool
michael@0: UnreachableCodeElimination::removeUnmarkedBlocksAndCleanup()
michael@0: {
michael@0:     // Everything is reachable, no work required.
michael@0:     JS_ASSERT(marked_ <= graph_.numBlocks());
michael@0:     if (marked_ == graph_.numBlocks()) {
michael@0:         graph_.unmarkBlocks();
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // Pass 2: Remove unmarked blocks (see analyze() above).
michael@0:     if (!removeUnmarkedBlocksAndClearDominators())
michael@0:         return false;
michael@0:     graph_.unmarkBlocks();
michael@0: 
michael@0:     AssertGraphCoherency(graph_);
michael@0: 
michael@0:     IonSpewPass("UCE-mid-point");
michael@0: 
michael@0:     // Pass 3: Recompute dominators and tweak phis.
michael@0:     BuildDominatorTree(graph_);
michael@0:     if (redundantPhis_ && !EliminatePhis(mir_, graph_, ConservativeObservability))
michael@0:         return false;
michael@0: 
michael@0:     // Pass 4: Rerun alias analysis
michael@0:     if (rerunAliasAnalysis_) {
michael@0:         AliasAnalysis analysis(mir_, graph_);
michael@0:         if (!analysis.analyze())
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     // Pass 5: It's important for optimizations to re-run GVN (and in
michael@0:     // turn alias analysis) after UCE if we eliminated branches.
michael@0:     if (rerunAliasAnalysis_ && mir_->optimizationInfo().gvnEnabled()) {
michael@0:         ValueNumberer gvn(mir_, graph_, mir_->optimizationInfo().gvnKind() == GVN_Optimistic);
michael@0:         if (!gvn.clear() || !gvn.analyze())
michael@0:             return false;
michael@0:         IonSpewPass("GVN-after-UCE");
michael@0:         AssertExtendedGraphCoherency(graph_);
michael@0: 
michael@0:         if (mir_->shouldCancel("GVN-after-UCE"))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: UnreachableCodeElimination::enqueue(MBasicBlock *block, BlockList &list)
michael@0: {
michael@0:     if (block->isMarked())
michael@0:         return true;
michael@0: 
michael@0:     block->mark();
michael@0:     marked_++;
michael@0:     return list.append(block);
michael@0: }
michael@0: 
michael@0: MBasicBlock *
michael@0: UnreachableCodeElimination::optimizableSuccessor(MBasicBlock *block)
michael@0: {
michael@0:     // If the last instruction in `block` is a test instruction of a
michael@0:     // constant value, returns the successor that the branch will
michael@0:     // always branch to at runtime. Otherwise, returns nullptr.
michael@0: 
michael@0:     MControlInstruction *ins = block->lastIns();
michael@0:     if (!ins->isTest())
michael@0:         return nullptr;
michael@0: 
michael@0:     MTest *testIns = ins->toTest();
michael@0:     MDefinition *v = testIns->getOperand(0);
michael@0:     if (!v->isConstant())
michael@0:         return nullptr;
michael@0: 
michael@0:     BranchDirection bdir = v->toConstant()->valueToBoolean() ? TRUE_BRANCH : FALSE_BRANCH;
michael@0:     return testIns->branchSuccessor(bdir);
michael@0: }
michael@0: 
michael@0: bool
michael@0: UnreachableCodeElimination::prunePointlessBranchesAndMarkReachableBlocks()
michael@0: {
michael@0:     BlockList worklist, optimizableBlocks;
michael@0: 
michael@0:     // Process everything reachable from the start block, ignoring any
michael@0:     // OSR block.
michael@0:     if (!enqueue(graph_.entryBlock(), worklist))
michael@0:         return false;
michael@0:     while (!worklist.empty()) {
michael@0:         if (mir_->shouldCancel("Eliminate Unreachable Code"))
michael@0:             return false;
michael@0: 
michael@0:         MBasicBlock *block = worklist.popCopy();
michael@0: 
michael@0:         // If this block is a test on a constant operand, only enqueue
michael@0:         // the relevant successor. Also, remember the block for later.
michael@0:         if (MBasicBlock *succ = optimizableSuccessor(block)) {
michael@0:             if (!optimizableBlocks.append(block))
michael@0:                 return false;
michael@0:             if (!enqueue(succ, worklist))
michael@0:                 return false;
michael@0:         } else {
michael@0:             // Otherwise just visit all successors.
michael@0:             for (size_t i = 0; i < block->numSuccessors(); i++) {
michael@0:                 MBasicBlock *succ = block->getSuccessor(i);
michael@0:                 if (!enqueue(succ, worklist))
michael@0:                     return false;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Now, if there is an OSR block, check that all of its successors
michael@0:     // were reachable (bug 880377). If not, we are in danger of
michael@0:     // creating a CFG with two disjoint parts, so simply mark all
michael@0:     // blocks as reachable. This generally occurs when the TI info for
michael@0:     // stack types is incorrect or incomplete, due to operations that
michael@0:     // have not yet executed in baseline.
michael@0:     if (graph_.osrBlock()) {
michael@0:         MBasicBlock *osrBlock = graph_.osrBlock();
michael@0:         JS_ASSERT(!osrBlock->isMarked());
michael@0:         if (!enqueue(osrBlock, worklist))
michael@0:             return false;
michael@0:         for (size_t i = 0; i < osrBlock->numSuccessors(); i++) {
michael@0:             if (!osrBlock->getSuccessor(i)->isMarked()) {
michael@0:                 // OSR block has an otherwise unreachable successor, abort.
michael@0:                 for (MBasicBlockIterator iter(graph_.begin()); iter != graph_.end(); iter++)
michael@0:                     iter->mark();
michael@0:                 marked_ = graph_.numBlocks();
michael@0:                 return true;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Now that we know we will not abort due to OSR, go back and
michael@0:     // transform any tests on constant operands into gotos.
michael@0:     for (uint32_t i = 0; i < optimizableBlocks.length(); i++) {
michael@0:         MBasicBlock *block = optimizableBlocks[i];
michael@0:         MBasicBlock *succ = optimizableSuccessor(block);
michael@0:         JS_ASSERT(succ);
michael@0: 
michael@0:         MGoto *gotoIns = MGoto::New(graph_.alloc(), succ);
michael@0:         block->discardLastIns();
michael@0:         block->end(gotoIns);
michael@0:         MBasicBlock *successorWithPhis = block->successorWithPhis();
michael@0:         if (successorWithPhis && successorWithPhis != succ)
michael@0:             block->setSuccessorWithPhis(nullptr, 0);
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void
michael@0: UnreachableCodeElimination::checkDependencyAndRemoveUsesFromUnmarkedBlocks(MDefinition *instr)
michael@0: {
michael@0:     // When the instruction depends on removed block,
michael@0:     // alias analysis needs to get rerun to have the right dependency.
michael@0:     if (!disableAliasAnalysis_ && instr->dependency() && !instr->dependency()->block()->isMarked())
michael@0:         rerunAliasAnalysis_ = true;
michael@0: 
michael@0:     for (MUseIterator iter(instr->usesBegin()); iter != instr->usesEnd(); ) {
michael@0:         if (!iter->consumer()->block()->isMarked()) {
michael@0:             instr->setUseRemovedUnchecked();
michael@0:             iter = instr->removeUse(iter);
michael@0:         } else {
michael@0:             iter++;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool
michael@0: UnreachableCodeElimination::removeUnmarkedBlocksAndClearDominators()
michael@0: {
michael@0:     // Removes blocks that are not marked from the graph.  For blocks
michael@0:     // that *are* marked, clears the mark and adjusts the id to its
michael@0:     // new value.  Also adds blocks that are immediately reachable
michael@0:     // from an unmarked block to the frontier.
michael@0: 
michael@0:     size_t id = marked_;
michael@0:     for (PostorderIterator iter(graph_.poBegin()); iter != graph_.poEnd();) {
michael@0:         if (mir_->shouldCancel("Eliminate Unreachable Code"))
michael@0:             return false;
michael@0: 
michael@0:         MBasicBlock *block = *iter;
michael@0:         iter++;
michael@0: 
michael@0:         // Unconditionally clear the dominators.  It's somewhat complex to
michael@0:         // adjust the values and relatively fast to just recompute.
michael@0:         block->clearDominatorInfo();
michael@0: 
michael@0:         if (block->isMarked()) {
michael@0:             block->setId(--id);
michael@0:             for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd(); iter++)
michael@0:                 checkDependencyAndRemoveUsesFromUnmarkedBlocks(*iter);
michael@0:             for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++)
michael@0:                 checkDependencyAndRemoveUsesFromUnmarkedBlocks(*iter);
michael@0:         } else {
michael@0:             if (block->numPredecessors() > 1) {
michael@0:                 // If this block had phis, then any reachable
michael@0:                 // predecessors need to have the successorWithPhis
michael@0:                 // flag cleared.
michael@0:                 for (size_t i = 0; i < block->numPredecessors(); i++)
michael@0:                     block->getPredecessor(i)->setSuccessorWithPhis(nullptr, 0);
michael@0:             }
michael@0: 
michael@0:             if (block->isLoopBackedge()) {
michael@0:                 // NB. We have to update the loop header if we
michael@0:                 // eliminate the backedge. At first I thought this
michael@0:                 // check would be insufficient, because it would be
michael@0:                 // possible to have code like this:
michael@0:                 //
michael@0:                 //    while (true) {
michael@0:                 //       ...;
michael@0:                 //       if (1 == 1) break;
michael@0:                 //    }
michael@0:                 //
michael@0:                 // in which the backedge is removed as part of
michael@0:                 // rewriting the condition, but no actual blocks are
michael@0:                 // removed.  However, in all such cases, the backedge
michael@0:                 // would be a critical edge and hence the critical
michael@0:                 // edge block is being removed.
michael@0:                 block->loopHeaderOfBackedge()->clearLoopHeader();
michael@0:             }
michael@0: 
michael@0:             for (size_t i = 0, c = block->numSuccessors(); i < c; i++) {
michael@0:                 MBasicBlock *succ = block->getSuccessor(i);
michael@0:                 if (succ->isMarked()) {
michael@0:                     // succ is on the frontier of blocks to be removed:
michael@0:                     succ->removePredecessor(block);
michael@0: 
michael@0:                     if (!redundantPhis_) {
michael@0:                         for (MPhiIterator iter(succ->phisBegin()); iter != succ->phisEnd(); iter++) {
michael@0:                             if (iter->operandIfRedundant()) {
michael@0:                                 redundantPhis_ = true;
michael@0:                                 break;
michael@0:                             }
michael@0:                         }
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             graph_.removeBlock(block);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     JS_ASSERT(id == 0);
michael@0: 
michael@0:     return true;
michael@0: }