js/src/jit/UnrollLoops.cpp

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

#include "mozilla/Maybe.h"

#include <stdio.h>

#include "jit/DominatorTree.h"
#include "jit/IonAnalysis.h"
#include "jit/MIRGraph.h"

namespace js {
namespace jit {

// [SMDOC] Loop unroller implementation summary
//
// This is a simple loop unroller, intended (initially at least) to handle only
// wasm loops, with the aims of amortizing the per-iteration interrupt check
// cost, and of lifting an initial iteration outside the loop so as to
// facilitate subsequent optimizations.  Unrolling and peeling can be selected
// independently, so the available choices are: peeling only, unrolling only,
// or both peeling and unrolling.
//
// The flow of control (for a single function) is roughly:
//
// (0) The top level function is UnrollLoops.
//
// (1) UnrollLoops calls FindInitialCandidates to identify "initial candidate"
//     loops in the function.  These are innermost loops.  Non-innermost loops
//     cannot be unrolled/peeled.
//
// (2) FindInitialCandidates counts blocks and value defs in each initial
//     candidate, creating an initial score which increases with loop size.
//
// (3) Back in UnrollLoops, initial candidates whose initial score does not
//     exceed InitialCandidateThreshold proceed to the next stage in the
//     process: they are passed to function AnalyzeLoop.
//
// (4) AnalyzeLoop, as called from UnrollLoops, checks many structural
//     invariants on each loop, since the core unroll machinery depends on
//     those invariants.  It also makes a final determination for each loop, as
//     to whether the loop should be peeled, unrolled, peeled and unrolled, or
//     be left unchanged.  In the latter case it returns one of a few reasons
//     why the loop is to be left unchanged.
//
// (5) AnalyzeLoop also identifies, for a loop, its basic blocks, the set of
//     blocks it jumps to when exiting, and the values defined in the loop
//     which are used afterwards.
//
// (6) Back in UnrollLoops, we now know which loops are suitable for
//     processing, what processing is to happen to them, and what their blocks
//     are.  This is used to construct and initialize a `struct UnrollState`
//     for each loop candidate that made it this far.
//
// (7) Before a loop can be unrolled, single-argument phi nodes need to be
//     added to its exit target blocks, to "catch" values defined in the loop
//     that are used afterwards.  This is a limited conversion into what is
//     called "Loop-Closed SSA form" in the GCC/Clang literature.  UnrollLoops
//     calls AddClosingPhisForLoop to get this done.  This is done for all
//     loops before proceeding further.
//
// (8) Finally, we get to the core of the unrolling: the loops are handed to
//     UnrollAndOrPeelLoop in turn.  This has extensive comments; a summary
//     of the actions is:
//     - blocks, phis and normal instructions are cloned so as to create
//       the extra loop body copies.
//     - the new blocks are added to the loop's UnrollState::blockTable.
//     - during cloning, value uses are remapped to the correct iteration
//       using an MDefinitionRemapper.
//     - also during cloning, the new values are parked in a ValueTable for
//       later reference.
//     - control flow edges and predecessor vectors in the new and original
//       block sets are fixed up, using RemapEdgeSource and
//       RemapEdgeDestination.
//     - header block phi nodes are fixed up in both the body copies
//       and the original.
//     - new exiting blocks are created, so as to maintain the invariant
//       that there are no critical edges.
//     - for exit target blocks, both their predecessor arrays and phi nodes
//       (as installed by AddClosingPhisForLoop) are augmented to handle
//       the new exit edges.
//     - Wasm interrupt checks in all but the last body copy are nop'd out.
//     - If peeling is required, the back edge of the unrolled loop is changed
//       so it points at the second body copy, not the first (the original).
//     - Finally, the new blocks are installed in the MIRGraph.
//
// (9) Back in UnrollLoops, once all loops have been processed,
//     some function-level fixups are done:
//     - the blocks are renumbered
//     - the dominator tree is rebuilt
//
// UnrollLoops now returns to OptimizeMIR, handing back an indication of how
// many loops were processed.  OptimizeMIR will tidy up the resulting function
// by re-running GVN, empty block removal, and possibly other transformations.

// The core logic in UnrollAndOrPeelLoop is heavily commented but still
// nearly incomprehensible.  For debugging and modification it is helpful to
// use the Dump{Block,Value}Table* routines provided.

// The logic below functions without reference to block IDs or value IDs.

// Much of the logic uses simple scans over vectors (classes BlockVector,
// Matrix, SimpleSet, MDefinitionRemapper) rather than more complex data
// structures.  The loops we process are small, which keeps the costs of these
// scans low.  The InitialCandidateThreshold value used limits most processed
// loops to about 6 blocks and 30-ish value definitions.

// The idiom `blockTable.rowContains(0, block)` in the logic below means
// "is `block` in the original loop?"

// =====================================================================
//
// Tunables

// As a crude first pass for filtering out unsuitable candidates, top level
// function UnrollLoops calculates a size-related value for each candidate,
// with lower values indicating more desirability for unrolling/peeling.
// Candidates with a score above this value will not be unrolled.  Reducing the
// value therefore reduces the aggressiveness of the unroller.
const float InitialCandidateThreshold = 100.0;

// On further analysis of candidates that pass the above test, we have more
// detailed limitations on size.  The specified action will not be taken for a
// loop if the associated metric exceeds the constants here.  Hence increasing
// these values increases the aggressiveness of the unroller, but only to point
// where the `InitialCandidateThreshold` would have cut it off.

// Loops with more than this number of basic blocks or values (phis and normal
// definitions) will be excluded from peeling.  The actual numbers are pretty
// much pulled out of a hat.
const size_t MaxBlocksForPeel = 12;
const size_t MaxValuesForPeel = 150;

// Loops with more than this number of blocks or values will be excluded from
// unrolling.  Unrolling adds multiple copies of the loop body, whereas peeling
// adds only one, so it seems prudent to make unrolling less aggressive than
// peeling.
const size_t MaxBlocksForUnroll = 10;
const size_t MaxValuesForUnroll = 100;

// =====================================================================
//
// BlockVector, a vector of MBasicBlock*s.

using BlockVector = mozilla::Vector<MBasicBlock*, 32, SystemAllocPolicy>;

static bool BlockVectorContains(const BlockVector& vec,
                                const MBasicBlock* block) {
  for (const MBasicBlock* b : vec) {
    if (b == block) {
      return true;
    }
  }
  return false;
}

// =====================================================================
//
// Matrix, a 2-D array of pointers

template <typename T, int N, typename AP>
class Matrix {
  static_assert(std::is_pointer<T>::value);
  mozilla::Vector<T, N, AP> vec_;
  size_t size1_ = 0;
  size_t size2_ = 0;
  inline size_t index(size_t ix1, size_t ix2) const {
    MOZ_ASSERT(ix1 < size1_ && ix2 < size2_);
    return ix1 * size2_ + ix2;
  }

 public:
  [[nodiscard]] bool init(size_t size1, size_t size2) {
    // Not already init'd.
    MOZ_ASSERT(size1_ == 0 && size2_ == 0 && vec_.empty());
    // This would be pointless.
    MOZ_ASSERT(size1 > 0 && size2 > 0);
    // So we can safely multiply them.  InitialCandidateThreshold ensures we'll
    // never have to process a loop anywhere near this big.
    MOZ_RELEASE_ASSERT(size1 <= 1000 && size2 <= 1000);
    size1_ = size1;
    size2_ = size2;
    if (!vec_.resize(size1 * size2)) {
      return false;
    }
    // Resizing also zero-initialises all the `vec_` entries.
    return true;
  }

  inline size_t size1() const {
    MOZ_ASSERT(size1_ * size2_ == vec_.length());
    return size1_;
  }
  inline size_t size2() const {
    MOZ_ASSERT(size1_ * size2_ == vec_.length());
    return size2_;
  }
  inline T get(size_t ix1, size_t ix2) const { return vec_[index(ix1, ix2)]; }
  inline void set(size_t ix1, size_t ix2, T value) {
    vec_[index(ix1, ix2)] = value;
  }

  // Does the matrix slice `[ix1, ..]` contain `value`?
  inline bool rowContains(size_t ix1, const T value) const {
    return findInRow(ix1, value).isSome();
  }

  // Find the column number (ix2) such that entry `[ix1, ix2] == value`.
  mozilla::Maybe<size_t> findInRow(size_t ix1, const T value) const {
    for (size_t ix2 = 0; ix2 < size2_; ix2++) {
      if (get(ix1, ix2) == value) {
        return mozilla::Some(ix2);
      }
    }
    return mozilla::Nothing();
  }
};

using BlockTable = Matrix<MBasicBlock*, 32, SystemAllocPolicy>;
using ValueTable = Matrix<MDefinition*, 128, SystemAllocPolicy>;

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

#ifdef JS_JITSPEW

// For debugging, dump specific rows (loop body copies) of a block table.
static void DumpBlockTableRows(const BlockTable& table, int32_t firstCix,
                               int32_t lastCix, const char* tag) {
  Fprinter& printer(JitSpewPrinter());
  printer.printf("<<<< %s\n", tag);
  for (int32_t cix = firstCix; cix <= lastCix; cix++) {
    if (cix == 0) {
      printer.printf("  -------- Original --------\n");
    } else {
      printer.printf("  -------- Copy %u --------\n", cix);
    }
    for (uint32_t bix = 0; bix < table.size2(); bix++) {
      DumpMIRBlock(printer, table.get(uint32_t(cix), bix),
                   /*showHashedPointers=*/true);
    }
  }
  printer.printf(">>>>\n");
}

// Dump an entire block table.
static void DumpBlockTable(const BlockTable& table, const char* tag) {
  DumpBlockTableRows(table, 0, int32_t(table.size1()) - 1, tag);
}

// Dump just the original loop body in a block table.
static void DumpBlockTableRowZero(const BlockTable& table, const char* tag) {
  DumpBlockTableRows(table, 0, 0, tag);
}

// Dump a value table.
static void DumpValueTable(const ValueTable& table, const char* tag) {
  Fprinter& printer(JitSpewPrinter());
  printer.printf("<<<< %s\n", tag);
  for (uint32_t cix = 0; cix < table.size1(); cix++) {
    if (cix == 0) {
      printer.printf("  -------- Original --------\n");
    } else {
      printer.printf("  -------- Copy %u --------\n", cix);
    }
    for (uint32_t vix = 0; vix < table.size2(); vix++) {
      printer.printf("    ");
      DumpMIRDefinition(printer, table.get(cix, vix),
                        /*showHashedPointers=*/true);
      printer.printf("\n");
    }
  }
  printer.printf(">>>>\n");
}

#endif  // JS_JITSPEW

// =====================================================================
//
// SimpleSet, a set of pointers

template <typename T, int N, typename AP>
class SimpleSet {
  static_assert(std::is_pointer<T>::value);
  mozilla::Vector<T, N, AP> vec_;

