tor-browser

MIRGraph.h (32424B)

---

/* -*- 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/. */

#ifndef jit_MIRGraph_h
#define jit_MIRGraph_h

// This file declares the data structures used to build a control-flow graph
// containing MIR.

#include "jit/CompileInfo.h"
#include "jit/FixedList.h"
#include "jit/InlineScriptTree.h"
#include "jit/JitAllocPolicy.h"
#include "jit/MIR-wasm.h"
#include "jit/MIR.h"

namespace js {
namespace jit {

class MBasicBlock;
class MIRGraph;
class MStart;

class MDefinitionIterator;

using MInstructionIterator = InlineListIterator<MInstruction>;
using MInstructionReverseIterator = InlineListReverseIterator<MInstruction>;
using MPhiIterator = InlineListIterator<MPhi>;

#ifdef DEBUG
using MResumePointIterator = InlineForwardListIterator<MResumePoint>;
#endif

class LBlock;

// Represents the likelihood of a basic block to be executed at runtime.
// Unknown: default value.
// Likely: Likely to be executed at runtime, hot block.
// Unlikely: unlikely to be executed, cold block.
enum class Frequency : uint8_t { Unknown = 0, Likely = 1, Unlikely = 2 };

class MBasicBlock : public TempObject, public InlineListNode<MBasicBlock> {
public:
 enum Kind {
   NORMAL,
   PENDING_LOOP_HEADER,
   LOOP_HEADER,
   SPLIT_EDGE,
   FAKE_LOOP_PRED,
   INTERNAL,
   DEAD
 };

private:
 MBasicBlock(MIRGraph& graph, const CompileInfo& info, BytecodeSite* site,
             Kind kind);
 [[nodiscard]] bool init();
 void copySlots(MBasicBlock* from);
 [[nodiscard]] bool inherit(TempAllocator& alloc, size_t stackDepth,
                            MBasicBlock* maybePred, uint32_t popped);

 // This block cannot be reached by any means.
 bool unreachable_ = false;

 // This block will unconditionally bail out.
 bool alwaysBails_ = false;

 // Represents the execution frequency of this block, considered unknown by
 // default. Various passes can use this information for optimizations.
 Frequency frequency_ = Frequency::Unknown;

 // Pushes a copy of a local variable or argument.
 void pushVariable(uint32_t slot) { push(slots_[slot]); }

 // Sets a variable slot to the top of the stack, correctly creating copies
 // as needed.
 void setVariable(uint32_t slot) {
   MOZ_ASSERT(stackPosition_ > info_.firstStackSlot());
   setSlot(slot, slots_[stackPosition_ - 1]);
 }

 enum ReferencesType {
   RefType_None = 0,

   // Assert that the instruction is unused.
   RefType_AssertNoUses = 1 << 0,

   // Discard the operands of the resume point / instructions if the
   // following flag are given too.
   RefType_DiscardOperands = 1 << 1,
   RefType_DiscardResumePoint = 1 << 2,
   RefType_DiscardInstruction = 1 << 3,

   // Discard operands of the instruction and its resume point.
   RefType_DefaultNoAssert = RefType_DiscardOperands |
                             RefType_DiscardResumePoint |
                             RefType_DiscardInstruction,

   // Discard everything and assert that the instruction is not used.
   RefType_Default = RefType_AssertNoUses | RefType_DefaultNoAssert,

   // Discard resume point operands only, without discarding the operands
   // of the current instruction.  Asserts that the instruction is unused.
   RefType_IgnoreOperands = RefType_AssertNoUses | RefType_DiscardOperands |
                            RefType_DiscardResumePoint
 };

 void discardResumePoint(MResumePoint* rp,
                         ReferencesType refType = RefType_Default);
 void removeResumePoint(MResumePoint* rp);

 // Remove all references to an instruction such that it can be removed from
 // the list of instruction, without keeping any dangling pointer to it. This
 // includes the operands of the instruction, and the resume point if
 // present.
 void prepareForDiscard(MInstruction* ins,
                        ReferencesType refType = RefType_Default);

public:
 ///////////////////////////////////////////////////////
 ////////// BEGIN GRAPH BUILDING INSTRUCTIONS //////////
 ///////////////////////////////////////////////////////

