tor-browser

IonAnalysis.cpp (191877B)

---

/* -*- 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/IonAnalysis.h"

#include "mozilla/CheckedArithmetic.h"
#include "mozilla/HashFunctions.h"

#include <algorithm>
#include <utility>  // for ::std::pair

#include "jit/AliasAnalysis.h"
#include "jit/CompileInfo.h"
#include "jit/DominatorTree.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"

#include "vm/BytecodeUtil-inl.h"

using namespace js;
using namespace js::jit;

using mozilla::DebugOnly;

// Stack used by FlagPhiInputsAsImplicitlyUsed. It stores the Phi instruction
// pointer and the MUseIterator which should be visited next.
using MPhiUseIteratorStack =
   Vector<std::pair<MPhi*, MUseIterator>, 16, SystemAllocPolicy>;

// Look for Phi uses with a depth-first search. If any uses are found the stack
// of MPhi instructions is returned in the |worklist| argument.
[[nodiscard]] static bool DepthFirstSearchUse(const MIRGenerator* mir,
                                             MPhiUseIteratorStack& worklist,
                                             MPhi* phi) {
 // Push a Phi and the next use to iterate over in the worklist.
 auto push = [&worklist](MPhi* phi, MUseIterator use) -> bool {
   phi->setInWorklist();
   return worklist.append(std::make_pair(phi, use));
 };

#ifdef DEBUG
 // Used to assert that when we have no uses, we at least visited all the
 // transitive uses.
 size_t refUseCount = phi->useCount();
 size_t useCount = 0;
#endif
 MOZ_ASSERT(worklist.empty());
 if (!push(phi, phi->usesBegin())) {
   return false;
 }

 while (!worklist.empty()) {
   // Resume iterating over the last phi-use pair added by the next loop.
   auto pair = worklist.popCopy();
   MPhi* producer = pair.first;
   MUseIterator use = pair.second;
   MUseIterator end(producer->usesEnd());
   producer->setNotInWorklist();

   // Keep going down the tree of uses, skipping (continue)
   // non-observable/unused cases and Phi which are already listed in the
   // worklist. Stop (return) as soon as one use is found.
   while (use != end) {
     MNode* consumer = (*use)->consumer();
     MUseIterator it = use;
     use++;
#ifdef DEBUG
     useCount++;
#endif
     if (mir->shouldCancel("FlagPhiInputsAsImplicitlyUsed inner loop")) {
       return false;
     }

     if (consumer->isResumePoint()) {
       MResumePoint* rp = consumer->toResumePoint();
       // Observable operands are similar to potential uses.
       if (rp->isObservableOperand(*it)) {
         return push(producer, use);
       }
       continue;
     }

     MDefinition* cdef = consumer->toDefinition();
     if (!cdef->isPhi()) {
       // The producer is explicitly used by a definition.
       return push(producer, use);
     }

     MPhi* cphi = cdef->toPhi();
     if (cphi->getUsageAnalysis() == PhiUsage::Used ||
         cphi->isImplicitlyUsed()) {
       // The information got cached on the Phi the last time it
       // got visited, or when flagging operands of implicitly used
       // instructions.
       return push(producer, use);
     }

     if (cphi->isInWorklist() || cphi == producer) {
       // We are already iterating over the uses of this Phi instruction which
       // are part of a loop, instead of trying to handle loops, conservatively
       // mark them as used.
       return push(producer, use);
     }

     if (cphi->getUsageAnalysis() == PhiUsage::Unused) {
       // The instruction already got visited and is known to have
       // no uses. Skip it.
       continue;
     }

     // We found another Phi instruction, move the use iterator to
     // the next use push it to the worklist stack. Then, continue
     // with a depth search.
     if (!push(producer, use)) {
       return false;
     }
     producer = cphi;
     use = producer->usesBegin();
     end = producer->usesEnd();
#ifdef DEBUG
     refUseCount += producer->useCount();
#endif
   }

   // When unused, we cannot bubble up this information without iterating
   // over the rest of the previous Phi instruction consumers.
   MOZ_ASSERT(use == end);
   producer->setUsageAnalysis(PhiUsage::Unused);
 }

 MOZ_ASSERT(useCount == refUseCount);
 return true;
}

[[nodiscard]] static bool FlagPhiInputsAsImplicitlyUsed(
   const MIRGenerator* mir, MBasicBlock* block, MBasicBlock* succ,
   MPhiUseIteratorStack& worklist) {
 // When removing an edge between 2 blocks, we might remove the ability of
 // later phases to figure out that the uses of a Phi should be considered as
 // a use of all its inputs. Thus we need to mark the Phi inputs as being
 // implicitly used iff the phi has any uses.
 //
 //
 //        +--------------------+         +---------------------+
 //        |12 MFoo 6           |         |32 MBar 5            |
 //        |                    |         |                     |
 //        |   ...              |         |   ...               |
 //        |                    |         |                     |
 //        |25 MGoto Block 4    |         |43 MGoto Block 4     |
 //        +--------------------+         +---------------------+
 //                   |                              |
 //             |     |                              |
 //             |     |                              |
 //             |     +-----X------------------------+
 //             |         Edge       |
 //             |        Removed     |
 //             |                    |
 //             |       +------------v-----------+
 //             |       |50 MPhi 12 32           |
 //             |       |                        |
 //             |       |   ...                  |
 //             |       |                        |
 //             |       |70 MReturn 50           |
 //             |       +------------------------+
 //             |
 //   - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 //             |
 //             v
 //
 //    ^   +--------------------+         +---------------------+
 //   /!\  |12 MConst opt-out   |         |32 MBar 5            |
 //  '---' |                    |         |                     |
 //        |   ...              |         |   ...               |
 //        |78 MBail            |         |                     |
 //        |80 MUnreachable     |         |43 MGoto Block 4     |
 //        +--------------------+         +---------------------+
 //                                                  |
 //                                                  |
 //                                                  |
 //                                  +---------------+
 //                                  |
 //                                  |
 //                                  |
 //                     +------------v-----------+
 //                     |50 MPhi 32              |
 //                     |                        |
 //                     |   ...                  |
 //                     |                        |
 //                     |70 MReturn 50           |
 //                     +------------------------+
 //
 //
 // If the inputs of the Phi are not flagged as implicitly used, then
 // later compilation phase might optimize them out. The problem is that a
 // bailout will use this value and give it back to baseline, which will then
 // use the OptimizedOut magic value in a computation.
 //
 // Unfortunately, we cannot be too conservative about flagging Phi inputs as
 // having implicit uses, as this would prevent many optimizations from being
 // used. Thus, the following code is in charge of flagging Phi instructions
 // as Unused or Used, and setting ImplicitlyUsed accordingly.
 size_t predIndex = succ->getPredecessorIndex(block);
 MPhiIterator end = succ->phisEnd();
 MPhiIterator it = succ->phisBegin();
 for (; it != end; it++) {
   MPhi* phi = *it;

   if (mir->shouldCancel("FlagPhiInputsAsImplicitlyUsed outer loop")) {
     return false;
   }

   // We are looking to mark the Phi inputs which are used across the edge
   // between the |block| and its successor |succ|.
   MDefinition* def = phi->getOperand(predIndex);
   if (def->isImplicitlyUsed()) {
     continue;
   }

   // If the Phi is either Used or Unused, set the ImplicitlyUsed flag
   // accordingly.
   if (phi->getUsageAnalysis() == PhiUsage::Used || phi->isImplicitlyUsed()) {
     def->setImplicitlyUsedUnchecked();
     continue;
   } else if (phi->getUsageAnalysis() == PhiUsage::Unused) {
     continue;
   }

   // We do not know if the Phi was Used or Unused, iterate over all uses
   // with a depth-search of uses. Returns the matching stack in the
   // worklist as soon as one use is found.
   MOZ_ASSERT(worklist.empty());
   if (!DepthFirstSearchUse(mir, worklist, phi)) {
     return false;
   }

   MOZ_ASSERT_IF(worklist.empty(),
                 phi->getUsageAnalysis() == PhiUsage::Unused);
   if (!worklist.empty()) {
     // One of the Phis is used, set Used flags on all the Phis which are
     // in the use chain.
     def->setImplicitlyUsedUnchecked();
     do {
       auto pair = worklist.popCopy();
       MPhi* producer = pair.first;
       producer->setUsageAnalysis(PhiUsage::Used);
       producer->setNotInWorklist();
     } while (!worklist.empty());
   }
   MOZ_ASSERT(phi->getUsageAnalysis() != PhiUsage::Unknown);
 }

 return true;
}

static MInstructionIterator FindFirstInstructionAfterBail(MBasicBlock* block) {
 MOZ_ASSERT(block->alwaysBails());
 for (MInstructionIterator it = block->begin(); it != block->end(); it++) {
   MInstruction* ins = *it;
   if (ins->isBail()) {
     it++;
     return it;
   }
 }
 MOZ_CRASH("Expected MBail in alwaysBails block");
}

// Given an iterator pointing to the first removed instruction, mark
// the operands of each removed instruction as having implicit uses.
[[nodiscard]] static bool FlagOperandsAsImplicitlyUsedAfter(
   const MIRGenerator* mir, MBasicBlock* block,
   MInstructionIterator firstRemoved) {
 MOZ_ASSERT(firstRemoved->block() == block);

 const CompileInfo& info = block->info();

 // Flag operands of removed instructions as having implicit uses.
 MInstructionIterator end = block->end();
 for (MInstructionIterator it = firstRemoved; it != end; it++) {
   if (mir->shouldCancel("FlagOperandsAsImplicitlyUsedAfter (loop 1)")) {
     return false;
   }

   MInstruction* ins = *it;
   for (size_t i = 0, e = ins->numOperands(); i < e; i++) {
     ins->getOperand(i)->setImplicitlyUsedUnchecked();
   }

   // Flag observable resume point operands as having implicit uses.
   if (MResumePoint* rp = ins->resumePoint()) {
     // Note: no need to iterate over the caller's of the resume point as
     // this is the same as the entry resume point.
     MOZ_ASSERT(&rp->block()->info() == &info);
     for (size_t i = 0, e = rp->numOperands(); i < e; i++) {
       if (info.isObservableSlot(i)) {
         rp->getOperand(i)->setImplicitlyUsedUnchecked();
       }
     }
   }
 }

 // Flag Phi inputs of the successors as having implicit uses.
 MPhiUseIteratorStack worklist;
 for (size_t i = 0, e = block->numSuccessors(); i < e; i++) {
   if (mir->shouldCancel("FlagOperandsAsImplicitlyUsedAfter (loop 2)")) {
     return false;
   }

   if (!FlagPhiInputsAsImplicitlyUsed(mir, block, block->getSuccessor(i),
                                      worklist)) {
     return false;
   }
 }

 return true;
}

[[nodiscard]] static bool FlagEntryResumePointOperands(const MIRGenerator* mir,
                                                      MBasicBlock* block) {
 // Flag observable operands of the entry resume point as having implicit uses.
 MResumePoint* rp = block->entryResumePoint();
 while (rp) {
   if (mir->shouldCancel("FlagEntryResumePointOperands")) {
     return false;
   }

   const CompileInfo& info = rp->block()->info();
   for (size_t i = 0, e = rp->numOperands(); i < e; i++) {
     if (info.isObservableSlot(i)) {
       rp->getOperand(i)->setImplicitlyUsedUnchecked();
     }
   }

   rp = rp->caller();
 }

 return true;
}

[[nodiscard]] static bool FlagAllOperandsAsImplicitlyUsed(
   const MIRGenerator* mir, MBasicBlock* block) {
 return FlagEntryResumePointOperands(mir, block) &&
        FlagOperandsAsImplicitlyUsedAfter(mir, block, block->begin());
}

// WarpBuilder sets the alwaysBails flag on blocks that contain an
// unconditional bailout. We trim any instructions in those blocks
// after the first unconditional bailout, and remove any blocks that
// are only reachable through bailing blocks.
bool jit::PruneUnusedBranches(const MIRGenerator* mir, MIRGraph& graph) {
 JitSpew(JitSpew_Prune, "Begin");

 // Pruning is guided by unconditional bailouts. Wasm does not have bailouts.
 MOZ_ASSERT(!mir->compilingWasm());

 Vector<MBasicBlock*, 16, SystemAllocPolicy> worklist;
 uint32_t numMarked = 0;
 bool needsTrim = false;

 auto markReachable = [&](MBasicBlock* block) -> bool {
   block->mark();
   numMarked++;
   if (block->alwaysBails()) {
     needsTrim = true;
   }
   return worklist.append(block);
 };

 // The entry block is always reachable.
 if (!markReachable(graph.entryBlock())) {
   return false;
 }

 // The OSR entry block is always reachable if it exists.
 if (graph.osrBlock() && !markReachable(graph.osrBlock())) {
   return false;
 }

 // Iteratively mark all reachable blocks.
 while (!worklist.empty()) {
   if (mir->shouldCancel("Prune unused branches (marking reachable)")) {
     return false;
   }
   MBasicBlock* block = worklist.popCopy();

   JitSpew(JitSpew_Prune, "Visit block %u:", block->id());
   JitSpewIndent indent(JitSpew_Prune);

   // If this block always bails, then it does not reach its successors.
   if (block->alwaysBails()) {
     continue;
   }

   for (size_t i = 0; i < block->numSuccessors(); i++) {
     MBasicBlock* succ = block->getSuccessor(i);
     if (succ->isMarked()) {
       continue;
     }
     JitSpew(JitSpew_Prune, "Reaches block %u", succ->id());
     if (!markReachable(succ)) {
       return false;
     }
   }
 }

 if (!needsTrim && numMarked == graph.numBlocks()) {
   // There is nothing to prune.
   graph.unmarkBlocks();
   return true;
 }

 JitSpew(JitSpew_Prune, "Remove unreachable instructions and blocks:");
 JitSpewIndent indent(JitSpew_Prune);

 // The operands of removed instructions may be needed in baseline
 // after bailing out.
 for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) {
   if (mir->shouldCancel("Prune unused branches (marking operands)")) {
     return false;
   }

   MBasicBlock* block = *it++;
   if (!block->isMarked()) {
     // If we are removing the block entirely, mark the operands of every
     // instruction as being implicitly used.
     if (!FlagAllOperandsAsImplicitlyUsed(mir, block)) {
       return false;
     }
   } else if (block->alwaysBails()) {
     // If we are only trimming instructions after a bail, only mark operands
     // of removed instructions.
     MInstructionIterator firstRemoved = FindFirstInstructionAfterBail(block);
     if (!FlagOperandsAsImplicitlyUsedAfter(mir, block, firstRemoved)) {
       return false;
     }
   }
 }

 // Remove the blocks in post-order such that consumers are visited before
 // the predecessors, the only exception being the Phi nodes of loop headers.
 for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) {
   if (mir->shouldCancel("Prune unused branches (removal loop)")) {
     return false;
   }
   if (!graph.alloc().ensureBallast()) {
     return false;
   }

   MBasicBlock* block = *it++;
   if (block->isMarked() && !block->alwaysBails()) {
     continue;
   }

   // As we are going to replace/remove the last instruction, we first have
   // to remove this block from the predecessor list of its successors.
   size_t numSucc = block->numSuccessors();
   for (uint32_t i = 0; i < numSucc; i++) {
     MBasicBlock* succ = block->getSuccessor(i);
     if (succ->isDead()) {
       continue;
     }

     // Our dominators code expects all loop headers to have two predecessors.
     // If we are removing the normal entry to a loop, but can still reach
     // the loop header via OSR, we create a fake unreachable predecessor.
     if (succ->isLoopHeader() && block != succ->backedge()) {
       MOZ_ASSERT(graph.osrBlock());
       if (!graph.alloc().ensureBallast()) {
         return false;
       }

       MBasicBlock* fake = MBasicBlock::NewFakeLoopPredecessor(graph, succ);
       if (!fake) {
         return false;
       }
       // Mark the block to avoid removing it as unreachable.
       fake->mark();

       JitSpew(JitSpew_Prune,
               "Header %u only reachable by OSR. Add fake predecessor %u",
               succ->id(), fake->id());
     }

     JitSpew(JitSpew_Prune, "Remove block edge %u -> %u.", block->id(),
             succ->id());
     succ->removePredecessor(block);
   }

   if (!block->isMarked()) {
     // Remove unreachable blocks from the CFG.
     JitSpew(JitSpew_Prune, "Remove block %u.", block->id());
     graph.removeBlock(block);
   } else {
     // Remove unreachable instructions after unconditional bailouts.
     JitSpew(JitSpew_Prune, "Trim block %u.", block->id());

     // Discard all instructions after the first MBail.
     MInstructionIterator firstRemoved = FindFirstInstructionAfterBail(block);
     block->discardAllInstructionsStartingAt(firstRemoved);

     if (block->outerResumePoint()) {
       block->clearOuterResumePoint();
     }

     block->end(MUnreachable::New(graph.alloc()));
   }
 }
 graph.unmarkBlocks();

 return true;
}

[[nodiscard]] static bool SplitCriticalEdgesForBlock(MIRGraph& graph,
                                                    MBasicBlock* block) {
 if (block->numSuccessors() < 2) {
   return true;
 }
 for (size_t i = 0; i < block->numSuccessors(); i++) {
   MBasicBlock* target = block->getSuccessor(i);
   if (target->numPredecessors() < 2) {
     continue;
   }

   // Create a simple new block which contains a goto and which split the
   // edge between block and target.
   MBasicBlock* split = MBasicBlock::NewSplitEdge(graph, block, i, target);
   if (!split) {
     return false;
   }
 }
 return true;
}

// A critical edge is an edge which is neither its successor's only predecessor
// nor its predecessor's only successor. Critical edges must be split to
// prevent copy-insertion and code motion from affecting other edges.
bool jit::SplitCriticalEdges(MIRGraph& graph) {
 for (MBasicBlockIterator iter(graph.begin()); iter != graph.end(); iter++) {
   MBasicBlock* block = *iter;
   if (!SplitCriticalEdgesForBlock(graph, block)) {
     return false;
   }
 }
 return true;
}

bool jit::IsUint32Type(const MDefinition* def) {
 if (def->isBeta()) {
   def = def->getOperand(0);
 }

 if (def->type() != MIRType::Int32) {
   return false;
 }

 return def->isUrsh() && def->getOperand(1)->isConstant() &&
        def->getOperand(1)->toConstant()->type() == MIRType::Int32 &&
        def->getOperand(1)->toConstant()->toInt32() == 0;
}

// Determine whether phiBlock/testBlock simply compute a phi and perform a
// test on it.
static bool BlockIsSingleTest(MBasicBlock* phiBlock, MBasicBlock* testBlock,
                             MPhi** pphi, MTest** ptest) {
 *pphi = nullptr;
 *ptest = nullptr;

 if (phiBlock != testBlock) {
   MOZ_ASSERT(phiBlock->numSuccessors() == 1 &&
              phiBlock->getSuccessor(0) == testBlock);
   if (!phiBlock->begin()->isGoto()) {
     return false;
   }
 }

 auto iter = testBlock->rbegin();
 if (!iter->isTest()) {
   return false;
 }
 MTest* test = iter->toTest();

 // Unwrap boolean conversion performed through the '!!' idiom.
 MInstruction* testOrNot = test;
 bool hasOddNumberOfNots = false;
 while (++iter != testBlock->rend()) {
   if (iter->isNot()) {
     // The MNot must only be used by |testOrNot|.
     auto* notIns = iter->toNot();
     if (testOrNot->getOperand(0) != notIns) {
       return false;
     }
     if (!notIns->hasOneUse()) {
       return false;
     }

     testOrNot = notIns;
     hasOddNumberOfNots = !hasOddNumberOfNots;
   } else {
     // Fail if there are any other instructions than MNot.
     return false;
   }
 }

 // There's an odd number of MNot, so this can't be the '!!' idiom.
 if (hasOddNumberOfNots) {
   return false;
 }

 MOZ_ASSERT(testOrNot->isTest() || testOrNot->isNot());

 MDefinition* testInput = testOrNot->getOperand(0);
 if (!testInput->isPhi()) {
   return false;
 }
 MPhi* phi = testInput->toPhi();
 if (phi->block() != phiBlock) {
   return false;
 }

 for (MUseIterator iter = phi->usesBegin(); iter != phi->usesEnd(); ++iter) {
   MUse* use = *iter;
   if (use->consumer() == testOrNot) {
     continue;
   }
   if (use->consumer()->isResumePoint()) {
     MBasicBlock* useBlock = use->consumer()->block();
     if (useBlock == phiBlock || useBlock == testBlock) {
       continue;
     }
   }
   return false;
 }

 for (MPhiIterator iter = phiBlock->phisBegin(); iter != phiBlock->phisEnd();
      ++iter) {
   if (*iter != phi) {
     return false;
   }
 }

 if (phiBlock != testBlock && !testBlock->phisEmpty()) {
   return false;
 }

 *pphi = phi;
 *ptest = test;

 return true;
}

// Determine if value is directly or indirectly the test input.
static bool IsTestInputMaybeToBool(MTest* test, MDefinition* value) {
 auto* input = test->input();
 bool hasEvenNumberOfNots = true;
 while (true) {
   // Only accept if there's an even number of MNot.
   if (input == value && hasEvenNumberOfNots) {
     return true;
   }

   // Unwrap boolean conversion performed through the '!!' idiom.
   if (input->isNot()) {
     input = input->toNot()->input();
     hasEvenNumberOfNots = !hasEvenNumberOfNots;
     continue;
   }

   return false;
 }
}

// Change |block| so that it ends in a goto to the specific |target| block.
// |existingPred| is an existing predecessor of the block.
//
// |blockResult| is the value computed by |block|. This was a phi input but the
// caller has determined that |blockResult| matches the input of an earlier
// MTest instruction and we don't need to test it a second time. Mark it as
// implicitly-used because we're removing a use.
[[nodiscard]] static bool UpdateGotoSuccessor(TempAllocator& alloc,
                                             MBasicBlock* block,
                                             MDefinition* blockResult,
                                             MBasicBlock* target,
                                             MBasicBlock* existingPred) {
 blockResult->setImplicitlyUsedUnchecked();

 MInstruction* ins = block->lastIns();
 MOZ_ASSERT(ins->isGoto());
 ins->toGoto()->target()->removePredecessor(block);
 block->discardLastIns();

 MGoto* newGoto = MGoto::New(alloc, target);
 block->end(newGoto);

 return target->addPredecessorSameInputsAs(block, existingPred);
}

// Change block so that it ends in a test of the specified value, going to
// either ifTrue or ifFalse. existingPred is an existing predecessor of ifTrue
// or ifFalse with the same values incoming to ifTrue/ifFalse as block.
// existingPred is not required to be a predecessor of ifTrue/ifFalse if block
// already ends in a test going to that block on a true/false result.
[[nodiscard]] static bool UpdateTestSuccessors(
   TempAllocator& alloc, MBasicBlock* block, MDefinition* value,
   MBasicBlock* ifTrue, MBasicBlock* ifFalse, MBasicBlock* existingPred) {
 MInstruction* ins = block->lastIns();
 if (ins->isTest()) {
   MTest* test = ins->toTest();
   MOZ_ASSERT(test->input() == value);

   if (ifTrue != test->ifTrue()) {
     test->ifTrue()->removePredecessor(block);
     if (!ifTrue->addPredecessorSameInputsAs(block, existingPred)) {
       return false;
     }
     MOZ_ASSERT(test->ifTrue() == test->getSuccessor(0));
     test->replaceSuccessor(0, ifTrue);
   }

   if (ifFalse != test->ifFalse()) {
     test->ifFalse()->removePredecessor(block);
     if (!ifFalse->addPredecessorSameInputsAs(block, existingPred)) {
       return false;
     }
     MOZ_ASSERT(test->ifFalse() == test->getSuccessor(1));
     test->replaceSuccessor(1, ifFalse);
   }

   return true;
 }

 MOZ_ASSERT(ins->isGoto());
 ins->toGoto()->target()->removePredecessor(block);
 block->discardLastIns();

 MTest* test = MTest::New(alloc, value, ifTrue, ifFalse);
 block->end(test);

 if (!ifTrue->addPredecessorSameInputsAs(block, existingPred)) {
   return false;
 }
 if (!ifFalse->addPredecessorSameInputsAs(block, existingPred)) {
   return false;
 }
 return true;
}

/*
* Look for a diamond pattern:
*
*        initialBlock
*          /     \
*  trueBranch  falseBranch
*          \     /
*          phiBlock
*             |
*         testBlock
*/
static bool IsDiamondPattern(MBasicBlock* initialBlock) {
 MInstruction* ins = initialBlock->lastIns();
 if (!ins->isTest()) {
   return false;
 }
 MTest* initialTest = ins->toTest();

 MBasicBlock* trueBranch = initialTest->ifTrue();
 if (trueBranch->numPredecessors() != 1 || !trueBranch->lastIns()->isGoto()) {
   return false;
 }

 MBasicBlock* falseBranch = initialTest->ifFalse();
 if (falseBranch->numPredecessors() != 1 ||
     !falseBranch->lastIns()->isGoto()) {
   return false;
 }

 MBasicBlock* phiBlock = trueBranch->getSuccessor(0);
 if (phiBlock != falseBranch->getSuccessor(0)) {
   return false;
 }
 if (phiBlock->numPredecessors() != 2) {
   return false;
 }
 return true;
}

