1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/UnreachableCodeElimination.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,298 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "jit/UnreachableCodeElimination.h"
1.11 +
1.12 +#include "jit/AliasAnalysis.h"
1.13 +#include "jit/IonAnalysis.h"
1.14 +#include "jit/MIRGenerator.h"
1.15 +#include "jit/ValueNumbering.h"
1.16 +
1.17 +using namespace js;
1.18 +using namespace jit;
1.19 +
1.20 +bool
1.21 +UnreachableCodeElimination::analyze()
1.22 +{
1.23 + // The goal of this routine is to eliminate code that is
1.24 + // unreachable, either because there is no path from the entry
1.25 + // block to the code, or because the path traverses a conditional
1.26 + // branch where the condition is a constant (e.g., "if (false) {
1.27 + // ... }"). The latter can either appear in the source form or
1.28 + // arise due to optimizations.
1.29 + //
1.30 + // The stategy is straightforward. The pass begins with a
1.31 + // depth-first search. We set a bit on each basic block that
1.32 + // is visited. If a block terminates in a conditional branch
1.33 + // predicated on a constant, we rewrite the block to an unconditional
1.34 + // jump and do not visit the now irrelevant basic block.
1.35 + //
1.36 + // Once the initial DFS is complete, we do a second pass over the
1.37 + // blocks to find those that were not reached. Those blocks are
1.38 + // simply removed wholesale. We must also correct any phis that
1.39 + // may be affected..
1.40 +
1.41 + // Pass 1: Identify unreachable blocks (if any).
1.42 + if (!prunePointlessBranchesAndMarkReachableBlocks())
1.43 + return false;
1.44 +
1.45 + return removeUnmarkedBlocksAndCleanup();
1.46 +}
1.47 +
1.48 +bool
1.49 +UnreachableCodeElimination::removeUnmarkedBlocks(size_t marked)
1.50 +{
1.51 + marked_ = marked;
1.52 + return removeUnmarkedBlocksAndCleanup();
1.53 +}
1.54 +
1.55 +bool
1.56 +UnreachableCodeElimination::removeUnmarkedBlocksAndCleanup()
1.57 +{
1.58 + // Everything is reachable, no work required.
1.59 + JS_ASSERT(marked_ <= graph_.numBlocks());
1.60 + if (marked_ == graph_.numBlocks()) {
1.61 + graph_.unmarkBlocks();
1.62 + return true;
1.63 + }
1.64 +
1.65 + // Pass 2: Remove unmarked blocks (see analyze() above).
1.66 + if (!removeUnmarkedBlocksAndClearDominators())
1.67 + return false;
1.68 + graph_.unmarkBlocks();
1.69 +
1.70 + AssertGraphCoherency(graph_);
1.71 +
1.72 + IonSpewPass("UCE-mid-point");
1.73 +
1.74 + // Pass 3: Recompute dominators and tweak phis.
1.75 + BuildDominatorTree(graph_);
1.76 + if (redundantPhis_ && !EliminatePhis(mir_, graph_, ConservativeObservability))
1.77 + return false;
1.78 +
1.79 + // Pass 4: Rerun alias analysis
1.80 + if (rerunAliasAnalysis_) {
1.81 + AliasAnalysis analysis(mir_, graph_);
1.82 + if (!analysis.analyze())
1.83 + return false;
1.84 + }
1.85 +
1.86 + // Pass 5: It's important for optimizations to re-run GVN (and in
1.87 + // turn alias analysis) after UCE if we eliminated branches.
1.88 + if (rerunAliasAnalysis_ && mir_->optimizationInfo().gvnEnabled()) {
1.89 + ValueNumberer gvn(mir_, graph_, mir_->optimizationInfo().gvnKind() == GVN_Optimistic);
1.90 + if (!gvn.clear() || !gvn.analyze())
1.91 + return false;
1.92 + IonSpewPass("GVN-after-UCE");
1.93 + AssertExtendedGraphCoherency(graph_);
1.94 +
1.95 + if (mir_->shouldCancel("GVN-after-UCE"))
1.96 + return false;
1.97 + }
1.98 +
1.99 + return true;
1.100 +}
1.101 +
1.102 +bool
1.103 +UnreachableCodeElimination::enqueue(MBasicBlock *block, BlockList &list)
1.104 +{
1.105 + if (block->isMarked())
1.106 + return true;
1.107 +
1.108 + block->mark();
1.109 + marked_++;
1.110 + return list.append(block);
1.111 +}
1.112 +
1.113 +MBasicBlock *
1.114 +UnreachableCodeElimination::optimizableSuccessor(MBasicBlock *block)
1.115 +{
1.116 + // If the last instruction in `block` is a test instruction of a
1.117 + // constant value, returns the successor that the branch will
1.118 + // always branch to at runtime. Otherwise, returns nullptr.
1.119 +
1.120 + MControlInstruction *ins = block->lastIns();
1.121 + if (!ins->isTest())
1.122 + return nullptr;
1.123 +
1.124 + MTest *testIns = ins->toTest();
1.125 + MDefinition *v = testIns->getOperand(0);
1.126 + if (!v->isConstant())
1.127 + return nullptr;
1.128 +
1.129 + BranchDirection bdir = v->toConstant()->valueToBoolean() ? TRUE_BRANCH : FALSE_BRANCH;
1.130 + return testIns->branchSuccessor(bdir);
1.131 +}
1.132 +
1.133 +bool
1.134 +UnreachableCodeElimination::prunePointlessBranchesAndMarkReachableBlocks()
1.135 +{
1.136 + BlockList worklist, optimizableBlocks;
1.137 +
1.138 + // Process everything reachable from the start block, ignoring any
1.139 + // OSR block.
1.140 + if (!enqueue(graph_.entryBlock(), worklist))
1.141 + return false;
1.142 + while (!worklist.empty()) {
1.143 + if (mir_->shouldCancel("Eliminate Unreachable Code"))
1.144 + return false;
1.145 +
1.146 + MBasicBlock *block = worklist.popCopy();
1.147 +
1.148 + // If this block is a test on a constant operand, only enqueue
1.149 + // the relevant successor. Also, remember the block for later.
1.150 + if (MBasicBlock *succ = optimizableSuccessor(block)) {
1.151 + if (!optimizableBlocks.append(block))
1.152 + return false;
1.153 + if (!enqueue(succ, worklist))
1.154 + return false;
1.155 + } else {
1.156 + // Otherwise just visit all successors.
1.157 + for (size_t i = 0; i < block->numSuccessors(); i++) {
1.158 + MBasicBlock *succ = block->getSuccessor(i);
1.159 + if (!enqueue(succ, worklist))
1.160 + return false;
1.161 + }
1.162 + }
1.163 + }
1.164 +
1.165 + // Now, if there is an OSR block, check that all of its successors
1.166 + // were reachable (bug 880377). If not, we are in danger of
1.167 + // creating a CFG with two disjoint parts, so simply mark all
1.168 + // blocks as reachable. This generally occurs when the TI info for
1.169 + // stack types is incorrect or incomplete, due to operations that
1.170 + // have not yet executed in baseline.
1.171 + if (graph_.osrBlock()) {
1.172 + MBasicBlock *osrBlock = graph_.osrBlock();
1.173 + JS_ASSERT(!osrBlock->isMarked());
1.174 + if (!enqueue(osrBlock, worklist))
1.175 + return false;
1.176 + for (size_t i = 0; i < osrBlock->numSuccessors(); i++) {
1.177 + if (!osrBlock->getSuccessor(i)->isMarked()) {
1.178 + // OSR block has an otherwise unreachable successor, abort.
1.179 + for (MBasicBlockIterator iter(graph_.begin()); iter != graph_.end(); iter++)
1.180 + iter->mark();
1.181 + marked_ = graph_.numBlocks();
1.182 + return true;
1.183 + }
1.184 + }
1.185 + }
1.186 +
1.187 + // Now that we know we will not abort due to OSR, go back and
1.188 + // transform any tests on constant operands into gotos.
1.189 + for (uint32_t i = 0; i < optimizableBlocks.length(); i++) {
1.190 + MBasicBlock *block = optimizableBlocks[i];
1.191 + MBasicBlock *succ = optimizableSuccessor(block);
1.192 + JS_ASSERT(succ);
1.193 +
1.194 + MGoto *gotoIns = MGoto::New(graph_.alloc(), succ);
1.195 + block->discardLastIns();
1.196 + block->end(gotoIns);
1.197 + MBasicBlock *successorWithPhis = block->successorWithPhis();
1.198 + if (successorWithPhis && successorWithPhis != succ)
1.199 + block->setSuccessorWithPhis(nullptr, 0);
1.200 + }
1.201 +
1.202 + return true;
1.203 +}
1.204 +
1.205 +void
1.206 +UnreachableCodeElimination::checkDependencyAndRemoveUsesFromUnmarkedBlocks(MDefinition *instr)
1.207 +{
1.208 + // When the instruction depends on removed block,
1.209 + // alias analysis needs to get rerun to have the right dependency.
1.210 + if (!disableAliasAnalysis_ && instr->dependency() && !instr->dependency()->block()->isMarked())
1.211 + rerunAliasAnalysis_ = true;
1.212 +
1.213 + for (MUseIterator iter(instr->usesBegin()); iter != instr->usesEnd(); ) {
1.214 + if (!iter->consumer()->block()->isMarked()) {
1.215 + instr->setUseRemovedUnchecked();
1.216 + iter = instr->removeUse(iter);
1.217 + } else {
1.218 + iter++;
1.219 + }
1.220 + }
1.221 +}
1.222 +
1.223 +bool
1.224 +UnreachableCodeElimination::removeUnmarkedBlocksAndClearDominators()
1.225 +{
1.226 + // Removes blocks that are not marked from the graph. For blocks
1.227 + // that *are* marked, clears the mark and adjusts the id to its
1.228 + // new value. Also adds blocks that are immediately reachable
1.229 + // from an unmarked block to the frontier.
1.230 +
1.231 + size_t id = marked_;
1.232 + for (PostorderIterator iter(graph_.poBegin()); iter != graph_.poEnd();) {
1.233 + if (mir_->shouldCancel("Eliminate Unreachable Code"))
1.234 + return false;
1.235 +
1.236 + MBasicBlock *block = *iter;
1.237 + iter++;
1.238 +
1.239 + // Unconditionally clear the dominators. It's somewhat complex to
1.240 + // adjust the values and relatively fast to just recompute.
1.241 + block->clearDominatorInfo();
1.242 +
1.243 + if (block->isMarked()) {
1.244 + block->setId(--id);
1.245 + for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd(); iter++)
1.246 + checkDependencyAndRemoveUsesFromUnmarkedBlocks(*iter);
1.247 + for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++)
1.248 + checkDependencyAndRemoveUsesFromUnmarkedBlocks(*iter);
1.249 + } else {
1.250 + if (block->numPredecessors() > 1) {
1.251 + // If this block had phis, then any reachable
1.252 + // predecessors need to have the successorWithPhis
1.253 + // flag cleared.
1.254 + for (size_t i = 0; i < block->numPredecessors(); i++)
1.255 + block->getPredecessor(i)->setSuccessorWithPhis(nullptr, 0);
1.256 + }
1.257 +
1.258 + if (block->isLoopBackedge()) {
1.259 + // NB. We have to update the loop header if we
1.260 + // eliminate the backedge. At first I thought this
1.261 + // check would be insufficient, because it would be
1.262 + // possible to have code like this:
1.263 + //
1.264 + // while (true) {
1.265 + // ...;
1.266 + // if (1 == 1) break;
1.267 + // }
1.268 + //
1.269 + // in which the backedge is removed as part of
1.270 + // rewriting the condition, but no actual blocks are
1.271 + // removed. However, in all such cases, the backedge
1.272 + // would be a critical edge and hence the critical
1.273 + // edge block is being removed.
1.274 + block->loopHeaderOfBackedge()->clearLoopHeader();
1.275 + }
1.276 +
1.277 + for (size_t i = 0, c = block->numSuccessors(); i < c; i++) {
1.278 + MBasicBlock *succ = block->getSuccessor(i);
1.279 + if (succ->isMarked()) {
1.280 + // succ is on the frontier of blocks to be removed:
1.281 + succ->removePredecessor(block);
1.282 +
1.283 + if (!redundantPhis_) {
1.284 + for (MPhiIterator iter(succ->phisBegin()); iter != succ->phisEnd(); iter++) {
1.285 + if (iter->operandIfRedundant()) {
1.286 + redundantPhis_ = true;
1.287 + break;
1.288 + }
1.289 + }
1.290 + }
1.291 + }
1.292 + }
1.293 +
1.294 + graph_.removeBlock(block);
1.295 + }
1.296 + }
1.297 +
1.298 + JS_ASSERT(id == 0);
1.299 +
1.300 + return true;
1.301 +}