 public:
  [[nodiscard]] bool copy(const SimpleSet<T, N, AP>& other) {
    vec_.clear();
    for (T elem : other.vec_) {
      if (!vec_.append(elem)) {
        return false;
      }
    }
    return true;
  }
  bool contains(T t) const {
    for (auto* existing : vec_) {
      if (existing == t) {
        return true;
      }
    }
    return false;
  }
  [[nodiscard]] bool add(T t) {
    MOZ_ASSERT(t);
    return contains(t) ? true : vec_.append(t);
  }
  bool empty() const { return vec_.empty(); }
  size_t size() const { return vec_.length(); }
  T get(size_t ix) const { return vec_[ix]; }
};

using BlockSet = SimpleSet<MBasicBlock*, 8, SystemAllocPolicy>;
using ValueSet = SimpleSet<MDefinition*, 64, SystemAllocPolicy>;

// =====================================================================
//
// MDefinitionRemapper, a very simple MDefinition*-remapping class.

class MDefinitionRemapper {
  using Pair = std::pair<MDefinition*, MDefinition*>;
  mozilla::Vector<Pair, 32, SystemAllocPolicy> pairs;

 public:
  MDefinitionRemapper() {}
  // Register `original` as a key in the mapper, and map it to itself.
  [[nodiscard]] bool enregister(MDefinition* original) {
    MOZ_ASSERT(original);
    for (auto& p : pairs) {
      (void)p;
      MOZ_ASSERT(p.first != original);  // not mapped at all
      MOZ_ASSERT(p.second == p.first);  // no `update` calls happened yet
    }
    return pairs.append(std::pair(original, original));
  }
  // Look up the binding for `original` in the mapper.
  MDefinition* lookup(const MDefinition* original) const {
    MOZ_ASSERT(original);
    MDefinition* res = nullptr;
    for (auto& p : pairs) {
      if (p.first == original) {
        res = p.second;
        break;
      }
    }
    return res;
  }
  // Update the mapper so as to map `original` to `replacement`.  `original`
  // must have previously been registered with ::enregister.
  void update(const MDefinition* original, MDefinition* replacement) {
    MOZ_ASSERT(original && replacement);
    MOZ_ASSERT(original != replacement);
    for (auto& p : pairs) {
      if (p.first == original) {
        p.second = replacement;
        return;
      }
    }
    MOZ_CRASH();  // asked to update a non-existent key
  }
};

// =====================================================================
//
// MakeReplacementInstruction / MakeReplacementPhi

// Make a cloned version of `ins`, but with its arguments remapped by `mapper`.
static MInstruction* MakeReplacementInstruction(
    TempAllocator& alloc, const MDefinitionRemapper& mapper,
    const MInstruction* ins) {
  MDefinitionVector inputs(alloc);
  for (size_t i = 0; i < ins->numOperands(); i++) {
    MDefinition* old = ins->getOperand(i);
    MDefinition* replacement = mapper.lookup(old);
    if (!replacement) {
      // The mapper didn't map it, which means that `old` is a value that's not
      // defined in the loop body.  So leave it unchanged.
      replacement = old;
    }
    if (!inputs.append(replacement)) {
      return nullptr;
    }
  }
  return ins->clone(alloc, inputs);
}

// Make a cloned version of `phi`, but with its arguments remapped by `mapper`.
static MPhi* MakeReplacementPhi(TempAllocator& alloc,
                                const MDefinitionRemapper& mapper,
                                const MPhi* phi) {
  MDefinitionVector inputs(alloc);
  for (size_t i = 0; i < phi->numOperands(); i++) {
    MDefinition* old = phi->getOperand(i);
    MDefinition* replacement = mapper.lookup(old);
    if (!replacement) {
      replacement = old;
    }
    if (!inputs.append(replacement)) {
      return nullptr;
    }
  }
  return phi->clone(alloc, inputs);
}

// =====================================================================
//
// UnrollState

enum class UnrollMode { Peel, Unroll, PeelAndUnroll };

struct UnrollState {
  // What should happen to the specified loop.
  const UnrollMode mode;

  // The central data structure: BlockTable, a 2-D array of block pointers.
  //
  // To create copies of the original loop body, we need to copy the original
  // blocks and fix up the inter-block edges and phis appropriately.  This
  // edge-fixup is done without reference to the block IDs; instead it is done
  // purely on the basis of the MBasicBlock* values themselves.  Hence it does
  // not make any assumption about the ordering of the block ID values.
  //
  // The block copies are managed using a 2-D array of block pointers, via
  // which we can uniformly access the original and new blocks.  The array is
  // indexed by `(copy index, block index in copy)`.  Both indices are
  // zero-based.  The sequencing of blocks implied by "block index in copy" is
  // the sequence produced by the RPO iterator as it enumerates the blocks in
  // the loop.
  //
  // Per the above, note that "block index" (`bix` in the code) is a zero-based
  // index into the RPO sequence of blocks in the loop and is not to be
  // confused with the pre-existing concept of "block ID".
  //
  // Note also that the required unroll factor (including that for the peeled
  // copy, if any) is equal to the first dimension of `blockTable`, and the
  // number of blocks in the original loop is implied by the second dimension
  // of `blockTable`.  Hence neither value needs to be stored explicitly.
  BlockTable blockTable;

  // The set of blocks arrived at (directly) by exiting branches in the
  // original loop.  FIXME: try to make const
  /*const*/ BlockSet exitTargetBlocks;

  // The set of values (MDefinition*s) defined in the original loop and used
  // afterwards.
  /*const*/ ValueSet exitingValues;

  explicit UnrollState(UnrollMode mode) : mode(mode) {}

  bool doPeeling() const {
    return mode == UnrollMode::Peel || mode == UnrollMode::PeelAndUnroll;
  }
  bool doUnrolling() const {
    return mode == UnrollMode::Unroll || mode == UnrollMode::PeelAndUnroll;
  }
};

// =====================================================================
//
// AnalyzeLoop and AnalysisResult

// Summarises the result of a detailed analysis of a candidate loop, producing
// either a recommendation about what to do with it, or a reason why it should
// be left unchanged.
enum class AnalysisResult {
  // OOM during analysis
  OOM,

  // The chosen transformation for the loop ..
  Peel,
  Unroll,
  PeelAndUnroll,