 // Creates a new basic block for a MIR generator. If |pred| is not nullptr,
 // its slots and stack depth are initialized from |pred|.
 static MBasicBlock* New(MIRGraph& graph, size_t stackDepth,
                         const CompileInfo& info, MBasicBlock* maybePred,
                         BytecodeSite* site, Kind kind);
 static MBasicBlock* New(MIRGraph& graph, const CompileInfo& info,
                         MBasicBlock* pred, Kind kind);
 static MBasicBlock* NewPopN(MIRGraph& graph, const CompileInfo& info,
                             MBasicBlock* pred, BytecodeSite* site, Kind kind,
                             uint32_t popn);
 static MBasicBlock* NewPendingLoopHeader(MIRGraph& graph,
                                          const CompileInfo& info,
                                          MBasicBlock* pred,
                                          BytecodeSite* site);
 static MBasicBlock* NewSplitEdge(MIRGraph& graph, MBasicBlock* pred,
                                  size_t predEdgeIdx, MBasicBlock* succ);
 static MBasicBlock* NewFakeLoopPredecessor(MIRGraph& graph,
                                            MBasicBlock* header);

 // Create a new basic block for internal control flow not present in the
 // original CFG.
 static MBasicBlock* NewInternal(MIRGraph& graph, MBasicBlock* orig,
                                 MResumePoint* activeResumePoint);

 bool dominates(const MBasicBlock* other) const {
   return other->domIndex() - domIndex() < numDominated();
 }

 void setId(uint32_t id) { id_ = id; }

 // Mark this block (and only this block) as unreachable.
 void setUnreachable() {
   MOZ_ASSERT(!unreachable_);
   setUnreachableUnchecked();
 }
 void setUnreachableUnchecked() { unreachable_ = true; }
 bool unreachable() const { return unreachable_; }

 void setAlwaysBails() { alwaysBails_ = true; }
 bool alwaysBails() const { return alwaysBails_; }

 // Move the definition to the top of the stack.
 void pick(int32_t depth);

 // Move the top of the stack definition under the depth-th stack value.
 void unpick(int32_t depth);

 // Exchange 2 stack slots at the defined depth
 void swapAt(int32_t depth);

 // Note: most of the methods below are hot. Do not un-inline them without
 // measuring the impact.

 // Gets the instruction associated with various slot types.
 MDefinition* peek(int32_t depth) {
   MOZ_ASSERT(depth < 0);
   MOZ_ASSERT(stackPosition_ + depth >= info_.firstStackSlot());
   return peekUnchecked(depth);
 }

 MDefinition* peekUnchecked(int32_t depth) {
   MOZ_ASSERT(depth < 0);
   return getSlot(stackPosition_ + depth);
 }

 MDefinition* environmentChain();
 MDefinition* argumentsObject();

 // Increase the number of slots available
 [[nodiscard]] bool increaseSlots(size_t num);
 [[nodiscard]] bool ensureHasSlots(size_t num);

 // Initializes a slot value; must not be called for normal stack
 // operations, as it will not create new SSA names for copies.
 void initSlot(uint32_t slot, MDefinition* ins) {
   slots_[slot] = ins;
   if (entryResumePoint()) {
     entryResumePoint()->initOperand(slot, ins);
   }
 }

 // Sets the instruction associated with various slot types. The
 // instruction must lie at the top of the stack.
 void setLocal(uint32_t local) { setVariable(info_.localSlot(local)); }
 void setArg(uint32_t arg) { setVariable(info_.argSlot(arg)); }
 void setSlot(uint32_t slot, MDefinition* ins) { slots_[slot] = ins; }

 // Tracks an instruction as being pushed onto the operand stack.
 void push(MDefinition* ins) {
   MOZ_ASSERT(stackPosition_ < nslots());
   slots_[stackPosition_++] = ins;
 }
 void pushArg(uint32_t arg) { pushVariable(info_.argSlot(arg)); }
 void pushArgUnchecked(uint32_t arg) {
   pushVariable(info_.argSlotUnchecked(arg));
 }
 void pushLocal(uint32_t local) { pushVariable(info_.localSlot(local)); }
 void pushSlot(uint32_t slot) { pushVariable(slot); }
 void setEnvironmentChain(MDefinition* ins);
 void setArgumentsObject(MDefinition* ins);

 // Returns the top of the stack, then decrements the virtual stack pointer.
 MDefinition* pop() {
   MOZ_ASSERT(stackPosition_ > info_.firstStackSlot());
   return slots_[--stackPosition_];
 }
 void popn(uint32_t n) {
   MOZ_ASSERT(stackPosition_ - n >= info_.firstStackSlot());
   MOZ_ASSERT(stackPosition_ >= stackPosition_ - n);
   stackPosition_ -= n;
 }

