Quelle  IonAnalysis.cpp   Sprache: C

/* -*- 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 <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 "util/CheckedArithmetic.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) {
  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);
  }
  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::New(graph.alloc(), MagicValue(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++) {
    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()) {
--> --------------------

--> maximum size reached

--> --------------------