  // .. or .. reasons why the loop can't be unrolled:
  //
  // The unrolling/peeling machinery below relies on the fact that MIR loops
  // are heavily constrained in their structure.  AnalyzeLoop checks the
  // relevant invariants carefully, with this value indicating non-compliance.
  // Top level function UnrollLoops will MOZ_CRASH if this happens.
  BadInvariants,
  // Cannot be handled by the unroller: if the loop defines value(s) that are
  // used after the loop, then we can only handle the case where it has one
  // exiting branch.
  TooComplex,
  // The loop contains MIR nodes that are uncloneable
  Uncloneable,
  // The loop has too many blocks or values
  TooLarge,
  // The loop is otherwise unsuitable:
  // * contains a call or table switch
  // * is an infinite loop
  Unsuitable
};

#ifdef JS_JITSPEW
static const char* Name_of_AnalysisResult(AnalysisResult res) {
  switch (res) {
    case AnalysisResult::OOM:
      return "OOM";
    case AnalysisResult::Peel:
      return "Peel";
    case AnalysisResult::Unroll:
      return "Unroll";
    case AnalysisResult::PeelAndUnroll:
      return "PeelAndUnroll";
    case AnalysisResult::BadInvariants:
      return "BadInvariants";
    case AnalysisResult::TooComplex:
      return "TooComplex";
    case AnalysisResult::Uncloneable:
      return "Uncloneable";
    case AnalysisResult::TooLarge:
      return "TooLarge";
    case AnalysisResult::Unsuitable:
      return "Unsuitable";
    default:
      MOZ_CRASH();
  }
}
#endif

// Examine the original loop in `originalBlocks` for unrolling suitability,
// and, if acceptable, collect auxiliary information:
//
// * the set of blocks that are direct exit targets for the loop
// * the set of values defined in the loop AND used afterwards

static AnalysisResult AnalyzeLoop(const BlockVector& originalBlocks,
                                  BlockSet* exitTargetBlocks,
                                  ValueSet* exitingValues) {
  MOZ_ASSERT(exitTargetBlocks->empty());
  MOZ_ASSERT(exitingValues->empty());

  // ==== BEGIN check invariants on the loop structure ====

  // The unroller/peeler below depends on these invariants.
  // In summary (where nBlocks == originalBlocks.length()):
  //
  // * At least 2 blocks in original loop (1 for header phis + possible insns,
  //   >= 0 for "ordinary" blocks, 1 for the backedge jump)
  //
  // * originalBlocks[0] is a loop header
  // * originalBlocks[nBlocks-1] == originalBlocks[0]->backedge
  //
  // * all blocks in original loop have at least one insn
  // * all blocks in original loop have a control insn as their last insn
  // * all blocks in original loop have non-control insns for all other insns
  // * all blocks in original loop have loop depth > 0
  //
  // * none of originalBlocks[0 .. nBlocks-2] (inclusive) jumps to header
  //
  // * originalBlocks[nBlocks-1] jumps unconditionally to header
  //
  // * original header node has 2 preds
  // * original header node pred[0] is from outside the loop, and
  //   pred[1] is from inside the loop.
  //
  // * original header node phis all have 2 args
  // * original header node phis have arg[0] from outside the loop
  //   (because pred[0] is the loop-entry edge)
  // * original header node phis have their arg[1] as
  //   -- (almost always) defined in the loop -- loop carried variable
  //   -- (very occasionally) defined outside the loop -- in which case
  //      this is just a vanilla phi, nothing to do with the loop.
  //   Hence there is nothing to check for phi arg[1]s, but leaving this
  //   here for clarity.
  //
  // Aside: how can a loop head phi not depend on a value defined within the
  // loop?  Consider the strange-but-valid case
  //
  //    x = 5 ; loop { .. x = 7; .. }
  //
  // The loop head phi will merge the initial value (5) and the loop-defined
  // value in the usual way.  Imagine now the loop is LICMd; the loop defined
  // value `x = 7;` is observed to be invariant and so is lifted out of the
  // loop.  Hence the loop head phi will have both args defined outside the
  // loop.

  // * At least 2 blocks in original loop (1 for header phis + possible insns,
  //   >= 0 for "ordinary" blocks, 1 for the backedge jump)
  const size_t numBlocksInOriginal = originalBlocks.length();
  if (numBlocksInOriginal < 2) {
    return AnalysisResult::BadInvariants;
  }

  // * originalBlocks[0] is a loop header
  // * originalBlocks[nBlocks-1] == originalBlocks[0]->backedge
  {
    MBasicBlock* header = originalBlocks[0];
    if (!header->isLoopHeader() ||
        header->backedge() != originalBlocks[numBlocksInOriginal - 1]) {
      return AnalysisResult::BadInvariants;
    }
  }

  // * all blocks in original loop have at least one insn
  // * all blocks in original loop have a control insn as their last insn
  // * all blocks in original loop have non-control insns for all other insns
  // * all blocks in original loop have loop depth > 0
  for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
    MBasicBlock* block = originalBlocks[bix];
    // This is a bit lame, but ..
    size_t numInsns = 0;
    for (MInstructionIterator insnIter(block->begin());
         insnIter != block->end(); insnIter++) {
      numInsns++;
    }
    if (numInsns < 1) {
      return AnalysisResult::BadInvariants;
    }
    bool ok = true;
    size_t curInsn = 0;
    for (MInstructionIterator insnIter(block->begin());
         insnIter != block->end(); insnIter++) {
      MInstruction* insn = *insnIter;
      if (curInsn == numInsns - 1) {
        ok = ok && insn->isControlInstruction();
      } else {
        ok = ok && !insn->isControlInstruction();
      }
      curInsn++;
    }
    MOZ_ASSERT(curInsn == numInsns);  // internal logic
    ok = ok && block->loopDepth() > 0;
    if (!ok) {
      return AnalysisResult::BadInvariants;
    }
  }

  // * none of originalBlocks[0 .. nBlocks-2] (inclusive) jumps to header
  {
    MBasicBlock* header = originalBlocks[0];
    for (uint32_t bix = 0; bix < numBlocksInOriginal - 1; bix++) {
      MBasicBlock* block = originalBlocks[bix];
      if (!block->hasLastIns()) {
        return AnalysisResult::BadInvariants;
      }
      MControlInstruction* lastIns = block->lastIns();
      for (size_t i = 0; i < lastIns->numSuccessors(); i++) {
        if (lastIns->getSuccessor(i) == header) {
          return AnalysisResult::BadInvariants;
        }
      }
    }
  }

  // originalBlocks[nBlocks-1] jumps unconditionally to header
  {
    MBasicBlock* header = originalBlocks[0];
    MBasicBlock* backedge = originalBlocks[numBlocksInOriginal - 1];
    if (!backedge->hasLastIns()) {
      return AnalysisResult::BadInvariants;
    }
    MControlInstruction* lastIns = backedge->lastIns();
    if (!lastIns->isGoto() || lastIns->toGoto()->target() != header) {
      return AnalysisResult::BadInvariants;
    }
  }

  // * original header node has 2 preds
  // * original header node pred[0] is from outside the loop.
  //   pred[1] is from inside the loop.
  {
    MBasicBlock* header = originalBlocks[0];
    if (header->numPredecessors() != 2 ||
        BlockVectorContains(originalBlocks, header->getPredecessor(0)) ||
        !BlockVectorContains(originalBlocks, header->getPredecessor(1))) {
      return AnalysisResult::BadInvariants;
    }
  }

  // * original header node phis all have 2 args
  // * original header node phis have arg[0] from outside the loop
  //   (because pred[0] is the loop-entry edge)
  // * original header node phis have their arg[1] as
  //   -- (almost always) defined in the loop -- loop carried variable
  //   -- (very occasionally) defined outside the loop -- in which case
  //      this is just a vanilla phi, nothing to do with the loop.
  //   Hence there is nothing to check for phi arg[1]s, but leaving this
  //   here for clarity.
  {
    MBasicBlock* header = originalBlocks[0];
    for (MPhiIterator phiIter(header->phisBegin());
         phiIter != header->phisEnd(); phiIter++) {
      MPhi* phi = *phiIter;
      if (phi->numOperands() != 2 ||
          BlockVectorContains(originalBlocks, phi->getOperand(0)->block())) {
        return AnalysisResult::BadInvariants;
      }
    }
  }

  // ==== END check invariants on the loop structure ====

  // Check that all the insns are cloneable.
  for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
    MBasicBlock* block = originalBlocks[bix];
    for (MInstructionIterator insIter(block->begin()); insIter != block->end();
         insIter++) {
      MInstruction* ins = *insIter;
      if (ins->isWasmCallCatchable() || ins->isWasmCallUncatchable() ||
          ins->isWasmReturnCall() || ins->isTableSwitch()
          /* TODO: other node kinds unsuitable for unrolling? */) {
        return AnalysisResult::Unsuitable;
      }
      if (!ins->canClone()) {
        // `ins->opName()` will show the name of the insn kind, if you want to
        // see it
        return AnalysisResult::Uncloneable;
      }
    }
  }

  // More analysis: make up a set of blocks that are not in the loop, but which
  // are jumped to from within the loop.  We will need this later.
  for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
    MBasicBlock* block = originalBlocks[bix];
    MControlInstruction* lastIns = block->lastIns();  // asserted safe above
    for (size_t i = 0; i < lastIns->numSuccessors(); i++) {
      MBasicBlock* succ = lastIns->getSuccessor(i);
      // See if `succ` is any of the blocks in the (original) loop.  If not,
      // add it to `exitTargetBlocks`.
      if (!BlockVectorContains(originalBlocks, succ)) {
        if (!exitTargetBlocks->add(succ)) {
          return AnalysisResult::OOM;
        }
      }
    }
  }

  // If the loop has zero exits, we consider it sufficiently mutant to ignore
  // (it's an infinite loop?)
  if (exitTargetBlocks->empty()) {
    return AnalysisResult::Unsuitable;
  }

  // Even more analysis: make up a set of MDefinition*s that are defined in the
  // original loop and which are used after the loop.  We will later need to
  // add phi nodes that generate the correct values for these, since, after
  // unrolling, these values will have multiple definition points (one per
  // unrolled iteration).  While we're at it, count the number of values
  // defined in the original loop.
  size_t numValuesInOriginal = 0;
  for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
    MBasicBlock* block = originalBlocks[bix];
    // Check all phi nodes ..
    for (MPhiIterator phiIter(block->phisBegin()); phiIter != block->phisEnd();
         phiIter++) {
      numValuesInOriginal++;
      MPhi* phi = *phiIter;
      bool usedAfterLoop = false;
      // Is the value of `phi` used after the loop?
      for (MUseIterator useIter(phi->usesBegin()); useIter != phi->usesEnd();
           useIter++) {
        MUse* use = *useIter;
        if (!BlockVectorContains(originalBlocks, use->consumer()->block())) {
          usedAfterLoop = true;
          break;
        }
      }
      if (usedAfterLoop && !exitingValues->add(phi)) {
        return AnalysisResult::OOM;
      }
    }
    // .. and all normal nodes ..
    for (MInstructionIterator insnIter(block->begin());
         insnIter != block->end(); insnIter++) {
      numValuesInOriginal++;
      MInstruction* insn = *insnIter;
      bool usedAfterLoop = false;
      // Is the value of `insn` used after the loop?
      for (MUseIterator useIter(insn->usesBegin()); useIter != insn->usesEnd();
           useIter++) {
        MUse* use = *useIter;
        if (!BlockVectorContains(originalBlocks, use->consumer()->block())) {
          usedAfterLoop = true;
          break;
        }
      }
      if (usedAfterLoop && !exitingValues->add(insn)) {
        return AnalysisResult::OOM;
      }
    }
  }

  // Due to limitations in AddClosingPhisForLoop (see comments there),
  // currently we can only unroll loops where, either:
  //
  // * no value defined in the loop is used afterwards, in which case we handle
  //   any number of exits from the loop.
  //
  // * one or more values defined in the loop is used afterwards, in which case
  //   there must be one exit point from the loop.
  //
  // IOW we can't handle multiple exits *and* values defined in the loop.
  if (exitTargetBlocks->size() >= 2 && exitingValues->size() > 0) {
    return AnalysisResult::TooComplex;
  }

  // There is an invariant that a loop exit target block does not contain any
  // phis.  This is really just the no-critical-edges invariant.
  //
  // By definition, a loop exit block has at least one successor in the loop
  // and at least one successor outside the loop.  If the loop exit target has
  // phis, that would imply it has multiple predecessors.  But then the edge
  // would be critical, because it connects a block with multiple successors to
  // a block with multiple predecessors.
  //
  // So enforce that; it simplifies the addition of loop-closing phis that will
  // happen shortly.
  for (size_t i = 0; i < exitTargetBlocks->size(); i++) {
    MBasicBlock* exitTargetBlock = exitTargetBlocks->get(i);
    if (!exitTargetBlock->phisEmpty()) {
      return AnalysisResult::BadInvariants;
    }
    // Also we need this, since we'll be adding single-argument phis to this
    // block during loop-closing.
    if (exitTargetBlock->numPredecessors() != 1) {
      return AnalysisResult::BadInvariants;
    }
  }

  // At this point, we've worked through all invariant- and structural- reasons
  // why we can't/shouldn't unroll/peel this loop.  Now we need to decide which
  // (or both) of those actions should happen.
  bool peel = true;
  bool unroll = true;
  if (numBlocksInOriginal > MaxBlocksForPeel ||
      numValuesInOriginal > MaxValuesForPeel) {
    peel = false;
  }
  if (numBlocksInOriginal > MaxBlocksForUnroll ||
      numValuesInOriginal > MaxValuesForUnroll) {
    unroll = false;
  }

  if (peel) {
    return unroll ? AnalysisResult::PeelAndUnroll : AnalysisResult::Peel;
  } else {
    return unroll ? AnalysisResult::Unroll : AnalysisResult::TooLarge;
  }
}