 // Adds an instruction to this block's instruction list.
 inline void add(MInstruction* ins);

 // Marks the last instruction of the block; no further instructions
 // can be added.
 void end(MControlInstruction* ins) {
   MOZ_ASSERT(!hasLastIns());  // Existing control instructions should be
                               // removed first.
   MOZ_ASSERT(ins);
   add(ins);
 }

 // Adds a phi instruction, but does not set successorWithPhis.
 void addPhi(MPhi* phi);

 // Adds a resume point to this block.
 void addResumePoint(MResumePoint* resume) {
#ifdef DEBUG
   resumePoints_.pushFront(resume);
#endif
 }

 // Discard pre-allocated resume point.
 void discardPreAllocatedResumePoint(MResumePoint* resume) {
   MOZ_ASSERT(!resume->instruction());
   discardResumePoint(resume);
 }

 // Adds a predecessor. Every predecessor must have the same exit stack
 // depth as the entry state to this block. Adding a predecessor
 // automatically creates phi nodes and rewrites uses as needed.
 [[nodiscard]] bool addPredecessor(TempAllocator& alloc, MBasicBlock* pred);
 [[nodiscard]] bool addPredecessorPopN(TempAllocator& alloc, MBasicBlock* pred,
                                       uint32_t popped);

 // Add a predecessor which won't introduce any new phis to this block.
 // This may be called after the contents of this block have been built.
 [[nodiscard]] bool addPredecessorSameInputsAs(MBasicBlock* pred,
                                               MBasicBlock* existingPred);

 // Stranger utilities used for inlining.
 [[nodiscard]] bool addPredecessorWithoutPhis(MBasicBlock* pred);
 void inheritSlots(MBasicBlock* parent);
 [[nodiscard]] bool initEntrySlots(TempAllocator& alloc);

 // Replaces an edge for a given block with a new block. This is
 // used for critical edge splitting.
 //
 // Note: If successorWithPhis is set, you must not be replacing it.
 void replacePredecessor(MBasicBlock* old, MBasicBlock* split);
 void replaceSuccessor(size_t pos, MBasicBlock* split);

 // Removes `pred` from the predecessor list. If this block defines phis,
 // removes the entry for `pred` and updates the indices of later entries.
 // This may introduce redundant phis if the new block has fewer
 // than two predecessors.
 void removePredecessor(MBasicBlock* pred);

 // A version of removePredecessor which expects that phi operands to
 // |pred| have already been removed.
 void removePredecessorWithoutPhiOperands(MBasicBlock* pred, size_t predIndex);

 // Resets all the dominator info so that it can be recomputed.
 void clearDominatorInfo();

 // Sets a back edge. This places phi nodes and rewrites instructions within
 // the current loop as necessary.
 [[nodiscard]] bool setBackedge(MBasicBlock* block);
 [[nodiscard]] bool setBackedgeWasm(MBasicBlock* block, size_t paramCount);

 // Resets a LOOP_HEADER block to a NORMAL block.  This is needed when
 // optimizations remove the backedge.
 void clearLoopHeader();

 // Sets a block to a LOOP_HEADER block, with newBackedge as its backedge.
 // This is needed when optimizations remove the normal entry to a loop
 // with multiple entries.
 void setLoopHeader(MBasicBlock* newBackedge);

 // Marks this as a LOOP_HEADER block, but doesn't change anything else.
 void setLoopHeader() {
   MOZ_ASSERT(!isLoopHeader());
   kind_ = LOOP_HEADER;
 }

 // Propagates backedge slots into phis operands of the loop header.
 [[nodiscard]] bool inheritPhisFromBackedge(MBasicBlock* backedge);

 void insertBefore(MInstruction* at, MInstruction* ins);
 void insertAfter(MInstruction* at, MInstruction* ins);

 void insertAtEnd(MInstruction* ins);

 // Move an instruction. Movement may cross block boundaries.
 void moveBefore(MInstruction* at, MInstruction* ins);

 enum IgnoreTop { IgnoreNone = 0, IgnoreRecover = 1 << 0 };

 // Locate the top of the |block|, where it is safe to insert a new
 // instruction.
 MInstruction* safeInsertTop(MDefinition* ins = nullptr,
                             IgnoreTop ignore = IgnoreNone);

 // Removes an instruction with the intention to discard it.
 void discard(MInstruction* ins);
 void discardLastIns();
 void discardAllInstructions();
 void discardAllInstructionsStartingAt(MInstructionIterator iter);
 void discardAllPhis();
 void discardAllResumePoints(bool discardEntry = true);
 void clear();