[[nodiscard]] static bool MaybeFoldDiamondConditionBlock(
   MIRGraph& graph, MBasicBlock* initialBlock) {
 MOZ_ASSERT(IsDiamondPattern(initialBlock));

 // Optimize the MIR graph to improve the code generated for conditional
 // operations. A test like 'if (a ? b : c)' normally requires four blocks,
 // with a phi for the intermediate value. This can be improved to use three
 // blocks with no phi value.

 /*
  * Look for a diamond pattern:
  *
  *        initialBlock
  *          /     \
  *  trueBranch  falseBranch
  *          \     /
  *          phiBlock
  *             |
  *         testBlock
  *
  * Where phiBlock contains a single phi combining values pushed onto the
  * stack by trueBranch and falseBranch, and testBlock contains a test on
  * that phi. phiBlock and testBlock may be the same block; generated code
  * will use different blocks if the (?:) op is in an inlined function.
  */

 MTest* initialTest = initialBlock->lastIns()->toTest();

 MBasicBlock* trueBranch = initialTest->ifTrue();
 MBasicBlock* falseBranch = initialTest->ifFalse();
 if (initialBlock->isLoopBackedge() || trueBranch->isLoopBackedge() ||
     falseBranch->isLoopBackedge()) {
   return true;
 }

 MBasicBlock* phiBlock = trueBranch->getSuccessor(0);
 MBasicBlock* testBlock = phiBlock;
 if (testBlock->numSuccessors() == 1) {
   if (testBlock->isLoopBackedge()) {
     return true;
   }
   testBlock = testBlock->getSuccessor(0);
   if (testBlock->numPredecessors() != 1) {
     return true;
   }
 }

 MPhi* phi;
 MTest* finalTest;
 if (!BlockIsSingleTest(phiBlock, testBlock, &phi, &finalTest)) {
   return true;
 }

 MOZ_ASSERT(phi->numOperands() == 2);

 // Make sure the test block does not have any outgoing loop backedges.
 if (!SplitCriticalEdgesForBlock(graph, testBlock)) {
   return false;
 }

 MDefinition* trueResult =
     phi->getOperand(phiBlock->indexForPredecessor(trueBranch));
 MDefinition* falseResult =
     phi->getOperand(phiBlock->indexForPredecessor(falseBranch));

 // OK, we found the desired pattern, now transform the graph.

 // Remove the phi from phiBlock.
 phiBlock->discardPhi(*phiBlock->phisBegin());

 // Change the end of the block to a test that jumps directly to successors of
 // testBlock, rather than to testBlock itself.

 if (IsTestInputMaybeToBool(initialTest, trueResult)) {
   if (!UpdateGotoSuccessor(graph.alloc(), trueBranch, trueResult,
                            finalTest->ifTrue(), testBlock)) {
     return false;
   }
 } else {
   if (!UpdateTestSuccessors(graph.alloc(), trueBranch, trueResult,
                             finalTest->ifTrue(), finalTest->ifFalse(),
                             testBlock)) {
     return false;
   }
 }

 if (IsTestInputMaybeToBool(initialTest, falseResult)) {
   if (!UpdateGotoSuccessor(graph.alloc(), falseBranch, falseResult,
                            finalTest->ifFalse(), testBlock)) {
     return false;
   }
 } else {
   if (!UpdateTestSuccessors(graph.alloc(), falseBranch, falseResult,
                             finalTest->ifTrue(), finalTest->ifFalse(),
                             testBlock)) {
     return false;
   }
 }

 // Remove phiBlock, if different from testBlock.
 if (phiBlock != testBlock) {
   testBlock->removePredecessor(phiBlock);
   graph.removeBlock(phiBlock);
 }

 // Remove testBlock itself.
 finalTest->ifTrue()->removePredecessor(testBlock);
 finalTest->ifFalse()->removePredecessor(testBlock);
 graph.removeBlock(testBlock);

 return true;
}

/*
* Look for a triangle pattern:
*
*        initialBlock
*          /     \
*  trueBranch     |
*          \     /
*     phiBlock+falseBranch
*             |
*         testBlock
*
* Or:
*
*        initialBlock
*          /     \
*         |    falseBranch
*          \     /
*     phiBlock+trueBranch
*             |
*         testBlock
*/
static bool IsTrianglePattern(MBasicBlock* initialBlock) {
 MInstruction* ins = initialBlock->lastIns();
 if (!ins->isTest()) {
   return false;
 }
 MTest* initialTest = ins->toTest();

 MBasicBlock* trueBranch = initialTest->ifTrue();
 MBasicBlock* falseBranch = initialTest->ifFalse();

 if (trueBranch->numSuccessors() == 1 &&
     trueBranch->getSuccessor(0) == falseBranch) {
   if (trueBranch->numPredecessors() != 1) {
     return false;
   }
   if (falseBranch->numPredecessors() != 2) {
     return false;
   }
   return true;
 }

 if (falseBranch->numSuccessors() == 1 &&
     falseBranch->getSuccessor(0) == trueBranch) {
   if (trueBranch->numPredecessors() != 2) {
     return false;
   }
   if (falseBranch->numPredecessors() != 1) {
     return false;
   }
   return true;
 }

 return false;
}

[[nodiscard]] static bool MaybeFoldTriangleConditionBlock(
   MIRGraph& graph, MBasicBlock* initialBlock) {
 MOZ_ASSERT(IsTrianglePattern(initialBlock));

 // Optimize the MIR graph to improve the code generated for boolean
 // operations. A test like 'if (a && b)' normally requires three blocks, with
 // a phi for the intermediate value. This can be improved to use no phi value.

 /*
  * Look for a triangle pattern:
  *
  *        initialBlock
  *          /     \
  *  trueBranch     |
  *          \     /
  *     phiBlock+falseBranch
  *             |
  *         testBlock
  *
  * Or:
  *
  *        initialBlock
  *          /     \
  *         |    falseBranch
  *          \     /
  *     phiBlock+trueBranch
  *             |
  *         testBlock
  *
  * Where phiBlock contains a single phi combining values pushed onto the stack
  * by trueBranch and falseBranch, and testBlock contains a test on that phi.
  * phiBlock and testBlock may be the same block; generated code will use
  * different blocks if the (&&) op is in an inlined function.
  */

 MTest* initialTest = initialBlock->lastIns()->toTest();

 MBasicBlock* trueBranch = initialTest->ifTrue();
 MBasicBlock* falseBranch = initialTest->ifFalse();
 if (initialBlock->isLoopBackedge() || trueBranch->isLoopBackedge() ||
     falseBranch->isLoopBackedge()) {
   return true;
 }

 MBasicBlock* phiBlock;
 if (trueBranch->numSuccessors() == 1 &&
     trueBranch->getSuccessor(0) == falseBranch) {
   phiBlock = falseBranch;
 } else {
   MOZ_ASSERT(falseBranch->getSuccessor(0) == trueBranch);
   phiBlock = trueBranch;
 }

 MBasicBlock* testBlock = phiBlock;
 if (testBlock->numSuccessors() == 1) {
   MOZ_ASSERT(!testBlock->isLoopBackedge());

   testBlock = testBlock->getSuccessor(0);
   if (testBlock->numPredecessors() != 1) {
     return true;
   }
 }

 MPhi* phi;
 MTest* finalTest;
 if (!BlockIsSingleTest(phiBlock, testBlock, &phi, &finalTest)) {
   return true;
 }

 MOZ_ASSERT(phi->numOperands() == 2);

 // If the phi-operand doesn't match the initial input, we can't fold the test.
 auto* phiInputForInitialBlock =
     phi->getOperand(phiBlock->indexForPredecessor(initialBlock));
 if (!IsTestInputMaybeToBool(initialTest, phiInputForInitialBlock)) {
   return true;
 }

 // Make sure the test block does not have any outgoing loop backedges.
 if (!SplitCriticalEdgesForBlock(graph, testBlock)) {
   return false;
 }

 MDefinition* trueResult;
 MDefinition* falseResult;
 if (phiBlock == trueBranch) {
   trueResult = phi->getOperand(phiBlock->indexForPredecessor(initialBlock));
   falseResult = phi->getOperand(phiBlock->indexForPredecessor(falseBranch));
 } else {
   trueResult = phi->getOperand(phiBlock->indexForPredecessor(trueBranch));
   falseResult = phi->getOperand(phiBlock->indexForPredecessor(initialBlock));
 }

 // OK, we found the desired pattern, now transform the graph.

 // Remove the phi from phiBlock.
 phiBlock->discardPhi(*phiBlock->phisBegin());

 // Change the end of the block to a test that jumps directly to successors of
 // testBlock, rather than to testBlock itself.

 if (phiBlock == trueBranch) {
   if (!UpdateTestSuccessors(graph.alloc(), initialBlock, initialTest->input(),
                             finalTest->ifTrue(), initialTest->ifFalse(),
                             testBlock)) {
     return false;
   }
 } else if (IsTestInputMaybeToBool(initialTest, trueResult)) {
   if (!UpdateGotoSuccessor(graph.alloc(), trueBranch, trueResult,
                            finalTest->ifTrue(), testBlock)) {
     return false;
   }
 } else {
   if (!UpdateTestSuccessors(graph.alloc(), trueBranch, trueResult,
                             finalTest->ifTrue(), finalTest->ifFalse(),
                             testBlock)) {
     return false;
   }
 }

 if (phiBlock == falseBranch) {
   if (!UpdateTestSuccessors(graph.alloc(), initialBlock, initialTest->input(),
                             initialTest->ifTrue(), finalTest->ifFalse(),
                             testBlock)) {
     return false;
   }
 } else if (IsTestInputMaybeToBool(initialTest, falseResult)) {
   if (!UpdateGotoSuccessor(graph.alloc(), falseBranch, falseResult,
                            finalTest->ifFalse(), testBlock)) {
     return false;
   }
 } else {
   if (!UpdateTestSuccessors(graph.alloc(), falseBranch, falseResult,
                             finalTest->ifTrue(), finalTest->ifFalse(),
                             testBlock)) {
     return false;
   }
 }

 // Remove phiBlock, if different from testBlock.
 if (phiBlock != testBlock) {
   testBlock->removePredecessor(phiBlock);
   graph.removeBlock(phiBlock);
 }

 // Remove testBlock itself.
 finalTest->ifTrue()->removePredecessor(testBlock);
 finalTest->ifFalse()->removePredecessor(testBlock);
 graph.removeBlock(testBlock);

 return true;
}

[[nodiscard]] static bool MaybeFoldConditionBlock(MIRGraph& graph,
                                                 MBasicBlock* initialBlock) {
 if (IsDiamondPattern(initialBlock)) {
   return MaybeFoldDiamondConditionBlock(graph, initialBlock);
 }
 if (IsTrianglePattern(initialBlock)) {
   return MaybeFoldTriangleConditionBlock(graph, initialBlock);
 }
 return true;
}

[[nodiscard]] static bool MaybeFoldTestBlock(MIRGraph& graph,
                                            MBasicBlock* initialBlock) {
 // Handle test expressions on more than two inputs. For example
 // |if ((x > 10) && (y > 20) && (z > 30)) { ... }|, which results in the below
 // pattern.
 //
 // Look for the pattern:
 //                       ┌─────────────────┐
 //                    1  │ 1 compare       │
 //                 ┌─────┤ 2 test compare1 │
 //                 │     └──────┬──────────┘
 //                 │            │0
 //         ┌───────▼─────────┐  │
 //         │ 3 compare       │  │
 //         │ 4 test compare3 │  └──────────┐
 //         └──┬──────────┬───┘             │
 //           1│          │0                │
 // ┌──────────▼──────┐   │                 │
 // │ 5 compare       │   └─────────┐       │
 // │ 6 goto          │             │       │
 // └───────┬─────────┘             │       │
 //         │                       │       │
 //         │    ┌──────────────────▼───────▼───────┐
 //         └───►│ 9 phi compare1 compare3 compare5 │
 //              │10 goto                           │
 //              └────────────────┬─────────────────┘
 //                               │
 //                      ┌────────▼────────┐
 //                      │11 test phi9     │
 //                      └─────┬─────┬─────┘
 //                           1│     │0
 //         ┌────────────┐     │     │      ┌─────────────┐
 //         │ TrueBranch │◄────┘     └─────►│ FalseBranch │
 //         └────────────┘                  └─────────────┘
 //
 // And transform it to:
 //
 //                      ┌─────────────────┐
 //                   1  │ 1 compare       │
 //                  ┌───┤ 2 test compare1 │
 //                  │   └──────────┬──────┘
 //                  │              │0
 //          ┌───────▼─────────┐    │
 //          │ 3 compare       │    │
 //          │ 4 test compare3 │    │
 //          └──┬─────────┬────┘    │
 //            1│         │0        │
 //  ┌──────────▼──────┐  │         │
 //  │ 5 compare       │  └──────┐  │
 //  │ 6 test compare5 │         │  │
 //  └────┬────────┬───┘         │  │
 //      1│        │0            │  │
 // ┌─────▼──────┐ │         ┌───▼──▼──────┐
 // │ TrueBranch │ └─────────► FalseBranch │
 // └────────────┘           └─────────────┘

 auto* ins = initialBlock->lastIns();
 if (!ins->isTest()) {
   return true;
 }
 auto* initialTest = ins->toTest();

 MBasicBlock* trueBranch = initialTest->ifTrue();
 MBasicBlock* falseBranch = initialTest->ifFalse();

 // MaybeFoldConditionBlock handles the case for two operands.
 MBasicBlock* phiBlock;
 if (trueBranch->numPredecessors() > 2) {
   phiBlock = trueBranch;
 } else if (falseBranch->numPredecessors() > 2) {
   phiBlock = falseBranch;
 } else {
   return true;
 }

 MBasicBlock* testBlock = phiBlock;
 if (testBlock->numSuccessors() == 1) {
   if (testBlock->isLoopBackedge()) {
     return true;
   }
   testBlock = testBlock->getSuccessor(0);
   if (testBlock->numPredecessors() != 1) {
     return true;
   }
 }

 MOZ_ASSERT(!phiBlock->isLoopBackedge());

 MPhi* phi = nullptr;
 MTest* finalTest = nullptr;
 if (!BlockIsSingleTest(phiBlock, testBlock, &phi, &finalTest)) {
   return true;
 }

 MOZ_ASSERT(phiBlock->numPredecessors() == phi->numOperands());

 // If the phi-operand doesn't match the initial input, we can't fold the test.
 auto* phiInputForInitialBlock =
     phi->getOperand(phiBlock->indexForPredecessor(initialBlock));
 if (!IsTestInputMaybeToBool(initialTest, phiInputForInitialBlock)) {
   return true;
 }

 MBasicBlock* newTestBlock = nullptr;
 MDefinition* newTestInput = nullptr;

 // The block of each phi operand must either end with a test instruction on
 // that phi operand or it's the sole block which ends with a goto instruction.
 for (size_t i = 0; i < phiBlock->numPredecessors(); i++) {
   auto* pred = phiBlock->getPredecessor(i);
   auto* operand = phi->getOperand(i);

   // Each predecessor must end with either a test or goto instruction.
   auto* lastIns = pred->lastIns();
   if (lastIns->isGoto() && !newTestBlock) {
     newTestBlock = pred;
     newTestInput = operand;
   } else if (lastIns->isTest()) {
     if (!IsTestInputMaybeToBool(lastIns->toTest(), operand)) {
       return true;
     }
   } else {
     return true;
   }

   MOZ_ASSERT(!pred->isLoopBackedge());
 }

 // Ensure we found the single goto block.
 if (!newTestBlock) {
   return true;
 }

 // Make sure the test block does not have any outgoing loop backedges.
 if (!SplitCriticalEdgesForBlock(graph, testBlock)) {
   return false;
 }

 // OK, we found the desired pattern, now transform the graph.

 // Remove the phi from phiBlock.
 phiBlock->discardPhi(*phiBlock->phisBegin());

 // Create the new test instruction.
 if (!UpdateTestSuccessors(graph.alloc(), newTestBlock, newTestInput,
                           finalTest->ifTrue(), finalTest->ifFalse(),
                           testBlock)) {
   return false;
 }

 // Update all test instructions to point to the final target.
 while (phiBlock->numPredecessors()) {
   mozilla::DebugOnly<size_t> oldNumPred = phiBlock->numPredecessors();

   auto* pred = phiBlock->getPredecessor(0);
   auto* test = pred->lastIns()->toTest();
   if (test->ifTrue() == phiBlock) {
     if (!UpdateTestSuccessors(graph.alloc(), pred, test->input(),
                               finalTest->ifTrue(), test->ifFalse(),
                               testBlock)) {
       return false;
     }
   } else {
     MOZ_ASSERT(test->ifFalse() == phiBlock);
     if (!UpdateTestSuccessors(graph.alloc(), pred, test->input(),
                               test->ifTrue(), finalTest->ifFalse(),
                               testBlock)) {
       return false;
     }
   }

   // Ensure we've made progress.
   MOZ_ASSERT(phiBlock->numPredecessors() + 1 == oldNumPred);
 }

 // Remove phiBlock, if different from testBlock.
 if (phiBlock != testBlock) {
   testBlock->removePredecessor(phiBlock);
   graph.removeBlock(phiBlock);
 }

 // Remove testBlock itself.
 finalTest->ifTrue()->removePredecessor(testBlock);
 finalTest->ifFalse()->removePredecessor(testBlock);
 graph.removeBlock(testBlock);

 return true;
}

bool jit::FoldTests(MIRGraph& graph) {
 for (PostorderIterator block(graph.poBegin()); block != graph.poEnd();
      block++) {
   if (!MaybeFoldConditionBlock(graph, *block)) {
     return false;
   }
   if (!MaybeFoldTestBlock(graph, *block)) {
     return false;
   }
 }
 return true;
}

bool jit::FoldEmptyBlocks(MIRGraph& graph, bool* changed) {
 *changed = false;

 for (MBasicBlockIterator iter(graph.begin()); iter != graph.end();) {
   MBasicBlock* block = *iter;
   iter++;

   if (block->numPredecessors() != 1 || block->numSuccessors() != 1) {
     continue;
   }

   if (!block->phisEmpty()) {
     continue;
   }

   if (block->outerResumePoint()) {
     continue;
   }

   if (*block->begin() != *block->rbegin()) {
     continue;
   }

   MBasicBlock* succ = block->getSuccessor(0);
   MBasicBlock* pred = block->getPredecessor(0);

   if (succ->numPredecessors() != 1) {
     continue;
   }

   size_t pos = pred->getSuccessorIndex(block);
   pred->lastIns()->replaceSuccessor(pos, succ);

   graph.removeBlock(block);

   if (!succ->addPredecessorSameInputsAs(pred, block)) {
     return false;
   }
   succ->removePredecessor(block);

   *changed = true;
 }
 return true;
}

static void EliminateTriviallyDeadResumePointOperands(MIRGraph& graph,
                                                     MResumePoint* rp) {
 // If we will pop the top of the stack immediately after resuming,
 // then don't preserve the top value in the resume point.
 if (rp->mode() != ResumeMode::ResumeAt) {
   return;
 }

 jsbytecode* pc = rp->pc();
 if (JSOp(*pc) == JSOp::JumpTarget) {
   pc += JSOpLength_JumpTarget;
 }
 if (JSOp(*pc) != JSOp::Pop) {
   return;
 }

 size_t top = rp->stackDepth() - 1;
 MOZ_ASSERT(!rp->isObservableOperand(top));

 MDefinition* def = rp->getOperand(top);
 if (def->isConstant()) {
   return;
 }

 MConstant* constant = rp->block()->optimizedOutConstant(graph.alloc());
 rp->replaceOperand(top, constant);
}

// Operands to a resume point which are dead at the point of the resume can be
// replaced with a magic value. This pass only replaces resume points which are
// trivially dead.
//
// This is intended to ensure that extra resume points within a basic block
// will not artificially extend the lifetimes of any SSA values. This could
// otherwise occur if the new resume point captured a value which is created
// between the old and new resume point and is dead at the new resume point.
bool jit::EliminateTriviallyDeadResumePointOperands(const MIRGenerator* mir,
                                                   MIRGraph& graph) {
 for (auto* block : graph) {
   if (MResumePoint* rp = block->entryResumePoint()) {
     if (!graph.alloc().ensureBallast()) {
       return false;
     }
     ::EliminateTriviallyDeadResumePointOperands(graph, rp);
   }
 }
 return true;
}

