1306 lines
47 KiB
C++
1306 lines
47 KiB
C++
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
|
|
* 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/AliasAnalysis.h"
|
|
#include "jit/IonAnalysis.h"
|
|
#include "jit/JitSpewer.h"
|
|
#include "jit/MIRGenerator.h"
|
|
|
|
using namespace js;
|
|
using namespace js::jit;
|
|
|
|
/*
|
|
* 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)
|
|
{}
|
|
|
|
// Initialize the set.
|
|
bool
|
|
ValueNumberer::VisibleValues::init()
|
|
{
|
|
return set_.init();
|
|
}
|
|
|
|
// 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 UseRemoved 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, UseRemovedOption useRemovedOption)
|
|
{
|
|
if (IsDiscardable(def)) {
|
|
values_.forget(def);
|
|
if (!deadDefs_.append(def))
|
|
return false;
|
|
} else {
|
|
if (useRemovedOption == SetUseRemoved)
|
|
def->setUseRemovedUnchecked();
|
|
}
|
|
return true;
|
|
}
|
|
|
|
// Discard |def| and anything in its use-def subtree which is no longer needed.
|
|
bool
|
|
ValueNumberer::discardDefsRecursively(MDefinition* def)
|
|
{
|
|
MOZ_ASSERT(deadDefs_.empty(), "deadDefs_ not cleared");
|
|
|
|
return discardDef(def) && 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 UseRemoved 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, SetUseRemoved))
|
|
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, DontSetUseRemoved))
|
|
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, DontSetUseRemoved))
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
// Discard |def| and mine its operands for any subsequently dead defs.
|
|
bool
|
|
ValueNumberer::discardDef(MDefinition* def)
|
|
{
|
|
#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(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, MBasicBlock* backedge)
|
|
{
|
|
// 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::New(graph_, block->info(), nullptr, MBasicBlock::NORMAL);
|
|
if (fake == nullptr)
|
|
return false;
|
|
|
|
graph_.insertBlockBefore(block, fake);
|
|
fake->setImmediateDominator(fake);
|
|
fake->addNumDominated(1);
|
|
fake->setDomIndex(fake->id());
|
|
fake->setUnreachable();
|
|
|
|
// Create zero-input phis to use as inputs for any phis in |block|.
|
|
// Again, this is a little odd, but it's the least-odd thing we can do
|
|
// without significant complexity.
|
|
for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd()); iter != end; ++iter) {
|
|
MPhi* phi = *iter;
|
|
MPhi* fakePhi = MPhi::New(graph_.alloc(), phi->type());
|
|
fake->addPhi(fakePhi);
|
|
if (!phi->addInputSlow(fakePhi))
|
|
return false;
|
|
}
|
|
|
|
fake->end(MGoto::New(graph_.alloc(), block));
|
|
|
|
if (!block->addPredecessorWithoutPhis(fake))
|
|
return false;
|
|
|
|
// Restore |backedge| as |block|'s loop backedge.
|
|
block->clearLoopHeader();
|
|
block->setLoopHeader(backedge);
|
|
|
|
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, DontSetUseRemoved) || !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;
|
|
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)
|
|
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 (DeadIfUnused(def)) {
|
|
if (!discardDefsRecursively(def))
|
|
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->updateForReplacement(def)) {
|
|
#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");
|
|
}
|
|
def = rep;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
// Visit the control instruction at the end of |block|.
|
|
bool
|
|
ValueNumberer::visitControlInstruction(MBasicBlock* block, const MBasicBlock* dominatorRoot)
|
|
{
|
|
// 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;
|
|
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, const MBasicBlock* dominatorRoot)
|
|
{
|
|
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;
|
|
|
|
// If the definition is dead, discard it.
|
|
if (IsDiscardable(def)) {
|
|
if (!discardDefsRecursively(def))
|
|
return false;
|
|
continue;
|
|
}
|
|
|
|
if (!visitDefinition(def))
|
|
return false;
|
|
}
|
|
nextDef_ = nullptr;
|
|
|
|
return visitControlInstruction(block, dominatorRoot);
|
|
}
|
|
|
|
// 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, dominatorRoot))
|
|
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, block->backedge()))
|
|
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),
|
|
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::init()
|
|
{
|
|
// Initialize the value set. It's tempting to pass in a size here of some
|
|
// function of graph_.getNumInstructionIds(), however 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.
|
|
return values_.init();
|
|
}
|
|
|
|
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;
|
|
}
|