 // Splits this block in two at a given instruction, inserting a new control
 // flow diamond with |ins| in the slow path, |fastpath| in the other, and
 // |condition| determining which path to take.
 bool wrapInstructionInFastpath(MInstruction* ins, MInstruction* fastpath,
                                MInstruction* condition);

 void moveOuterResumePointTo(MBasicBlock* dest);

 // Move an instruction from this block to a block that has not yet been
 // terminated.
 void moveToNewBlock(MInstruction* ins, MBasicBlock* dst);

 // Same as |void discard(MInstruction* ins)| but assuming that
 // all operands are already discarded.
 void discardIgnoreOperands(MInstruction* ins);

 // Discards a phi instruction and updates predecessor successorWithPhis.
 void discardPhi(MPhi* phi);

 // Some instruction which are guarding against some MIRType value, or
 // against a type expectation should be considered as removing a potenatial
 // branch where the guard does not hold.  We need to register such
 // instructions in order to do destructive optimizations correctly, such as
 // Range Analysis.
 void flagOperandsOfPrunedBranches(MInstruction* ins);

 // Mark this block as having been removed from the graph.
 void markAsDead() {
   MOZ_ASSERT(kind_ != DEAD);
   kind_ = DEAD;
 }

 ///////////////////////////////////////////////////////
 /////////// END GRAPH BUILDING INSTRUCTIONS ///////////
 ///////////////////////////////////////////////////////

 MIRGraph& graph() { return graph_; }
 const CompileInfo& info() const { return info_; }
 jsbytecode* pc() const { return trackedSite_->pc(); }
 jsbytecode* entryPC() const { return entryResumePoint()->pc(); }
 uint32_t nslots() const { return slots_.length(); }
 uint32_t id() const { return id_; }
 uint32_t numPredecessors() const { return predecessors_.length(); }

 bool isUnknownFrequency() const { return frequency_ == Frequency::Unknown; }

 bool isLikelyFrequency() const { return frequency_ == Frequency::Likely; }

 bool isUnlikelyFrequency() const { return frequency_ == Frequency::Unlikely; }

 Frequency getFrequency() const { return frequency_; }
 void setFrequency(Frequency value) { frequency_ = value; }

 uint32_t domIndex() const {
   MOZ_ASSERT(!isDead());
   return domIndex_;
 }
 void setDomIndex(uint32_t d) { domIndex_ = d; }

 MBasicBlock* getPredecessor(uint32_t i) const { return predecessors_[i]; }
 void setPredecessor(uint32_t i, MBasicBlock* p) { predecessors_[i] = p; }
 [[nodiscard]]
 bool appendPredecessor(MBasicBlock* p) {
   return predecessors_.append(p);
 }
 void erasePredecessor(uint32_t i) { predecessors_.erase(&predecessors_[i]); }

 size_t indexForPredecessor(MBasicBlock* block) const {
   // This should only be called before critical edge splitting.
   MOZ_ASSERT(!block->successorWithPhis());

   for (size_t i = 0; i < predecessors_.length(); i++) {
     if (predecessors_[i] == block) {
       return i;
     }
   }
   MOZ_CRASH();
 }
 bool hasAnyIns() const { return !instructions_.empty(); }
 bool hasLastIns() const {
   return hasAnyIns() && instructions_.rbegin()->isControlInstruction();
 }
 MControlInstruction* lastIns() const {
   MOZ_ASSERT(hasLastIns());
   return instructions_.rbegin()->toControlInstruction();
 }
 // Find or allocate an optimized out constant.
 MConstant* optimizedOutConstant(TempAllocator& alloc);
 MPhiIterator phisBegin() const { return phis_.begin(); }
 MPhiIterator phisBegin(MPhi* at) const { return phis_.begin(at); }
 MPhiIterator phisEnd() const { return phis_.end(); }
 bool phisEmpty() const { return phis_.empty(); }
#ifdef DEBUG
 MResumePointIterator resumePointsBegin() const {
   return resumePoints_.begin();
 }
 MResumePointIterator resumePointsEnd() const { return resumePoints_.end(); }
 bool resumePointsEmpty() const { return resumePoints_.empty(); }
#endif
 MInstructionIterator begin() { return instructions_.begin(); }
 MInstructionIterator begin(MInstruction* at) {
   MOZ_ASSERT(at->block() == this);
   return instructions_.begin(at);
 }
 MInstructionIterator end() { return instructions_.end(); }
 MInstructionReverseIterator rbegin() { return instructions_.rbegin(); }
 MInstructionReverseIterator rbegin(MInstruction* at) {
   MOZ_ASSERT(at->block() == this);
   return instructions_.rbegin(at);
 }
 MInstructionReverseIterator rend() { return instructions_.rend(); }