// Operands to a resume point which are dead at the point of the resume can be
// replaced with a magic value. This analysis supports limited detection of
// dead operands, pruning those which are defined in the resume point's basic
// block and have no uses outside the block or at points later than the resume
// point.
//
// This is intended to ensure that extra resume points within a basic block
// will not artificially extend the lifetimes of any SSA values. This could
// otherwise occur if the new resume point captured a value which is created
// between the old and new resume point and is dead at the new resume point.
bool jit::EliminateDeadResumePointOperands(const MIRGenerator* mir,
                                          MIRGraph& graph) {
 // If we are compiling try blocks, locals and arguments may be observable
 // from catch or finally blocks (which Ion does not compile). For now just
 // disable the pass in this case.
 if (graph.hasTryBlock()) {
   return true;
 }

 for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
      block++) {
   if (mir->shouldCancel("Eliminate Dead Resume Point Operands (main loop)")) {
     return false;
   }

   if (MResumePoint* rp = block->entryResumePoint()) {
     if (!graph.alloc().ensureBallast()) {
       return false;
     }
     ::EliminateTriviallyDeadResumePointOperands(graph, rp);
   }

   // The logic below can get confused on infinite loops.
   if (block->isLoopHeader() && block->backedge() == *block) {
     continue;
   }

   for (MInstructionIterator ins = block->begin(); ins != block->end();
        ins++) {
     if (MResumePoint* rp = ins->resumePoint()) {
       if (!graph.alloc().ensureBallast()) {
         return false;
       }
       ::EliminateTriviallyDeadResumePointOperands(graph, rp);
     }

     // No benefit to replacing constant operands with other constants.
     if (ins->isConstant()) {
       continue;
     }

     // Scanning uses does not give us sufficient information to tell
     // where instructions that are involved in box/unbox operations or
     // parameter passing might be live. Rewriting uses of these terms
     // in resume points may affect the interpreter's behavior. Rather
     // than doing a more sophisticated analysis, just ignore these.
     if (ins->isUnbox() || ins->isParameter() || ins->isBoxNonStrictThis()) {
       continue;
     }

     // Early intermediate values captured by resume points, such as
     // ArrayState and its allocation, may be legitimately dead in Ion code,
     // but are still needed if we bail out. They can recover on bailout.
     if (ins->isRecoveredOnBailout()) {
       MOZ_ASSERT(ins->canRecoverOnBailout());
       continue;
     }

     // If the instruction's behavior has been constant folded into a
     // separate instruction, we can't determine precisely where the
     // instruction becomes dead and can't eliminate its uses.
     if (ins->isImplicitlyUsed()) {
       continue;
     }

     // Check if this instruction's result is only used within the
     // current block, and keep track of its last use in a definition
     // (not resume point). This requires the instructions in the block
     // to be numbered, ensured by running this immediately after alias
     // analysis.
     uint32_t maxDefinition = 0;
     for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd();
          uses++) {
       MNode* consumer = uses->consumer();
       if (consumer->isResumePoint()) {
         // If the instruction's is captured by one of the resume point, then
         // it might be observed indirectly while the frame is live on the
         // stack, so it has to be computed.
         MResumePoint* resume = consumer->toResumePoint();
         if (resume->isObservableOperand(*uses)) {
           maxDefinition = UINT32_MAX;
           break;
         }
         continue;
       }

       MDefinition* def = consumer->toDefinition();
       if (def->block() != *block || def->isBox() || def->isPhi()) {
         maxDefinition = UINT32_MAX;
         break;
       }
       maxDefinition = std::max(maxDefinition, def->id());
     }
     if (maxDefinition == UINT32_MAX) {
       continue;
     }

     // Walk the uses a second time, removing any in resume points after
     // the last use in a definition.
     for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd();) {
       MUse* use = *uses++;
       if (use->consumer()->isDefinition()) {
         continue;
       }
       MResumePoint* mrp = use->consumer()->toResumePoint();
       if (mrp->block() != *block || !mrp->instruction() ||
           mrp->instruction() == *ins ||
           mrp->instruction()->id() <= maxDefinition) {
         continue;
       }

       if (!graph.alloc().ensureBallast()) {
         return false;
       }

       // Store an optimized out magic value in place of all dead
       // resume point operands. Making any such substitution can in
       // general alter the interpreter's behavior, even though the
       // code is dead, as the interpreter will still execute opcodes
       // whose effects cannot be observed. If the magic value value
       // were to flow to, say, a dead property access the
       // interpreter could throw an exception; we avoid this problem
       // by removing dead operands before removing dead code.
       MConstant* constant =
           MConstant::NewMagic(graph.alloc(), JS_OPTIMIZED_OUT);
       block->insertBefore(*(block->begin()), constant);
       use->replaceProducer(constant);
     }
   }
 }

 return true;
}

// Test whether |def| would be needed if it had no uses.
bool js::jit::DeadIfUnused(const MDefinition* def) {
 // Effectful instructions of course cannot be removed.
 if (def->isEffectful()) {
   return false;
 }

 // Never eliminate guard instructions.
 if (def->isGuard()) {
   return false;
 }

 // Required to be preserved, as the type guard related to this instruction
 // is part of the semantics of a transformation.
 if (def->isGuardRangeBailouts()) {
   return false;
 }

 // Control instructions have no uses, but also shouldn't be optimized out
 if (def->isControlInstruction()) {
   return false;
 }

 // Used when lowering to generate the corresponding snapshots and aggregate
 // the list of recover instructions to be repeated.
 if (def->isInstruction() && def->toInstruction()->resumePoint()) {
   return false;
 }

 return true;
}

// Similar to DeadIfUnused(), but additionally allows effectful instructions.
bool js::jit::DeadIfUnusedAllowEffectful(const MDefinition* def) {
 // Never eliminate guard instructions.
 if (def->isGuard()) {
   return false;
 }

 // Required to be preserved, as the type guard related to this instruction
 // is part of the semantics of a transformation.
 if (def->isGuardRangeBailouts()) {
   return false;
 }

 // Control instructions have no uses, but also shouldn't be optimized out
 if (def->isControlInstruction()) {
   return false;
 }

 // Used when lowering to generate the corresponding snapshots and aggregate
 // the list of recover instructions to be repeated.
 if (def->isInstruction() && def->toInstruction()->resumePoint()) {
   // All effectful instructions must have a resume point attached. We're
   // allowing effectful instructions here, so we have to ignore any resume
   // points if we want to consider effectful instructions as dead.
   if (!def->isEffectful()) {
     return false;
   }
 }

 return true;
}

// Test whether |def| may be safely discarded, due to being dead or due to being
// located in a basic block which has itself been marked for discarding.
bool js::jit::IsDiscardable(const MDefinition* def) {
 return !def->hasUses() && (DeadIfUnused(def) || def->block()->isMarked());
}

// Similar to IsDiscardable(), but additionally allows effectful instructions.
bool js::jit::IsDiscardableAllowEffectful(const MDefinition* def) {
 return !def->hasUses() &&
        (DeadIfUnusedAllowEffectful(def) || def->block()->isMarked());
}

// Instructions are useless if they are unused and have no side effects.
// This pass eliminates useless instructions.
// The graph itself is unchanged.
bool jit::EliminateDeadCode(const MIRGenerator* mir, MIRGraph& graph) {
 // Traverse in postorder so that we hit uses before definitions.
 // Traverse instruction list backwards for the same reason.
 for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
      block++) {
   if (mir->shouldCancel("Eliminate Dead Code (main loop)")) {
     return false;
   }

   // Remove unused instructions.
   for (MInstructionReverseIterator iter = block->rbegin();
        iter != block->rend();) {
     MInstruction* inst = *iter++;
     if (js::jit::IsDiscardable(inst)) {
       block->discard(inst);
     }
   }
 }

 return true;
}

static inline bool IsPhiObservable(MPhi* phi, Observability observe) {
 // If the phi has uses which are not reflected in SSA, then behavior in the
 // interpreter may be affected by removing the phi.
 if (phi->isImplicitlyUsed()) {
   return true;
 }

 // Check for uses of this phi node outside of other phi nodes.
 // Note that, initially, we skip reading resume points, which we
 // don't count as actual uses. If the only uses are resume points,
 // then the SSA name is never consumed by the program.  However,
 // after optimizations have been performed, it's possible that the
 // actual uses in the program have been (incorrectly) optimized
 // away, so we must be more conservative and consider resume
 // points as well.
 for (MUseIterator iter(phi->usesBegin()); iter != phi->usesEnd(); iter++) {
   MNode* consumer = iter->consumer();
   if (consumer->isResumePoint()) {
     MResumePoint* resume = consumer->toResumePoint();
     if (observe == ConservativeObservability) {
       return true;
     }
     if (resume->isObservableOperand(*iter)) {
       return true;
     }
   } else {
     MDefinition* def = consumer->toDefinition();
     if (!def->isPhi()) {
       return true;
     }
   }
 }

 return false;
}

// Handles cases like:
//    x is phi(a, x) --> a
//    x is phi(a, a) --> a
static inline MDefinition* IsPhiRedundant(MPhi* phi) {
 MDefinition* first = phi->operandIfRedundant();
 if (first == nullptr) {
   return nullptr;
 }

 // Propagate the ImplicitlyUsed flag if |phi| is replaced with another phi.
 if (phi->isImplicitlyUsed()) {
   first->setImplicitlyUsedUnchecked();
 }

 return first;
}

bool jit::EliminatePhis(const MIRGenerator* mir, MIRGraph& graph,
                       Observability observe) {
 // Eliminates redundant or unobservable phis from the graph.  A
 // redundant phi is something like b = phi(a, a) or b = phi(a, b),
 // both of which can be replaced with a.  An unobservable phi is
 // one that whose value is never used in the program.
 //
 // Note that we must be careful not to eliminate phis representing
 // values that the interpreter will require later.  When the graph
 // is first constructed, we can be more aggressive, because there
 // is a greater correspondence between the CFG and the bytecode.
 // After optimizations such as GVN have been performed, however,
 // the bytecode and CFG may not correspond as closely to one
 // another.  In that case, we must be more conservative.  The flag
 // |conservativeObservability| is used to indicate that eliminate
 // phis is being run after some optimizations have been performed,
 // and thus we should use more conservative rules about
 // observability.  The particular danger is that we can optimize
 // away uses of a phi because we think they are not executable,
 // but the foundation for that assumption is false TI information
 // that will eventually be invalidated.  Therefore, if
 // |conservativeObservability| is set, we will consider any use
 // from a resume point to be observable.  Otherwise, we demand a
 // use from an actual instruction.

 Vector<MPhi*, 16, SystemAllocPolicy> worklist;

 // Add all observable phis to a worklist. We use the "in worklist" bit to
 // mean "this phi is live".
 for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
      block++) {
   MPhiIterator iter = block->phisBegin();
   while (iter != block->phisEnd()) {
     MPhi* phi = *iter++;

     if (mir->shouldCancel("Eliminate Phis (populate loop)")) {
       return false;
     }

     // Flag all as unused, only observable phis would be marked as used
     // when processed by the work list.
     phi->setUnused();

     // If the phi is redundant, remove it here.
     if (MDefinition* redundant = IsPhiRedundant(phi)) {
       phi->justReplaceAllUsesWith(redundant);
       block->discardPhi(phi);
       continue;
     }

     // Enqueue observable Phis.
     if (IsPhiObservable(phi, observe)) {
       phi->setInWorklist();
       if (!worklist.append(phi)) {
         return false;
       }
     }
   }
 }

 // Iteratively mark all phis reachable from live phis.
 while (!worklist.empty()) {
   if (mir->shouldCancel("Eliminate Phis (worklist)")) {
     return false;
   }

   MPhi* phi = worklist.popCopy();
   MOZ_ASSERT(phi->isUnused());
   phi->setNotInWorklist();

   // The removal of Phis can produce newly redundant phis.
   if (MDefinition* redundant = IsPhiRedundant(phi)) {
     // Add to the worklist the used phis which are impacted.
     for (MUseDefIterator it(phi); it; it++) {
       if (it.def()->isPhi()) {
         MPhi* use = it.def()->toPhi();
         if (!use->isUnused()) {
           use->setUnusedUnchecked();
           use->setInWorklist();
           if (!worklist.append(use)) {
             return false;
           }
         }
       }
     }
     phi->justReplaceAllUsesWith(redundant);
   } else {
     // Otherwise flag them as used.
     phi->setNotUnused();
   }

   // The current phi is/was used, so all its operands are used.
   for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
     MDefinition* in = phi->getOperand(i);
     if (!in->isPhi() || !in->isUnused() || in->isInWorklist()) {
       continue;
     }
     in->setInWorklist();
     if (!worklist.append(in->toPhi())) {
       return false;
     }
   }
 }

 // Sweep dead phis.
 for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
      block++) {
   if (mir->shouldCancel("Eliminate Phis (sweep dead phis)")) {
     return false;
   }

   MPhiIterator iter = block->phisBegin();
   while (iter != block->phisEnd()) {
     MPhi* phi = *iter++;
     if (phi->isUnused()) {
       if (!phi->optimizeOutAllUses(graph.alloc())) {
         return false;
       }
       block->discardPhi(phi);
     }
   }
 }

 return true;
}

namespace {

// The type analysis algorithm inserts conversions and box/unbox instructions
// to make the IR graph well-typed for future passes.
//
// Phi adjustment: If a phi's inputs are all the same type, the phi is
// specialized to return that type.
//
// Input adjustment: Each input is asked to apply conversion operations to its
// inputs. This may include Box, Unbox, or other instruction-specific type
// conversion operations.
//
class TypeAnalyzer {
 const MIRGenerator* mir;
 MIRGraph& graph;
 Vector<MPhi*, 0, SystemAllocPolicy> phiWorklist_;

 TempAllocator& alloc() const { return graph.alloc(); }

 bool addPhiToWorklist(MPhi* phi) {
   if (phi->isInWorklist()) {
     return true;
   }
   if (!phiWorklist_.append(phi)) {
     return false;
   }
   phi->setInWorklist();
   return true;
 }
 MPhi* popPhi() {
   MPhi* phi = phiWorklist_.popCopy();
   phi->setNotInWorklist();
   return phi;
 }

 [[nodiscard]] bool propagateAllPhiSpecializations();

 bool respecialize(MPhi* phi, MIRType type);
 bool propagateSpecialization(MPhi* phi);
 bool specializePhis();
 bool specializeOsrOnlyPhis();
 void replaceRedundantPhi(MPhi* phi);
 bool adjustPhiInputs(MPhi* phi);
 bool adjustInputs(MDefinition* def);
 bool insertConversions();

 bool checkFloatCoherency();
 bool graphContainsFloat32();
 bool markPhiConsumers();
 bool markPhiProducers();
 bool specializeValidFloatOps();
 bool tryEmitFloatOperations();
 bool propagateUnbox();

 bool shouldSpecializeOsrPhis() const;
 MIRType guessPhiType(MPhi* phi) const;

public:
 TypeAnalyzer(const MIRGenerator* mir, MIRGraph& graph)
     : mir(mir), graph(graph) {}

 bool analyze();
};

} /* anonymous namespace */

bool TypeAnalyzer::shouldSpecializeOsrPhis() const {
 // [SMDOC] OSR Phi Type Specialization
 //
 // Without special handling for OSR phis, we end up with unspecialized phis
 // (MIRType::Value) in the loop (pre)header and other blocks, resulting in
 // unnecessary boxing and unboxing in the loop body.
 //
 // To fix this, phi type specialization needs special code to deal with the
 // OSR entry block. Recall that OSR results in the following basic block
 // structure:
 //
 //  +------------------+                 +-----------------+
 //  | Code before loop |                 | OSR entry block |
 //  +------------------+                 +-----------------+
 //          |                                       |
 //          |                                       |
 //          |           +---------------+           |
 //          +---------> | OSR preheader | <---------+
 //                      +---------------+
 //                              |
 //                              V
 //                      +---------------+
 //                      | Loop header   |<-----+
 //                      +---------------+      |
 //                              |              |
 //                             ...             |
 //                              |              |
 //                      +---------------+      |
 //                      | Loop backedge |------+
 //                      +---------------+
 //
 // OSR phi specialization happens in three steps:
 //
 // (1) Specialize phis but ignore MOsrValue phi inputs. In other words,
 //     pretend the OSR entry block doesn't exist. See guessPhiType.
 //
 // (2) Once phi specialization is done, look at the types of loop header phis
 //     and add these types to the corresponding preheader phis. This way, the
 //     types of the preheader phis are based on the code before the loop and
 //     the code in the loop body. These are exactly the types we expect for
 //     the OSR Values. See the last part of TypeAnalyzer::specializePhis.
 //
 // (3) For type-specialized preheader phis, add guard/unbox instructions to
 //     the OSR entry block to guard the incoming Value indeed has this type.
 //     This happens in:
 //
 //     * TypeAnalyzer::adjustPhiInputs: adds a fallible unbox for values that
 //       can be unboxed.
 //
 //     * TypeAnalyzer::replaceRedundantPhi: adds a type guard for values that
 //       can't be unboxed (null/undefined/magic Values).
 if (!graph.osrBlock()) {
   return false;
 }

 return !mir->outerInfo().hadSpeculativePhiBailout();
}

// Try to specialize this phi based on its non-cyclic inputs.
MIRType TypeAnalyzer::guessPhiType(MPhi* phi) const {
#ifdef DEBUG
 // Check that different magic constants aren't flowing together. Ignore
 // JS_OPTIMIZED_OUT, since an operand could be legitimately optimized
 // away.
 MIRType magicType = MIRType::None;
 for (size_t i = 0; i < phi->numOperands(); i++) {
   MDefinition* in = phi->getOperand(i);
   if (in->type() == MIRType::MagicHole ||
       in->type() == MIRType::MagicIsConstructing) {
     if (magicType == MIRType::None) {
       magicType = in->type();
     }
     MOZ_ASSERT(magicType == in->type());
   }
 }
#endif

 MIRType type = MIRType::None;
 bool convertibleToFloat32 = false;
 bool hasOSRValueInput = false;
 DebugOnly<bool> hasSpecializableInput = false;
 for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
   MDefinition* in = phi->getOperand(i);
   if (in->isPhi()) {
     hasSpecializableInput = true;
     if (!in->toPhi()->triedToSpecialize()) {
       continue;
     }
     if (in->type() == MIRType::None) {
       // The operand is a phi we tried to specialize, but we were
       // unable to guess its type. propagateSpecialization will
       // propagate the type to this phi when it becomes known.
       continue;
     }
   }

   // See shouldSpecializeOsrPhis comment. This is the first step mentioned
   // there.
   if (shouldSpecializeOsrPhis() && in->isOsrValue()) {
     hasOSRValueInput = true;
     hasSpecializableInput = true;
     continue;
   }

   if (type == MIRType::None) {
     type = in->type();
     if (in->canProduceFloat32() &&
         !mir->outerInfo().hadSpeculativePhiBailout()) {
       convertibleToFloat32 = true;
     }
     continue;
   }

   if (type == in->type()) {
     convertibleToFloat32 = convertibleToFloat32 && in->canProduceFloat32();
   } else {
     if (convertibleToFloat32 && in->type() == MIRType::Float32) {
       // If we only saw definitions that can be converted into Float32 before
       // and encounter a Float32 value, promote previous values to Float32
       type = MIRType::Float32;
     } else if (IsTypeRepresentableAsDouble(type) &&
                IsTypeRepresentableAsDouble(in->type())) {
       // Specialize phis with int32 and double operands as double.
       type = MIRType::Double;
       convertibleToFloat32 = convertibleToFloat32 && in->canProduceFloat32();
     } else {
       return MIRType::Value;
     }
   }
 }

 if (hasOSRValueInput && type == MIRType::Float32) {
   // TODO(post-Warp): simplify float32 handling in this function or (better)
   // make the float32 analysis a stand-alone optimization pass instead of
   // complicating type analysis. See bug 1655773.
   type = MIRType::Double;
 }

 MOZ_ASSERT_IF(type == MIRType::None, hasSpecializableInput);
 return type;
}

bool TypeAnalyzer::respecialize(MPhi* phi, MIRType type) {
 if (phi->type() == type) {
   return true;
 }
 phi->specialize(type);
 return addPhiToWorklist(phi);
}

bool TypeAnalyzer::propagateSpecialization(MPhi* phi) {
 MOZ_ASSERT(phi->type() != MIRType::None);

 // Verify that this specialization matches any phis depending on it.
 for (MUseDefIterator iter(phi); iter; iter++) {
   if (!iter.def()->isPhi()) {
     continue;
   }
   MPhi* use = iter.def()->toPhi();
   if (!use->triedToSpecialize()) {
     continue;
   }
   if (use->type() == MIRType::None) {
     // We tried to specialize this phi, but were unable to guess its
     // type. Now that we know the type of one of its operands, we can
     // specialize it. If it can't be specialized as float32, specialize
     // as double.
     MIRType type = phi->type();
     if (type == MIRType::Float32 && !use->canProduceFloat32()) {
       type = MIRType::Double;
     }
     if (!respecialize(use, type)) {
       return false;
     }
     continue;
   }
   if (use->type() != phi->type()) {
     // Specialize phis with int32 that can be converted to float and float
     // operands as floats.
     if ((use->type() == MIRType::Int32 && use->canProduceFloat32() &&
          phi->type() == MIRType::Float32) ||
         (phi->type() == MIRType::Int32 && phi->canProduceFloat32() &&
          use->type() == MIRType::Float32)) {
       if (!respecialize(use, MIRType::Float32)) {
         return false;
       }
       continue;
     }

     // Specialize phis with int32 and double operands as double.
     if (IsTypeRepresentableAsDouble(use->type()) &&
         IsTypeRepresentableAsDouble(phi->type())) {
       if (!respecialize(use, MIRType::Double)) {
         return false;
       }
       continue;
     }

     // This phi in our use chain can now no longer be specialized.
     if (!respecialize(use, MIRType::Value)) {
       return false;
     }
   }
 }

 return true;
}

bool TypeAnalyzer::propagateAllPhiSpecializations() {
 while (!phiWorklist_.empty()) {
   if (mir->shouldCancel("Specialize Phis (worklist)")) {
     return false;
   }

   MPhi* phi = popPhi();
   if (!propagateSpecialization(phi)) {
     return false;
   }
 }

 return true;
}

// If branch pruning removes the path from the entry block to the OSR
// preheader, we may have phis (or chains of phis) with no operands
// other than OsrValues. These phis will still have MIRType::None.
// Since we don't have any information about them, we specialize them
// as MIRType::Value.
bool TypeAnalyzer::specializeOsrOnlyPhis() {
 MOZ_ASSERT(graph.osrBlock());
 MOZ_ASSERT(graph.osrPreHeaderBlock()->numPredecessors() == 1);

 for (PostorderIterator block(graph.poBegin()); block != graph.poEnd();
      block++) {
   if (mir->shouldCancel("Specialize osr-only phis (main loop)")) {
     return false;
   }

   for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
     if (mir->shouldCancel("Specialize osr-only phis (inner loop)")) {
       return false;
     }

     if (phi->type() == MIRType::None) {
       phi->specialize(MIRType::Value);
     }
   }
 }
 return true;
}

bool TypeAnalyzer::specializePhis() {
 for (PostorderIterator block(graph.poBegin()); block != graph.poEnd();
      block++) {
   if (mir->shouldCancel("Specialize Phis (main loop)")) {
     return false;
   }

   for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
     if (mir->shouldCancel("Specialize Phis (inner loop)")) {
       return false;
     }

     MIRType type = guessPhiType(*phi);
     phi->specialize(type);
     if (type == MIRType::None) {
       // We tried to guess the type but failed because all operands are
       // phis we still have to visit. Set the triedToSpecialize flag but
       // don't propagate the type to other phis, propagateSpecialization
       // will do that once we know the type of one of the operands.
       continue;
     }
     if (!propagateSpecialization(*phi)) {
       return false;
     }
   }
 }

 if (!propagateAllPhiSpecializations()) {
   return false;
 }

 if (shouldSpecializeOsrPhis()) {
   // See shouldSpecializeOsrPhis comment. This is the second step, propagating
   // loop header phi types to preheader phis.
   MBasicBlock* preHeader = graph.osrPreHeaderBlock();
   MBasicBlock* header = preHeader->getSingleSuccessor();

   if (preHeader->numPredecessors() == 1) {
     MOZ_ASSERT(preHeader->getPredecessor(0) == graph.osrBlock());
     // Branch pruning has removed the path from the entry block
     // to the preheader. Specialize any phis with no non-osr inputs.
     if (!specializeOsrOnlyPhis()) {
       return false;
     }
   } else if (header->isLoopHeader()) {
     for (MPhiIterator phi(header->phisBegin()); phi != header->phisEnd();
          phi++) {
       MPhi* preHeaderPhi = phi->getOperand(0)->toPhi();
       MOZ_ASSERT(preHeaderPhi->block() == preHeader);

       if (preHeaderPhi->type() == MIRType::Value) {
         // Already includes everything.
         continue;
       }

       MIRType loopType = phi->type();
       if (!respecialize(preHeaderPhi, loopType)) {
         return false;
       }
     }
     if (!propagateAllPhiSpecializations()) {
       return false;
     }
   } else {
     // Edge case: there is no backedge in this loop. This can happen
     // if the header is a 'pending' loop header when control flow in
     // the loop body is terminated unconditionally, or if a block
     // that dominates the backedge unconditionally bails out. In
     // this case the header only has the preheader as predecessor
     // and we don't need to do anything.
     MOZ_ASSERT(header->numPredecessors() == 1);
   }
 }

 MOZ_ASSERT(phiWorklist_.empty());
 return true;
}