// =====================================================================
//
// AddClosingPhisForLoop

// Add "loop-closing phis" for values defined in a loop and used afterwards.
// In GCC parlance, the resulting form is called LCSSA (Loop-Closed SSA).  This
// is a very limited intervention in that it can only handle a single exit in a
// loop, thereby restricting the places where the phis should go to the
// one-and-only exit block, and avoiding the need to compute iterated dominance
// frontiers.

[[nodiscard]]
static bool AddClosingPhisForLoop(TempAllocator& alloc,
                                  const UnrollState& state) {
  // If no values exit the loop, we don't care how many exit target blocks
  // there are, and need to make no changes.
  if (state.exitingValues.empty()) {
    return true;
  }

  // Ensured by AnalyzeLoop
  MOZ_ASSERT(state.exitTargetBlocks.size() == 1);
  MBasicBlock* targetBlock = state.exitTargetBlocks.get(0);
  // Ensured by AnalyzeLoop.  Required because we're adding single-arg phis
  // to `targetBlock`.
  MOZ_ASSERT(targetBlock->numPredecessors() == 1);

  for (size_t i = 0; i < state.exitingValues.size(); i++) {
    MDefinition* exitingValue = state.exitingValues.get(i);
    // In `targetBlock`, add a single-argument phi node that "catches"
    // `exitingValue`, and change all uses of `exitingValue` to be the phi
    // node instead.
    MPhi* phi = MPhi::New(alloc, exitingValue->type());
    if (!phi) {
      return false;
    }
    targetBlock->addPhi(phi);
    // Change all uses of `exitingValue` outside of the loop into uses of
    // `phi`.
    for (MUseIterator useIter(exitingValue->usesBegin()),
         useIterEnd(exitingValue->usesEnd());
         useIter != useIterEnd;
         /**/) {
      MUse* use = *useIter++;
      if (state.blockTable.rowContains(0, use->consumer()->block())) {
        continue;
      }
      MOZ_ASSERT(use->consumer());
      use->replaceProducer(phi);
    }
    // Finally, make `phi` be the one-and-only user of `exitingValue`.
    if (!phi->addInputFallible(exitingValue)) {
      return false;
    }
  }

  // Invariant that should hold at this point: for each exiting value, all uses
  // of it outside the loop should only be phi nodes.
  for (size_t i = 0; i < state.exitingValues.size(); i++) {
    MDefinition* exitingValue = state.exitingValues.get(i);
    for (MUseIterator useIter(exitingValue->usesBegin());
         useIter != exitingValue->usesEnd(); useIter++) {
      mozilla::DebugOnly<MUse*> use = *useIter;
      MOZ_ASSERT_IF(!state.blockTable.rowContains(0, use->consumer()->block()),
                    use->consumer()->isDefinition() &&
                        use->consumer()->toDefinition()->isPhi());
    }
  }

  return true;
}

// =====================================================================
//
// UnrollAndOrPeelLoop

[[nodiscard]]
static bool UnrollAndOrPeelLoop(MIRGraph& graph, UnrollState& state) {
  // Prerequisites (assumed):
  // * AnalyzeLoop has approved this loop for peeling and/or unrolling
  // * AddClosingPhisForLoop has been called for it
  //
  // We expect `state` to be ready to go, with the caveat that only the first
  // row of entries in `state.blockTable` have been filled in (these are the
  // original loop blocks).  All other entries are null and will be filled in
  // by this routine.
  //
  // Almost all the logic here is to do with unrolling.  That's because peeling
  // (done far below) can be done by a trivial modification of the loop
  // resulting from unrolling: make the backedge jump to the second copy of the
  // loop body rather than the first.  That leaves the first copy (that is, the
  // original loop body) in a "will only be executed once" state, as we desire.

  // We need this so often it's worth pulling out specially.
  const MBasicBlock* originalHeader = state.blockTable.get(0, 0);
  MOZ_ASSERT(originalHeader->isLoopHeader());

#ifdef JS_JITSPEW
  if (JitSpewEnabled(JitSpew_UnrollDetails)) {
    Fprinter& printer(JitSpewPrinter());
    printer.printf(
        "<<<< ORIGINAL FUNCTION (after LCSSA-ification of chosen loops)\n");
    DumpMIRGraph(printer, graph, /*showHashedPointers=*/true);
    printer.printf(">>>>\n");
  }
#endif

  // Decide on the total unroll factor.  "Copy #0" is the original loop, so the
  // number of new copies is `unrollFactor - 1`.  For example, if the original
  // loop was `loop { B; }` then with `unrollFactor == 3`, the unrolled loop
  // will be `loop { B; B; B; }`.  Note that the value acquired here includes
  // the copy needed for peeling, if that has been requested.
  const uint32_t unrollFactor = state.blockTable.size1();
  // The logic below will fail if this doesn't hold.
  MOZ_ASSERT(unrollFactor >= 2);

  // The number of blocks in the original loop.
  const uint32_t numBlocksInOriginal = state.blockTable.size2();

  // The number of values (phis and normal values) in the original loop.
  uint32_t numValuesInOriginal = 0;
  for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
    MBasicBlock* block = state.blockTable.get(0, bix);
    // This is very feeble, but I can't think of anything better.
    for (MPhiIterator phiIter(block->phisBegin()); phiIter != block->phisEnd();
         phiIter++) {
      numValuesInOriginal++;
    }
    for (MInstructionIterator insnIter(block->begin());
         insnIter != block->end(); insnIter++) {
      numValuesInOriginal++;
    }
  }
  // `numValuesInOriginal` is const after this point.

#ifdef JS_JITSPEW
  if (JitSpewEnabled(JitSpew_UnrollDetails)) {
    DumpBlockTableRowZero(state.blockTable, "ORIGINAL LOOP");
    Fprinter& printer(JitSpewPrinter());
    printer.printf("<<<< EXIT TARGET BLOCKS: ");
    for (size_t i = 0; i < state.exitTargetBlocks.size(); i++) {
      MBasicBlock* targetBlock = state.exitTargetBlocks.get(i);
      DumpMIRBlockID(printer, targetBlock, /*showHashedPointers=*/true);
      printer.printf(" ");
    }
    printer.printf(">>>>\n");
    printer.printf("<<<< EXITING VALUES: ");
    for (size_t i = 0; i < state.exitingValues.size(); i++) {
      MDefinition* exitingValue = state.exitingValues.get(i);
      DumpMIRDefinitionID(printer, exitingValue, /*showHashedPointers=*/true);
      printer.printf(" ");
    }
    printer.printf(">>>>\n");
  }