 bool isLoopHeader() const { return kind_ == LOOP_HEADER; }
 bool isPendingLoopHeader() const { return kind_ == PENDING_LOOP_HEADER; }

 bool hasUniqueBackedge() const {
   MOZ_ASSERT(isLoopHeader());
   MOZ_ASSERT(numPredecessors() >= 1);
   if (numPredecessors() == 1 || numPredecessors() == 2) {
     return true;
   }
   if (numPredecessors() == 3) {
     // fixup block added by NewFakeLoopPredecessor
     return getPredecessor(1)->numPredecessors() == 0;
   }
   return false;
 }
 MBasicBlock* backedge() const {
   MOZ_ASSERT(hasUniqueBackedge());
   return getPredecessor(numPredecessors() - 1);
 }
 MBasicBlock* loopHeaderOfBackedge() const {
   MOZ_ASSERT(isLoopBackedge());
   return getSuccessor(numSuccessors() - 1);
 }
 MBasicBlock* loopPredecessor() const {
   MOZ_ASSERT(isLoopHeader());
   return getPredecessor(0);
 }
 bool isLoopBackedge() const {
   if (!numSuccessors()) {
     return false;
   }
   MBasicBlock* lastSuccessor = getSuccessor(numSuccessors() - 1);
   return lastSuccessor->isLoopHeader() &&
          lastSuccessor->hasUniqueBackedge() &&
          lastSuccessor->backedge() == this;
 }
 bool isSplitEdge() const { return kind_ == SPLIT_EDGE; }
 bool isDead() const { return kind_ == DEAD; }
 bool isFakeLoopPred() const { return kind_ == FAKE_LOOP_PRED; }

 uint32_t stackDepth() const { return stackPosition_; }
 bool isMarked() const { return mark_; }
 void mark() {
   MOZ_ASSERT(!mark_, "Marking already-marked block");
   markUnchecked();
 }
 void markUnchecked() { mark_ = true; }
 void unmark() {
   MOZ_ASSERT(mark_, "Unarking unmarked block");
   unmarkUnchecked();
 }
 void unmarkUnchecked() { mark_ = false; }

 MBasicBlock* immediateDominator() const { return immediateDominator_; }

 void setImmediateDominator(MBasicBlock* dom) { immediateDominator_ = dom; }

 MTest* immediateDominatorBranch(BranchDirection* pdirection);

 size_t numImmediatelyDominatedBlocks() const {
   return immediatelyDominated_.length();
 }

 MBasicBlock* getImmediatelyDominatedBlock(size_t i) const {
   return immediatelyDominated_[i];
 }

 MBasicBlock** immediatelyDominatedBlocksBegin() {
   return immediatelyDominated_.begin();
 }

 MBasicBlock** immediatelyDominatedBlocksEnd() {
   return immediatelyDominated_.end();
 }

 // Return the number of blocks dominated by this block. All blocks
 // dominate at least themselves, so this will always be non-zero.
 size_t numDominated() const {
   MOZ_ASSERT(numDominated_ != 0);
   return numDominated_;
 }

 void addNumDominated(size_t n) { numDominated_ += n; }

 // Add |child| to this block's immediately-dominated set.
 bool addImmediatelyDominatedBlock(MBasicBlock* child);

 // Remove |child| from this block's immediately-dominated set.
 void removeImmediatelyDominatedBlock(MBasicBlock* child);

 // This function retrieves the internal instruction associated with a
 // slot, and should not be used for normal stack operations. It is an
 // internal helper that is also used to enhance spew.
 MDefinition* getSlot(uint32_t index) {
   MOZ_ASSERT(index < stackPosition_);
   return slots_[index];
 }