bool TypeAnalyzer::adjustPhiInputs(MPhi* phi) {
 MIRType phiType = phi->type();
 MOZ_ASSERT(phiType != MIRType::None);

 // If we specialized a type that's not Value, there are 3 cases:
 // 1. Every input is of that type.
 // 2. Every observed input is of that type (i.e., some inputs haven't been
 // executed yet).
 // 3. Inputs were numbers, and was specialized to floating point type.
 if (phiType != MIRType::Value) {
   for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
     MDefinition* in = phi->getOperand(i);
     if (in->type() == phiType) {
       continue;
     }

     if (in->isBox() && in->toBox()->input()->type() == phiType) {
       phi->replaceOperand(i, in->toBox()->input());
       continue;
     }

     if (!alloc().ensureBallast()) {
       return false;
     }

     MBasicBlock* predecessor = phi->block()->getPredecessor(i);

     MInstruction* replacement;
     if (IsFloatingPointType(phiType) &&
         IsTypeRepresentableAsDouble(in->type())) {
       // Convert number operands to |phiType|.
       if (phiType == MIRType::Double) {
         replacement = MToDouble::New(alloc(), in);
       } else {
         MOZ_ASSERT(phiType == MIRType::Float32);
         replacement = MToFloat32::New(alloc(), in);
       }
     } else {
       // If we know this branch will fail to convert to phiType, insert a box
       // that'll immediately fail in the fallible unbox below.
       if (in->type() != MIRType::Value) {
         auto* box = MBox::New(alloc(), in);
         predecessor->insertAtEnd(box);
         in = box;
       }

       // Be optimistic and insert unboxes when the operand is a value.
       if (phiType == MIRType::Float32) {
         // Float32 is unboxed as Double, then converted.
         auto* unbox =
             MUnbox::New(alloc(), in, MIRType::Double, MUnbox::Fallible);
         unbox->setBailoutKind(BailoutKind::SpeculativePhi);
         predecessor->insertAtEnd(unbox);
         replacement = MToFloat32::New(alloc(), unbox);
       } else {
         replacement = MUnbox::New(alloc(), in, phiType, MUnbox::Fallible);
         replacement->setBailoutKind(BailoutKind::SpeculativePhi);
       }
     }
     MOZ_ASSERT(replacement->type() == phiType);

     predecessor->insertAtEnd(replacement);
     phi->replaceOperand(i, replacement);
   }

   return true;
 }

 // Box every typed input.
 for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
   MDefinition* in = phi->getOperand(i);
   if (in->type() == MIRType::Value) {
     continue;
   }

   // The input is being explicitly unboxed, so sneak past and grab the
   // original box. Don't bother optimizing if magic values are involved.
   if (in->isUnbox()) {
     MDefinition* unboxInput = in->toUnbox()->input();
     if (!IsMagicType(unboxInput->type()) && phi->typeIncludes(unboxInput)) {
       in = in->toUnbox()->input();
     }
   }

   if (in->type() != MIRType::Value) {
     if (!alloc().ensureBallast()) {
       return false;
     }

     MBasicBlock* pred = phi->block()->getPredecessor(i);
     in = BoxAt(alloc(), pred->lastIns(), in);
   }

   phi->replaceOperand(i, in);
 }

 return true;
}

bool TypeAnalyzer::adjustInputs(MDefinition* def) {
 // Definitions such as MPhi have no type policy.
 if (!def->isInstruction()) {
   return true;
 }

 MInstruction* ins = def->toInstruction();
 const TypePolicy* policy = ins->typePolicy();
 if (policy && !policy->adjustInputs(alloc(), ins)) {
   return false;
 }
 return true;
}

void TypeAnalyzer::replaceRedundantPhi(MPhi* phi) {
 MBasicBlock* block = phi->block();
 js::Value v;
 switch (phi->type()) {
   case MIRType::Undefined:
     v = UndefinedValue();
     break;
   case MIRType::Null:
     v = NullValue();
     break;
   case MIRType::MagicOptimizedOut:
     v = MagicValue(JS_OPTIMIZED_OUT);
     break;
   case MIRType::MagicUninitializedLexical:
     v = MagicValue(JS_UNINITIALIZED_LEXICAL);
     break;
   case MIRType::MagicIsConstructing:
     v = MagicValue(JS_IS_CONSTRUCTING);
     break;
   case MIRType::MagicHole:
   default:
     MOZ_CRASH("unexpected type");
 }
 MConstant* c = MConstant::New(alloc(), v);
 // The instruction pass will insert the box
 block->insertBefore(*(block->begin()), c);
 phi->justReplaceAllUsesWith(c);

 if (shouldSpecializeOsrPhis()) {
   // See shouldSpecializeOsrPhis comment. This is part of the third step,
   // guard the incoming MOsrValue is of this type.
   for (uint32_t i = 0; i < phi->numOperands(); i++) {
     MDefinition* def = phi->getOperand(i);
     if (def->type() != phi->type()) {
       MOZ_ASSERT(def->isOsrValue() || def->isPhi());
       MOZ_ASSERT(def->type() == MIRType::Value);
       MGuardValue* guard = MGuardValue::New(alloc(), def, v);
       guard->setBailoutKind(BailoutKind::SpeculativePhi);
       def->block()->insertBefore(def->block()->lastIns(), guard);
     }
   }
 }
}

bool TypeAnalyzer::insertConversions() {
 // Instructions are processed in reverse postorder: all uses are defs are
 // seen before uses. This ensures that output adjustment (which may rewrite
 // inputs of uses) does not conflict with input adjustment.
 for (ReversePostorderIterator block(graph.rpoBegin());
      block != graph.rpoEnd(); block++) {
   if (mir->shouldCancel("Insert Conversions")) {
     return false;
   }

   for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd());
        iter != end;) {
     MPhi* phi = *iter++;
     if (IsNullOrUndefined(phi->type()) || IsMagicType(phi->type())) {
       // We can replace this phi with a constant.
       if (!alloc().ensureBallast()) {
         return false;
       }
       replaceRedundantPhi(phi);
       block->discardPhi(phi);
     } else {
       if (!adjustPhiInputs(phi)) {
         return false;
       }
     }
   }

   // AdjustInputs can add/remove/mutate instructions before and after the
   // current instruction. Only increment the iterator after it is finished.
   for (MInstructionIterator iter(block->begin()); iter != block->end();
        iter++) {
     if (!alloc().ensureBallast()) {
       return false;
     }

     if (!adjustInputs(*iter)) {
       return false;
     }
   }
 }
 return true;
}

/* clang-format off */
//
// This function tries to emit Float32 specialized operations whenever it's possible.
// MIR nodes are flagged as:
// - Producers, when they can create Float32 that might need to be coerced into a Double.
//   Loads in Float32 arrays and conversions to Float32 are producers.
// - Consumers, when they can have Float32 as inputs and validate a legal use of a Float32.
//   Stores in Float32 arrays and conversions to Float32 are consumers.
// - Float32 commutative, when using the Float32 instruction instead of the Double instruction
//   does not result in a compound loss of precision. This is the case for +, -, /, * with 2
//   operands, for instance. However, an addition with 3 operands is not commutative anymore,
//   so an intermediate coercion is needed.
// Except for phis, all these flags are known after Ion building, so they cannot change during
// the process.
//
// The idea behind the algorithm is easy: whenever we can prove that a commutative operation
// has only producers as inputs and consumers as uses, we can specialize the operation as a
// float32 operation. Otherwise, we have to convert all float32 inputs to doubles. Even
// if a lot of conversions are produced, GVN will take care of eliminating the redundant ones.
//
// Phis have a special status. Phis need to be flagged as producers or consumers as they can
// be inputs or outputs of commutative instructions. Fortunately, producers and consumers
// properties are such that we can deduce the property using all non phis inputs first (which form
// an initial phi graph) and then propagate all properties from one phi to another using a
// fixed point algorithm. The algorithm is ensured to terminate as each iteration has less or as
// many flagged phis as the previous iteration (so the worst steady state case is all phis being
// flagged as false).
//
// In a nutshell, the algorithm applies three passes:
// 1 - Determine which phis are consumers. Each phi gets an initial value by making a global AND on
// all its non-phi inputs. Then each phi propagates its value to other phis. If after propagation,
// the flag value changed, we have to reapply the algorithm on all phi operands, as a phi is a
// consumer if all of its uses are consumers.
// 2 - Determine which phis are producers. It's the same algorithm, except that we have to reapply
// the algorithm on all phi uses, as a phi is a producer if all of its operands are producers.
// 3 - Go through all commutative operations and ensure their inputs are all producers and their
// uses are all consumers.
//
/* clang-format on */
bool TypeAnalyzer::markPhiConsumers() {
 MOZ_ASSERT(phiWorklist_.empty());

 // Iterate in postorder so worklist is initialized to RPO.
 for (PostorderIterator block(graph.poBegin()); block != graph.poEnd();
      ++block) {
   if (mir->shouldCancel(
           "Ensure Float32 commutativity - Consumer Phis - Initial state")) {
     return false;
   }

   for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); ++phi) {
     MOZ_ASSERT(!phi->isInWorklist());
     bool canConsumeFloat32 = !phi->isImplicitlyUsed();
     for (MUseDefIterator use(*phi); canConsumeFloat32 && use; use++) {
       MDefinition* usedef = use.def();
       canConsumeFloat32 &=
           usedef->isPhi() || usedef->canConsumeFloat32(use.use());
     }
     phi->setCanConsumeFloat32(canConsumeFloat32);
     if (canConsumeFloat32 && !addPhiToWorklist(*phi)) {
       return false;
     }
   }
 }

 while (!phiWorklist_.empty()) {
   if (mir->shouldCancel(
           "Ensure Float32 commutativity - Consumer Phis - Fixed point")) {
     return false;
   }

   MPhi* phi = popPhi();
   MOZ_ASSERT(phi->canConsumeFloat32(nullptr /* unused */));

   bool validConsumer = true;
   for (MUseDefIterator use(phi); use; use++) {
     MDefinition* def = use.def();
     if (def->isPhi() && !def->canConsumeFloat32(use.use())) {
       validConsumer = false;
       break;
     }
   }

   if (validConsumer) {
     continue;
   }

   // Propagate invalidated phis
   phi->setCanConsumeFloat32(false);
   for (size_t i = 0, e = phi->numOperands(); i < e; ++i) {
     MDefinition* input = phi->getOperand(i);
     if (input->isPhi() && !input->isInWorklist() &&
         input->canConsumeFloat32(nullptr /* unused */)) {
       if (!addPhiToWorklist(input->toPhi())) {
         return false;
       }
     }
   }
 }
 return true;
}

bool TypeAnalyzer::markPhiProducers() {
 MOZ_ASSERT(phiWorklist_.empty());

 // Iterate in reverse postorder so worklist is initialized to PO.
 for (ReversePostorderIterator block(graph.rpoBegin());
      block != graph.rpoEnd(); ++block) {
   if (mir->shouldCancel(
           "Ensure Float32 commutativity - Producer Phis - initial state")) {
     return false;
   }

   for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); ++phi) {
     MOZ_ASSERT(!phi->isInWorklist());
     bool canProduceFloat32 = true;
     for (size_t i = 0, e = phi->numOperands(); canProduceFloat32 && i < e;
          ++i) {
       MDefinition* input = phi->getOperand(i);
       canProduceFloat32 &= input->isPhi() || input->canProduceFloat32();
     }
     phi->setCanProduceFloat32(canProduceFloat32);
     if (canProduceFloat32 && !addPhiToWorklist(*phi)) {
       return false;
     }
   }
 }

 while (!phiWorklist_.empty()) {
   if (mir->shouldCancel(
           "Ensure Float32 commutativity - Producer Phis - Fixed point")) {
     return false;
   }

   MPhi* phi = popPhi();
   MOZ_ASSERT(phi->canProduceFloat32());

   bool validProducer = true;
   for (size_t i = 0, e = phi->numOperands(); i < e; ++i) {
     MDefinition* input = phi->getOperand(i);
     if (input->isPhi() && !input->canProduceFloat32()) {
       validProducer = false;
       break;
     }
   }

   if (validProducer) {
     continue;
   }

   // Propagate invalidated phis
   phi->setCanProduceFloat32(false);
   for (MUseDefIterator use(phi); use; use++) {
     MDefinition* def = use.def();
     if (def->isPhi() && !def->isInWorklist() && def->canProduceFloat32()) {
       if (!addPhiToWorklist(def->toPhi())) {
         return false;
       }
     }
   }
 }
 return true;
}

bool TypeAnalyzer::specializeValidFloatOps() {
 for (ReversePostorderIterator block(graph.rpoBegin());
      block != graph.rpoEnd(); ++block) {
   if (mir->shouldCancel("Ensure Float32 commutativity - Instructions")) {
     return false;
   }

   for (MInstructionIterator ins(block->begin()); ins != block->end(); ++ins) {
     if (!ins->isFloat32Commutative()) {
       continue;
     }

     if (ins->type() == MIRType::Float32) {
       continue;
     }

     if (!alloc().ensureBallast()) {
       return false;
     }

     // This call will try to specialize the instruction iff all uses are
     // consumers and all inputs are producers.
     ins->trySpecializeFloat32(alloc());
   }
 }
 return true;
}

bool TypeAnalyzer::graphContainsFloat32() {
 for (ReversePostorderIterator block(graph.rpoBegin());
      block != graph.rpoEnd(); ++block) {
   for (MDefinitionIterator def(*block); def; def++) {
     if (mir->shouldCancel(
             "Ensure Float32 commutativity - Graph contains Float32")) {
       return false;
     }

     if (def->type() == MIRType::Float32) {
       return true;
     }
   }
 }
 return false;
}

bool TypeAnalyzer::tryEmitFloatOperations() {
 // Asm.js uses the ahead of time type checks to specialize operations, no need
 // to check them again at this point.
 if (mir->compilingWasm()) {
   return true;
 }

 // Check ahead of time that there is at least one definition typed as Float32,
 // otherwise we don't need this pass.
 if (!graphContainsFloat32()) {
   return true;
 }

 // WarpBuilder skips over code that can't be reached except through
 // a catch block. Locals and arguments may be observable in such
 // code after bailing out, so we can't rely on seeing all uses.
 if (graph.hasTryBlock()) {
   return true;
 }

 if (!markPhiConsumers()) {
   return false;
 }
 if (!markPhiProducers()) {
   return false;
 }
 if (!specializeValidFloatOps()) {
   return false;
 }
 return true;
}

bool TypeAnalyzer::checkFloatCoherency() {
#ifdef DEBUG
 // Asserts that all Float32 instructions are flowing into Float32 consumers or
 // specialized operations
 for (ReversePostorderIterator block(graph.rpoBegin());
      block != graph.rpoEnd(); ++block) {
   if (mir->shouldCancel("Check Float32 coherency")) {
     return false;
   }

   for (MDefinitionIterator def(*block); def; def++) {
     if (def->type() != MIRType::Float32) {
       continue;
     }

     for (MUseDefIterator use(*def); use; use++) {
       MDefinition* consumer = use.def();
       MOZ_ASSERT(consumer->isConsistentFloat32Use(use.use()));
     }
   }
 }
#endif
 return true;
}

static bool HappensBefore(const MDefinition* earlier,
                         const MDefinition* later) {
 MOZ_ASSERT(earlier->block() == later->block());

 for (auto* ins : *earlier->block()) {
   if (ins == earlier) {
     return true;
   }
   if (ins == later) {
     return false;
   }
 }
 MOZ_CRASH("earlier and later are instructions in the block");
}

// Propagate type information from dominating unbox instructions.
//
// This optimization applies for example for self-hosted String.prototype
// functions.
//
// Example:
// ```
// String.prototype.id = function() {
//   // Strict mode to avoid ToObject on primitive this-values.
//   "use strict";
//
//   // Template string to apply ToString on the this-value.
//   return `${this}`;
// };
//
// function f(s) {
//   // Assume |s| is a string value.
//   return s.id();
// }
// ```
//
// Compiles into: (Graph after Scalar Replacement)
//
// ┌───────────────────────────────────────────────────────────────────────────┐
// │                             Block 0                                       │
// │ resumepoint 1 0 2 2                                                       │
// │ 0 parameter THIS_SLOT                                           Value     │
// │ 1 parameter 0                                                   Value     │
// │ 2 constant undefined                                            Undefined │
// │ 3 start                                                                   │
// │ 4 checkoverrecursed                                                       │
// │ 5 unbox parameter1 to String (fallible)                         String    │
// │ 6 constant object 1d908053e088 (String)                         Object    │
// │ 7 guardshape constant6:Object                                   Object    │
// │ 8 slots guardshape7:Object                                      Slots     │
// │ 9 loaddynamicslot slots8:Slots (slot 53)                        Value     │
// │ 10 constant 0x0                                                 Int32     │
// │ 11 unbox loaddynamicslot9 to Object (fallible)                  Object    │
// │ 12 nurseryobject                                                Object    │
// │ 13 guardspecificfunction unbox11:Object nurseryobject12:Object  Object    │
// │ 14 goto block1                                                            │
// └──────────────────────────────────┬────────────────────────────────────────┘
//                                    │
// ┌──────────────────────────────────▼────────────────────────────────────────┐
// │                               Block 1                                     │
// │ ((0)) resumepoint 15 1 15 15 | 1 13 1 0 2 2                               │
// │ 15 constant undefined                                           Undefined │
// │ 16 tostring parameter1:Value                                    String    │
// │ 18 goto block2                                                            │
// └──────────────────────────────────┬────────────────────────────────────────┘
//                                    │
//                     ┌──────────────▼──────────────┐
//                     │           Block 2           │
//                     │ resumepoint 16 1 0 2 2      │
//                     │ 19 return tostring16:String │
//                     └─────────────────────────────┘
//
// The Unbox instruction is used as a type guard. The ToString instruction
// doesn't use the type information from the preceding Unbox instruction and
// therefore has to assume its operand can be any value.
//
// When instead propagating the type information from the preceding Unbox
// instruction, this graph is constructed after the "Apply types" phase:
//
// ┌───────────────────────────────────────────────────────────────────────────┐
// │                             Block 0                                       │
// │ resumepoint 1 0 2 2                                                       │
// │ 0 parameter THIS_SLOT                                           Value     │
// │ 1 parameter 0                                                   Value     │
// │ 2 constant undefined                                            Undefined │
// │ 3 start                                                                   │
// │ 4 checkoverrecursed                                                       │
// │ 5 unbox parameter1 to String (fallible)                         String    │
// │ 6 constant object 1d908053e088 (String)                         Object    │
// │ 7 guardshape constant6:Object                                   Object    │
// │ 8 slots guardshape7:Object                                      Slots     │
// │ 9 loaddynamicslot slots8:Slots (slot 53)                        Value     │
// │ 10 constant 0x0                                                 Int32     │
// │ 11 unbox loaddynamicslot9 to Object (fallible)                  Object    │
// │ 12 nurseryobject                                                Object    │
// │ 13 guardspecificfunction unbox11:Object nurseryobject12:Object  Object    │
// │ 14 goto block1                                                            │
// └──────────────────────────────────┬────────────────────────────────────────┘
//                                    │
// ┌──────────────────────────────────▼────────────────────────────────────────┐
// │                               Block 1                                     │
// │ ((0)) resumepoint 15 1 15 15 | 1 13 1 0 2 2                               │
// │ 15 constant undefined                                           Undefined │
// │ 20 unbox parameter1 to String (fallible)                        String    │
// │ 16 tostring parameter1:Value                                    String    │
// │ 18 goto block2                                                            │
// └──────────────────────────────────┬────────────────────────────────────────┘
//                                    │
//                     ┌──────────────▼─────────────────────┐
//                     │           Block 2                  │
//                     │ resumepoint 16 1 0 2 2             │
//                     │ 21 box tostring16:String     Value │
//                     │ 19 return box21:Value              │
//                     └────────────────────────────────────┘
//
// GVN will later merge both Unbox instructions and fold away the ToString
// instruction, so we get this final graph:
//
// ┌───────────────────────────────────────────────────────────────────────────┐
// │                             Block 0                                       │
// │ resumepoint 1 0 2 2                                                       │
// │ 0 parameter THIS_SLOT                                           Value     │
// │ 1 parameter 0                                                   Value     │
// │ 2 constant undefined                                            Undefined │
// │ 3 start                                                                   │
// │ 4 checkoverrecursed                                                       │
// │ 5 unbox parameter1 to String (fallible)                         String    │
// │ 6 constant object 1d908053e088 (String)                         Object    │
// │ 7 guardshape constant6:Object                                   Object    │
// │ 8 slots guardshape7:Object                                      Slots     │
// │ 22 loaddynamicslotandunbox slots8:Slots (slot 53)               Object    │
// │ 11 nurseryobject                                                Object    │
// │ 12 guardspecificfunction load22:Object nurseryobject11:Object   Object    │
// │ 13 goto block1                                                            │
// └──────────────────────────────────┬────────────────────────────────────────┘
//                                    │
// ┌──────────────────────────────────▼────────────────────────────────────────┐
// │                               Block 1                                     │
// │ ((0)) resumepoint 2 1 2 2 | 1 12 1 0 2 2                                  │
// │ 14 goto block2                                                            │
// └──────────────────────────────────┬────────────────────────────────────────┘
//                                    │
//                     ┌──────────────▼─────────────────────┐
//                     │           Block 2                  │
//                     │ resumepoint 5 1 0 2 2              │
//                     │ 15 return parameter1:Value         │
//                     └────────────────────────────────────┘
//
bool TypeAnalyzer::propagateUnbox() {
 // Visit the blocks in post-order, so that the type information of the closest
 // unbox operation is used.
 for (PostorderIterator block(graph.poBegin()); block != graph.poEnd();
      block++) {
   if (mir->shouldCancel("Propagate Unbox")) {
     return false;
   }

   // Iterate over all instructions to look for unbox instructions.
   for (MInstructionIterator iter(block->begin()); iter != block->end();
        iter++) {
     if (!iter->isUnbox()) {
       continue;
     }

     auto* unbox = iter->toUnbox();
     auto* input = unbox->input();

     // Ignore unbox operations on typed values.
     if (input->type() != MIRType::Value) {
       continue;
     }

     // Ignore unbox to floating point types, because propagating boxed Int32
     // values as Double can lead to repeated bailouts when later instructions
     // expect Int32 inputs.
     if (IsFloatingPointType(unbox->type())) {
       continue;
     }

     // Inspect other uses of |input| to propagate the unboxed type information
     // from |unbox|.
     for (auto uses = input->usesBegin(); uses != input->usesEnd();) {
       auto* use = *uses++;

       // Ignore resume points.
       if (!use->consumer()->isDefinition()) {
         continue;
       }
       auto* def = use->consumer()->toDefinition();

       // Ignore any unbox operations, including the current |unbox|.
       if (def->isUnbox()) {
         continue;
       }

       // Ignore phi nodes, because we don't yet support them.
       if (def->isPhi()) {
         continue;
       }

       // The unbox operation needs to happen before the other use, otherwise
       // we can't propagate the type information.
       if (unbox->block() == def->block()) {
         if (!HappensBefore(unbox, def)) {
           continue;
         }
       } else {
         if (!unbox->block()->dominates(def->block())) {
           continue;
         }
       }

       // Replace the use with |unbox|, so that GVN knows about the actual
       // value type and can more easily fold unnecessary operations. If the
       // instruction actually needs a boxed input, the BoxPolicy type policy
       // will simply unwrap the unbox instruction.
       use->replaceProducer(unbox);

       // The uses in the MIR graph no longer reflect the uses in the bytecode,
       // so we have to mark |input| as implicitly used.
       input->setImplicitlyUsedUnchecked();
     }
   }
 }
 return true;
}