#endif

  // At this point, `state.blockTable` row zero contains the original blocks,
  // and all other rows are nulled out.

  // Set up the value table.  This is a structure similar to
  // `state.blockTable`: a 2-D array of values.  This is local to this routine
  // rather than being part of `state` because it is only needed here, and can
  // take quite a lot of space.
  //
  // As with the block table, the main (actually, only) purpose of the value
  // table is to make it possible to find equivalent definitions in different
  // iterations.  Also as above, "value index" (`vix` in the code) is a
  // zero-based index into the sequence of values (including phis) in the loop
  // as generated by the RPO traversal of the loop's blocks.

  ValueTable valueTable;
  if (!valueTable.init(unrollFactor, numValuesInOriginal)) {
    return false;
  }

  // Copy the original values into row zero of `valueTable`, parking them
  // end-to-end, without regard to block boundaries.  All other rows remain
  // nulled out for now.
  {
    uint32_t vix = 0;
    for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
      MBasicBlock* block = state.blockTable.get(0, bix);
      for (MPhiIterator phiIter(block->phisBegin());
           phiIter != block->phisEnd(); phiIter++) {
        valueTable.set(0, vix, *phiIter);
        vix++;
      }
      for (MInstructionIterator insnIter(block->begin());
           insnIter != block->end(); insnIter++) {
        valueTable.set(0, vix, *insnIter);
        vix++;
      }
    }
    MOZ_ASSERT(vix == numValuesInOriginal);
  }

  // Set up the value remapper.  This maps MDefinitions* in the original body
  // to their "current" definition in new bodies.  The only allowed keys are
  // MDefinition*s from the original body.  To enforce this, the keys have to
  // be "registered" before use.
  MDefinitionRemapper mapper;
  for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
    MBasicBlock* originalBlock = state.blockTable.get(0, bix);
    // Create initial entries in `mapper` for both the normal insns and phi
    // nodes in `originalBlock`.
    for (MPhiIterator phiIter(originalBlock->phisBegin());
         phiIter != originalBlock->phisEnd(); phiIter++) {
      MPhi* originalPhi = *phiIter;
      if (!mapper.enregister(originalPhi)) {
        return false;
      }
    }
    for (MInstructionIterator insnIter(originalBlock->begin());
         insnIter != originalBlock->end(); insnIter++) {
      MInstruction* originalInsn = *insnIter;
      if (!mapper.enregister(originalInsn)) {
        return false;
      }
    }
  }

  // Now we begin with the very core of the unrolling activity.

  // Create new empty blocks for copy indices 1 .. (unrollFactor-1)
  const CompileInfo& info = originalHeader->info();
  for (uint32_t cix = 1; cix < unrollFactor; cix++) {
    for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
      MBasicBlock* empty = MBasicBlock::New(graph, info, /*pred=*/nullptr,
                                            MBasicBlock::Kind::NORMAL);
      if (!empty) {
        return false;
      }
      empty->setLoopDepth(state.blockTable.get(0, bix)->loopDepth());
      // We don't bother to set the block's ID, because the logic below not
      // depend on it. In any case the blocks will get renumbered at the end of
      // UnrollLoops, so it doesn't matter what we choose here.  Unrolling
      // still works even if we don't set the ID to anything.
      MOZ_ASSERT(!state.blockTable.get(cix, bix));
      state.blockTable.set(cix, bix, empty);
    }
  }

  // Copy verbatim, blocks in the original loop, into our new copies.
  // For each copy of the loop ..
  for (uint32_t cix = 1; cix < unrollFactor; cix++) {
    // For each block in the original copy ..
    uint32_t vix = 0;
    for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
      MBasicBlock* originalBlock = state.blockTable.get(0, bix);
      MBasicBlock* clonedBlock = state.blockTable.get(cix, bix);

      // Clone the phi nodes, but don't update the mapper until all original
      // arguments have been looked up.  This is required because the phi nodes
      // collectively implement a parallel assignment; there is no implied
      // sequentiality.
      mozilla::Vector<std::pair<const MPhi*, MPhi*>, 16, SystemAllocPolicy>
          mapperUpdates;
      for (MPhiIterator phiIter(originalBlock->phisBegin());
           phiIter != originalBlock->phisEnd(); phiIter++) {
        const MPhi* originalPhi = *phiIter;
        MPhi* clonedPhi =
            MakeReplacementPhi(graph.alloc(), mapper, originalPhi);
        if (!clonedPhi) {
          return false;
        }
        clonedBlock->addPhi(clonedPhi);
        MOZ_ASSERT(!valueTable.get(cix, vix));
        valueTable.set(cix, vix, clonedPhi);
        vix++;
        if (!mapperUpdates.append(std::pair(originalPhi, clonedPhi))) {
          return false;
        }
      }
      for (auto& p : mapperUpdates) {
        // Update the value mapper.  The `originalPhi` values must be part of
        // the original loop body and so must already have a key in `mapper`.
        mapper.update(p.first, p.second);
      }

      // Cloning the instructions is simpler, since we can incrementally update
      // the mapper.
      for (MInstructionIterator insnIter(originalBlock->begin());
           insnIter != originalBlock->end(); insnIter++) {
        const MInstruction* originalInsn = *insnIter;
        MInstruction* clonedInsn =
            MakeReplacementInstruction(graph.alloc(), mapper, originalInsn);
        if (!clonedInsn) {
          return false;
        }
        clonedBlock->insertAtEnd(clonedInsn);
        MOZ_ASSERT(!valueTable.get(cix, vix));
        valueTable.set(cix, vix, clonedInsn);
        vix++;
        // Update the value mapper.  `originalInsn` must be part of the
        // original loop body and so must already have a key in `mapper`.
        mapper.update(originalInsn, clonedInsn);
      }

      // Clone the block's predecessor array
      MOZ_ASSERT(clonedBlock->numPredecessors() == 0);
      for (uint32_t i = 0; i < originalBlock->numPredecessors(); i++) {
        MBasicBlock* pred = originalBlock->getPredecessor(i);
        if (!clonedBlock->appendPredecessor(pred)) {
          return false;
        }
      }
    }

    MOZ_ASSERT(vix == numValuesInOriginal);

    // Check we didn't mess up the valueTable ordering relative to the original
    // (best effort assertion).
    for (vix = 0; vix < numValuesInOriginal; vix++) {
      MOZ_ASSERT(valueTable.get(cix, vix)->op() ==
                 valueTable.get(0, vix)->op());
    }
  }

#ifdef JS_JITSPEW
  if (JitSpewEnabled(JitSpew_UnrollDetails)) {
    DumpValueTable(valueTable, "VALUE TABLE (final)");
  }