 MResumePoint* entryResumePoint() const { return entryResumePoint_; }
 void setEntryResumePoint(MResumePoint* rp) { entryResumePoint_ = rp; }
 void clearEntryResumePoint() {
   discardResumePoint(entryResumePoint_);
   entryResumePoint_ = nullptr;
 }
 MResumePoint* outerResumePoint() const { return outerResumePoint_; }
 void setOuterResumePoint(MResumePoint* outer) {
   MOZ_ASSERT(!outerResumePoint_);
   outerResumePoint_ = outer;
 }
 void clearOuterResumePoint() {
   discardResumePoint(outerResumePoint_);
   outerResumePoint_ = nullptr;
 }
 MResumePoint* callerResumePoint() const { return callerResumePoint_; }
 void setCallerResumePoint(MResumePoint* caller) {
   callerResumePoint_ = caller;
 }

 LBlock* lir() const { return lir_; }
 void assignLir(LBlock* lir) {
   MOZ_ASSERT(!lir_);
   lir_ = lir;
 }

 MBasicBlock* successorWithPhis() const { return successorWithPhis_; }
 uint32_t positionInPhiSuccessor() const {
   MOZ_ASSERT(successorWithPhis());
   return positionInPhiSuccessor_;
 }
 void setSuccessorWithPhis(MBasicBlock* successor, uint32_t id) {
   successorWithPhis_ = successor;
   positionInPhiSuccessor_ = id;
 }
 void clearSuccessorWithPhis() { successorWithPhis_ = nullptr; }
 size_t numSuccessors() const {
   MOZ_ASSERT(lastIns());
   return lastIns()->numSuccessors();
 }
 MBasicBlock* getSuccessor(size_t index) const {
   MOZ_ASSERT(lastIns());
   return lastIns()->getSuccessor(index);
 }
 MBasicBlock* getSingleSuccessor() const {
   MOZ_ASSERT(numSuccessors() == 1);
   return getSuccessor(0);
 }
 size_t getSuccessorIndex(MBasicBlock*) const;
 size_t getPredecessorIndex(MBasicBlock*) const;

 void setLoopDepth(uint32_t loopDepth) { loopDepth_ = loopDepth; }
 uint32_t loopDepth() const { return loopDepth_; }

 void dumpStack(GenericPrinter& out);
 void dumpStack();

 void dump(GenericPrinter& out);
 void dump();

 void updateTrackedSite(BytecodeSite* site) {
   MOZ_ASSERT(site->tree() == trackedSite_->tree());
   trackedSite_ = site;
 }
 BytecodeSite* trackedSite() const { return trackedSite_; }
 InlineScriptTree* trackedTree() const { return trackedSite_->tree(); }

 // Find the previous resume point that would be used if this instruction
 // bails out.
 MResumePoint* activeResumePoint(MInstruction* ins);

#ifdef JS_JITSPEW
 const char* nameOfKind() const {
   switch (kind_) {
     case MBasicBlock::Kind::NORMAL:
       return "NORMAL";
     case MBasicBlock::Kind::PENDING_LOOP_HEADER:
       return "PENDING_LOOP_HEADER";
     case MBasicBlock::Kind::LOOP_HEADER:
       return "LOOP_HEADER";
     case MBasicBlock::Kind::SPLIT_EDGE:
       return "SPLIT_EDGE";
     case MBasicBlock::Kind::FAKE_LOOP_PRED:
       return "FAKE_LOOP_PRED";
     case MBasicBlock::Kind::INTERNAL:
       return "INTERNAL";
     case MBasicBlock::Kind::DEAD:
       return "DEAD";
     default:
       return "MBasicBlock::Kind::???";
   }
 }
#endif

private:
 MIRGraph& graph_;
 const CompileInfo& info_;  // Each block originates from a particular script.
 InlineList<MInstruction> instructions_;
 Vector<MBasicBlock*, 1, JitAllocPolicy> predecessors_;
 InlineList<MPhi> phis_;
 FixedList<MDefinition*> slots_;
 uint32_t stackPosition_;
 uint32_t id_;
 uint32_t domIndex_;  // Index in the dominator tree.
 uint32_t numDominated_;
 LBlock* lir_;

 // Copy of a dominator block's outerResumePoint_ which holds the state of
 // caller frame at the time of the call. If not null, this implies that this
 // basic block corresponds to an inlined script.
 MResumePoint* callerResumePoint_;

 // Resume point holding baseline-like frame for the PC corresponding to the
 // entry of this basic block.
 MResumePoint* entryResumePoint_;

 // Resume point holding baseline-like frame for the PC corresponding to the
 // beginning of the call-site which is being inlined after this block.
 MResumePoint* outerResumePoint_;

#ifdef DEBUG
 // Unordered list used to verify that all the resume points which are
 // registered are correctly removed when a basic block is removed.
 InlineForwardList<MResumePoint> resumePoints_;
#endif

