The Tor Browser / file revision

 /* -*- 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;

 }