#endif

  // Fix up (remap) inter-block edges in both the original and copies, using
  // uniform indexing as above (original = index 0, copies = indices >= 1):

  // For a block with copy-index N, inspect each edge.  Determine the role the
  // edge-destination (target) plays in the original copy:
  //
  // * backedge
  //     -> remap to header node of copy (N + 1) % unrollFactor
  //        (so, generates a backedge in the last copy)
  // * internal jump within the original body
  //     -> remap to corresponding block in copy N
  // * jump to after the original body
  //     -> unchanged (it is an exiting edge)
  // * jump to before the original body
  //     -> this can't happen
  //        (but if it did, it would be just another exit block)
  auto RemapEdgeDestination =
      [=, &state](uint32_t cix, MBasicBlock* oldDestination) -> MBasicBlock* {
    // `oldDestination` is the target of a control-flow insn in the original
    // loop.  Figure out what its replacement should be, for copy index `cix`
    // (with `cix == 0` meaning the original copy).

    // If it is a back edge, remap to the header node of the next copy, with
    // wraparound for the last copy.
    if (oldDestination == state.blockTable.get(0, 0)) {
      MOZ_ASSERT(oldDestination == originalHeader);
      return state.blockTable.get((cix + 1) % unrollFactor, 0);
    }

    // If it is to some other node within the original body, remap to the
    // corresponding node in this copy.
    for (uint32_t i = 1; i < numBlocksInOriginal; i++) {
      if (oldDestination == state.blockTable.get(0, i)) {
        return state.blockTable.get(cix, i);
      }
    }

    // The target of the edge is not in the original loop.  Either it's to
    // after the loop (an exiting branch) or it is to before the loop, although
    // that would be bizarre and probably illegal.  Either way, leave it
    // unchanged.
    return oldDestination;
  };

  // Similarly, for an edge that claims to come from `oldSource` in the
  // original loop, determine where it should come from if we imagine that it
  // applies to copy index `cix`.
  auto RemapEdgeSource = [=, &state](uint32_t cix,
                                     MBasicBlock* oldSource) -> MBasicBlock* {
    if (oldSource == state.blockTable.get(0, numBlocksInOriginal - 1)) {
      // Source is backedge node in the original loop.  Remap to the backedge
      // node in the previous iteration.
      MOZ_ASSERT(oldSource == originalHeader->backedge());
      return state.blockTable.get(cix == 0 ? (unrollFactor - 1) : (cix - 1),
                                  numBlocksInOriginal - 1);
    }
    for (uint32_t i = 0; i < numBlocksInOriginal - 1; i++) {
      if (oldSource == state.blockTable.get(0, i)) {
        // Source is a non-backedge node in the original loop.  Remap it to
        // the equivalent node in this copy.
        return state.blockTable.get(cix, i);
      }
    }
    // Source is not in the original loop.  Leave unchanged.
    return oldSource;
  };

  // Work through all control-flow instructions in all copies and remap their
  // edges.
  // For each copy of the loop, including the original ..
  for (uint32_t cix = 0; cix < unrollFactor; cix++) {
    // For each block in the copy ..
    for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
      MBasicBlock* b = state.blockTable.get(cix, bix);
      MControlInstruction* lastI = b->lastIns();
      if (lastI->isGoto()) {
        MGoto* insn = lastI->toGoto();
        insn->setTarget(RemapEdgeDestination(cix, insn->target()));
      } else if (lastI->isTest()) {
        MTest* insn = lastI->toTest();
        insn->setIfTrue(RemapEdgeDestination(cix, insn->ifTrue()));
        insn->setIfFalse(RemapEdgeDestination(cix, insn->ifFalse()));
      } else {
        // The other existing control instructions are MTableSwitch,
        // MUnreachable, MWasmTrap, MWasmReturn, and MWasmReturnVoid.
        // MTableSwitch is ruled out above.  The others end a block without a
        // successor, which means that they can't be loop blocks
        // (MarkLoopBlocks marks blocks that are predecessors of the back
        // edge.)  So we don't expect to see them here.
        MOZ_CRASH();
      }
    }
  }

  // Also we need to remap within the each block's predecessors vector.
  // We have to do this backwards to stop RemapEdgeSource from asserting.
  // For each copy of the loop, including the original ..
  for (int32_t cix = unrollFactor - 1; cix >= 0; cix--) {
    // For each block in the copy ..
    for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
      MBasicBlock* block = state.blockTable.get(cix, bix);
      for (uint32_t i = 0; i < block->numPredecessors(); i++) {
        MBasicBlock* oldPred = block->getPredecessor(i);
        MBasicBlock* newPred = RemapEdgeSource(cix, oldPred);
        block->setPredecessor(i, newPred);
      }
    }
  }

  // Clean up the header node copies (but not for the original copy) since they
  // all still claim to have two predecessors, the first of which is the entry
  // edge from outside the loop.  This is no longer true, so delete that
  // predecessor.  Remove the corresponding Phi args too.  This leaves
  // one-argument phis, meh.
  for (uint32_t cix = 1; cix < unrollFactor; cix++) {
    MBasicBlock* block = state.blockTable.get(cix, 0);
    MOZ_ASSERT(block->numPredecessors() == 2);  // from AnalyzeLoop
    block->erasePredecessor(0);
    MOZ_ASSERT(block->numPredecessors() == 1);  // duh
    for (MPhiIterator phiIter(block->phisBegin()); phiIter != block->phisEnd();
         phiIter++) {
      MPhi* phi = *phiIter;
      MOZ_ASSERT(phi->numOperands() == 2);  // from AnalyzeLoop
      phi->removeOperand(0);
      MOZ_ASSERT(phi->numOperands() == 1);
    }
  }

  // Fix up the phi nodes in the original header; the previous step did not do
  // that.  Specifically, the second arg in each phi -- which are values that
  // flow in from the backedge block -- need to be the ones from the last body
  // copy; but currently they are from the original copy.  At this point, the
  // `mapper` should be able to tell us the correct value.
  for (MPhiIterator phiIter(originalHeader->phisBegin());
       phiIter != originalHeader->phisEnd(); phiIter++) {
    MPhi* phi = *phiIter;
    MOZ_ASSERT(phi->numOperands() == 2);  // from AnalyzeLoop
    // phi arg[0] is defined before the loop.  Ensured by AnalyzeLoop.
    MOZ_ASSERT(!state.blockTable.rowContains(0, phi->getOperand(0)->block()));
    // phi arg[1] is almost always defined in the loop (hence it is a
    // loop-carried value) but is very occasionally defined before the loop
    // (so it is unrelated to the loop).  Proceed with maximum paranoia.
    MDefinition* operand1 = phi->getOperand(1);
    MDefinition* replacement = mapper.lookup(operand1);
    // If we didn't find a replacement (unlikely but possible) then
    // `operand1` must be defined before the loop.
    MOZ_ASSERT((replacement == nullptr) ==
               !state.blockTable.rowContains(0, operand1->block()));
    if (replacement) {
      phi->replaceOperand(1, replacement);
    }
  }

  // Now we need to fix up the exit target blocks, by adding sources of exiting
  // edges to their `predecessors_` vectors and updating their phi nodes
  // accordingly.  Recall that those phi nodes were previously installed in
  // these blocks by AddClosingPhisForLoop.
  //
  // Currently the exit target blocks mention only predecessors in the original
  // loop, but they also need to mention equivalent predecessors in each of the
  // loop copies.
  for (uint32_t cix = 0; cix < unrollFactor; cix++) {
    for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
      MBasicBlock* block = state.blockTable.get(cix, bix);
      MControlInstruction* lastIns = block->lastIns();
      for (size_t i = 0; i < lastIns->numSuccessors(); i++) {
        MBasicBlock* succ = lastIns->getSuccessor(i);
        if (!state.exitTargetBlocks.contains(succ)) {
          // This isn't an exiting edge -- not interesting.
          continue;
        }
        // If `cix` is zero (the original body), we expect `succ` to already
        // list `block` as a predecessor.  If `cix` is nonzero (a body copy)
        // then we expect `succ` *not* to list it, and we must add it.
        mozilla::DebugOnly<bool> found = false;
        for (uint32_t j = 0; j < succ->numPredecessors(); j++) {
          if (block == succ->getPredecessor(j)) {
            found = true;
            break;
          }
        }
        MOZ_ASSERT((cix == 0) == found);
        if (cix > 0) {
          if (!succ->appendPredecessor(block)) {
            return false;
          }
          for (MPhiIterator phiIter(succ->phisBegin());
               phiIter != succ->phisEnd(); phiIter++) {
            MPhi* phi = *phiIter;
            // "+ 1" because we just added a predecessor
            MOZ_ASSERT(phi->numOperands() + 1 == succ->numPredecessors());
            MDefinition* exitingValue = phi->getOperand(0);
            MOZ_ASSERT(state.exitingValues.contains(exitingValue));
            // `exitingValue` is defined in the original loop body.  We need to
            // find the equivalent value in copy `cix` so we can add it as an
            // argument to the phi.  This bit is the one-and-only reason for
            // `valueTable`s existence.
            mozilla::Maybe<size_t> colIndex =
                valueTable.findInRow(0, exitingValue);
            MOZ_ASSERT(colIndex.isSome());  // We must find it!
            MDefinition* equivValue = valueTable.get(cix, colIndex.value());
            if (!phi->addInputFallible(equivValue)) {
              return false;
            }
          }
        }
      }
    }
  }

  // At this point the control flow is correct.  But we may now have critical
  // edges where none existed before.  Consider a loop {Block1, Block2} with an
  // exit target Block9:
  //
  //   Block1
  //     stuff1
  //     Goto Block2
  //   Block2
  //     stuff2
  //     Test true->Block1(== continue) false->Block9(== break)
  //   ...
  //   Block9
  //     this is a loop-exit target
  //     preds = Block2
  //
  // After factor-of-2 unrolling:
  //
  //   Block1
  //     stuff1
  //     Goto Block2
  //   Block2
  //     stuff2
  //     Test true->Block3(== continue) false->Block9(== break)
  //   Block3
  //     stuff3
  //     Goto Block4
  //   Block4
  //     stuff4
  //     Test true->Block1(== continue) false->Block9(== break)
  //   ...
  //   Block9
  //     preds = Block2, Block4
  //
  // Now the exiting edges (Block2 to Block9 and Block4 to Block9) are critical.
  //
  // The obvious fix is to insert a new block on each exiting edge.

  mozilla::Vector<MBasicBlock*, 16, SystemAllocPolicy> splitterBlocks;
  for (uint32_t cix = 0; cix < unrollFactor; cix++) {
    for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
      MBasicBlock* block = state.blockTable.get(cix, bix);
      // Inspect all successors of `block`.  If any are exiting edges, create a
      // new block and route through that instead.
      MControlInstruction* lastIns = block->lastIns();
      for (size_t i = 0; i < lastIns->numSuccessors(); i++) {
        MBasicBlock* succ = lastIns->getSuccessor(i);
        if (!state.exitTargetBlocks.contains(succ)) {
          // This isn't an exiting edge -- not interesting.
          continue;
        }
        // Invent a new block.
        MBasicBlock* splitter =
            MBasicBlock::New(graph, info, block, MBasicBlock::Kind::SPLIT_EDGE);
        if (!splitter || !splitterBlocks.append(splitter)) {
          return false;
        }
        splitter->setLoopDepth(succ->loopDepth());
        // As with empty-block creation earlier in this routine, we don't
        // bother to set the block's ID since none of the logic depends on it,
        // and it will eventually be renumbered anyway by UnrollLoops.
        MGoto* jump = MGoto::New(graph.alloc(), succ);
        if (!jump) {
          return false;
        }
        splitter->insertAtEnd(jump);
        // For the target, fix up the `predecessor_` entry.
        mozilla::DebugOnly<bool> found = false;
        for (uint32_t j = 0; j < succ->numPredecessors(); j++) {
          if (succ->getPredecessor(j) == block) {
            succ->setPredecessor(j, splitter);
            found = true;
            break;
          }
        }
        // Finally, reroute the jump to `succ` via `splitter`.
        lastIns->replaceSuccessor(i, splitter);
        MOZ_ASSERT(found);
      }
    }
  }

  // Now the control flow is correct *and* we don't have any critical edges.
  // Fix up the `successorWithPhis_` and `positionInPhiSuccessor_` fields in
  // both the unrolled loop and the splitter blocks, thusly:
  //
  // For all blocks `B` in the unrolled loop, and for all splitter blocks, fix
  // up the `B.successorWithPhis_` and `B.positionInPhiSuccessor_` fields.
  // Each block may have at maximum one successor that has phi nodes, in which
  // case `B.successorWithPhis_` should point at that block.  And
  // `B.positionInPhiSuccessor_` should indicate the index that successor's
  // `predecessors_` vector, of B.
  {
    // Make up a list of blocks to fix up, then process them.
    mozilla::Vector<MBasicBlock*, 32 + 16, SystemAllocPolicy> workList;
    for (uint32_t cix = 0; cix < unrollFactor; cix++) {
      for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
        MBasicBlock* block = state.blockTable.get(cix, bix);
        if (!workList.append(block)) {
          return false;
        }
      }
    }
    for (MBasicBlock* block : splitterBlocks) {
      if (!workList.append(block)) {
        return false;
      }
    }
    // Now process them.
    for (MBasicBlock* block : workList) {
      // Inspect `block`s successors.
      MBasicBlock* succWithPhis = nullptr;
      MControlInstruction* lastIns = block->lastIns();
      // Determine `succWithPhis`, if one exists.
      for (size_t i = 0; i < lastIns->numSuccessors(); i++) {
        MBasicBlock* succ = lastIns->getSuccessor(i);
        if (succ->phisEmpty()) {
          continue;
        }
        MOZ_ASSERT(succ);
        // `succ` is a successor to `block` that has phis.  So we can't already
        // have seen a (different) successor.
        if (!succWithPhis) {
          succWithPhis = succ;
        } else if (succWithPhis == succ) {
          // ignore duplicate successors
        } else {
          // More than one successor with phis.  Structural invariants
          // invalidated.  Give up.
          MOZ_CRASH();
        }
      }
      // Annotate `block`.
      if (!succWithPhis) {
        block->setSuccessorWithPhis(nullptr, 0);
      } else {
        MOZ_ASSERT(!succWithPhis->phisEmpty());
        // Figure out which of `succWithPhis`s predecessors `block` is.
        // Should we assert `succWithPhis->predecessors_` is duplicate-free?
        uint32_t predIx = UINT32_MAX;  // invalid
        for (uint32_t i = 0; i < succWithPhis->numPredecessors(); i++) {
          if (succWithPhis->getPredecessor(i) == block) {
            predIx = i;
            break;
          }
        }
        MOZ_ASSERT(predIx != UINT32_MAX);
        block->setSuccessorWithPhis(succWithPhis, predIx);
      }
    }
  }

  // Find and remove the MWasmInterruptCheck in all but the last iteration.
  // We don't assume that there is an interrupt check, since
  // wasm::FunctionCompiler::fillArray, at least, generates a loop with no
  // check.
  for (uint32_t cix = 0; cix < unrollFactor - 1; cix++) {
    for (uint32_t vix = 0; vix < numValuesInOriginal; vix++) {
      MDefinition* ins = valueTable.get(cix, vix);
      if (!ins->isWasmInterruptCheck()) {
        continue;
      }
      MWasmInterruptCheck* ic = ins->toWasmInterruptCheck();
      ic->block()->discard(ic);
      valueTable.set(cix, vix, nullptr);
    }
  }

  // We're all done with unrolling.  If peeling was also requested, make a
  // minor modification to the unrolled loop: change the backedge so that,
  // instead of jumping to the first body copy, make it jump to the second body
  // copy.  This leaves the first body copy in a
  // will-only-ever-be-executed-once state, hence achieving peeling.
  if (state.doPeeling()) {
    MBasicBlock* backedge =
        state.blockTable.get(unrollFactor - 1, numBlocksInOriginal - 1);
    MBasicBlock* header0 = state.blockTable.get(0, 0);
    MBasicBlock* header1 = state.blockTable.get(1, 0);
    MOZ_ASSERT(header0 == originalHeader);

    // Fix up the back edge, to make it jump to the second copy of the loop
    // body
    MOZ_ASSERT(backedge->hasLastIns());  // should always hold (AnalyzeLoop)
    MOZ_ASSERT(backedge->lastIns()->isGoto());  // AnalyzeLoop ensures
    MGoto* backedgeG = backedge->lastIns()->toGoto();
    MOZ_ASSERT(backedgeG->target() == header0);  // AnalyzeLoop ensures
    backedgeG->setTarget(header1);
    header0->clearLoopHeader();
    header1->setLoopHeader();
    for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
      MBasicBlock* originalBlock = state.blockTable.get(0, bix);
      MOZ_ASSERT(originalBlock->loopDepth() > 0);
      originalBlock->setLoopDepth(originalBlock->loopDepth() - 1);
    }

    // Fix up the preds of the original header
    MOZ_ASSERT(header0->numPredecessors() == 2);
    MOZ_ASSERT(header0->getPredecessor(1) == backedge);
    header0->erasePredecessor(1);

    // Fix up the preds of the new header
    MOZ_ASSERT(header1->numPredecessors() == 1);
    if (!header1->appendPredecessor(backedge)) {
      return false;
    }

    // Fix up phis of both headers, by moving the second operand of each phi of
    // `header0` to be the second operand of the corresponding phi in
    // `header1`.
    MPhiIterator phiIter0(header0->phisBegin());
    MPhiIterator phiIter1(header1->phisBegin());
    while (true) {
      bool finished0 = phiIter0 == header0->phisEnd();
      mozilla::DebugOnly<bool> finished1 = phiIter1 == header1->phisEnd();
      // The two blocks must have the same number of phis.
      MOZ_ASSERT(finished0 == finished1);
      if (finished0) {
        break;
      }
      MPhi* phi0 = *phiIter0;
      MPhi* phi1 = *phiIter1;
      MOZ_ASSERT(phi0->numOperands() == 2);
      MOZ_ASSERT(phi1->numOperands() == 1);
      MDefinition* phi0arg1 = phi0->getOperand(1);
      phi0->removeOperand(1);
      if (!phi1->addInputFallible(phi0arg1)) {
        return false;
      }
      phiIter0++;
      phiIter1++;
    }

    // Fix the succ-w-phis entry for `backEdge`.  In very rare circumstances,
    // the loop may have no header phis, so this must be conditional.
    if (backedge->successorWithPhis()) {
      MOZ_ASSERT(backedge->successorWithPhis() == header0);
      MOZ_ASSERT(backedge->positionInPhiSuccessor() == 1);
      backedge->setSuccessorWithPhis(header1, 1);
    }
  }