 MBasicBlock* successorWithPhis_;
 uint32_t positionInPhiSuccessor_;
 uint32_t loopDepth_;
 Kind kind_ : 8;

 // Utility mark for traversal algorithms.
 bool mark_;

 Vector<MBasicBlock*, 1, JitAllocPolicy> immediatelyDominated_;
 MBasicBlock* immediateDominator_;

 // Track bailouts by storing the current pc in MIR instruction added at
 // this cycle. This is also used for tracking calls and optimizations when
 // profiling.
 BytecodeSite* trackedSite_;
};

using MBasicBlockIterator = InlineListIterator<MBasicBlock>;
using ReversePostorderIterator = InlineListIterator<MBasicBlock>;
using PostorderIterator = InlineListReverseIterator<MBasicBlock>;

using MIRGraphReturns = Vector<MBasicBlock*, 1, JitAllocPolicy>;

class MIRGraph {
 InlineList<MBasicBlock> blocks_;
 TempAllocator* alloc_;
 MIRGraphReturns* returnAccumulator_;
 uint32_t blockIdGen_;
 uint32_t idGen_;
 MBasicBlock* osrBlock_;

 size_t numBlocks_;
 bool hasTryBlock_;

 InlineList<MPhi> phiFreeList_;
 size_t phiFreeListLength_;

public:
 explicit MIRGraph(TempAllocator* alloc)
     : alloc_(alloc),
       returnAccumulator_(nullptr),
       blockIdGen_(0),
       idGen_(0),
       osrBlock_(nullptr),
       numBlocks_(0),
       hasTryBlock_(false),
       phiFreeListLength_(0) {}

 TempAllocator& alloc() const { return *alloc_; }

 void addBlock(MBasicBlock* block);
 void insertBlockAfter(MBasicBlock* at, MBasicBlock* block);
 void insertBlockBefore(MBasicBlock* at, MBasicBlock* block);

 void unmarkBlocks();

 void setReturnAccumulator(MIRGraphReturns* accum) {
   returnAccumulator_ = accum;
 }
 MIRGraphReturns* returnAccumulator() const { return returnAccumulator_; }

 [[nodiscard]] bool addReturn(MBasicBlock* returnBlock) {
   if (!returnAccumulator_) {
     return true;
   }

   return returnAccumulator_->append(returnBlock);
 }

 MBasicBlock* entryBlock() { return *blocks_.begin(); }
 MBasicBlockIterator begin() { return blocks_.begin(); }
 MBasicBlockIterator begin(const MBasicBlock* at) { return blocks_.begin(at); }
 MBasicBlockIterator end() { return blocks_.end(); }
 PostorderIterator poBegin() { return blocks_.rbegin(); }
 PostorderIterator poBegin(const MBasicBlock* at) {
   return blocks_.rbegin(at);
 }
 PostorderIterator poEnd() { return blocks_.rend(); }
 ReversePostorderIterator rpoBegin() { return blocks_.begin(); }
 ReversePostorderIterator rpoBegin(const MBasicBlock* at) {
   return blocks_.begin(at);
 }
 ReversePostorderIterator rpoEnd() { return blocks_.end(); }
 void removeBlock(MBasicBlock* block);
 void moveBlockToEnd(MBasicBlock* block) {
   blocks_.remove(block);
   MOZ_ASSERT_IF(!blocks_.empty(), block->id());
   blocks_.pushBack(block);
 }
 void moveBlockBefore(MBasicBlock* at, MBasicBlock* block) {
   MOZ_ASSERT(block->id());
   blocks_.remove(block);
   blocks_.insertBefore(at, block);
 }
 void moveBlockAfter(MBasicBlock* at, MBasicBlock* block) {
   MOZ_ASSERT(block->id());
   blocks_.remove(block);
   blocks_.insertAfter(at, block);
 }
 size_t numBlocks() const { return numBlocks_; }
 uint32_t numBlockIds() const { return blockIdGen_; }
 void allocDefinitionId(MDefinition* ins) { ins->setId(idGen_++); }
 uint32_t getNumInstructionIds() { return idGen_; }
 MResumePoint* entryResumePoint() { return entryBlock()->entryResumePoint(); }

 void setOsrBlock(MBasicBlock* osrBlock) {
   MOZ_ASSERT(!osrBlock_);
   osrBlock_ = osrBlock;
 }
 MBasicBlock* osrBlock() const { return osrBlock_; }

