tor-browser

ValueNumbering.cpp (47990B)

---

/* -*- 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 MIR type");
 MOZ_ASSERT(!to->isDiscarded(),
            "GVN replaces an instruction by a removed instruction");

 // Update the node's wasm ref type to the LUB of the two nodes being combined.
 // This ensures that any type-based optimizations downstream remain correct.
 to->setWasmRefType(wasm::MaybeRefType::leastUpperBound(from->wasmRefType(),
                                                        to->wasmRefType()));

 // 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) {
#ifdef DEBUG
     if (sim->isObjectKeysLength() && def->isArrayLength()) {
       // /!\ Exception: MArrayLength::foldsTo replaces a sequence of
       // instructions containing an effectful instruction by an effectful
       // instruction.
     } else {
       // Otherwise, a new |sim| node mustn't be effectful when |def| wasn't
       // effectful.
       MOZ_ASSERT_IF(sim->isEffectful(), def->isEffectful());
     }
#endif

     // 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());
   }

   // Get rid of flags that are meaningless for wasm and that hinder dead code
   // removal below.  Do this separately for |def| and |sim| to guard against
   // future scenarios where they come from different (JS-vs-wasm) worlds.
   // See bug 1969987.  This is an interim fix to a larger problem, as
   // described in bug 1973635.
   if (def->isGuardRangeBailouts() && def->block()->info().compilingWasm()) {
     def->setNotGuardRangeBailoutsUnchecked();
   }
   if (sim->isGuardRangeBailouts() && sim->block()->info().compilingWasm()) {
     sim->setNotGuardRangeBailoutsUnchecked();
   }

#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 |sim|. If |def| is a
   // guard, then either |sim| 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(const 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;
}