#ifdef JS_JITSPEW
  if (JitSpewEnabled(JitSpew_UnrollDetails)) {
    DumpBlockTable(state.blockTable, "LOOP BLOCKS (final)");
    Fprinter& printer(JitSpewPrinter());
    printer.printf("<<<< SPLITTER BLOCKS\n");
    for (MBasicBlock* block : splitterBlocks) {
      DumpMIRBlock(printer, block, /*showHashedPointers=*/true);
    }
    printer.printf(">>>>\n");
  }
#endif

  // Add the new blocks to the graph.
  {
    // We want to add them to the end of the existing loop.
    MBasicBlock* cursor = state.blockTable.get(0, numBlocksInOriginal - 1);
    for (uint32_t cix = 1; cix < unrollFactor; cix++) {
      for (uint32_t bix = 0; bix < numBlocksInOriginal; bix++) {
        MBasicBlock* addMe = state.blockTable.get(cix, bix);
        graph.insertBlockAfter(cursor, addMe);
        cursor = addMe;
      }
    }
    for (MBasicBlock* addMe : splitterBlocks) {
      graph.insertBlockAfter(cursor, addMe);
      cursor = addMe;
    }
  }

  // UnrollLoops will renumber the blocks and redo the dominator tree once all
  // loops have been unrolled.

#ifdef JS_JITSPEW
  if (JitSpewEnabled(JitSpew_UnrollDetails)) {
    Fprinter& printer(JitSpewPrinter());
    printer.printf("<<<< FUNCTION AFTER UNROLLING\n");
    DumpMIRGraph(printer, graph, /*showHashedPointers=*/true);
    printer.printf(">>>>\n");
  }
#endif

  return true;
}

// =====================================================================
//
// FindInitialCandidates, which finds "initial candidates" for
// unrolling/peeling.  See SMDOC at the top of this file.

struct InitialCandidate {
  MBasicBlock* header;
  uint32_t numBlocks;
  float score;
  bool valid;
  InitialCandidate(MBasicBlock* header, uint32_t numBlocks)
      : header(header), numBlocks(numBlocks), score(0.0), valid(true) {}
};

using InitialCandidateVector =
    mozilla::Vector<InitialCandidate, 64, SystemAllocPolicy>;

[[nodiscard]]
bool FindInitialCandidates(MIRGraph& graph,
                           InitialCandidateVector& initialCandidates) {
  // Find initial candidate loops, and place them in `initialCandidates`.
  MOZ_ASSERT(initialCandidates.empty());

  // TODO: possibly use a linear-time algorithm to find innermost loops, as
  // BackTrackingAllocator.cpp does, rather than the scheme below.
  // See bug 1959074.

  // Collect up the loops in the function.  The iteration order doesn't matter
  // here, but we have to choose something.
  for (auto rpoIter(graph.rpoBegin()), rpoIterEnd(graph.rpoEnd());
       rpoIter != rpoIterEnd; ++rpoIter) {
    MBasicBlock* header = *rpoIter;
    if (!header->isLoopHeader()) {
      continue;
    }

    bool hasOsrEntry;
    size_t numBlocks = MarkLoopBlocks(graph, header, &hasOsrEntry);
    if (numBlocks == 0) {
      // Bogus; skip.
      continue;
    }
    UnmarkLoopBlocks(graph, header);
    if (hasOsrEntry) {
      // Unhandled; skip.
      continue;
    }

    MOZ_RELEASE_ASSERT(numBlocks <= UINT32_MAX);
    if (!initialCandidates.append(InitialCandidate(header, numBlocks))) {
      return false;
    }
  }

  // Sort the loops by size (in blocks).
  std::sort(initialCandidates.begin(), initialCandidates.end(),
            [](const InitialCandidate& cand1, const InitialCandidate& cand2) {
              return cand1.numBlocks < cand2.numBlocks;
            });

  // Remove non-innermost candidates from consideration.  We expect
  // `initialCandidates` to describe contiguous, properly nested candidates.
  // For each loop in `initialCandidates`, scan forwards in the vector and mark
  // as invalid, any subsequent loops that contain it.
  for (size_t i = 0; i < initialCandidates.length(); i++) {
    const InitialCandidate& candI = initialCandidates[i];
    MOZ_ASSERT(candI.numBlocks > 0);

    for (size_t j = i + 1; j < initialCandidates.length(); j++) {
      InitialCandidate& candJ = initialCandidates[j];
      MOZ_ASSERT(candJ.numBlocks > 0);
      // Because sorted by size:
      MOZ_ASSERT(candI.numBlocks <= candJ.numBlocks);
      if (!candJ.valid) {
        // Already invalidated
        continue;
      }

      // Determine relationship of I vs J.  Either non-overlapping, or I is
      // completely contained inside J.  In which case invalidate J.
      MOZ_ASSERT(candI.numBlocks > 0);
      if (candI.header->id() + candI.numBlocks <= candJ.header->id()) {
        continue;  // no overlap
      }
      if (candJ.header->id() + candJ.numBlocks <= candI.header->id()) {
        continue;  // no overlap
      }
      // "I is completely contained within J"
      MOZ_ASSERT(candJ.header->id() <= candI.header->id());
      MOZ_ASSERT(candI.header->id() + candI.numBlocks <=
                 candJ.header->id() + candJ.numBlocks);
      // and they aren't identical
      MOZ_ASSERT(candI.header->id() != candJ.header->id() ||
                 candI.numBlocks != candJ.numBlocks);
      candJ.valid = false;
    }
  }

  // Slide the valid ones to the start of the vector and sort by starting block
  // ID.  This makes it easy to verify that the cands are non-overlapping.
  {
    size_t wr = 0;
    size_t rd;
    for (rd = 0; rd < initialCandidates.length(); rd++) {
      if (initialCandidates[rd].valid) {
        initialCandidates[wr++] = initialCandidates[rd];
      }
    }
    while (wr < rd) {
      initialCandidates.popBack();
      wr++;
    }
  }

  // Sort the loops by header ID.
  std::sort(initialCandidates.begin(), initialCandidates.end(),
            [](const InitialCandidate& cand1, const InitialCandidate& cand2) {
              return cand1.header->id() < cand2.header->id();
            });

  // Now we can conveniently assert non-overlappingness.
  for (size_t i = 1; i < initialCandidates.length(); i++) {
    MOZ_ASSERT(initialCandidates[i - 1].header->id() +
                   initialCandidates[i - 1].numBlocks <=
               initialCandidates[i].header->id());
  }

  // Heuristics: calculate a "score" for each loop, indicating our desire to
  // unroll it.  **Lower** values indicate a higher desirability for unrolling.
  //
  // A loop gets a lower score if:
  // * it is small
  // * it has few blocks
  // * it is deeply nested (currently ignored)

  for (InitialCandidate& cand : initialCandidates) {
    uint32_t nBlocks = cand.numBlocks;
    uint32_t nInsns = 0;
    uint32_t nPhis = 0;

    // Visit each block in the loop
    mozilla::DebugOnly<uint32_t> numBlocksVisited = 0;
    const MBasicBlock* backedge = cand.header->backedge();

    for (auto i(graph.rpoBegin(cand.header)); /**/; ++i) {
      MOZ_ASSERT(i != graph.rpoEnd(),
                 "UnrollLoops: loop blocks overrun graph end");
      MBasicBlock* block = *i;
      numBlocksVisited++;
      for (MInstructionIterator iter(block->begin()); iter != block->end();
           iter++) {
        nInsns++;
      }
      for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd();
           iter++) {
        nPhis++;
      }

      if (block == backedge) {
        break;
      }
    }

    MOZ_ASSERT(numBlocksVisited == nBlocks);

    cand.score =
        10.0 * float(nBlocks) + 2.0 * float(nInsns) + 1.0 * float(nPhis);
  }

  // Sort the loops by `score`.
  std::sort(initialCandidates.begin(), initialCandidates.end(),
            [](const InitialCandidate& cand1, const InitialCandidate& cand2) {
              return cand1.score < cand2.score;
            });

  return true;
}

