diff options
Diffstat (limited to 'js/src/jit/ValueNumbering.cpp')
| -rw-r--r-- | js/src/jit/ValueNumbering.cpp | 1338 |
1 files changed, 1338 insertions, 0 deletions
diff --git a/js/src/jit/ValueNumbering.cpp b/js/src/jit/ValueNumbering.cpp new file mode 100644 index 0000000000..263fbce1a9 --- /dev/null +++ b/js/src/jit/ValueNumbering.cpp @@ -0,0 +1,1338 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * 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/ValueNumbering.h" + +#include "jit/IonAnalysis.h" +#include "jit/JitSpewer.h" +#include "jit/MIRGenerator.h" +#include "jit/MIRGraph.h" + +using namespace js; +using namespace js::jit; + +/* + * [SMDOC] IonMonkey Value Numbering + * + * Some notes on the main algorithm here: + * - The SSA identifier id() is the value number. We do replaceAllUsesWith as + * we go, so there's always at most one visible value with a given number. + * + * - Consequently, the GVN algorithm is effectively pessimistic. This means it + * is not as powerful as an optimistic GVN would be, but it is simpler and + * faster. + * + * - We iterate in RPO, so that when visiting a block, we've already optimized + * and hashed all values in dominating blocks. With occasional exceptions, + * this allows us to do everything in a single pass. + * + * - When we do use multiple passes, we just re-run the algorithm on the whole + * graph instead of doing sparse propagation. This is a tradeoff to keep the + * algorithm simpler and lighter on inputs that don't have a lot of + * interesting unreachable blocks or degenerate loop induction variables, at + * the expense of being slower on inputs that do. The loop for this always + * terminates, because it only iterates when code is or will be removed, so + * eventually it must stop iterating. + * + * - Values are not immediately removed from the hash set when they go out of + * scope. Instead, we check for dominance after a lookup. If the dominance + * check fails, the value is removed. + */ + +HashNumber ValueNumberer::VisibleValues::ValueHasher::hash(Lookup ins) { + return ins->valueHash(); +} + +// Test whether two MDefinitions are congruent. +bool ValueNumberer::VisibleValues::ValueHasher::match(Key k, Lookup l) { + // If one of the instructions depends on a store, and the other instruction + // does not depend on the same store, the instructions are not congruent. + if (k->dependency() != l->dependency()) { + return false; + } + + bool congruent = + k->congruentTo(l); // Ask the values themselves what they think. +#ifdef JS_JITSPEW + if (congruent != l->congruentTo(k)) { + JitSpew( + JitSpew_GVN, + " congruentTo relation is not symmetric between %s%u and %s%u!!", + k->opName(), k->id(), l->opName(), l->id()); + } +#endif + return congruent; +} + +void ValueNumberer::VisibleValues::ValueHasher::rekey(Key& k, Key newKey) { + k = newKey; +} + +ValueNumberer::VisibleValues::VisibleValues(TempAllocator& alloc) + : set_(alloc) {} + +// Look up the first entry for |def|. +ValueNumberer::VisibleValues::Ptr ValueNumberer::VisibleValues::findLeader( + const MDefinition* def) const { + return set_.lookup(def); +} + +// Look up the first entry for |def|. +ValueNumberer::VisibleValues::AddPtr +ValueNumberer::VisibleValues::findLeaderForAdd(MDefinition* def) { + return set_.lookupForAdd(def); +} + +// Insert a value into the set. +bool ValueNumberer::VisibleValues::add(AddPtr p, MDefinition* def) { + return set_.add(p, def); +} + +// Insert a value onto the set overwriting any existing entry. +void ValueNumberer::VisibleValues::overwrite(AddPtr p, MDefinition* def) { + set_.replaceKey(p, def); +} + +// |def| will be discarded, so remove it from any sets. +void ValueNumberer::VisibleValues::forget(const MDefinition* def) { + Ptr p = set_.lookup(def); + if (p && *p == def) { + set_.remove(p); + } +} + +// Clear all state. +void ValueNumberer::VisibleValues::clear() { set_.clear(); } + +#ifdef DEBUG +// Test whether |def| is in the set. +bool ValueNumberer::VisibleValues::has(const MDefinition* def) const { + Ptr p = set_.lookup(def); + return p && *p == def; +} +#endif + +// Call MDefinition::justReplaceAllUsesWith, and add some GVN-specific asserts. +static void ReplaceAllUsesWith(MDefinition* from, MDefinition* to) { + MOZ_ASSERT(from != to, "GVN shouldn't try to replace a value with itself"); + MOZ_ASSERT(from->type() == to->type(), "Def replacement has different type"); + MOZ_ASSERT(!to->isDiscarded(), + "GVN replaces an instruction by a removed instruction"); + + // We don't need the extra setting of ImplicitlyUsed flags that the regular + // replaceAllUsesWith does because we do it ourselves. + from->justReplaceAllUsesWith(to); +} + +// Test whether |succ| is a successor of |block|. +static bool HasSuccessor(const MControlInstruction* block, + const MBasicBlock* succ) { + for (size_t i = 0, e = block->numSuccessors(); i != e; ++i) { + if (block->getSuccessor(i) == succ) { + return true; + } + } + return false; +} + +// Given a block which has had predecessors removed but is still reachable, test +// whether the block's new dominator will be closer than its old one and whether +// it will expose potential optimization opportunities. +static MBasicBlock* ComputeNewDominator(MBasicBlock* block, MBasicBlock* old) { + MBasicBlock* now = block->getPredecessor(0); + for (size_t i = 1, e = block->numPredecessors(); i < e; ++i) { + MBasicBlock* pred = block->getPredecessor(i); + // Note that dominators haven't been recomputed yet, so we have to check + // whether now dominates pred, not block. + while (!now->dominates(pred)) { + MBasicBlock* next = now->immediateDominator(); + if (next == old) { + return old; + } + if (next == now) { + MOZ_ASSERT(block == old, + "Non-self-dominating block became self-dominating"); + return block; + } + now = next; + } + } + MOZ_ASSERT(old != block || old != now, + "Missed self-dominating block staying self-dominating"); + return now; +} + +// Test for any defs which look potentially interesting to GVN. +static bool BlockHasInterestingDefs(MBasicBlock* block) { + return !block->phisEmpty() || *block->begin() != block->lastIns(); +} + +// Walk up the dominator tree from |block| to the root and test for any defs +// which look potentially interesting to GVN. +static bool ScanDominatorsForDefs(MBasicBlock* block) { + for (MBasicBlock* i = block;;) { + if (BlockHasInterestingDefs(block)) { + return true; + } + + MBasicBlock* immediateDominator = i->immediateDominator(); + if (immediateDominator == i) { + break; + } + i = immediateDominator; + } + return false; +} + +// Walk up the dominator tree from |now| to |old| and test for any defs which +// look potentially interesting to GVN. +static bool ScanDominatorsForDefs(MBasicBlock* now, MBasicBlock* old) { + MOZ_ASSERT(old->dominates(now), + "Refined dominator not dominated by old dominator"); + + for (MBasicBlock* i = now; i != old; i = i->immediateDominator()) { + if (BlockHasInterestingDefs(i)) { + return true; + } + } + return false; +} + +// Given a block which has had predecessors removed but is still reachable, test +// whether the block's new dominator will be closer than its old one and whether +// it will expose potential optimization opportunities. +static bool IsDominatorRefined(MBasicBlock* block) { + MBasicBlock* old = block->immediateDominator(); + MBasicBlock* now = ComputeNewDominator(block, old); + + // If this block is just a goto and it doesn't dominate its destination, + // removing its predecessors won't refine the dominators of anything + // interesting. + MControlInstruction* control = block->lastIns(); + if (*block->begin() == control && block->phisEmpty() && control->isGoto() && + !block->dominates(control->toGoto()->target())) { + return false; + } + + // We've computed block's new dominator. Test whether there are any + // newly-dominating definitions which look interesting. + if (block == old) { + return block != now && ScanDominatorsForDefs(now); + } + MOZ_ASSERT(block != now, "Non-self-dominating block became self-dominating"); + return ScanDominatorsForDefs(now, old); +} + +// |def| has just had one of its users release it. If it's now dead, enqueue it +// for discarding, otherwise just make note of it. +bool ValueNumberer::handleUseReleased(MDefinition* def, + ImplicitUseOption implicitUseOption) { + if (IsDiscardable(def)) { + values_.forget(def); + if (!deadDefs_.append(def)) { + return false; + } + } else { + if (implicitUseOption == SetImplicitUse) { + def->setImplicitlyUsedUnchecked(); + } + } + return true; +} + +// Discard |def| and anything in its use-def subtree which is no longer needed. +bool ValueNumberer::discardDefsRecursively(MDefinition* def, + AllowEffectful allowEffectful) { + MOZ_ASSERT(deadDefs_.empty(), "deadDefs_ not cleared"); + + return discardDef(def, allowEffectful) && processDeadDefs(); +} + +// Assuming |resume| is unreachable, release its operands. +// It might be nice to integrate this code with prepareForDiscard, however GVN +// needs it to call handleUseReleased so that it can observe when a definition +// becomes unused, so it isn't trivial to do. +bool ValueNumberer::releaseResumePointOperands(MResumePoint* resume) { + for (size_t i = 0, e = resume->numOperands(); i < e; ++i) { + if (!resume->hasOperand(i)) { + continue; + } + MDefinition* op = resume->getOperand(i); + resume->releaseOperand(i); + + // We set the ImplicitlyUsed flag when removing resume point operands, + // because even though we may think we're certain that a particular + // branch might not be taken, the type information might be incomplete. + if (!handleUseReleased(op, SetImplicitUse)) { + return false; + } + } + return true; +} + +// Assuming |phi| is dead, release and remove its operands. If an operand +// becomes dead, push it to the discard worklist. +bool ValueNumberer::releaseAndRemovePhiOperands(MPhi* phi) { + // MPhi saves operands in a vector so we iterate in reverse. + for (int o = phi->numOperands() - 1; o >= 0; --o) { + MDefinition* op = phi->getOperand(o); + phi->removeOperand(o); + if (!handleUseReleased(op, DontSetImplicitUse)) { + return false; + } + } + return true; +} + +// Assuming |def| is dead, release its operands. If an operand becomes dead, +// push it to the discard worklist. +bool ValueNumberer::releaseOperands(MDefinition* def) { + for (size_t o = 0, e = def->numOperands(); o < e; ++o) { + MDefinition* op = def->getOperand(o); + def->releaseOperand(o); + if (!handleUseReleased(op, DontSetImplicitUse)) { + return false; + } + } + return true; +} + +// Discard |def| and mine its operands for any subsequently dead defs. +bool ValueNumberer::discardDef(MDefinition* def, + AllowEffectful allowEffectful) { +#ifdef JS_JITSPEW + JitSpew(JitSpew_GVN, " Discarding %s %s%u", + def->block()->isMarked() ? "unreachable" : "dead", def->opName(), + def->id()); +#endif +#ifdef DEBUG + MOZ_ASSERT(def != nextDef_, "Invalidating the MDefinition iterator"); + if (def->block()->isMarked()) { + MOZ_ASSERT(!def->hasUses(), "Discarding def that still has uses"); + } else { + MOZ_ASSERT(allowEffectful == AllowEffectful::Yes + ? IsDiscardableAllowEffectful(def) + : IsDiscardable(def), + "Discarding non-discardable definition"); + MOZ_ASSERT(!values_.has(def), "Discarding a definition still in the set"); + } +#endif + + MBasicBlock* block = def->block(); + if (def->isPhi()) { + MPhi* phi = def->toPhi(); + if (!releaseAndRemovePhiOperands(phi)) { + return false; + } + block->discardPhi(phi); + } else { + MInstruction* ins = def->toInstruction(); + if (MResumePoint* resume = ins->resumePoint()) { + if (!releaseResumePointOperands(resume)) { + return false; + } + } + if (!releaseOperands(ins)) { + return false; + } + block->discardIgnoreOperands(ins); + } + + // If that was the last definition in the block, it can be safely removed + // from the graph. + if (block->phisEmpty() && block->begin() == block->end()) { + MOZ_ASSERT(block->isMarked(), + "Reachable block lacks at least a control instruction"); + + // As a special case, don't remove a block which is a dominator tree + // root so that we don't invalidate the iterator in visitGraph. We'll + // check for this and remove it later. + if (block->immediateDominator() != block) { + JitSpew(JitSpew_GVN, " Block block%u is now empty; discarding", + block->id()); + graph_.removeBlock(block); + blocksRemoved_ = true; + } else { + JitSpew(JitSpew_GVN, + " Dominator root block%u is now empty; will discard later", + block->id()); + } + } + + return true; +} + +// Recursively discard all the defs on the deadDefs_ worklist. +bool ValueNumberer::processDeadDefs() { + MDefinition* nextDef = nextDef_; + while (!deadDefs_.empty()) { + MDefinition* def = deadDefs_.popCopy(); + + // Don't invalidate the MDefinition iterator. This is what we're going + // to visit next, so we won't miss anything. + if (def == nextDef) { + continue; + } + + if (!discardDef(def)) { + return false; + } + } + return true; +} + +// Test whether |block|, which is a loop header, has any predecessors other than +// |loopPred|, the loop predecessor, which it doesn't dominate. +static bool hasNonDominatingPredecessor(MBasicBlock* block, + MBasicBlock* loopPred) { + MOZ_ASSERT(block->isLoopHeader()); + MOZ_ASSERT(block->loopPredecessor() == loopPred); + + for (uint32_t i = 0, e = block->numPredecessors(); i < e; ++i) { + MBasicBlock* pred = block->getPredecessor(i); + if (pred != loopPred && !block->dominates(pred)) { + return true; + } + } + return false; +} + +// A loop is about to be made reachable only through an OSR entry into one of +// its nested loops. Fix everything up. +bool ValueNumberer::fixupOSROnlyLoop(MBasicBlock* block) { + // Create an empty and unreachable(!) block which jumps to |block|. This + // allows |block| to remain marked as a loop header, so we don't have to + // worry about moving a different block into place as the new loop header, + // which is hard, especially if the OSR is into a nested loop. Doing all + // that would produce slightly more optimal code, but this is so + // extraordinarily rare that it isn't worth the complexity. + MBasicBlock* fake = MBasicBlock::NewFakeLoopPredecessor(graph_, block); + if (!fake) { + return false; + } + fake->setImmediateDominator(fake); + fake->addNumDominated(1); + fake->setDomIndex(fake->id()); + + JitSpew(JitSpew_GVN, " Created fake block%u", fake->id()); + hasOSRFixups_ = true; + return true; +} + +// Remove the CFG edge between |pred| and |block|, after releasing the phi +// operands on that edge and discarding any definitions consequently made dead. +bool ValueNumberer::removePredecessorAndDoDCE(MBasicBlock* block, + MBasicBlock* pred, + size_t predIndex) { + MOZ_ASSERT( + !block->isMarked(), + "Block marked unreachable should have predecessors removed already"); + + // Before removing the predecessor edge, scan the phi operands for that edge + // for dead code before they get removed. + MOZ_ASSERT(nextDef_ == nullptr); + for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd()); + iter != end;) { + MPhi* phi = *iter++; + MOZ_ASSERT(!values_.has(phi), + "Visited phi in block having predecessor removed"); + MOZ_ASSERT(!phi->isGuard()); + + MDefinition* op = phi->getOperand(predIndex); + phi->removeOperand(predIndex); + + nextDef_ = iter != end ? *iter : nullptr; + if (!handleUseReleased(op, DontSetImplicitUse) || !processDeadDefs()) { + return false; + } + + // If |nextDef_| became dead while we had it pinned, advance the + // iterator and discard it now. + while (nextDef_ && !nextDef_->hasUses() && + !nextDef_->isGuardRangeBailouts()) { + phi = nextDef_->toPhi(); + iter++; + nextDef_ = iter != end ? *iter : nullptr; + if (!discardDefsRecursively(phi)) { + return false; + } + } + } + nextDef_ = nullptr; + + block->removePredecessorWithoutPhiOperands(pred, predIndex); + return true; +} + +// Remove the CFG edge between |pred| and |block|, and if this makes |block| +// unreachable, mark it so, and remove the rest of its incoming edges too. And +// discard any instructions made dead by the entailed release of any phi +// operands. +bool ValueNumberer::removePredecessorAndCleanUp(MBasicBlock* block, + MBasicBlock* pred) { + MOZ_ASSERT(!block->isMarked(), + "Removing predecessor on block already marked unreachable"); + + // We'll be removing a predecessor, so anything we know about phis in this + // block will be wrong. + for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd()); + iter != end; ++iter) { + values_.forget(*iter); + } + + // If this is a loop header, test whether it will become an unreachable + // loop, or whether it needs special OSR-related fixups. + bool isUnreachableLoop = false; + if (block->isLoopHeader()) { + if (block->loopPredecessor() == pred) { + if (MOZ_UNLIKELY(hasNonDominatingPredecessor(block, pred))) { + JitSpew(JitSpew_GVN, + " " + "Loop with header block%u is now only reachable through an " + "OSR entry into the middle of the loop!!", + block->id()); + } else { + // Deleting the entry into the loop makes the loop unreachable. + isUnreachableLoop = true; + JitSpew(JitSpew_GVN, + " " + "Loop with header block%u is no longer reachable", + block->id()); + } +#ifdef JS_JITSPEW + } else if (block->hasUniqueBackedge() && block->backedge() == pred) { + JitSpew(JitSpew_GVN, " Loop with header block%u is no longer a loop", + block->id()); +#endif + } + } + + // Actually remove the CFG edge. + if (!removePredecessorAndDoDCE(block, pred, + block->getPredecessorIndex(pred))) { + return false; + } + + // We've now edited the CFG; check to see if |block| became unreachable. + if (block->numPredecessors() == 0 || isUnreachableLoop) { + JitSpew(JitSpew_GVN, " Disconnecting block%u", block->id()); + + // Remove |block| from its dominator parent's subtree. This is the only + // immediately-dominated-block information we need to update, because + // everything dominated by this block is about to be swept away. + MBasicBlock* parent = block->immediateDominator(); + if (parent != block) { + parent->removeImmediatelyDominatedBlock(block); + } + + // Completely disconnect it from the CFG. We do this now rather than + // just doing it later when we arrive there in visitUnreachableBlock + // so that we don't leave a partially broken loop sitting around. This + // also lets visitUnreachableBlock assert that numPredecessors() == 0, + // which is a nice invariant. + if (block->isLoopHeader()) { + block->clearLoopHeader(); + } + for (size_t i = 0, e = block->numPredecessors(); i < e; ++i) { + if (!removePredecessorAndDoDCE(block, block->getPredecessor(i), i)) { + return false; + } + } + + // Clear out the resume point operands, as they can hold things that + // don't appear to dominate them live. + if (MResumePoint* resume = block->entryResumePoint()) { + if (!releaseResumePointOperands(resume) || !processDeadDefs()) { + return false; + } + if (MResumePoint* outer = block->outerResumePoint()) { + if (!releaseResumePointOperands(outer) || !processDeadDefs()) { + return false; + } + } + MOZ_ASSERT(nextDef_ == nullptr); + for (MInstructionIterator iter(block->begin()), end(block->end()); + iter != end;) { + MInstruction* ins = *iter++; + nextDef_ = iter != end ? *iter : nullptr; + if (MResumePoint* resume = ins->resumePoint()) { + if (!releaseResumePointOperands(resume) || !processDeadDefs()) { + return false; + } + } + } + nextDef_ = nullptr; + } else { +#ifdef DEBUG + MOZ_ASSERT(block->outerResumePoint() == nullptr, + "Outer resume point in block without an entry resume point"); + for (MInstructionIterator iter(block->begin()), end(block->end()); + iter != end; ++iter) { + MOZ_ASSERT(iter->resumePoint() == nullptr, + "Instruction with resume point in block without entry " + "resume point"); + } +#endif + } + + // Use the mark to note that we've already removed all its predecessors, + // and we know it's unreachable. + block->mark(); + } + + return true; +} + +// Return a simplified form of |def|, if we can. +MDefinition* ValueNumberer::simplified(MDefinition* def) const { + return def->foldsTo(graph_.alloc()); +} + +// If an equivalent and dominating value already exists in the set, return it. +// Otherwise insert |def| into the set and return it. +MDefinition* ValueNumberer::leader(MDefinition* def) { + // If the value isn't suitable for eliminating, don't bother hashing it. The + // convention is that congruentTo returns false for node kinds that wish to + // opt out of redundance elimination. + // TODO: It'd be nice to clean up that convention (bug 1031406). + if (!def->isEffectful() && def->congruentTo(def)) { + // Look for a match. + VisibleValues::AddPtr p = values_.findLeaderForAdd(def); + if (p) { + MDefinition* rep = *p; + if (!rep->isDiscarded() && rep->block()->dominates(def->block())) { + // We found a dominating congruent value. + return rep; + } + + // The congruent value doesn't dominate. It never will again in this + // dominator tree, so overwrite it. + values_.overwrite(p, def); + } else { + // No match. Add a new entry. + if (!values_.add(p, def)) { + return nullptr; + } + } + +#ifdef JS_JITSPEW + JitSpew(JitSpew_GVN, " Recording %s%u", def->opName(), def->id()); +#endif + } + + return def; +} + +// Test whether |phi| is dominated by a congruent phi. +bool ValueNumberer::hasLeader(const MPhi* phi, + const MBasicBlock* phiBlock) const { + if (VisibleValues::Ptr p = values_.findLeader(phi)) { + const MDefinition* rep = *p; + return rep != phi && rep->block()->dominates(phiBlock); + } + return false; +} + +// Test whether there are any phis in |header| which are newly optimizable, as a +// result of optimizations done inside the loop. This is not a sparse approach, +// but restarting is rare enough in practice. Termination is ensured by +// discarding the phi triggering the iteration. +bool ValueNumberer::loopHasOptimizablePhi(MBasicBlock* header) const { + // If the header is unreachable, don't bother re-optimizing it. + if (header->isMarked()) { + return false; + } + + // Rescan the phis for any that can be simplified, since they may be reading + // values from backedges. + for (MPhiIterator iter(header->phisBegin()), end(header->phisEnd()); + iter != end; ++iter) { + MPhi* phi = *iter; + MOZ_ASSERT_IF(!phi->hasUses(), !DeadIfUnused(phi)); + + if (phi->operandIfRedundant() || hasLeader(phi, header)) { + return true; // Phi can be simplified. + } + } + return false; +} + +// Visit |def|. +bool ValueNumberer::visitDefinition(MDefinition* def) { + // Nop does not fit in any of the previous optimization, as its only purpose + // is to reduce the register pressure by keeping additional resume + // point. Still, there is no need consecutive list of MNop instructions, and + // this will slow down every other iteration on the Graph. + if (def->isNop()) { + MNop* nop = def->toNop(); + MBasicBlock* block = nop->block(); + + // We look backward to know if we can remove the previous Nop, we do not + // look forward as we would not benefit from the folding made by GVN. + MInstructionReverseIterator iter = ++block->rbegin(nop); + + // This nop is at the beginning of the basic block, just replace the + // resume point of the basic block by the one from the resume point. + if (iter == block->rend()) { + JitSpew(JitSpew_GVN, " Removing Nop%u", nop->id()); + nop->moveResumePointAsEntry(); + block->discard(nop); + return true; + } + + // The previous instruction is also a Nop, no need to keep it anymore. + MInstruction* prev = *iter; + if (prev->isNop()) { + JitSpew(JitSpew_GVN, " Removing Nop%u", prev->id()); + block->discard(prev); + return true; + } + + // The Nop is introduced to capture the result and make sure the operands + // are not live anymore when there are no further uses. Though when + // all operands are still needed the Nop doesn't decrease the liveness + // and can get removed. + MResumePoint* rp = nop->resumePoint(); + if (rp && rp->numOperands() > 0 && + rp->getOperand(rp->numOperands() - 1) == prev && + !nop->block()->lastIns()->isThrow() && + !prev->isAssertRecoveredOnBailout()) { + size_t numOperandsLive = 0; + for (size_t j = 0; j < prev->numOperands(); j++) { + for (size_t i = 0; i < rp->numOperands(); i++) { + if (prev->getOperand(j) == rp->getOperand(i)) { + numOperandsLive++; + break; + } + } + } + + if (numOperandsLive == prev->numOperands()) { + JitSpew(JitSpew_GVN, " Removing Nop%u", nop->id()); + block->discard(nop); + } + } + + return true; + } + + // Skip optimizations on instructions which are recovered on bailout, to + // avoid mixing instructions which are recovered on bailouts with + // instructions which are not. + if (def->isRecoveredOnBailout()) { + return true; + } + + // If this instruction has a dependency() into an unreachable block, we'll + // need to update AliasAnalysis. + MDefinition* dep = def->dependency(); + if (dep != nullptr && (dep->isDiscarded() || dep->block()->isDead())) { + JitSpew(JitSpew_GVN, " AliasAnalysis invalidated"); + if (updateAliasAnalysis_ && !dependenciesBroken_) { + // TODO: Recomputing alias-analysis could theoretically expose more + // GVN opportunities. + JitSpew(JitSpew_GVN, " Will recompute!"); + dependenciesBroken_ = true; + } + // Temporarily clear its dependency, to protect foldsTo, which may + // wish to use the dependency to do store-to-load forwarding. + def->setDependency(def->toInstruction()); + } else { + dep = nullptr; + } + + // Look for a simplified form of |def|. + MDefinition* sim = simplified(def); + if (sim != def) { + if (sim == nullptr) { + return false; + } + + bool isNewInstruction = sim->block() == nullptr; + + // If |sim| doesn't belong to a block, insert it next to |def|. + if (isNewInstruction) { + // A new |sim| node mustn't be effectful when |def| wasn't effectful. + MOZ_ASSERT((def->isEffectful() && sim->isEffectful()) || + !sim->isEffectful()); + + // If both instructions are effectful, |sim| must have stolen the resume + // point of |def| when it's a new instruction. + MOZ_ASSERT_IF(def->isEffectful() && sim->isEffectful(), + !def->toInstruction()->resumePoint() && + sim->toInstruction()->resumePoint()); + + def->block()->insertAfter(def->toInstruction(), sim->toInstruction()); + } + +#ifdef JS_JITSPEW + JitSpew(JitSpew_GVN, " Folded %s%u to %s%u", def->opName(), def->id(), + sim->opName(), sim->id()); +#endif + MOZ_ASSERT(!sim->isDiscarded()); + ReplaceAllUsesWith(def, sim); + + // The node's foldsTo said |def| can be replaced by |rep|. If |def| is a + // guard, then either |rep| is also a guard, or a guard isn't actually + // needed, so we can clear |def|'s guard flag and let it be discarded. + def->setNotGuardUnchecked(); + + if (def->isGuardRangeBailouts()) { + sim->setGuardRangeBailoutsUnchecked(); + } + + if (sim->bailoutKind() == BailoutKind::Unknown) { + sim->setBailoutKind(def->bailoutKind()); + } + + // Discard |def| if it's now unused. Similar to guards, we allow to replace + // effectful instructions when the node's foldsTo method said |def| can be + // replaced. + if (DeadIfUnusedAllowEffectful(def)) { + if (!discardDefsRecursively(def, AllowEffectful::Yes)) { + return false; + } + + // If that ended up discarding |sim|, then we're done here. + if (sim->isDiscarded()) { + return true; + } + } + + if (!rerun_ && def->isPhi() && !sim->isPhi()) { + rerun_ = true; + JitSpew(JitSpew_GVN, + " Replacing phi%u may have enabled cascading optimisations; " + "will re-run", + def->id()); + } + + // Otherwise, procede to optimize with |sim| in place of |def|. + def = sim; + + // If the simplified instruction was already part of the graph, then we + // probably already visited and optimized this instruction. + if (!isNewInstruction) { + return true; + } + } + + // Now that foldsTo is done, re-enable the original dependency. Even though + // it may be pointing into a discarded block, it's still valid for the + // purposes of detecting congruent loads. + if (dep != nullptr) { + def->setDependency(dep); + } + + // Look for a dominating def which makes |def| redundant. + MDefinition* rep = leader(def); + if (rep != def) { + if (rep == nullptr) { + return false; + } + + if (rep->isPhi()) { + MOZ_ASSERT(def->isPhi()); + rep->toPhi()->updateForReplacement(def->toPhi()); + } + +#ifdef JS_JITSPEW + JitSpew(JitSpew_GVN, " Replacing %s%u with %s%u", def->opName(), + def->id(), rep->opName(), rep->id()); +#endif + ReplaceAllUsesWith(def, rep); + + // The node's congruentTo said |def| is congruent to |rep|, and it's + // dominated by |rep|. If |def| is a guard, it's covered by |rep|, + // so we can clear |def|'s guard flag and let it be discarded. + def->setNotGuardUnchecked(); + + if (DeadIfUnused(def)) { + // discardDef should not add anything to the deadDefs, as the + // redundant operation should have the same input operands. + mozilla::DebugOnly<bool> r = discardDef(def); + MOZ_ASSERT( + r, + "discardDef shouldn't have tried to add anything to the worklist, " + "so it shouldn't have failed"); + MOZ_ASSERT(deadDefs_.empty(), + "discardDef shouldn't have added anything to the worklist"); + } + } + + return true; +} + +// Visit the control instruction at the end of |block|. +bool ValueNumberer::visitControlInstruction(MBasicBlock* block) { + // Look for a simplified form of the control instruction. + MControlInstruction* control = block->lastIns(); + MDefinition* rep = simplified(control); + if (rep == control) { + return true; + } + + if (rep == nullptr) { + return false; + } + + MControlInstruction* newControl = rep->toControlInstruction(); + MOZ_ASSERT(!newControl->block(), + "Control instruction replacement shouldn't already be in a block"); +#ifdef JS_JITSPEW + JitSpew(JitSpew_GVN, " Folded control instruction %s%u to %s%u", + control->opName(), control->id(), newControl->opName(), + graph_.getNumInstructionIds()); +#endif + + // If the simplification removes any CFG edges, update the CFG and remove + // any blocks that become dead. + size_t oldNumSuccs = control->numSuccessors(); + size_t newNumSuccs = newControl->numSuccessors(); + if (newNumSuccs != oldNumSuccs) { + MOZ_ASSERT(newNumSuccs < oldNumSuccs, + "New control instruction has too many successors"); + for (size_t i = 0; i != oldNumSuccs; ++i) { + MBasicBlock* succ = control->getSuccessor(i); + if (HasSuccessor(newControl, succ)) { + continue; + } + if (succ->isMarked()) { + continue; + } + if (!removePredecessorAndCleanUp(succ, block)) { + return false; + } + if (succ->isMarked()) { + continue; + } + if (!rerun_) { + if (!remainingBlocks_.append(succ)) { + return false; + } + } + } + } + + if (!releaseOperands(control)) { + return false; + } + block->discardIgnoreOperands(control); + block->end(newControl); + if (block->entryResumePoint() && newNumSuccs != oldNumSuccs) { + block->flagOperandsOfPrunedBranches(newControl); + } + return processDeadDefs(); +} + +// |block| is unreachable. Mine it for opportunities to delete more dead +// code, and then discard it. +bool ValueNumberer::visitUnreachableBlock(MBasicBlock* block) { + JitSpew(JitSpew_GVN, " Visiting unreachable block%u%s%s%s", block->id(), + block->isLoopHeader() ? " (loop header)" : "", + block->isSplitEdge() ? " (split edge)" : "", + block->immediateDominator() == block ? " (dominator root)" : ""); + + MOZ_ASSERT(block->isMarked(), + "Visiting unmarked (and therefore reachable?) block"); + MOZ_ASSERT(block->numPredecessors() == 0, + "Block marked unreachable still has predecessors"); + MOZ_ASSERT(block != graph_.entryBlock(), "Removing normal entry block"); + MOZ_ASSERT(block != graph_.osrBlock(), "Removing OSR entry block"); + MOZ_ASSERT(deadDefs_.empty(), "deadDefs_ not cleared"); + + // Disconnect all outgoing CFG edges. + for (size_t i = 0, e = block->numSuccessors(); i < e; ++i) { + MBasicBlock* succ = block->getSuccessor(i); + if (succ->isDead() || succ->isMarked()) { + continue; + } + if (!removePredecessorAndCleanUp(succ, block)) { + return false; + } + if (succ->isMarked()) { + continue; + } + // |succ| is still reachable. Make a note of it so that we can scan + // it for interesting dominator tree changes later. + if (!rerun_) { + if (!remainingBlocks_.append(succ)) { + return false; + } + } + } + + // Discard any instructions with no uses. The remaining instructions will be + // discarded when their last use is discarded. + MOZ_ASSERT(nextDef_ == nullptr); + for (MDefinitionIterator iter(block); iter;) { + MDefinition* def = *iter++; + if (def->hasUses()) { + continue; + } + nextDef_ = iter ? *iter : nullptr; + if (!discardDefsRecursively(def)) { + return false; + } + } + + nextDef_ = nullptr; + MControlInstruction* control = block->lastIns(); + return discardDefsRecursively(control); +} + +// Visit all the phis and instructions |block|. +bool ValueNumberer::visitBlock(MBasicBlock* block) { + MOZ_ASSERT(!block->isMarked(), "Blocks marked unreachable during GVN"); + MOZ_ASSERT(!block->isDead(), "Block to visit is already dead"); + + JitSpew(JitSpew_GVN, " Visiting block%u", block->id()); + + // Visit the definitions in the block top-down. + MOZ_ASSERT(nextDef_ == nullptr); + for (MDefinitionIterator iter(block); iter;) { + if (!graph_.alloc().ensureBallast()) { + return false; + } + MDefinition* def = *iter++; + + // Remember where our iterator is so that we don't invalidate it. + nextDef_ = iter ? *iter : nullptr; + + // If the definition is dead, discard it. + if (IsDiscardable(def)) { + if (!discardDefsRecursively(def)) { + return false; + } + continue; + } + + if (!visitDefinition(def)) { + return false; + } + } + nextDef_ = nullptr; + + if (!graph_.alloc().ensureBallast()) { + return false; + } + + return visitControlInstruction(block); +} + +// Visit all the blocks dominated by dominatorRoot. +bool ValueNumberer::visitDominatorTree(MBasicBlock* dominatorRoot) { + JitSpew(JitSpew_GVN, + " Visiting dominator tree (with %" PRIu64 + " blocks) rooted at block%u%s", + uint64_t(dominatorRoot->numDominated()), dominatorRoot->id(), + dominatorRoot == graph_.entryBlock() ? " (normal entry block)" + : dominatorRoot == graph_.osrBlock() ? " (OSR entry block)" + : dominatorRoot->numPredecessors() == 0 + ? " (odd unreachable block)" + : " (merge point from normal entry and OSR entry)"); + MOZ_ASSERT(dominatorRoot->immediateDominator() == dominatorRoot, + "root is not a dominator tree root"); + + // Visit all blocks dominated by dominatorRoot, in RPO. This has the nice + // property that we'll always visit a block before any block it dominates, + // so we can make a single pass through the list and see every full + // redundance. + size_t numVisited = 0; + size_t numDiscarded = 0; + for (ReversePostorderIterator iter(graph_.rpoBegin(dominatorRoot));;) { + MOZ_ASSERT(iter != graph_.rpoEnd(), "Inconsistent dominator information"); + MBasicBlock* block = *iter++; + // We're only visiting blocks in dominatorRoot's tree right now. + if (!dominatorRoot->dominates(block)) { + continue; + } + + // If this is a loop backedge, remember the header, as we may not be able + // to find it after we simplify the block. + MBasicBlock* header = + block->isLoopBackedge() ? block->loopHeaderOfBackedge() : nullptr; + + if (block->isMarked()) { + // This block has become unreachable; handle it specially. + if (!visitUnreachableBlock(block)) { + return false; + } + ++numDiscarded; + } else { + // Visit the block! + if (!visitBlock(block)) { + return false; + } + ++numVisited; + } + + // If the block is/was a loop backedge, check to see if the block that + // is/was its header has optimizable phis, which would want a re-run. + if (!rerun_ && header && loopHasOptimizablePhi(header)) { + JitSpew(JitSpew_GVN, + " Loop phi in block%u can now be optimized; will re-run GVN!", + header->id()); + rerun_ = true; + remainingBlocks_.clear(); + } + + MOZ_ASSERT(numVisited <= dominatorRoot->numDominated() - numDiscarded, + "Visited blocks too many times"); + if (numVisited >= dominatorRoot->numDominated() - numDiscarded) { + break; + } + } + + totalNumVisited_ += numVisited; + values_.clear(); + return true; +} + +// Visit all the blocks in the graph. +bool ValueNumberer::visitGraph() { + // Due to OSR blocks, the set of blocks dominated by a blocks may not be + // contiguous in the RPO. Do a separate traversal for each dominator tree + // root. There's always the main entry, and sometimes there's an OSR entry, + // and then there are the roots formed where the OSR paths merge with the + // main entry paths. + for (ReversePostorderIterator iter(graph_.rpoBegin());;) { + MOZ_ASSERT(iter != graph_.rpoEnd(), "Inconsistent dominator information"); + MBasicBlock* block = *iter; + if (block->immediateDominator() == block) { + if (!visitDominatorTree(block)) { + return false; + } + + // Normally unreachable blocks would be removed by now, but if this + // block is a dominator tree root, it has been special-cased and left + // in place in order to avoid invalidating our iterator. Now that + // we've finished the tree, increment the iterator, and then if it's + // marked for removal, remove it. + ++iter; + if (block->isMarked()) { + JitSpew(JitSpew_GVN, " Discarding dominator root block%u", + block->id()); + MOZ_ASSERT( + block->begin() == block->end(), + "Unreachable dominator tree root has instructions after tree walk"); + MOZ_ASSERT(block->phisEmpty(), + "Unreachable dominator tree root has phis after tree walk"); + graph_.removeBlock(block); + blocksRemoved_ = true; + } + + MOZ_ASSERT(totalNumVisited_ <= graph_.numBlocks(), + "Visited blocks too many times"); + if (totalNumVisited_ >= graph_.numBlocks()) { + break; + } + } else { + // This block a dominator tree root. Proceed to the next one. + ++iter; + } + } + totalNumVisited_ = 0; + return true; +} + +bool ValueNumberer::insertOSRFixups() { + ReversePostorderIterator end(graph_.end()); + for (ReversePostorderIterator iter(graph_.begin()); iter != end;) { + MBasicBlock* block = *iter++; + + // Only add fixup block above for loops which can be reached from OSR. + if (!block->isLoopHeader()) { + continue; + } + + // If the loop header is not self-dominated, then this loop does not + // have to deal with a second entry point, so there is no need to add a + // second entry point with a fixup block. + if (block->immediateDominator() != block) { + continue; + } + + if (!fixupOSROnlyLoop(block)) { + return false; + } + } + + return true; +} + +// OSR fixups serve the purpose of representing the non-OSR entry into a loop +// when the only real entry is an OSR entry into the middle. However, if the +// entry into the middle is subsequently folded away, the loop may actually +// have become unreachable. Mark-and-sweep all blocks to remove all such code. +bool ValueNumberer::cleanupOSRFixups() { + // Mark. + Vector<MBasicBlock*, 0, JitAllocPolicy> worklist(graph_.alloc()); + unsigned numMarked = 2; + graph_.entryBlock()->mark(); + graph_.osrBlock()->mark(); + if (!worklist.append(graph_.entryBlock()) || + !worklist.append(graph_.osrBlock())) { + return false; + } + while (!worklist.empty()) { + MBasicBlock* block = worklist.popCopy(); + for (size_t i = 0, e = block->numSuccessors(); i != e; ++i) { + MBasicBlock* succ = block->getSuccessor(i); + if (!succ->isMarked()) { + ++numMarked; + succ->mark(); + if (!worklist.append(succ)) { + return false; + } + } else if (succ->isLoopHeader() && succ->loopPredecessor() == block && + succ->numPredecessors() == 3) { + // Unmark fixup blocks if the loop predecessor is marked after + // the loop header. + succ->getPredecessor(1)->unmarkUnchecked(); + } + } + + // OSR fixup blocks are needed if and only if the loop header is + // reachable from its backedge (via the OSR block) and not from its + // original loop predecessor. + // + // Thus OSR fixup blocks are removed if the loop header is not + // reachable, or if the loop header is reachable from both its backedge + // and its original loop predecessor. + if (block->isLoopHeader()) { + MBasicBlock* maybeFixupBlock = nullptr; + if (block->numPredecessors() == 2) { + maybeFixupBlock = block->getPredecessor(0); + } else { + MOZ_ASSERT(block->numPredecessors() == 3); + if (!block->loopPredecessor()->isMarked()) { + maybeFixupBlock = block->getPredecessor(1); + } + } + + if (maybeFixupBlock && !maybeFixupBlock->isMarked() && + maybeFixupBlock->numPredecessors() == 0) { + MOZ_ASSERT(maybeFixupBlock->numSuccessors() == 1, + "OSR fixup block should have exactly one successor"); + MOZ_ASSERT(maybeFixupBlock != graph_.entryBlock(), + "OSR fixup block shouldn't be the entry block"); + MOZ_ASSERT(maybeFixupBlock != graph_.osrBlock(), + "OSR fixup block shouldn't be the OSR entry block"); + maybeFixupBlock->mark(); + } + } + } + + // And sweep. + return RemoveUnmarkedBlocks(mir_, graph_, numMarked); +} + +ValueNumberer::ValueNumberer(MIRGenerator* mir, MIRGraph& graph) + : mir_(mir), + graph_(graph), + // Initialize the value set. It's tempting to pass in a length that is a + // function of graph_.getNumInstructionIds(). But if we start out with a + // large capacity, it will be far larger than the actual element count for + // most of the pass, so when we remove elements, it would often think it + // needs to compact itself. Empirically, just letting the HashTable grow + // as needed on its own seems to work pretty well. + values_(graph.alloc()), + deadDefs_(graph.alloc()), + remainingBlocks_(graph.alloc()), + nextDef_(nullptr), + totalNumVisited_(0), + rerun_(false), + blocksRemoved_(false), + updateAliasAnalysis_(false), + dependenciesBroken_(false), + hasOSRFixups_(false) {} + +bool ValueNumberer::run(UpdateAliasAnalysisFlag updateAliasAnalysis) { + updateAliasAnalysis_ = updateAliasAnalysis == UpdateAliasAnalysis; + + JitSpew(JitSpew_GVN, "Running GVN on graph (with %" PRIu64 " blocks)", + uint64_t(graph_.numBlocks())); + + // Adding fixup blocks only make sense iff we have a second entry point into + // the graph which cannot be reached any more from the entry point. + if (graph_.osrBlock()) { + if (!insertOSRFixups()) { + return false; + } + } + + // Top level non-sparse iteration loop. If an iteration performs a + // significant change, such as discarding a block which changes the + // dominator tree and may enable more optimization, this loop takes another + // iteration. + int runs = 0; + for (;;) { + if (!visitGraph()) { + return false; + } + + // Test whether any block which was not removed but which had at least + // one predecessor removed will have a new dominator parent. + while (!remainingBlocks_.empty()) { + MBasicBlock* block = remainingBlocks_.popCopy(); + if (!block->isDead() && IsDominatorRefined(block)) { + JitSpew(JitSpew_GVN, + " Dominator for block%u can now be refined; will re-run GVN!", + block->id()); + rerun_ = true; + remainingBlocks_.clear(); + break; + } + } + + if (blocksRemoved_) { + if (!AccountForCFGChanges(mir_, graph_, dependenciesBroken_, + /* underValueNumberer = */ true)) { + return false; + } + + blocksRemoved_ = false; + dependenciesBroken_ = false; + } + + if (mir_->shouldCancel("GVN (outer loop)")) { + return false; + } + + // If no further opportunities have been discovered, we're done. + if (!rerun_) { + break; + } + + rerun_ = false; + + // Enforce an arbitrary iteration limit. This is rarely reached, and + // isn't even strictly necessary, as the algorithm is guaranteed to + // terminate on its own in a finite amount of time (since every time we + // re-run we discard the construct which triggered the re-run), but it + // does help avoid slow compile times on pathological code. + ++runs; + if (runs == 6) { + JitSpew(JitSpew_GVN, "Re-run cutoff of %d reached. Terminating GVN!", + runs); + break; + } + + JitSpew(JitSpew_GVN, + "Re-running GVN on graph (run %d, now with %" PRIu64 " blocks)", + runs, uint64_t(graph_.numBlocks())); + } + + if (MOZ_UNLIKELY(hasOSRFixups_)) { + if (!cleanupOSRFixups()) { + return false; + } + hasOSRFixups_ = false; + } + + return true; +} |