bool TypeAnalyzer::analyze() {
 if (!tryEmitFloatOperations()) {
   return false;
 }
 if (!specializePhis()) {
   return false;
 }
 if (!propagateUnbox()) {
   return false;
 }
 if (!insertConversions()) {
   return false;
 }
 if (!checkFloatCoherency()) {
   return false;
 }
 return true;
}

bool jit::ApplyTypeInformation(const MIRGenerator* mir, MIRGraph& graph) {
 TypeAnalyzer analyzer(mir, graph);

 if (!analyzer.analyze()) {
   return false;
 }

 return true;
}

void jit::RenumberBlocks(MIRGraph& graph) {
 size_t id = 0;
 for (ReversePostorderIterator block(graph.rpoBegin());
      block != graph.rpoEnd(); block++) {
   block->setId(id++);
 }
}

// A utility for code which adds/deletes blocks. Renumber the remaining blocks,
// recompute dominators, and optionally recompute AliasAnalysis dependencies.
bool jit::AccountForCFGChanges(const MIRGenerator* mir, MIRGraph& graph,
                              bool updateAliasAnalysis,
                              bool underValueNumberer) {
 // Renumber the blocks and clear out the old dominator info.
 size_t id = 0;
 for (ReversePostorderIterator i(graph.rpoBegin()), e(graph.rpoEnd()); i != e;
      ++i) {
   i->clearDominatorInfo();
   i->setId(id++);
 }

 // Recompute dominator info.
 if (!BuildDominatorTree(mir, graph)) {
   return false;
 }

 // If needed, update alias analysis dependencies.
 if (updateAliasAnalysis) {
   if (!AliasAnalysis(mir, graph).analyze()) {
     return false;
   }
 }

 AssertExtendedGraphCoherency(graph, underValueNumberer);
 return true;
}

// Remove all blocks not marked with isMarked(). Unmark all remaining blocks.
// Alias analysis dependencies may be invalid after calling this function.
bool jit::RemoveUnmarkedBlocks(const MIRGenerator* mir, MIRGraph& graph,
                              uint32_t numMarkedBlocks) {
 if (numMarkedBlocks == graph.numBlocks()) {
   // If all blocks are marked, no blocks need removal. Just clear the
   // marks. We'll still need to update the dominator tree below though,
   // since we may have removed edges even if we didn't remove any blocks.
   graph.unmarkBlocks();
 } else {
   // As we are going to remove edges and basic blocks, we have to mark
   // instructions which would be needed by baseline if we were to
   // bailout.
   for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) {
     MBasicBlock* block = *it++;
     if (block->isMarked()) {
       continue;
     }

     if (!FlagAllOperandsAsImplicitlyUsed(mir, block)) {
       return false;
     }
   }

   // Find unmarked blocks and remove them.
   for (ReversePostorderIterator iter(graph.rpoBegin());
        iter != graph.rpoEnd();) {
     MBasicBlock* block = *iter++;

     if (block->isMarked()) {
       block->unmark();
       continue;
     }

     // The block is unreachable. Clear out the loop header flag, as
     // we're doing the sweep of a mark-and-sweep here, so we no longer
     // need to worry about whether an unmarked block is a loop or not.
     if (block->isLoopHeader()) {
       block->clearLoopHeader();
     }

     for (size_t i = 0, e = block->numSuccessors(); i != e; ++i) {
       block->getSuccessor(i)->removePredecessor(block);
     }
     graph.removeBlock(block);
   }
 }

 // Renumber the blocks and update the dominator tree.
 return AccountForCFGChanges(mir, graph, /*updateAliasAnalysis=*/false);
}

bool jit::BuildPhiReverseMapping(MIRGraph& graph) {
 // Build a mapping such that given a basic block, whose successor has one or
 // more phis, we can find our specific input to that phi. To make this fast
 // mapping work we rely on a specific property of our structured control
 // flow graph: For a block with phis, its predecessors each have only one
 // successor with phis. Consider each case:
 //   * Blocks with less than two predecessors cannot have phis.
 //   * Breaks. A break always has exactly one successor, and the break
 //             catch block has exactly one predecessor for each break, as
 //             well as a final predecessor for the actual loop exit.
 //   * Continues. A continue always has exactly one successor, and the
 //             continue catch block has exactly one predecessor for each
 //             continue, as well as a final predecessor for the actual
 //             loop continuation. The continue itself has exactly one
 //             successor.
 //   * An if. Each branch as exactly one predecessor.
 //   * A switch. Each branch has exactly one predecessor.
 //   * Loop tail. A new block is always created for the exit, and if a
 //             break statement is present, the exit block will forward
 //             directly to the break block.
 for (MBasicBlockIterator block(graph.begin()); block != graph.end();
      block++) {
   if (block->phisEmpty()) {
     continue;
   }

   // Assert on the above.
   for (size_t j = 0; j < block->numPredecessors(); j++) {
     MBasicBlock* pred = block->getPredecessor(j);

#ifdef DEBUG
     size_t numSuccessorsWithPhis = 0;
     for (size_t k = 0; k < pred->numSuccessors(); k++) {
       MBasicBlock* successor = pred->getSuccessor(k);
       if (!successor->phisEmpty()) {
         numSuccessorsWithPhis++;
       }
     }
     MOZ_ASSERT(numSuccessorsWithPhis <= 1);
#endif

     pred->setSuccessorWithPhis(*block, j);
   }
 }

 return true;
}

#ifdef DEBUG
static bool CheckSuccessorImpliesPredecessor(MBasicBlock* A, MBasicBlock* B) {
 // Assuming B = succ(A), verify A = pred(B).
 for (size_t i = 0; i < B->numPredecessors(); i++) {
   if (A == B->getPredecessor(i)) {
     return true;
   }
 }
 return false;
}

static bool CheckPredecessorImpliesSuccessor(MBasicBlock* A, MBasicBlock* B) {
 // Assuming B = pred(A), verify A = succ(B).
 for (size_t i = 0; i < B->numSuccessors(); i++) {
   if (A == B->getSuccessor(i)) {
     return true;
   }
 }
 return false;
}

// If you have issues with the usesBalance assertions, then define the macro
// _DEBUG_CHECK_OPERANDS_USES_BALANCE to spew information on the error output.
// This output can then be processed with the following awk script to filter and
// highlight which checks are missing or if there is an unexpected operand /
// use.
//
// define _DEBUG_CHECK_OPERANDS_USES_BALANCE 1
/*

$ ./js 2>stderr.log
$ gawk '
   /^==Check/ { context = ""; state = $2; }
   /^[a-z]/ { context = context "\n\t" $0; }
   /^==End/ {
     if (state == "Operand") {
       list[context] = list[context] - 1;
     } else if (state == "Use") {
       list[context] = list[context] + 1;
     }
   }
   END {
     for (ctx in list) {
       if (list[ctx] > 0) {
         print "Missing operand check", ctx, "\n"
       }
       if (list[ctx] < 0) {
         print "Missing use check", ctx, "\n"
       }
     };
   }'  < stderr.log

*/

static void CheckOperand(const MNode* consumer, const MUse* use,
                        int32_t* usesBalance) {
 MOZ_ASSERT(use->hasProducer());
 MDefinition* producer = use->producer();
 MOZ_ASSERT(!producer->isDiscarded());
 MOZ_ASSERT(producer->block() != nullptr);
 MOZ_ASSERT(use->consumer() == consumer);
#  ifdef _DEBUG_CHECK_OPERANDS_USES_BALANCE
 Fprinter print(stderr);
 print.printf("==Check Operand\n");
 use->producer()->dump(print);
 print.printf("  index: %zu\n", use->consumer()->indexOf(use));
 use->consumer()->dump(print);
 print.printf("==End\n");
#  endif
 --*usesBalance;
}

static void CheckUse(const MDefinition* producer, const MUse* use,
                    int32_t* usesBalance) {
 MOZ_ASSERT(!use->consumer()->block()->isDead());
 MOZ_ASSERT_IF(use->consumer()->isDefinition(),
               !use->consumer()->toDefinition()->isDiscarded());
 MOZ_ASSERT(use->consumer()->block() != nullptr);
 MOZ_ASSERT(use->consumer()->getOperand(use->index()) == producer);
#  ifdef _DEBUG_CHECK_OPERANDS_USES_BALANCE
 Fprinter print(stderr);
 print.printf("==Check Use\n");
 use->producer()->dump(print);
 print.printf("  index: %zu\n", use->consumer()->indexOf(use));
 use->consumer()->dump(print);
 print.printf("==End\n");
#  endif
 ++*usesBalance;
}

// To properly encode entry resume points, we have to ensure that all the
// operands of the entry resume point are located before the safeInsertTop
// location.
static void AssertOperandsBeforeSafeInsertTop(MResumePoint* resume) {
 MBasicBlock* block = resume->block();
 if (block == block->graph().osrBlock()) {
   return;
 }
 MInstruction* stop = block->safeInsertTop();
 for (size_t i = 0, e = resume->numOperands(); i < e; ++i) {
   MDefinition* def = resume->getOperand(i);
   if (def->block() != block) {
     continue;
   }
   if (def->isPhi()) {
     continue;
   }

   for (MInstructionIterator ins = block->begin(); true; ins++) {
     if (*ins == def) {
       break;
     }
     MOZ_ASSERT(
         *ins != stop,
         "Resume point operand located after the safeInsertTop location");
   }
 }
}
#endif  // DEBUG

void jit::AssertBasicGraphCoherency(MIRGraph& graph, bool force) {
#ifdef DEBUG
 if (!JitOptions.fullDebugChecks && !force) {
   return;
 }

 MOZ_ASSERT(graph.entryBlock()->numPredecessors() == 0);
 MOZ_ASSERT(graph.entryBlock()->phisEmpty());
 MOZ_ASSERT(!graph.entryBlock()->unreachable());

 if (MBasicBlock* osrBlock = graph.osrBlock()) {
   MOZ_ASSERT(osrBlock->numPredecessors() == 0);
   MOZ_ASSERT(osrBlock->phisEmpty());
   MOZ_ASSERT(osrBlock != graph.entryBlock());
   MOZ_ASSERT(!osrBlock->unreachable());
 }

 if (MResumePoint* resumePoint = graph.entryResumePoint()) {
   MOZ_ASSERT(resumePoint->block() == graph.entryBlock());
 }

 // Assert successor and predecessor list coherency.
 uint32_t count = 0;
 int32_t usesBalance = 0;
 for (MBasicBlockIterator block(graph.begin()); block != graph.end();
      block++) {
   count++;

   MOZ_ASSERT(&block->graph() == &graph);
   MOZ_ASSERT(!block->isDead());
   MOZ_ASSERT_IF(block->outerResumePoint() != nullptr,
                 block->entryResumePoint() != nullptr);

   for (size_t i = 0; i < block->numSuccessors(); i++) {
     MOZ_ASSERT(
         CheckSuccessorImpliesPredecessor(*block, block->getSuccessor(i)));
   }

   for (size_t i = 0; i < block->numPredecessors(); i++) {
     MOZ_ASSERT(
         CheckPredecessorImpliesSuccessor(*block, block->getPredecessor(i)));
   }

   if (MResumePoint* resume = block->entryResumePoint()) {
     MOZ_ASSERT(!resume->instruction());
     MOZ_ASSERT(resume->block() == *block);
     AssertOperandsBeforeSafeInsertTop(resume);
   }
   if (MResumePoint* resume = block->outerResumePoint()) {
     MOZ_ASSERT(!resume->instruction());
     MOZ_ASSERT(resume->block() == *block);
   }
   for (MResumePointIterator iter(block->resumePointsBegin());
        iter != block->resumePointsEnd(); iter++) {
     // We cannot yet assert that is there is no instruction then this is
     // the entry resume point because we are still storing resume points
     // in the InlinePropertyTable.
     MOZ_ASSERT_IF(iter->instruction(),
                   iter->instruction()->block() == *block);
     for (uint32_t i = 0, e = iter->numOperands(); i < e; i++) {
       CheckOperand(*iter, iter->getUseFor(i), &usesBalance);
     }
   }
   for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
     MOZ_ASSERT(phi->numOperands() == block->numPredecessors());
     MOZ_ASSERT(!phi->isRecoveredOnBailout());
     MOZ_ASSERT(phi->type() != MIRType::None);
     MOZ_ASSERT(phi->dependency() == nullptr);
   }
   for (MDefinitionIterator iter(*block); iter; iter++) {
     MOZ_ASSERT(iter->block() == *block);
     MOZ_ASSERT_IF(iter->hasUses(), iter->type() != MIRType::None);
     MOZ_ASSERT(!iter->isDiscarded());
     MOZ_ASSERT_IF(iter->isStart(),
                   *block == graph.entryBlock() || *block == graph.osrBlock());
     MOZ_ASSERT_IF(iter->isParameter(),
                   *block == graph.entryBlock() || *block == graph.osrBlock());
     MOZ_ASSERT_IF(iter->isOsrEntry(), *block == graph.osrBlock());
     MOZ_ASSERT_IF(iter->isOsrValue(), *block == graph.osrBlock());

     // Assert that use chains are valid for this instruction.
     for (uint32_t i = 0, end = iter->numOperands(); i < end; i++) {
       CheckOperand(*iter, iter->getUseFor(i), &usesBalance);
     }
     for (MUseIterator use(iter->usesBegin()); use != iter->usesEnd(); use++) {
       CheckUse(*iter, *use, &usesBalance);
     }

     if (iter->isInstruction()) {
       if (MResumePoint* resume = iter->toInstruction()->resumePoint()) {
         MOZ_ASSERT(resume->instruction() == *iter);
         MOZ_ASSERT(resume->block() == *block);
         MOZ_ASSERT(resume->block()->entryResumePoint() != nullptr);
       }
     }

     if (iter->isRecoveredOnBailout()) {
       MOZ_ASSERT(!iter->hasLiveDefUses());
     }
   }

   // The control instruction is not visited by the MDefinitionIterator.
   MControlInstruction* control = block->lastIns();
   MOZ_ASSERT(control->block() == *block);
   MOZ_ASSERT(!control->hasUses());
   MOZ_ASSERT(control->type() == MIRType::None);
   MOZ_ASSERT(!control->isDiscarded());
   MOZ_ASSERT(!control->isRecoveredOnBailout());
   MOZ_ASSERT(control->resumePoint() == nullptr);
   for (uint32_t i = 0, end = control->numOperands(); i < end; i++) {
     CheckOperand(control, control->getUseFor(i), &usesBalance);
   }
   for (size_t i = 0; i < control->numSuccessors(); i++) {
     MOZ_ASSERT(control->getSuccessor(i));
   }
 }

 // In case issues, see the _DEBUG_CHECK_OPERANDS_USES_BALANCE macro above.
 MOZ_ASSERT(usesBalance <= 0, "More use checks than operand checks");
 MOZ_ASSERT(usesBalance >= 0, "More operand checks than use checks");
 MOZ_ASSERT(graph.numBlocks() == count);
#endif
}

#ifdef DEBUG
static void AssertReversePostorder(MIRGraph& graph) {
 // Check that every block is visited after all its predecessors (except
 // backedges).
 for (ReversePostorderIterator iter(graph.rpoBegin()); iter != graph.rpoEnd();
      ++iter) {
   MBasicBlock* block = *iter;
   MOZ_ASSERT(!block->isMarked());

   for (size_t i = 0; i < block->numPredecessors(); i++) {
     MBasicBlock* pred = block->getPredecessor(i);
     if (!pred->isMarked()) {
       MOZ_ASSERT(pred->isLoopBackedge());
       MOZ_ASSERT(block->backedge() == pred);
     }
   }

   block->mark();
 }

 graph.unmarkBlocks();
}
#endif

#ifdef DEBUG
static void AssertDominatorTree(MIRGraph& graph) {
 // Check dominators.

 MOZ_ASSERT(graph.entryBlock()->immediateDominator() == graph.entryBlock());
 if (MBasicBlock* osrBlock = graph.osrBlock()) {
   MOZ_ASSERT(osrBlock->immediateDominator() == osrBlock);
 } else {
   MOZ_ASSERT(graph.entryBlock()->numDominated() == graph.numBlocks());
 }

 size_t i = graph.numBlocks();
 size_t totalNumDominated = 0;
 for (MBasicBlockIterator block(graph.begin()); block != graph.end();
      block++) {
   MOZ_ASSERT(block->dominates(*block));

   MBasicBlock* idom = block->immediateDominator();
   MOZ_ASSERT(idom->dominates(*block));
   MOZ_ASSERT(idom == *block || idom->id() < block->id());

   if (idom == *block) {
     totalNumDominated += block->numDominated();
   } else {
     bool foundInParent = false;
     for (size_t j = 0; j < idom->numImmediatelyDominatedBlocks(); j++) {
       if (idom->getImmediatelyDominatedBlock(j) == *block) {
         foundInParent = true;
         break;
       }
     }
     MOZ_ASSERT(foundInParent);
   }

   size_t numDominated = 1;
   for (size_t j = 0; j < block->numImmediatelyDominatedBlocks(); j++) {
     MBasicBlock* dom = block->getImmediatelyDominatedBlock(j);
     MOZ_ASSERT(block->dominates(dom));
     MOZ_ASSERT(dom->id() > block->id());
     MOZ_ASSERT(dom->immediateDominator() == *block);

     numDominated += dom->numDominated();
   }
   MOZ_ASSERT(block->numDominated() == numDominated);
   MOZ_ASSERT(block->numDominated() <= i);
   MOZ_ASSERT(block->numSuccessors() != 0 || block->numDominated() == 1);
   i--;
 }
 MOZ_ASSERT(i == 0);
 MOZ_ASSERT(totalNumDominated == graph.numBlocks());
}
#endif

void jit::AssertGraphCoherency(MIRGraph& graph, bool force) {
#ifdef DEBUG
 if (!JitOptions.checkGraphConsistency) {
   return;
 }
 if (!JitOptions.fullDebugChecks && !force) {
   return;
 }
 AssertBasicGraphCoherency(graph, force);
 AssertReversePostorder(graph);
#endif
}

#ifdef DEBUG
static bool IsResumableMIRType(MIRType type) {
 // see CodeGeneratorShared::encodeAllocation
 switch (type) {
   case MIRType::Undefined:
   case MIRType::Null:
   case MIRType::Boolean:
   case MIRType::Int32:
   case MIRType::Double:
   case MIRType::Float32:
   case MIRType::String:
   case MIRType::Symbol:
   case MIRType::BigInt:
   case MIRType::Object:
   case MIRType::Shape:
   case MIRType::MagicOptimizedOut:
   case MIRType::MagicUninitializedLexical:
   case MIRType::MagicIsConstructing:
   case MIRType::Value:
   case MIRType::Int64:
   case MIRType::IntPtr:
     return true;

   case MIRType::Simd128:
   case MIRType::MagicHole:
   case MIRType::None:
   case MIRType::Slots:
   case MIRType::Elements:
   case MIRType::Pointer:
   case MIRType::WasmAnyRef:
   case MIRType::WasmStructData:
   case MIRType::WasmArrayData:
   case MIRType::StackResults:
     return false;
 }
 MOZ_CRASH("Unknown MIRType.");
}

static void AssertResumableOperands(MNode* node) {
 for (size_t i = 0, e = node->numOperands(); i < e; ++i) {
   MDefinition* op = node->getOperand(i);
   if (op->isRecoveredOnBailout()) {
     continue;
   }
   MOZ_ASSERT(IsResumableMIRType(op->type()),
              "Resume point cannot encode its operands");
 }
}

static void AssertIfResumableInstruction(MDefinition* def) {
 if (!def->isRecoveredOnBailout()) {
   return;
 }
 AssertResumableOperands(def);
}

static void AssertResumePointDominatedByOperands(MResumePoint* resume) {
 for (size_t i = 0, e = resume->numOperands(); i < e; ++i) {
   MDefinition* op = resume->getOperand(i);
   MOZ_ASSERT(op->block()->dominates(resume->block()),
              "Resume point is not dominated by its operands");
 }
}
#endif  // DEBUG