 MBasicBlock* osrPreHeaderBlock() const {
   return osrBlock() ? osrBlock()->getSingleSuccessor() : nullptr;
 }

 bool hasTryBlock() const { return hasTryBlock_; }
 void setHasTryBlock() { hasTryBlock_ = true; }

 void dump(GenericPrinter& out);
 void dump();

 void addPhiToFreeList(MPhi* phi) {
   phiFreeList_.pushBack(phi);
   phiFreeListLength_++;
 }
 size_t phiFreeListLength() const { return phiFreeListLength_; }
 MPhi* takePhiFromFreeList() {
   MOZ_ASSERT(phiFreeListLength_ > 0);
   phiFreeListLength_--;
   return phiFreeList_.popBack();
 }

 void removeFakeLoopPredecessors();

#ifdef DEBUG
 // Dominators can't be built after we remove fake loop predecessors.
private:
 bool canBuildDominators_ = true;

public:
 bool canBuildDominators() const { return canBuildDominators_; }
#endif
};

class MDefinitionIterator {
 friend class MBasicBlock;
 friend class MNodeIterator;

private:
 MBasicBlock* block_;
 MPhiIterator phiIter_;
 MInstructionIterator iter_;

 bool atPhi() const { return phiIter_ != block_->phisEnd(); }

 MDefinition* getIns() {
   if (atPhi()) {
     return *phiIter_;
   }
   return *iter_;
 }

 bool more() const { return atPhi() || (*iter_) != block_->lastIns(); }

public:
 explicit MDefinitionIterator(MBasicBlock* block)
     : block_(block), phiIter_(block->phisBegin()), iter_(block->begin()) {}

 MDefinitionIterator operator++() {
   MOZ_ASSERT(more());
   if (atPhi()) {
     ++phiIter_;
   } else {
     ++iter_;
   }
   return *this;
 }

 MDefinitionIterator operator++(int) {
   MDefinitionIterator old(*this);
   operator++();
   return old;
 }

 explicit operator bool() const { return more(); }

 MDefinition* operator*() { return getIns(); }

 MDefinition* operator->() { return getIns(); }
};

// Iterates on all resume points, phis, and instructions of a MBasicBlock.
// Resume points are visited as long as they have not been discarded.
class MNodeIterator {
private:
 // If this is non-null, the resume point that we will visit next (unless
 // it has been discarded). Initialized to the entry resume point.
 // Otherwise, resume point of the most recently visited instruction.
 MResumePoint* resumePoint_;

 mozilla::DebugOnly<MInstruction*> lastInstruction_ = nullptr;

 // Definition iterator which is one step ahead when visiting resume points.
 // This is in order to avoid incrementing the iterator while it is settled
 // on a discarded instruction.
 MDefinitionIterator defIter_;

 MBasicBlock* block() const { return defIter_.block_; }

 bool atResumePoint() const {
   MOZ_ASSERT_IF(lastInstruction_ && !lastInstruction_->isDiscarded(),
                 lastInstruction_->resumePoint() == resumePoint_);
   return resumePoint_ && !resumePoint_->isDiscarded();
 }

 MNode* getNode() {
   if (atResumePoint()) {
     return resumePoint_;
   }
   return *defIter_;
 }

 void next() {
   if (!atResumePoint()) {
     if (defIter_->isInstruction()) {
       resumePoint_ = defIter_->toInstruction()->resumePoint();
       lastInstruction_ = defIter_->toInstruction();
     }
     defIter_++;
   } else {
     resumePoint_ = nullptr;
     lastInstruction_ = nullptr;
   }
 }

 bool more() const { return defIter_ || atResumePoint(); }

public:
 explicit MNodeIterator(MBasicBlock* block)
     : resumePoint_(block->entryResumePoint()), defIter_(block) {
   MOZ_ASSERT(bool(block->entryResumePoint()) == atResumePoint());
 }

 MNodeIterator operator++(int) {
   MNodeIterator old(*this);
   if (more()) {
     next();
   }
   return old;
 }

 explicit operator bool() const { return more(); }

 MNode* operator*() { return getNode(); }

 MNode* operator->() { return getNode(); }
};

void MBasicBlock::add(MInstruction* ins) {
 MOZ_ASSERT(!hasLastIns());
 ins->setInstructionBlock(this, trackedSite_);
 graph().allocDefinitionId(ins);
 instructions_.pushBack(ins);
}

}  // namespace jit
}  // namespace js

#endif /* jit_MIRGraph_h */