path: root/js/src/jit/MIRGraph.h

/* -*- 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.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
typedef InlineForwardListIterator<MResumePoint> MResumePointIterator;
#endif

class LBlock;

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;

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

  // 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(); }
  uint32_t nslots() const { return slots_.length(); }
  uint32_t id() const { return id_; }
  uint32_t numPredecessors() const { return predecessors_.length(); }

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

  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);

 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_;

  unsigned lineno_;
  unsigned columnIndex_;

 public:
  void setLineno(unsigned l) { lineno_ = l; }
  unsigned lineno() const { return lineno_; }
  void setColumnIndex(unsigned c) { columnIndex_ = c; }
  unsigned columnIndex() const { return columnIndex_; }
};

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

typedef Vector<MBasicBlock*, 1, JitAllocPolicy> MIRGraphReturns;

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(MBasicBlock* at) { return blocks_.begin(at); }
  MBasicBlockIterator end() { return blocks_.end(); }
  PostorderIterator poBegin() { return blocks_.rbegin(); }
  PostorderIterator poBegin(MBasicBlock* at) { return blocks_.rbegin(at); }
  PostorderIterator poEnd() { return blocks_.rend(); }
  ReversePostorderIterator rpoBegin() { return blocks_.begin(); }
  ReversePostorderIterator rpoBegin(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 */