// =====================================================================
//
// UnrollLoops, the top level of the unroller.

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

#ifdef JS_JITSPEW
  if (JitSpewEnabled(JitSpew_Unroll)) {
    JitSpew(JitSpew_Unroll, "BEGIN UnrollLoops");
  }
#endif

  // Make up a vector of initial candidates, which are innermost loops only,
  // and not too big.

  InitialCandidateVector initialCandidates;
  if (!FindInitialCandidates(graph, initialCandidates)) {
    return false;
  }

#ifdef JS_JITSPEW
  if (JitSpewEnabled(JitSpew_Unroll)) {
    for (const InitialCandidate& cand : initialCandidates) {
      MOZ_ASSERT(cand.valid);
      JitSpew(JitSpew_Unroll, "   initial cand:  score=%-5.1f  blocks=%u-%u",
              cand.score, cand.header->id(),
              cand.header->id() + cand.numBlocks - 1);
    }
  }
#endif

  // Perform a more expensive analysis of the candidates, leading to a further
  // reduction in the set.  For those remaining, an UnrollState is created and
  // initialized.  Also a decision is made whether to unroll only, peel only,
  // or both.

  mozilla::Vector<UnrollState, 32, SystemAllocPolicy> unrollStates;

  for (const InitialCandidate& cand : initialCandidates) {
    if (cand.score > InitialCandidateThreshold) {
      // Give up.  We just sorted them by `score`, so the rest will be even
      // more undesirable for unrolling.
      break;
    }

    // Park the loop's blocks in a vector, so we can hand it off to
    // AnalyzeLoops for examination.  This is the place where the original
    // block sequence, as seen by the entire rest of the machinery, is fixed.
    BlockVector originalBlocks;

    const MBasicBlock* backedge = cand.header->backedge();

    for (auto blockIter(graph.rpoBegin(cand.header)); /**/; ++blockIter) {
      MOZ_ASSERT(blockIter != graph.rpoEnd());
      MBasicBlock* block = *blockIter;
      if (!originalBlocks.append(block)) {
        return false;
      }
      if (block == backedge) {
        break;
      }
    }

    // Analyze the candidate in detail.  If unrolling and/or peeling is
    // approved, this also collects up for us, the loop's target block set and
    // exiting value set.
    BlockSet exitTargetBlocks;
    ValueSet exitingValues;

    AnalysisResult res =
        AnalyzeLoop(originalBlocks, &exitTargetBlocks, &exitingValues);

#ifdef JS_JITSPEW
    if (JitSpewEnabled(JitSpew_Unroll)) {
      MOZ_ASSERT(cand.valid);
      JitSpew(JitSpew_Unroll, "  %13s:  score=%-5.1f  blocks=%u-%u",
              Name_of_AnalysisResult(res), cand.score, cand.header->id(),
              cand.header->id() + cand.numBlocks - 1);
    }
#endif

    switch (res) {
      case AnalysisResult::OOM:
        return false;
      case AnalysisResult::Peel:
      case AnalysisResult::Unroll:
      case AnalysisResult::PeelAndUnroll:
        break;
      case AnalysisResult::BadInvariants:
        MOZ_CRASH("js::jit::UnrollLoops: unexpected incoming MIR");
      case AnalysisResult::TooComplex:
      case AnalysisResult::Uncloneable:
      case AnalysisResult::TooLarge:
      case AnalysisResult::Unsuitable:
        // Ignore this loop
        continue;
      default:
        MOZ_CRASH();
    }

    // The candidate has been accepted for unrolling and/or peeling.  Make an
    // initial UnrollState for it and add it to our collection thereof.

    UnrollMode mode;
    if (res == AnalysisResult::Peel) {
      mode = UnrollMode::Peel;
    } else if (res == AnalysisResult::Unroll) {
      mode = UnrollMode::Unroll;
    } else if (res == AnalysisResult::PeelAndUnroll) {
      mode = UnrollMode::PeelAndUnroll;
    } else {
      MOZ_CRASH();
    }

    if (!unrollStates.emplaceBack(mode)) {
      return false;
    }
    UnrollState* state = &unrollStates.back();
    if (!state->exitTargetBlocks.copy(exitTargetBlocks) ||
        !state->exitingValues.copy(exitingValues)) {
      return false;
    }

    // Ignoring peeling, how many times should we unroll a loop?
    // For example, if the original loop was `loop { B; }` then with
    // `basicUnrollingFactor = 3`, the unrolled loop will be `loop { B; B; B;
    // }`.  If peeling is also requested then we will unroll one more time than
    // this, giving overall result `B; loop { B; B; B; }`.
    uint32_t basicUnrollingFactor = JS::Prefs::wasm_unroll_factor();
    if (basicUnrollingFactor < 2) {
      // It needs to be at least 2, else we're not unrolling at all.
      basicUnrollingFactor = 2;
    } else if (basicUnrollingFactor > 8) {
      // Unrolling gives rapidly diminishing marginal gains.  Even beyond 4
      // there's little benefit to be had.
      basicUnrollingFactor = 8;
    }

    // Decide on the total number of duplicates of the loop body we'll need
    // (including the original).
    uint32_t unrollingFactor;
    if (res == AnalysisResult::Peel) {
      // 1 for the peeled iteration,
      // 1 for the loop (since we are not unrolling it)
      unrollingFactor = 1 + 1;
    } else if (res == AnalysisResult::Unroll) {
      // No peeled iteration, we unroll only
      unrollingFactor = 0 + basicUnrollingFactor;
    } else if (res == AnalysisResult::PeelAndUnroll) {
      // 1 peeled iteration, and we unroll the loop
      unrollingFactor = 1 + basicUnrollingFactor;
    } else {
      MOZ_CRASH();
    }

    // Set up UnrollState::blockTable and copy in the initial loop blocks.
    if (!state->blockTable.init(unrollingFactor, originalBlocks.length())) {
      return false;
    }
    for (uint32_t bix = 0; bix < originalBlocks.length(); bix++) {
      state->blockTable.set(0, bix, originalBlocks[bix]);
    }
  }

  // Now, finally, we have an initialized vector of UnrollStates ready to go.
  // After this point, `originalBlocks` is no longer used.  Also, because of
  // the checking done in AnalyzeLoop, we know the transformations can't fail
  // (apart from OOMing).

  // Add "loop-closing phis" for values defined in the loop and used
  // afterwards.  See comments on AddClosingPhisForLoop.
  for (const UnrollState& state : unrollStates) {
    if (!AddClosingPhisForLoop(graph.alloc(), state)) {
      return false;
    }
  }

  // Actually do the unrolling and/or peeling.
  uint32_t numLoopsPeeled = 0;
  uint32_t numLoopsUnrolled = 0;
  uint32_t numLoopsPeeledAndUnrolled = 0;
  for (UnrollState& state : unrollStates) {
    if (!UnrollAndOrPeelLoop(graph, state)) {
      return false;
    }
    // Update stats.
    switch (state.mode) {
      case UnrollMode::Peel:
        numLoopsPeeled++;
        break;
      case UnrollMode::Unroll:
        numLoopsUnrolled++;
        break;
      case UnrollMode::PeelAndUnroll:
        numLoopsPeeledAndUnrolled++;
        break;
      default:
        MOZ_CRASH();
    }
  }

  // Do function-level fixups, if anything changed.
  if (!unrollStates.empty()) {
    RenumberBlocks(graph);
    ClearDominatorTree(graph);
    if (!BuildDominatorTree(mir, graph)) {
      return false;
    }
  }

  uint32_t numLoopsChanged =
      numLoopsPeeled + numLoopsUnrolled + numLoopsPeeledAndUnrolled;

#ifdef JS_JITSPEW
  if (JitSpewEnabled(JitSpew_Unroll)) {
    if (numLoopsChanged == 0) {
      JitSpew(JitSpew_Unroll, "END   UnrollLoops");
    } else {
      JitSpew(JitSpew_Unroll,
              "END UnrollLoops, %u processed (P=%u, U=%u, P&U=%u)",
              numLoopsChanged, numLoopsPeeled, numLoopsUnrolled,
              numLoopsPeeledAndUnrolled);
    }
  }
#endif

  *changed = numLoopsChanged > 0;
  return true;
}

}  // namespace jit
}  // namespace js