// Checks the basic GraphCoherency but also other conditions that
// do not hold immediately (such as the fact that critical edges
// are split, or conditions related to wasm semantics)
void jit::AssertExtendedGraphCoherency(MIRGraph& graph, bool underValueNumberer,
                                      bool force) {
#ifdef DEBUG
 if (!JitOptions.checkGraphConsistency) {
   return;
 }
 if (!JitOptions.fullDebugChecks && !force) {
   return;
 }

 AssertGraphCoherency(graph, force);

 AssertDominatorTree(graph);

 DebugOnly<uint32_t> idx = 0;
 for (MBasicBlockIterator block(graph.begin()); block != graph.end();
      block++) {
   MOZ_ASSERT(block->id() == idx);
   ++idx;

   // No critical edges:
   if (block->numSuccessors() > 1) {
     for (size_t i = 0; i < block->numSuccessors(); i++) {
       MOZ_ASSERT(block->getSuccessor(i)->numPredecessors() == 1);
     }
   }

   if (block->isLoopHeader()) {
     if (underValueNumberer && block->numPredecessors() == 3) {
       // Fixup block.
       MOZ_ASSERT(block->getPredecessor(1)->numPredecessors() == 0);
       MOZ_ASSERT(graph.osrBlock(),
                  "Fixup blocks should only exists if we have an osr block.");
     } else {
       MOZ_ASSERT(block->numPredecessors() == 2);
     }
     MBasicBlock* backedge = block->backedge();
     MOZ_ASSERT(backedge->id() >= block->id());
     MOZ_ASSERT(backedge->numSuccessors() == 1);
     MOZ_ASSERT(backedge->getSuccessor(0) == *block);
   }

   if (!block->phisEmpty()) {
     for (size_t i = 0; i < block->numPredecessors(); i++) {
       MBasicBlock* pred = block->getPredecessor(i);
       MOZ_ASSERT(pred->successorWithPhis() == *block);
       MOZ_ASSERT(pred->positionInPhiSuccessor() == i);
     }
   }

   uint32_t successorWithPhis = 0;
   for (size_t i = 0; i < block->numSuccessors(); i++) {
     if (!block->getSuccessor(i)->phisEmpty()) {
       successorWithPhis++;
     }
   }

   MOZ_ASSERT(successorWithPhis <= 1);
   MOZ_ASSERT((successorWithPhis != 0) ==
              (block->successorWithPhis() != nullptr));

   // Verify that phi operands dominate the corresponding CFG predecessor
   // edges.
   for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd());
        iter != end; ++iter) {
     MPhi* phi = *iter;
     for (size_t i = 0, e = phi->numOperands(); i < e; ++i) {
       MOZ_ASSERT(
           phi->getOperand(i)->block()->dominates(block->getPredecessor(i)),
           "Phi input is not dominated by its operand");
     }
   }

   // Verify that instructions are dominated by their operands.
   for (MInstructionIterator iter(block->begin()), end(block->end());
        iter != end; ++iter) {
     MInstruction* ins = *iter;
     for (size_t i = 0, e = ins->numOperands(); i < e; ++i) {
       MDefinition* op = ins->getOperand(i);
       MBasicBlock* opBlock = op->block();
       MOZ_ASSERT(opBlock->dominates(*block),
                  "Instruction is not dominated by its operands");

       // If the operand is an instruction in the same block, check
       // that it comes first.
       if (opBlock == *block && !op->isPhi()) {
         MInstructionIterator opIter = block->begin(op->toInstruction());
         do {
           ++opIter;
           MOZ_ASSERT(opIter != block->end(),
                      "Operand in same block as instruction does not precede");
         } while (*opIter != ins);
       }
     }
     AssertIfResumableInstruction(ins);
     if (MResumePoint* resume = ins->resumePoint()) {
       AssertResumePointDominatedByOperands(resume);
       AssertResumableOperands(resume);
     }
   }

   // Verify that the block resume points are dominated by their operands.
   if (MResumePoint* resume = block->entryResumePoint()) {
     AssertResumePointDominatedByOperands(resume);
     AssertResumableOperands(resume);
   }
   if (MResumePoint* resume = block->outerResumePoint()) {
     AssertResumePointDominatedByOperands(resume);
     AssertResumableOperands(resume);
   }

   // Verify that any nodes with a wasm ref type have MIRType WasmAnyRef.
   for (MDefinitionIterator def(*block); def; def++) {
     MOZ_ASSERT_IF(def->wasmRefType().isSome(),
                   def->type() == MIRType::WasmAnyRef);
   }
 }
#endif
}

struct BoundsCheckInfo {
 MBoundsCheck* check;
 uint32_t validEnd;
};

using BoundsCheckMap =
   HashMap<uint32_t, BoundsCheckInfo, DefaultHasher<uint32_t>, JitAllocPolicy>;

// Compute a hash for bounds checks which ignores constant offsets in the index.
static HashNumber BoundsCheckHashIgnoreOffset(MBoundsCheck* check) {
 SimpleLinearSum indexSum = ExtractLinearSum(check->index());
 uintptr_t index = indexSum.term ? uintptr_t(indexSum.term) : 0;
 uintptr_t length = uintptr_t(check->length());
 return index ^ length;
}

static MBoundsCheck* FindDominatingBoundsCheck(BoundsCheckMap& checks,
                                              MBoundsCheck* check,
                                              size_t index) {
 // Since we are traversing the dominator tree in pre-order, when we
 // are looking at the |index|-th block, the next numDominated() blocks
 // we traverse are precisely the set of blocks that are dominated.
 //
 // So, this value is visible in all blocks if:
 // index <= index + ins->block->numDominated()
 // and becomes invalid after that.
 HashNumber hash = BoundsCheckHashIgnoreOffset(check);
 BoundsCheckMap::Ptr p = checks.lookup(hash);
 if (!p || index >= p->value().validEnd) {
   // We didn't find a dominating bounds check.
   BoundsCheckInfo info;
   info.check = check;
   info.validEnd = index + check->block()->numDominated();

   if (!checks.put(hash, info)) return nullptr;

   return check;
 }

 return p->value().check;
}

static MathSpace ExtractMathSpace(MDefinition* ins) {
 MOZ_ASSERT(ins->isAdd() || ins->isSub());
 MBinaryArithInstruction* arith = nullptr;
 if (ins->isAdd()) {
   arith = ins->toAdd();
 } else {
   arith = ins->toSub();
 }
 switch (arith->truncateKind()) {
   case TruncateKind::NoTruncate:
   case TruncateKind::TruncateAfterBailouts:
     // TruncateAfterBailouts is considered as infinite space because the
     // LinearSum will effectively remove the bailout check.
     return MathSpace::Infinite;
   case TruncateKind::IndirectTruncate:
   case TruncateKind::Truncate:
     return MathSpace::Modulo;
 }
 MOZ_CRASH("Unknown TruncateKind");
}

static bool MonotoneAdd(int32_t lhs, int32_t rhs) {
 return (lhs >= 0 && rhs >= 0) || (lhs <= 0 && rhs <= 0);
}

static bool MonotoneSub(int32_t lhs, int32_t rhs) {
 return (lhs >= 0 && rhs <= 0) || (lhs <= 0 && rhs >= 0);
}

// Extract a linear sum from ins, if possible (otherwise giving the
// sum 'ins + 0').
SimpleLinearSum jit::ExtractLinearSum(MDefinition* ins, MathSpace space,
                                     int32_t recursionDepth) {
 const int32_t SAFE_RECURSION_LIMIT = 100;
 if (recursionDepth > SAFE_RECURSION_LIMIT) {
   return SimpleLinearSum(ins, 0);
 }

 // Unwrap Int32ToIntPtr. This instruction only changes the representation
 // (int32_t to intptr_t) without affecting the value.
 if (ins->isInt32ToIntPtr()) {
   ins = ins->toInt32ToIntPtr()->input();
 }

 if (ins->isBeta()) {
   ins = ins->getOperand(0);
 }

 MOZ_ASSERT(!ins->isInt32ToIntPtr());

 if (ins->type() != MIRType::Int32) {
   return SimpleLinearSum(ins, 0);
 }

 if (ins->isConstant()) {
   return SimpleLinearSum(nullptr, ins->toConstant()->toInt32());
 }

 if (!ins->isAdd() && !ins->isSub()) {
   return SimpleLinearSum(ins, 0);
 }

 // Only allow math which are in the same space.
 MathSpace insSpace = ExtractMathSpace(ins);
 if (space == MathSpace::Unknown) {
   space = insSpace;
 } else if (space != insSpace) {
   return SimpleLinearSum(ins, 0);
 }
 MOZ_ASSERT(space == MathSpace::Modulo || space == MathSpace::Infinite);

 if (space == MathSpace::Modulo) {
   return SimpleLinearSum(ins, 0);
 }

 MDefinition* lhs = ins->getOperand(0);
 MDefinition* rhs = ins->getOperand(1);
 if (lhs->type() != MIRType::Int32 || rhs->type() != MIRType::Int32) {
   return SimpleLinearSum(ins, 0);
 }

 // Extract linear sums of each operand.
 SimpleLinearSum lsum = ExtractLinearSum(lhs, space, recursionDepth + 1);
 SimpleLinearSum rsum = ExtractLinearSum(rhs, space, recursionDepth + 1);

 // LinearSum only considers a single term operand, if both sides have
 // terms, then ignore extracted linear sums.
 if (lsum.term && rsum.term) {
   return SimpleLinearSum(ins, 0);
 }

 // Check if this is of the form <SUM> + n or n + <SUM>.
 if (ins->isAdd()) {
   int32_t constant;
   if (space == MathSpace::Modulo) {
     constant = uint32_t(lsum.constant) + uint32_t(rsum.constant);
   } else if (!mozilla::SafeAdd(lsum.constant, rsum.constant, &constant) ||
              !MonotoneAdd(lsum.constant, rsum.constant)) {
     return SimpleLinearSum(ins, 0);
   }
   return SimpleLinearSum(lsum.term ? lsum.term : rsum.term, constant);
 }

 MOZ_ASSERT(ins->isSub());
 // Check if this is of the form <SUM> - n.
 if (lsum.term) {
   int32_t constant;
   if (space == MathSpace::Modulo) {
     constant = uint32_t(lsum.constant) - uint32_t(rsum.constant);
   } else if (!mozilla::SafeSub(lsum.constant, rsum.constant, &constant) ||
              !MonotoneSub(lsum.constant, rsum.constant)) {
     return SimpleLinearSum(ins, 0);
   }
   return SimpleLinearSum(lsum.term, constant);
 }

 // Ignore any of the form n - <SUM>.
 return SimpleLinearSum(ins, 0);
}

// Extract a linear inequality holding when a boolean test goes in the
// specified direction, of the form 'lhs + lhsN <= rhs' (or >=).
bool jit::ExtractLinearInequality(const MTest* test, BranchDirection direction,
                                 SimpleLinearSum* plhs, MDefinition** prhs,
                                 bool* plessEqual) {
 if (!test->getOperand(0)->isCompare()) {
   return false;
 }

 MCompare* compare = test->getOperand(0)->toCompare();

 MDefinition* lhs = compare->getOperand(0);
 MDefinition* rhs = compare->getOperand(1);

 // TODO: optimize Compare_UInt32
 if (!compare->isInt32Comparison()) {
   return false;
 }

 MOZ_ASSERT(lhs->type() == MIRType::Int32);
 MOZ_ASSERT(rhs->type() == MIRType::Int32);

 JSOp jsop = compare->jsop();
 if (direction == FALSE_BRANCH) {
   jsop = NegateCompareOp(jsop);
 }

 SimpleLinearSum lsum = ExtractLinearSum(lhs);
 SimpleLinearSum rsum = ExtractLinearSum(rhs);

 if (!mozilla::SafeSub(lsum.constant, rsum.constant, &lsum.constant)) {
   return false;
 }

 // Normalize operations to use <= or >=.
 switch (jsop) {
   case JSOp::Le:
     *plessEqual = true;
     break;
   case JSOp::Lt:
     /* x < y ==> x + 1 <= y */
     if (!mozilla::SafeAdd(lsum.constant, 1, &lsum.constant)) {
       return false;
     }
     *plessEqual = true;
     break;
   case JSOp::Ge:
     *plessEqual = false;
     break;
   case JSOp::Gt:
     /* x > y ==> x - 1 >= y */
     if (!mozilla::SafeSub(lsum.constant, 1, &lsum.constant)) {
       return false;
     }
     *plessEqual = false;
     break;
   default:
     return false;
 }

 *plhs = lsum;
 *prhs = rsum.term;

 return true;
}

static bool TryEliminateBoundsCheck(BoundsCheckMap& checks, size_t blockIndex,
                                   MBoundsCheck* dominated, bool* eliminated) {
 MOZ_ASSERT(!*eliminated);

 // Replace all uses of the bounds check with the actual index.
 // This is (a) necessary, because we can coalesce two different
 // bounds checks and would otherwise use the wrong index and
 // (b) helps register allocation. Note that this is safe since
 // no other pass after bounds check elimination moves instructions.
 dominated->replaceAllUsesWith(dominated->index());

 if (!dominated->isMovable()) {
   return true;
 }

 if (!dominated->fallible()) {
   return true;
 }

 MBoundsCheck* dominating =
     FindDominatingBoundsCheck(checks, dominated, blockIndex);
 if (!dominating) {
   return false;
 }

 if (dominating == dominated) {
   // We didn't find a dominating bounds check.
   return true;
 }

 // We found two bounds checks with the same hash number, but we still have
 // to make sure the lengths and index terms are equal.
 if (dominating->length() != dominated->length()) {
   return true;
 }

 SimpleLinearSum sumA = ExtractLinearSum(dominating->index());
 SimpleLinearSum sumB = ExtractLinearSum(dominated->index());

 // Both terms should be nullptr or the same definition.
 if (sumA.term != sumB.term) {
   return true;
 }

 // This bounds check is redundant.
 *eliminated = true;

 // Normalize the ranges according to the constant offsets in the two indexes.
 int32_t minimumA, maximumA, minimumB, maximumB;
 if (!mozilla::SafeAdd(sumA.constant, dominating->minimum(), &minimumA) ||
     !mozilla::SafeAdd(sumA.constant, dominating->maximum(), &maximumA) ||
     !mozilla::SafeAdd(sumB.constant, dominated->minimum(), &minimumB) ||
     !mozilla::SafeAdd(sumB.constant, dominated->maximum(), &maximumB)) {
   return false;
 }

 // Update the dominating check to cover both ranges, denormalizing the
 // result per the constant offset in the index.
 int32_t newMinimum, newMaximum;
 if (!mozilla::SafeSub(std::min(minimumA, minimumB), sumA.constant,
                       &newMinimum) ||
     !mozilla::SafeSub(std::max(maximumA, maximumB), sumA.constant,
                       &newMaximum)) {
   return false;
 }

 dominating->setMinimum(newMinimum);
 dominating->setMaximum(newMaximum);
 dominating->setBailoutKind(BailoutKind::HoistBoundsCheck);

 return true;
}

// Eliminate checks which are redundant given each other or other instructions.
//
// A bounds check is considered redundant if it's dominated by another bounds
// check with the same length and the indexes differ by only a constant amount.
// In this case we eliminate the redundant bounds check and update the other one
// to cover the ranges of both checks.
//
// Bounds checks are added to a hash map and since the hash function ignores
// differences in constant offset, this offers a fast way to find redundant
// checks.
bool jit::EliminateRedundantChecks(MIRGraph& graph) {
 BoundsCheckMap checks(graph.alloc());

 // Stack for pre-order CFG traversal.
 Vector<MBasicBlock*, 1, JitAllocPolicy> worklist(graph.alloc());

 // The index of the current block in the CFG traversal.
 size_t index = 0;

 // Add all self-dominating blocks to the worklist.
 // This includes all roots. Order does not matter.
 for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) {
   MBasicBlock* block = *i;
   if (block->immediateDominator() == block) {
     if (!worklist.append(block)) {
       return false;
     }
   }
 }

 // Starting from each self-dominating block, traverse the CFG in pre-order.
 while (!worklist.empty()) {
   MBasicBlock* block = worklist.popCopy();

   // Add all immediate dominators to the front of the worklist.
   if (!worklist.append(block->immediatelyDominatedBlocksBegin(),
                        block->immediatelyDominatedBlocksEnd())) {
     return false;
   }

   for (MDefinitionIterator iter(block); iter;) {
     MDefinition* def = *iter++;

     if (!def->isBoundsCheck()) {
       continue;
     }
     auto* boundsCheck = def->toBoundsCheck();

     bool eliminated = false;
     if (!TryEliminateBoundsCheck(checks, index, boundsCheck, &eliminated)) {
       return false;
     }

     if (eliminated) {
       block->discard(boundsCheck);
     }
   }
   index++;
 }

 MOZ_ASSERT(index == graph.numBlocks());

 return true;
}

static bool ShapeGuardIsRedundant(MGuardShape* guard,
                                 const MDefinition* storeObject,
                                 const Shape* storeShape) {
 const MDefinition* guardObject = guard->object()->skipObjectGuards();
 if (guardObject != storeObject) {
   JitSpew(JitSpew_RedundantShapeGuards, "SKIP: different objects (%d vs %d)",
           guardObject->id(), storeObject->id());
   return false;
 }

 const Shape* guardShape = guard->shape();
 if (guardShape != storeShape) {
   JitSpew(JitSpew_RedundantShapeGuards, "SKIP: different shapes");
   return false;
 }

 return true;
}

// Eliminate shape guards which are redundant given other instructions.
//
// A shape guard is redundant if we can prove that the object being
// guarded already has the correct shape. The conditions for doing so
// are as follows:
//
// 1. We can see the most recent change to the shape of this object.
//    (This can be an AddAndStoreSlot, an AllocateAndStoreSlot, or the
//    creation of the object itself.
// 2. That mutation dominates the shape guard.
// 3. The shape that was assigned at that point matches the shape
//    we expect.
//
// If all of these conditions hold, then we can remove the shape guard.
// In debug, we replace it with an AssertShape to help verify correctness.
bool jit::EliminateRedundantShapeGuards(MIRGraph& graph) {
 JitSpew(JitSpew_RedundantShapeGuards, "Begin");

 for (ReversePostorderIterator block = graph.rpoBegin();
      block != graph.rpoEnd(); block++) {
   for (MInstructionIterator insIter(block->begin());
        insIter != block->end();) {
     MInstruction* ins = *insIter;
     insIter++;

     // Skip instructions that aren't shape guards.
     if (!ins->isGuardShape()) {
       continue;
     }
     MGuardShape* guard = ins->toGuardShape();
     MDefinition* lastStore = guard->dependency();

     JitSpew(JitSpew_RedundantShapeGuards, "Visit shape guard %d",
             guard->id());
     JitSpewIndent spewIndent(JitSpew_RedundantShapeGuards);

     if (lastStore->isDiscarded() || lastStore->block()->isDead() ||
         !lastStore->block()->dominates(guard->block())) {
       JitSpew(JitSpew_RedundantShapeGuards,
               "SKIP: ins %d does not dominate block %d", lastStore->id(),
               guard->block()->id());
       continue;
     }

     if (lastStore->isAddAndStoreSlot()) {
       auto* add = lastStore->toAddAndStoreSlot();
       auto* addObject = add->object()->skipObjectGuards();
       if (!ShapeGuardIsRedundant(guard, addObject, add->shape())) {
         continue;
       }
     } else if (lastStore->isAllocateAndStoreSlot()) {
       auto* allocate = lastStore->toAllocateAndStoreSlot();
       auto* allocateObject = allocate->object()->skipObjectGuards();
       if (!ShapeGuardIsRedundant(guard, allocateObject, allocate->shape())) {
         continue;
       }
     } else if (lastStore->isStart()) {
       // The guard doesn't depend on any other instruction that is modifying
       // the object operand, so we check the object operand directly.
       auto* obj = guard->object()->skipObjectGuards();

       const Shape* initialShape = nullptr;
       if (obj->isNewObject()) {
         auto* templateObject = obj->toNewObject()->templateObject();
         if (!templateObject) {
           JitSpew(JitSpew_RedundantShapeGuards, "SKIP: no template");
           continue;
         }
         initialShape = templateObject->shape();
       } else if (obj->isNewPlainObject()) {
         initialShape = obj->toNewPlainObject()->shape();
       } else {
         JitSpew(JitSpew_RedundantShapeGuards,
                 "SKIP: not NewObject or NewPlainObject (%d)", obj->id());
         continue;
       }
       if (initialShape != guard->shape()) {
         JitSpew(JitSpew_RedundantShapeGuards, "SKIP: shapes don't match");
         continue;
       }
     } else {
       JitSpew(JitSpew_RedundantShapeGuards,
               "SKIP: Last store not supported (%d)", lastStore->id());
       continue;
     }

#ifdef DEBUG
     if (!graph.alloc().ensureBallast()) {
       return false;
     }
     auto* assert = MAssertShape::New(graph.alloc(), guard->object(),
                                      const_cast<Shape*>(guard->shape()));
     guard->block()->insertBefore(guard, assert);
#endif

     JitSpew(JitSpew_RedundantShapeGuards, "SUCCESS: Removing shape guard %d",
             guard->id());
     guard->replaceAllUsesWith(guard->input());
     guard->block()->discard(guard);
   }
 }

 return true;
}

[[nodiscard]] static bool TryEliminateGCBarriersForAllocation(
   TempAllocator& alloc, MInstruction* allocation) {
 MOZ_ASSERT(allocation->type() == MIRType::Object);

 JitSpew(JitSpew_RedundantGCBarriers, "Analyzing allocation %s",
         allocation->opName());

 MBasicBlock* block = allocation->block();
 MInstructionIterator insIter(block->begin(allocation));

 // Skip `allocation`.
 MOZ_ASSERT(*insIter == allocation);
 insIter++;

 // Try to optimize the other instructions in the block.
 while (insIter != block->end()) {
   MInstruction* ins = *insIter;
   insIter++;
   switch (ins->op()) {
     case MDefinition::Opcode::Constant:
     case MDefinition::Opcode::Box:
     case MDefinition::Opcode::Unbox:
     case MDefinition::Opcode::AssertCanElidePostWriteBarrier:
       // These instructions can't trigger GC or affect this analysis in other
       // ways.
       break;
     case MDefinition::Opcode::StoreFixedSlot: {
       auto* store = ins->toStoreFixedSlot();
       if (store->object() != allocation) {
         JitSpew(JitSpew_RedundantGCBarriers,
                 "Stopped at StoreFixedSlot for other object");
         return true;
       }
       store->setNeedsBarrier(false);
       JitSpew(JitSpew_RedundantGCBarriers, "Elided StoreFixedSlot barrier");
       break;
     }
     case MDefinition::Opcode::PostWriteBarrier: {
       auto* barrier = ins->toPostWriteBarrier();
       if (barrier->object() != allocation) {
         JitSpew(JitSpew_RedundantGCBarriers,
                 "Stopped at PostWriteBarrier for other object");
         return true;
       }
#ifdef DEBUG
       if (!alloc.ensureBallast()) {
         return false;
       }
       MDefinition* value = barrier->value();
       if (value->type() != MIRType::Value) {
         value = MBox::New(alloc, value);
         block->insertBefore(barrier, value->toInstruction());
       }
       auto* assert =
           MAssertCanElidePostWriteBarrier::New(alloc, allocation, value);
       block->insertBefore(barrier, assert);
#endif
       block->discard(barrier);
       JitSpew(JitSpew_RedundantGCBarriers, "Elided PostWriteBarrier");
       break;
     }
     default:
       JitSpew(JitSpew_RedundantGCBarriers,
               "Stopped at unsupported instruction %s", ins->opName());
       return true;
   }
 }

 return true;
}

bool jit::EliminateRedundantGCBarriers(MIRGraph& graph) {
 // Peephole optimization for the following pattern:
 //
 //   0: MNewCallObject
 //   1: MStoreFixedSlot(0, ...)
 //   2: MStoreFixedSlot(0, ...)
 //   3: MPostWriteBarrier(0, ...)
 //
 // If the instructions immediately following the allocation instruction can't
 // trigger GC and we are storing to the new object's slots, we can elide the
 // pre-barrier.
 //
 // We also eliminate the post barrier and (in debug builds) replace it with an
 // assertion.
 //
 // See also the similar optimizations in WarpBuilder::buildCallObject.

 JitSpew(JitSpew_RedundantGCBarriers, "Begin");

 for (ReversePostorderIterator block = graph.rpoBegin();
      block != graph.rpoEnd(); block++) {
   for (MInstructionIterator insIter(block->begin()); insIter != block->end();
        insIter++) {
     MInstruction* ins = *insIter;
     if (ins->isNewCallObject()) {
       MNewCallObject* allocation = ins->toNewCallObject();
       // We can only eliminate the post barrier if we know the call object
       // will be allocated in the nursery.
       if (allocation->initialHeap() == gc::Heap::Default) {
         if (!TryEliminateGCBarriersForAllocation(graph.alloc(), allocation)) {
           return false;
         }
       }
     }
   }
 }

 return true;
}

bool jit::MarkLoadsUsedAsPropertyKeys(MIRGraph& graph) {
 // When a string is used as a property key, or as the key for a Map or Set, we
 // require it to be atomized. To avoid repeatedly atomizing the same string,
 // this analysis looks for cases where we are loading a value from the slot of
 // an object (which includes access to global variables and global lexicals)
 // and using it as a property key, and marks those loads. During codegen,
 // marked loads will check whether the value loaded is a non-atomized string.
 // If it is, we will atomize the string and update the stored value, ensuring
 // that future loads from the same slot will not have to atomize again.
 JitSpew(JitSpew_MarkLoadsUsedAsPropertyKeys, "Begin");

 for (ReversePostorderIterator block = graph.rpoBegin();
      block != graph.rpoEnd(); block++) {
   for (MInstructionIterator insIter(block->begin());
        insIter != block->end();) {
     MInstruction* ins = *insIter;
     insIter++;

     MDefinition* idVal = nullptr;
     if (ins->isGetPropertyCache()) {
       idVal = ins->toGetPropertyCache()->idval();
     } else if (ins->isHasOwnCache()) {
       idVal = ins->toHasOwnCache()->idval();
     } else if (ins->isSetPropertyCache()) {
       idVal = ins->toSetPropertyCache()->idval();
     } else if (ins->isGetPropSuperCache()) {
       idVal = ins->toGetPropSuperCache()->idval();
     } else if (ins->isMegamorphicLoadSlotByValue()) {
       idVal = ins->toMegamorphicLoadSlotByValue()->idVal();
     } else if (ins->isMegamorphicLoadSlotByValuePermissive()) {
       idVal = ins->toMegamorphicLoadSlotByValuePermissive()->idVal();
     } else if (ins->isMegamorphicHasProp()) {
       idVal = ins->toMegamorphicHasProp()->idVal();
     } else if (ins->isMegamorphicSetElement()) {
       idVal = ins->toMegamorphicSetElement()->index();
     } else if (ins->isProxyGetByValue()) {
       idVal = ins->toProxyGetByValue()->idVal();
     } else if (ins->isProxyHasProp()) {
       idVal = ins->toProxyHasProp()->idVal();
     } else if (ins->isProxySetByValue()) {
       idVal = ins->toProxySetByValue()->idVal();
     } else if (ins->isIdToStringOrSymbol()) {
       idVal = ins->toIdToStringOrSymbol()->idVal();
     } else if (ins->isGuardSpecificAtom()) {
       idVal = ins->toGuardSpecificAtom()->input();
     } else if (ins->isToHashableString()) {
       idVal = ins->toToHashableString()->input();
     } else if (ins->isToHashableValue()) {
       idVal = ins->toToHashableValue()->input();
     } else if (ins->isMapObjectHasValueVMCall()) {
       idVal = ins->toMapObjectHasValueVMCall()->value();
     } else if (ins->isMapObjectGetValueVMCall()) {
       idVal = ins->toMapObjectGetValueVMCall()->value();
     } else if (ins->isSetObjectHasValueVMCall()) {
       idVal = ins->toSetObjectHasValueVMCall()->value();
     } else {
       continue;
     }
     JitSpew(JitSpew_MarkLoadsUsedAsPropertyKeys,
             "Analyzing property access %s%d with idVal %s%d", ins->opName(),
             ins->id(), idVal->opName(), idVal->id());

     // Skip intermediate nodes.
     do {
       if (idVal->isLexicalCheck()) {
         idVal = idVal->toLexicalCheck()->input();
         JitSpew(JitSpew_MarkLoadsUsedAsPropertyKeys,
                 "- Skipping lexical check. idVal is now %s%d",
                 idVal->opName(), idVal->id());
         continue;
       }
       if (idVal->isUnbox() && idVal->type() == MIRType::String) {
         idVal = idVal->toUnbox()->input();
         JitSpew(JitSpew_MarkLoadsUsedAsPropertyKeys,
                 "- Skipping unbox. idVal is now %s%d", idVal->opName(),
                 idVal->id());
         continue;
       }
       break;
     } while (true);

     if (idVal->isLoadFixedSlot()) {
       JitSpew(JitSpew_MarkLoadsUsedAsPropertyKeys,
               "- SUCCESS: Marking fixed slot");
       idVal->toLoadFixedSlot()->setUsedAsPropertyKey();
     } else if (idVal->isLoadDynamicSlot()) {
       JitSpew(JitSpew_MarkLoadsUsedAsPropertyKeys,
               "- SUCCESS: Marking dynamic slot");
       idVal->toLoadDynamicSlot()->setUsedAsPropertyKey();
     } else {
       JitSpew(JitSpew_MarkLoadsUsedAsPropertyKeys, "- SKIP: %s not supported",
               idVal->opName());
     }
   }
 }

 return true;
}

// Updates the wasm ref type of a node and verifies that in this pass we only
// narrow types, and never widen.
static bool UpdateWasmRefType(MDefinition* def) {
 wasm::MaybeRefType newRefType = def->computeWasmRefType();
 bool changed = newRefType != def->wasmRefType();

 // Ensure that we do not regress from Some to Nothing.
 MOZ_ASSERT(!(def->wasmRefType().isSome() && newRefType.isNothing()));
 // Ensure that the new ref type is a subtype of the previous one (i.e. we
 // only narrow ref types).
 MOZ_ASSERT_IF(def->wasmRefType().isSome(),
               wasm::RefType::isSubTypeOf(newRefType.value(),
                                          def->wasmRefType().value()));

 def->setWasmRefType(newRefType);
 return changed;
}

// Since wasm has a fairly rich type system enforced in validation, we can use
// this type system within MIR to robustly track the types of ref values. This
// allows us to make MIR-level optimizations such as eliding null checks or
// omitting redundant casts.
//
// This analysis pass performs simple data flow analysis by assigning ref types
// to each definition, then revisiting phis and their uses as necessary until
// the types have narrowed to a fixed point.
bool jit::TrackWasmRefTypes(MIRGraph& graph) {
 // The worklist tracks nodes whose types have changed and whose uses must
 // therefore be re-evaluated.
 Vector<MDefinition*, 16, SystemAllocPolicy> worklist;

 // Assign an initial ref type to each definition. Reverse postorder ensures
 // that nodes are always visited before their uses, with the exception of loop
 // backedge phis.
 for (ReversePostorderIterator blockIter = graph.rpoBegin();
      blockIter != graph.rpoEnd(); blockIter++) {
   MBasicBlock* block = *blockIter;
   for (MDefinitionIterator def(block); def; def++) {
     // Set the initial type on all nodes. If a type is produced, then any
     // loop backedge phis that use this node must have been previously
     // visited, and must be updated and possibly added to the worklist. (Any
     // other uses of this node will be visited later in this first pass.)

     if (def->type() != MIRType::WasmAnyRef) {
       continue;
     }

     bool hasType = UpdateWasmRefType(*def);
     if (hasType) {
       for (MUseIterator use(def->usesBegin()); use != def->usesEnd(); use++) {
         MNode* consumer = use->consumer();
         if (!consumer->isDefinition() || !consumer->toDefinition()->isPhi()) {
           continue;
         }
         MPhi* phi = consumer->toDefinition()->toPhi();
         if (phi->block()->isLoopHeader() &&
             *def == phi->getLoopBackedgeOperand()) {
           bool changed = UpdateWasmRefType(phi);
           if (changed && !worklist.append(phi)) {
             return false;
           }
         } else {
           // Any other type of use must not have a ref type yet, because we
           // are yet to hit it in this forward pass.
           MOZ_ASSERT(consumer->toDefinition()->wasmRefType().isNothing());
         }
       }
     }
   }
 }

 // Until the worklist is empty, update the uses of any worklist nodes and
 // track the ones whose types change.
 while (!worklist.empty()) {
   MDefinition* def = worklist.popCopy();

   for (MUseIterator use(def->usesBegin()); use != def->usesEnd(); use++) {
     if (!use->consumer()->isDefinition()) {
       continue;
     }
     bool changed = UpdateWasmRefType(use->consumer()->toDefinition());
     if (changed && !worklist.append(use->consumer()->toDefinition())) {
       return false;
     }
   }
 }

 return true;
}

static bool NeedsKeepAlive(MInstruction* slotsOrElements, MInstruction* use) {
 MOZ_ASSERT(slotsOrElements->type() == MIRType::Elements ||
            slotsOrElements->type() == MIRType::Slots);

 if (slotsOrElements->block() != use->block()) {
   return true;
 }

 MBasicBlock* block = use->block();
 MInstructionIterator iter(block->begin(slotsOrElements));
 MOZ_ASSERT(*iter == slotsOrElements);
 ++iter;

 while (true) {
   MInstruction* ins = *iter;
   switch (ins->op()) {
     case MDefinition::Opcode::Nop:
     case MDefinition::Opcode::Constant:
     case MDefinition::Opcode::KeepAliveObject:
     case MDefinition::Opcode::Unbox:
     case MDefinition::Opcode::LoadDynamicSlot:
     case MDefinition::Opcode::LoadDynamicSlotAndUnbox:
     case MDefinition::Opcode::StoreDynamicSlot:
     case MDefinition::Opcode::LoadFixedSlot:
     case MDefinition::Opcode::LoadFixedSlotAndUnbox:
     case MDefinition::Opcode::StoreFixedSlot:
     case MDefinition::Opcode::LoadElement:
     case MDefinition::Opcode::LoadElementAndUnbox:
     case MDefinition::Opcode::LoadElementHole:
     case MDefinition::Opcode::StoreElement:
     case MDefinition::Opcode::StoreHoleValueElement:
     case MDefinition::Opcode::LoadUnboxedScalar:
     case MDefinition::Opcode::StoreUnboxedScalar:
     case MDefinition::Opcode::StoreTypedArrayElementHole:
     case MDefinition::Opcode::LoadDataViewElement:
     case MDefinition::Opcode::StoreDataViewElement:
     case MDefinition::Opcode::AtomicTypedArrayElementBinop:
     case MDefinition::Opcode::AtomicExchangeTypedArrayElement:
     case MDefinition::Opcode::CompareExchangeTypedArrayElement:
     case MDefinition::Opcode::InitializedLength:
     case MDefinition::Opcode::SetInitializedLength:
     case MDefinition::Opcode::ArrayLength:
     case MDefinition::Opcode::BoundsCheck:
     case MDefinition::Opcode::GuardElementNotHole:
     case MDefinition::Opcode::GuardElementsArePacked:
     case MDefinition::Opcode::InArray:
     case MDefinition::Opcode::SpectreMaskIndex:
     case MDefinition::Opcode::DebugEnterGCUnsafeRegion:
     case MDefinition::Opcode::DebugLeaveGCUnsafeRegion:
       break;
     case MDefinition::Opcode::LoadTypedArrayElementHole: {
       // Allocating a BigInt can GC, so we have to keep the object alive.
       auto* loadIns = ins->toLoadTypedArrayElementHole();
       if (Scalar::isBigIntType(loadIns->arrayType())) {
         return true;
       }
       break;
     }
     default:
       return true;
   }

   if (ins == use) {
     // We didn't find any instructions in range [slotsOrElements, use] that
     // can GC.
     return false;
   }
   iter++;
 }

 MOZ_CRASH("Unreachable");
}

bool jit::AddKeepAliveInstructions(MIRGraph& graph) {
 for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) {
   MBasicBlock* block = *i;

   for (MInstructionIterator insIter(block->begin()); insIter != block->end();
        insIter++) {
     MInstruction* ins = *insIter;
     if (ins->type() != MIRType::Elements && ins->type() != MIRType::Slots) {
       continue;
     }

     MDefinition* ownerObject;
     switch (ins->op()) {
       case MDefinition::Opcode::Elements:
       case MDefinition::Opcode::ArrayBufferViewElements:
         MOZ_ASSERT(ins->numOperands() == 1);
         ownerObject = ins->getOperand(0);
         break;
       case MDefinition::Opcode::ArrayBufferViewElementsWithOffset:
         MOZ_ASSERT(ins->numOperands() == 2);
         ownerObject = ins->getOperand(0);
         break;
       case MDefinition::Opcode::Slots:
         ownerObject = ins->toSlots()->object();
         break;
       default:
         MOZ_CRASH("Unexpected op");
     }

     MOZ_ASSERT(ownerObject->type() == MIRType::Object);

     const MDefinition* unwrapped = ownerObject->skipObjectGuards();
     if (unwrapped->isConstant() || unwrapped->isNurseryObject()) {
       // Constants are kept alive by other pointers, for instance ImmGCPtr in
       // JIT code. NurseryObjects will be kept alive by the IonScript.
       continue;
     }

     for (MUseDefIterator uses(ins); uses; uses++) {
       MInstruction* use = uses.def()->toInstruction();

       if (use->isStoreElementHole()) {
         // StoreElementHole has an explicit object operand. If GVN
         // is disabled, we can get different unbox instructions with
         // the same object as input, so we check for that case.
         MOZ_ASSERT_IF(!use->toStoreElementHole()->object()->isUnbox() &&
                           !ownerObject->isUnbox(),
                       use->toStoreElementHole()->object() == ownerObject);
         continue;
       }

       if (!NeedsKeepAlive(ins, use)) {
#ifdef DEBUG
         if (!graph.alloc().ensureBallast()) {
           return false;
         }

         // Enter a GC unsafe region while the elements/slots are on the stack.
         auto* enter = MDebugEnterGCUnsafeRegion::New(graph.alloc());
         use->block()->insertAfter(ins, enter);

         // Leave the region after the use.
         auto* leave = MDebugLeaveGCUnsafeRegion::New(graph.alloc());
         use->block()->insertAfter(use, leave);
#endif
         continue;
       }

       if (!graph.alloc().ensureBallast()) {
         return false;
       }
       MKeepAliveObject* keepAlive =
           MKeepAliveObject::New(graph.alloc(), ownerObject);
       use->block()->insertAfter(use, keepAlive);
     }
   }
 }

 return true;
}

bool LinearSum::multiply(int32_t scale) {
 for (size_t i = 0; i < terms_.length(); i++) {
   if (!mozilla::SafeMul(scale, terms_[i].scale, &terms_[i].scale)) {
     return false;
   }
 }
 return mozilla::SafeMul(scale, constant_, &constant_);
}

bool LinearSum::divide(uint32_t scale) {
 MOZ_ASSERT(scale > 0);

 for (size_t i = 0; i < terms_.length(); i++) {
   if (terms_[i].scale % scale != 0) {
     return false;
   }
 }
 if (constant_ % scale != 0) {
   return false;
 }

 for (size_t i = 0; i < terms_.length(); i++) {
   terms_[i].scale /= scale;
 }
 constant_ /= scale;

 return true;
}

bool LinearSum::add(const LinearSum& other, int32_t scale /* = 1 */) {
 for (size_t i = 0; i < other.terms_.length(); i++) {
   int32_t newScale = scale;
   if (!mozilla::SafeMul(scale, other.terms_[i].scale, &newScale)) {
     return false;
   }
   if (!add(other.terms_[i].term, newScale)) {
     return false;
   }
 }
 int32_t newConstant = scale;
 if (!mozilla::SafeMul(scale, other.constant_, &newConstant)) {
   return false;
 }
 return add(newConstant);
}

bool LinearSum::add(SimpleLinearSum other, int32_t scale) {
 if (other.term && !add(other.term, scale)) {
   return false;
 }

 int32_t constant;
 if (!mozilla::SafeMul(other.constant, scale, &constant)) {
   return false;
 }

 return add(constant);
}

bool LinearSum::add(MDefinition* term, int32_t scale) {
 MOZ_ASSERT(term);

 if (scale == 0) {
   return true;
 }

 if (MConstant* termConst = term->maybeConstantValue()) {
   int32_t constant = termConst->toInt32();
   if (!mozilla::SafeMul(constant, scale, &constant)) {
     return false;
   }
   return add(constant);
 }

 for (size_t i = 0; i < terms_.length(); i++) {
   if (term == terms_[i].term) {
     if (!mozilla::SafeAdd(scale, terms_[i].scale, &terms_[i].scale)) {
       return false;
     }
     if (terms_[i].scale == 0) {
       terms_[i] = terms_.back();
       terms_.popBack();
     }
     return true;
   }
 }

 AutoEnterOOMUnsafeRegion oomUnsafe;
 if (!terms_.append(LinearTerm(term, scale))) {
   oomUnsafe.crash("LinearSum::add");
 }

 return true;
}

bool LinearSum::add(int32_t constant) {
 return mozilla::SafeAdd(constant, constant_, &constant_);
}

void LinearSum::dump(GenericPrinter& out) const {
 for (size_t i = 0; i < terms_.length(); i++) {
   int32_t scale = terms_[i].scale;
   int32_t id = terms_[i].term->id();
   MOZ_ASSERT(scale);
   if (scale > 0) {
     if (i) {
       out.printf("+");
     }
     if (scale == 1) {
       out.printf("#%d", id);
     } else {
       out.printf("%d*#%d", scale, id);
     }
   } else if (scale == -1) {
     out.printf("-#%d", id);
   } else {
     out.printf("%d*#%d", scale, id);
   }
 }
 if (constant_ > 0) {
   out.printf("+%d", constant_);
 } else if (constant_ < 0) {
   out.printf("%d", constant_);
 }
}

void LinearSum::dump() const {
 Fprinter out(stderr);
 dump(out);
 out.finish();
}

MDefinition* jit::ConvertLinearSum(TempAllocator& alloc, MBasicBlock* block,
                                  const LinearSum& sum,
                                  BailoutKind bailoutKind) {
 MDefinition* def = nullptr;

 for (size_t i = 0; i < sum.numTerms(); i++) {
   LinearTerm term = sum.term(i);
   MOZ_ASSERT(!term.term->isConstant());
   if (term.scale == 1) {
     if (def) {
       def = MAdd::New(alloc, def, term.term, MIRType::Int32);
       def->setBailoutKind(bailoutKind);
       block->insertAtEnd(def->toInstruction());
       def->computeRange(alloc);
     } else {
       def = term.term;
     }
   } else if (term.scale == -1) {
     if (!def) {
       def = MConstant::NewInt32(alloc, 0);
       block->insertAtEnd(def->toInstruction());
       def->computeRange(alloc);
     }
     def = MSub::New(alloc, def, term.term, MIRType::Int32);
     def->setBailoutKind(bailoutKind);
     block->insertAtEnd(def->toInstruction());
     def->computeRange(alloc);
   } else {
     MOZ_ASSERT(term.scale != 0);
     MConstant* factor = MConstant::NewInt32(alloc, term.scale);
     block->insertAtEnd(factor);
     MMul* mul = MMul::New(alloc, term.term, factor, MIRType::Int32);
     mul->setBailoutKind(bailoutKind);
     block->insertAtEnd(mul);
     mul->computeRange(alloc);
     if (def) {
       def = MAdd::New(alloc, def, mul, MIRType::Int32);
       def->setBailoutKind(bailoutKind);
       block->insertAtEnd(def->toInstruction());
       def->computeRange(alloc);
     } else {
       def = mul;
     }
   }
 }

 if (!def) {
   def = MConstant::NewInt32(alloc, 0);
   block->insertAtEnd(def->toInstruction());
   def->computeRange(alloc);
 }

 return def;
}

// Mark all the blocks that are in the loop with the given header.
// Returns the number of blocks marked. Set *canOsr to true if the loop is
// reachable from both the normal entry and the OSR entry.
size_t jit::MarkLoopBlocks(MIRGraph& graph, const MBasicBlock* header,
                          bool* canOsr) {
#ifdef DEBUG
 for (ReversePostorderIterator i = graph.rpoBegin(), e = graph.rpoEnd();
      i != e; ++i) {
   MOZ_ASSERT(!i->isMarked(), "Some blocks already marked");
 }
#endif

 MBasicBlock* osrBlock = graph.osrBlock();
 *canOsr = false;

 // The blocks are in RPO; start at the loop backedge, which marks the bottom
 // of the loop, and walk up until we get to the header. Loops may be
 // discontiguous, so we trace predecessors to determine which blocks are
 // actually part of the loop. The backedge is always part of the loop, and
 // so are its predecessors, transitively, up to the loop header or an OSR
 // entry.
 MBasicBlock* backedge = header->backedge();
 backedge->mark();
 size_t numMarked = 1;
 for (PostorderIterator i = graph.poBegin(backedge);; ++i) {
   MOZ_ASSERT(
       i != graph.poEnd(),
       "Reached the end of the graph while searching for the loop header");
   MBasicBlock* block = *i;
   // If we've reached the loop header, we're done.
   if (block == header) {
     break;
   }
   // A block not marked by the time we reach it is not in the loop.
   if (!block->isMarked()) {
     continue;
   }

   // This block is in the loop; trace to its predecessors.
   for (size_t p = 0, e = block->numPredecessors(); p != e; ++p) {
     MBasicBlock* pred = block->getPredecessor(p);
     if (pred->isMarked()) {
       continue;
     }

     // Blocks dominated by the OSR entry are not part of the loop
     // (unless they aren't reachable from the normal entry).
     if (osrBlock && pred != header && osrBlock->dominates(pred) &&
         !osrBlock->dominates(header)) {
       *canOsr = true;
       continue;
     }

     MOZ_ASSERT(pred->id() >= header->id() && pred->id() <= backedge->id(),
                "Loop block not between loop header and loop backedge");

     pred->mark();
     ++numMarked;

     // A nested loop may not exit back to the enclosing loop at its
     // bottom. If we just marked its header, then the whole nested loop
     // is part of the enclosing loop.
     if (pred->isLoopHeader()) {
       MBasicBlock* innerBackedge = pred->backedge();
       if (!innerBackedge->isMarked()) {
         // Mark its backedge so that we add all of its blocks to the
         // outer loop as we walk upwards.
         innerBackedge->mark();
         ++numMarked;

         // If the nested loop is not contiguous, we may have already
         // passed its backedge. If this happens, back up.
         if (innerBackedge->id() > block->id()) {
           i = graph.poBegin(innerBackedge);
           --i;
         }
       }
     }
   }
 }

 // If there's no path connecting the header to the backedge, then this isn't
 // actually a loop. This can happen when the code starts with a loop but GVN
 // folds some branches away.
 if (!header->isMarked()) {
   jit::UnmarkLoopBlocks(graph, header);
   return 0;
 }

 return numMarked;
}

// Unmark all the blocks that are in the loop with the given header.
void jit::UnmarkLoopBlocks(MIRGraph& graph, const MBasicBlock* header) {
 MBasicBlock* backedge = header->backedge();
 for (ReversePostorderIterator i = graph.rpoBegin(header);; ++i) {
   MOZ_ASSERT(i != graph.rpoEnd(),
              "Reached the end of the graph while searching for the backedge");
   MBasicBlock* block = *i;
   if (block->isMarked()) {
     block->unmark();
     if (block == backedge) {
       break;
     }
   }
 }

#ifdef DEBUG
 for (ReversePostorderIterator i = graph.rpoBegin(), e = graph.rpoEnd();
      i != e; ++i) {
   MOZ_ASSERT(!i->isMarked(), "Not all blocks got unmarked");
 }
#endif
}

bool jit::FoldLoadsWithUnbox(const MIRGenerator* mir, MIRGraph& graph) {
 // This pass folds MLoadFixedSlot, MLoadDynamicSlot, MLoadElement instructions
 // followed by MUnbox into a single instruction. For LoadElement this allows
 // us to fuse the hole check with the type check for the unbox. It may also
 // allow us to remove some GuardElementsArePacked nodes.

 Vector<MInstruction*, 16, SystemAllocPolicy> optimizedElements;
 for (MBasicBlockIterator block(graph.begin()); block != graph.end();
      block++) {
   if (mir->shouldCancel("FoldLoadsWithUnbox")) {
     return false;
   }

   for (MInstructionIterator insIter(block->begin());
        insIter != block->end();) {
     MInstruction* ins = *insIter;
     insIter++;

     // We're only interested in loads producing a Value.
     if (!ins->isLoadFixedSlot() && !ins->isLoadDynamicSlot() &&
         !ins->isLoadElement() && !ins->isSuperFunction()) {
       continue;
     }
     if (ins->type() != MIRType::Value) {
       continue;
     }

     MInstruction* load = ins;

     // Ensure there's a single def-use (ignoring resume points) and it's an
     // unbox. Unwrap MLexicalCheck because it's redundant if we have a
     // fallible unbox (checked below).
     MDefinition* defUse = load->maybeSingleDefUse();
     if (!defUse) {
       continue;
     }
     MLexicalCheck* lexicalCheck = nullptr;
     if (defUse->isLexicalCheck()) {
       lexicalCheck = defUse->toLexicalCheck();
       defUse = lexicalCheck->maybeSingleDefUse();
       if (!defUse) {
         continue;
       }
     }
     if (!defUse->isUnbox()) {
       continue;
     }

     // For now require the load and unbox to be in the same block. This isn't
     // strictly necessary but it's the common case and could prevent bailouts
     // when moving the unbox before a loop.
     MUnbox* unbox = defUse->toUnbox();
     if (unbox->block() != *block) {
       continue;
     }
     MOZ_ASSERT_IF(lexicalCheck, lexicalCheck->block() == *block);

     MOZ_ASSERT(!IsMagicType(unbox->type()));

     // If this is a LoadElement or if we have a lexical check between the load
     // and unbox, we only support folding the load with a fallible unbox so
     // that we can eliminate the MagicValue check.
     if ((load->isLoadElement() || lexicalCheck) && !unbox->fallible()) {
       continue;
     }

     // If this is a SuperFunction, we only support folding the load when the
     // unbox is fallible and its type is Object.
     //
     // SuperFunction is currently only used for `super()` constructor calls
     // in classes, which always use fallible unbox to Object.
     if (load->isSuperFunction() &&
         !(unbox->type() == MIRType::Object && unbox->fallible())) {
       continue;
     }

     // Combine the load and unbox into a single MIR instruction.
     if (!graph.alloc().ensureBallast()) {
       return false;
     }

     MIRType type = unbox->type();
     MUnbox::Mode mode = unbox->mode();

     MInstruction* replacement;
     switch (load->op()) {
       case MDefinition::Opcode::LoadFixedSlot: {
         auto* loadIns = load->toLoadFixedSlot();
         replacement = MLoadFixedSlotAndUnbox::New(
             graph.alloc(), loadIns->object(), loadIns->slot(), mode, type,
             loadIns->usedAsPropertyKey());
         break;
       }
       case MDefinition::Opcode::LoadDynamicSlot: {
         auto* loadIns = load->toLoadDynamicSlot();
         replacement = MLoadDynamicSlotAndUnbox::New(
             graph.alloc(), loadIns->slots(), loadIns->slot(), mode, type,
             loadIns->usedAsPropertyKey());
         break;
       }
       case MDefinition::Opcode::LoadElement: {
         auto* loadIns = load->toLoadElement();
         MOZ_ASSERT(unbox->fallible());
         replacement = MLoadElementAndUnbox::New(
             graph.alloc(), loadIns->elements(), loadIns->index(), mode, type);
         MOZ_ASSERT(!IsMagicType(type));
         // FoldElementAndUnbox will implicitly check for holes by unboxing. We
         // may be able to remove a GuardElementsArePacked check. Add this
         // Elements to a list to check later (unless we just added it for
         // a different load).
         if ((optimizedElements.empty() ||
              optimizedElements.back() != loadIns) &&
             !optimizedElements.append(loadIns->elements()->toInstruction())) {
           return false;
         }
         break;
       }
       case MDefinition::Opcode::SuperFunction: {
         auto* loadIns = load->toSuperFunction();
         MOZ_ASSERT(unbox->fallible());
         MOZ_ASSERT(unbox->type() == MIRType::Object);
         replacement =
             MSuperFunctionAndUnbox::New(graph.alloc(), loadIns->callee());
         break;
       }
       default:
         MOZ_CRASH("Unexpected instruction");
     }
     replacement->setBailoutKind(BailoutKind::UnboxFolding);

     block->insertBefore(load, replacement);
     unbox->replaceAllUsesWith(replacement);
     if (lexicalCheck) {
       lexicalCheck->replaceAllUsesWith(replacement);
     }
     load->replaceAllUsesWith(replacement);

     if (lexicalCheck && *insIter == lexicalCheck) {
       insIter++;
     }
     if (*insIter == unbox) {
       insIter++;
     }
     block->discard(unbox);
     if (lexicalCheck) {
       block->discard(lexicalCheck);
     }
     block->discard(load);
   }
 }

 // For each Elements that had a load folded with an unbox, check to see if
 // there is a GuardElementsArePacked node that can be removed. It can't be
 // removed if:
 //     1. There is a loadElement/storeElement use that will not emit a
 //        hole check.
 //     2. There is another use that has not been allow-listed.
 // It is safe to add additional operations to the allow list if they don't
 // require a packed Elements array as input.
 for (auto* elements : optimizedElements) {
   bool canRemovePackedChecks = true;
   Vector<MInstruction*, 4, SystemAllocPolicy> guards;
   for (MUseDefIterator uses(elements); uses; uses++) {
     MInstruction* use = uses.def()->toInstruction();
     if (use->isGuardElementsArePacked()) {
       if (!guards.append(use)) {
         return false;
       }
     } else if (use->isLoadElement()) {
       if (!use->toLoadElement()->needsHoleCheck()) {
         canRemovePackedChecks = false;
         break;
       }
     } else if (use->isStoreElement()) {
       if (!use->toStoreElement()->needsHoleCheck()) {
         canRemovePackedChecks = false;
         break;
       }
     } else if (use->isLoadElementAndUnbox() || use->isInitializedLength() ||
                use->isArrayLength()) {
       // These operations are not affected by the packed flag.
       continue;
     } else {
       canRemovePackedChecks = false;
       break;
     }
   }
   if (!canRemovePackedChecks) {
     continue;
   }
   for (auto* guard : guards) {
     guard->block()->discard(guard);
   }
 }

 return true;
}

// Reorder the blocks in the loop starting at the given header to be contiguous.
static void MakeLoopContiguous(MIRGraph& graph, MBasicBlock* header,
                              size_t numMarked) {
 MBasicBlock* backedge = header->backedge();

 MOZ_ASSERT(header->isMarked(), "Loop header is not part of loop");
 MOZ_ASSERT(backedge->isMarked(), "Loop backedge is not part of loop");

 // If there are any blocks between the loop header and the loop backedge
 // that are not part of the loop, prepare to move them to the end. We keep
 // them in order, which preserves RPO.
 ReversePostorderIterator insertIter = graph.rpoBegin(backedge);
 insertIter++;
 MBasicBlock* insertPt = *insertIter;

 // Visit all the blocks from the loop header to the loop backedge.
 size_t headerId = header->id();
 size_t inLoopId = headerId;
 size_t notInLoopId = inLoopId + numMarked;
 ReversePostorderIterator i = graph.rpoBegin(header);
 for (;;) {
   MBasicBlock* block = *i++;
   MOZ_ASSERT(block->id() >= header->id() && block->id() <= backedge->id(),
              "Loop backedge should be last block in loop");

   if (block->isMarked()) {
     // This block is in the loop.
     block->unmark();
     block->setId(inLoopId++);
     // If we've reached the loop backedge, we're done!
     if (block == backedge) {
       break;
     }
   } else {
     // This block is not in the loop. Move it to the end.
     graph.moveBlockBefore(insertPt, block);
     block->setId(notInLoopId++);
   }
 }
 MOZ_ASSERT(header->id() == headerId, "Loop header id changed");
 MOZ_ASSERT(inLoopId == headerId + numMarked,
            "Wrong number of blocks kept in loop");
 MOZ_ASSERT(notInLoopId == (insertIter != graph.rpoEnd() ? insertPt->id()
                                                         : graph.numBlocks()),
            "Wrong number of blocks moved out of loop");
}

// Reorder the blocks in the graph so that loops are contiguous.
bool jit::MakeLoopsContiguous(MIRGraph& graph) {
 // Visit all loop headers (in any order).
 for (MBasicBlockIterator i(graph.begin()); i != graph.end(); i++) {
   MBasicBlock* header = *i;
   if (!header->isLoopHeader()) {
     continue;
   }

   // Mark all blocks that are actually part of the loop.
   bool canOsr;
   size_t numMarked = MarkLoopBlocks(graph, header, &canOsr);

   // If the loop isn't a loop, don't try to optimize it.
   if (numMarked == 0) {
     continue;
   }

   // If there's an OSR block entering the loop in the middle, it's tricky,
   // so don't try to handle it, for now.
   if (canOsr) {
     UnmarkLoopBlocks(graph, header);
     continue;
   }

   // Move all blocks between header and backedge that aren't marked to
   // the end of the loop, making the loop itself contiguous.
   MakeLoopContiguous(graph, header, numMarked);
 }

 return true;
}

static MDefinition* SkipIterObjectUnbox(MDefinition* ins) {
 if (ins->isGuardIsNotProxy()) {
   ins = ins->toGuardIsNotProxy()->input();
 }
 if (ins->isUnbox()) {
   ins = ins->toUnbox()->input();
 }
 return ins;
}

static MDefinition* SkipBox(MDefinition* ins) {
 if (ins->isBox()) {
   return ins->toBox()->input();
 }
 return ins;
}

static MObjectToIterator* FindObjectToIteratorUse(MDefinition* ins) {
 for (MUseIterator use(ins->usesBegin()); use != ins->usesEnd(); use++) {
   if (!(*use)->consumer()->isDefinition()) {
     continue;
   }
   MDefinition* def = (*use)->consumer()->toDefinition();
   if (def->isGuardIsNotProxy()) {
     MObjectToIterator* recursed = FindObjectToIteratorUse(def);
     if (recursed) {
       return recursed;
     }
   } else if (def->isUnbox()) {
     MObjectToIterator* recursed = FindObjectToIteratorUse(def);
     if (recursed) {
       return recursed;
     }
   } else if (def->isObjectToIterator()) {
     return def->toObjectToIterator();
   }
 }

 return nullptr;
}

bool jit::OptimizeIteratorIndices(const MIRGenerator* mir, MIRGraph& graph) {
 bool changed = false;

 for (ReversePostorderIterator blockIter = graph.rpoBegin();
      blockIter != graph.rpoEnd();) {
   MBasicBlock* block = *blockIter++;
   for (MInstructionIterator insIter(block->begin());
        insIter != block->end();) {
     MInstruction* ins = *insIter;
     insIter++;
     if (!graph.alloc().ensureBallast()) {
       return false;
     }

     MDefinition* receiver = nullptr;
     MDefinition* idVal = nullptr;
     MDefinition* setValue = nullptr;
     if (ins->isMegamorphicHasProp() &&
         ins->toMegamorphicHasProp()->hasOwn()) {
       receiver = ins->toMegamorphicHasProp()->object();
       idVal = ins->toMegamorphicHasProp()->idVal();
     } else if (ins->isHasOwnCache()) {
       receiver = ins->toHasOwnCache()->value();
       idVal = ins->toHasOwnCache()->idval();
     } else if (ins->isMegamorphicLoadSlotByValue()) {
       receiver = ins->toMegamorphicLoadSlotByValue()->object();
       idVal = ins->toMegamorphicLoadSlotByValue()->idVal();
     } else if (ins->isMegamorphicLoadSlotByValuePermissive()) {
       receiver = ins->toMegamorphicLoadSlotByValuePermissive()->object();
       idVal = ins->toMegamorphicLoadSlotByValuePermissive()->idVal();
     } else if (ins->isGetPropertyCache()) {
       receiver = ins->toGetPropertyCache()->value();
       idVal = ins->toGetPropertyCache()->idval();
     } else if (ins->isMegamorphicSetElement()) {
       receiver = ins->toMegamorphicSetElement()->object();
       idVal = ins->toMegamorphicSetElement()->index();
       setValue = ins->toMegamorphicSetElement()->value();
     } else if (ins->isSetPropertyCache()) {
       receiver = ins->toSetPropertyCache()->object();
       idVal = ins->toSetPropertyCache()->idval();
       setValue = ins->toSetPropertyCache()->value();
     }

     if (!receiver) {
       continue;
     }

     // Given the following structure (that occurs inside for-in loops or
     // when iterating a scalar-replaced Object.keys result):
     //   obj: some object
     //   iter: ObjectToIterator <obj>
     //   iterLoad: IteratorMore <iter> | LoadIteratorElement <iter, index>
     //   access: HasProp/GetElem <obj> <iterLoad>
     // If the iterator object has an indices array, we can speed up the
     // property access:
     // 1. If the property access is a HasProp looking for own properties,
     //    then the result will always be true if the iterator has indices,
     //    because we only populate the indices array for objects with no
     //    enumerable properties on the prototype.
     // 2. If the property access is a GetProp, then we can use the contents
     //    of the indices array to find the correct property faster than
     //    the megamorphic cache.
     // 3. If the property access is a SetProp, then we can use the contents
     //    of the indices array to find the correct slots faster than the
     //    megamorphic cache.
     //
     // In some cases involving Object.keys, we can also end up with a pattern
     // like this:
     //
     //   obj1: some object
     //   obj2: some object
     //   iter1: ObjectToIterator <obj1>
     //   iter2: ObjectToIterator <obj2>
     //   iterLoad: LoadIteratorElement <iter1>
     //   access: GetElem <obj2> <iterLoad>
     //
     // This corresponds to `obj2[Object.keys(obj1)[index]]`. In the general
     // case we can't do much with this, but if obj1 and obj2 have the same
     // shape, then we may reuse the iterator, in which case iter1 == iter2.
     // In that case, we can optimize the access as if it were using iter2,
     // at the cost of a single comparison to see if iter1 == iter2.
#ifdef JS_CODEGEN_X86
     // The ops required for this want more registers than is convenient on
     // x86
     bool supportObjectKeys = false;
#else
     bool supportObjectKeys = true;
#endif

     MObjectToIterator* iter = nullptr;
     MObjectToIterator* otherIter = nullptr;
     MDefinition* iterElementIndex = nullptr;
     if (idVal->isIteratorMore()) {
       auto* iterNext = idVal->toIteratorMore();

       if (!iterNext->iterator()->isObjectToIterator()) {
         continue;
       }

       iter = iterNext->iterator()->toObjectToIterator();
       if (SkipIterObjectUnbox(iter->object()) !=
           SkipIterObjectUnbox(receiver)) {
         continue;
       }
     } else if (supportObjectKeys && SkipBox(idVal)->isLoadIteratorElement()) {
       auto* iterLoad = SkipBox(idVal)->toLoadIteratorElement();

       if (!iterLoad->iter()->isObjectToIterator()) {
         continue;
       }

       iter = iterLoad->iter()->toObjectToIterator();
       if (SkipIterObjectUnbox(iter->object()) !=
           SkipIterObjectUnbox(receiver)) {
         if (!setValue) {
           otherIter = FindObjectToIteratorUse(SkipIterObjectUnbox(receiver));
         }

         if (!otherIter || !otherIter->block()->dominates(ins->block())) {
           continue;
         }
       }
       iterElementIndex = iterLoad->index();
     } else {
       continue;
     }

     MOZ_ASSERT_IF(iterElementIndex, supportObjectKeys);
     MOZ_ASSERT_IF(otherIter, supportObjectKeys);

     MInstruction* indicesCheck = nullptr;
     if (otherIter) {
       indicesCheck = MIteratorsMatchAndHaveIndices::New(
           graph.alloc(), otherIter->object(), iter, otherIter);
     } else {
       indicesCheck =
           MIteratorHasIndices::New(graph.alloc(), iter->object(), iter);
     }

     MInstruction* replacement;
     if (ins->isHasOwnCache() || ins->isMegamorphicHasProp()) {
       MOZ_ASSERT(!setValue);
       replacement = MConstant::NewBoolean(graph.alloc(), true);
     } else if (ins->isMegamorphicLoadSlotByValue() ||
                ins->isMegamorphicLoadSlotByValuePermissive() ||
                ins->isGetPropertyCache()) {
       MOZ_ASSERT(!setValue);
       if (iterElementIndex) {
         replacement = MLoadSlotByIteratorIndexIndexed::New(
             graph.alloc(), receiver, iter, iterElementIndex);
       } else {
         replacement =
             MLoadSlotByIteratorIndex::New(graph.alloc(), receiver, iter);
       }
     } else {
       MOZ_ASSERT(ins->isMegamorphicSetElement() || ins->isSetPropertyCache());
       MOZ_ASSERT(setValue);
       if (iterElementIndex) {
         replacement = MStoreSlotByIteratorIndexIndexed::New(
             graph.alloc(), receiver, iter, iterElementIndex, setValue);
       } else {
         replacement = MStoreSlotByIteratorIndex::New(graph.alloc(), receiver,
                                                      iter, setValue);
       }
     }

     if (!block->wrapInstructionInFastpath(ins, replacement, indicesCheck)) {
       return false;
     }

     iter->setWantsIndices(true);
     changed = true;

     // Advance to join block.
     blockIter = graph.rpoBegin(block->getSuccessor(0)->getSuccessor(0));
     break;
   }
 }
 if (changed && !AccountForCFGChanges(mir, graph,
                                      /*updateAliasAnalysis=*/false)) {
   return false;
 }

 return true;
}

// =====================================================================
//
// Debug printing

void jit::DumpHashedPointer(GenericPrinter& out, const void* p) {
#ifdef JS_JITSPEW
 if (!p) {
   out.printf("NULL");
   return;
 }
 char tab[27] = "abcdefghijklmnopqrstuvwxyz";
 MOZ_ASSERT(tab[26] == '\0');
 mozilla::HashNumber hash = mozilla::AddToHash(mozilla::HashNumber(0), p);
 hash %= (26 * 26 * 26 * 26 * 26);
 char buf[6];
 for (int i = 0; i <= 4; i++) {
   buf[i] = tab[hash % 26];
   hash /= 26;
 }
 buf[5] = '\0';
 out.printf("%s", buf);
#endif
}

void jit::DumpMIRDefinitionID(GenericPrinter& out, const MDefinition* def,
                             bool showDetails) {
#ifdef JS_JITSPEW
 if (!def) {
   out.printf("(null)");
   return;
 }
 if (showDetails) {
   DumpHashedPointer(out, def);
   out.printf(".");
 }
 out.printf("%u", def->id());
#endif
}

void jit::DumpMIRDefinition(GenericPrinter& out, const MDefinition* def,
                           bool showDetails) {
#ifdef JS_JITSPEW
 DumpMIRDefinitionID(out, def, showDetails);
 out.printf(" = %s.", StringFromMIRType(def->type()));
 if (def->isConstant()) {
   def->printOpcode(out);
 } else {
   MDefinition::PrintOpcodeName(out, def->op());
 }

 // Get any extra bits of text that the MIR node wants to show us.  Both the
 // vector and the strings added to it belong to this function, so both will
 // be automatically freed at exit.
 ExtrasCollector extras;
 def->getExtras(&extras);
 for (size_t i = 0; i < extras.count(); i++) {
   out.printf(" %s", extras.get(i).get());
 }

 for (size_t i = 0; i < def->numOperands(); i++) {
   out.printf(" ");
   DumpMIRDefinitionID(out, def->getOperand(i), showDetails);
 }

 if (def->dependency() && showDetails) {
   out.printf(" DEP=");
   DumpMIRDefinitionID(out, def->dependency(), showDetails);
 }

 if (def->hasUses()) {
   out.printf("   uses=");
   bool first = true;
   for (auto use = def->usesBegin(); use != def->usesEnd(); use++) {
     MNode* consumer = (*use)->consumer();
     if (!first) {
       out.printf(",");
     }
     if (consumer->isDefinition()) {
       out.printf("%d", consumer->toDefinition()->id());
     } else {
       out.printf("?");
     }
     first = false;
   }
 }

 if (def->hasAnyFlags() && showDetails) {
   out.printf("   flags=");
   bool first = true;
#  define OUTPUT_FLAG(_F)                          \
   do {                                           \
     if (def->is##_F()) {                         \
       out.printf("%s%s", first ? "" : ",", #_F); \
       first = false;                             \
     }                                            \
   } while (0);
   MIR_FLAG_LIST(OUTPUT_FLAG);
#  undef OUTPUT_FLAG
 }
#endif
}

void jit::DumpMIRBlockID(GenericPrinter& out, const MBasicBlock* block,
                        bool showDetails) {
#ifdef JS_JITSPEW
 if (!block) {
   out.printf("Block(null)");
   return;
 }
 out.printf("Block");
 if (showDetails) {
   out.printf(".");
   DumpHashedPointer(out, block);
   out.printf(".");
 }
 out.printf("%u", block->id());
#endif
}

void jit::DumpMIRBlock(GenericPrinter& out, MBasicBlock* block,
                      bool showDetails) {
#ifdef JS_JITSPEW
 out.printf("  ");
 DumpMIRBlockID(out, block, showDetails);
 out.printf(" -- preds=[");
 for (uint32_t i = 0; i < block->numPredecessors(); i++) {
   MBasicBlock* pred = block->getPredecessor(i);
   out.printf("%s", i == 0 ? "" : ", ");
   DumpMIRBlockID(out, pred, showDetails);
 }
 out.printf("] -- LD=%u -- K=%s -- s-w-phis=", block->loopDepth(),
            block->nameOfKind());
 if (block->successorWithPhis()) {
   DumpMIRBlockID(out, block->successorWithPhis(), showDetails);
   out.printf(",#%u\n", block->positionInPhiSuccessor());
 } else {
   out.printf("(null)\n");
 }
 for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd());
      iter != end; iter++) {
   out.printf("    ");
   jit::DumpMIRDefinition(out, *iter, showDetails);
   out.printf("\n");
 }
 for (MInstructionIterator iter(block->begin()), end(block->end());
      iter != end; iter++) {
   out.printf("    ");
   DumpMIRDefinition(out, *iter, showDetails);
   out.printf("\n");
 }
#endif
}

void jit::DumpMIRGraph(GenericPrinter& out, MIRGraph& graph, bool showDetails) {
#ifdef JS_JITSPEW
 for (ReversePostorderIterator block(graph.rpoBegin());
      block != graph.rpoEnd(); block++) {
   DumpMIRBlock(out, *block, showDetails);
 }
#endif
}

void jit::DumpMIRExpressions(GenericPrinter& out, MIRGraph& graph,
                            const CompileInfo& info, const char* phase,
                            bool showDetails) {
#ifdef JS_JITSPEW
 if (!JitSpewEnabled(JitSpew_MIRExpressions)) {
   return;
 }

 out.printf("===== %s =====\n", phase);

 DumpMIRGraph(out, graph, showDetails);

 if (info.compilingWasm()) {
   out.printf("===== end wasm MIR dump =====\n");
 } else {
   out.printf("===== %s:%u =====\n", info.filename(), info.lineno());
 }
#endif
}