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

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * 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/FixedList.h"
#include "jit/JitAllocPolicy.h"
#include "jit/MIR.h"

namespace js {
namespace jit {

class BytecodeAnalysis;
class MBasicBlock;
class MIRGraph;
class MStart;

class MDefinitionIterator;

typedef InlineListIterator<MInstruction> MInstructionIterator;
typedef InlineListReverseIterator<MInstruction> MInstructionReverseIterator;
typedef InlineListIterator<MPhi> MPhiIterator;

#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,
        DEAD
    };

  private:
    MBasicBlock(MIRGraph& graph, const CompileInfo& info, BytecodeSite* site, Kind kind);
    MOZ_MUST_USE bool init();
    void copySlots(MBasicBlock* from);
    MOZ_MUST_USE bool inherit(TempAllocator& alloc, BytecodeAnalysis* analysis, MBasicBlock* pred,
                                        uint32_t popped, unsigned stackPhiCount = 0);
    MOZ_MUST_USE bool inheritResumePoint(MBasicBlock* pred);
    void assertUsesAreNotWithin(MUseIterator use, MUseIterator end);

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

    // Pushes a copy of a local variable or argument.
    void pushVariable(uint32_t slot);

    // Sets a variable slot to the top of the stack, correctly creating copies
    // as needed.
    void setVariable(uint32_t slot);

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

    // 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, BytecodeAnalysis* analysis, const CompileInfo& info,
                            MBasicBlock* pred, 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* NewWithResumePoint(MIRGraph& graph, const CompileInfo& info,
                                           MBasicBlock* pred, BytecodeSite* site,
                                           MResumePoint* resumePoint);
    static MBasicBlock* NewPendingLoopHeader(MIRGraph& graph, const CompileInfo& info,
                                             MBasicBlock* pred, BytecodeSite* site,
                                             unsigned loopStateSlots);
    static MBasicBlock* NewSplitEdge(MIRGraph& graph, MBasicBlock* pred,
                                     size_t predEdgeIdx, MBasicBlock* succ);

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

    // Gets the instruction associated with various slot types.
    MDefinition* peek(int32_t depth);

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

    // Increase the number of slots available
    MOZ_MUST_USE bool increaseSlots(size_t num);
    MOZ_MUST_USE 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 index, MDefinition* ins);

    // Discard the slot at the given depth, lowering all slots above.
    void shimmySlots(int discardDepth);

    // In an OSR block, set all MOsrValues to use the MResumePoint attached to
    // the MStart.
    MOZ_MUST_USE bool linkOsrValues(MStart* start);

    // Sets the instruction associated with various slot types. The
    // instruction must lie at the top of the stack.
    void setLocal(uint32_t local);
    void setArg(uint32_t arg);
    void setSlot(uint32_t slot);
    void setSlot(uint32_t slot, MDefinition* ins);

    // Rewrites a slot directly, bypassing the stack transition. This should
    // not be used under most circumstances.
    void rewriteSlot(uint32_t slot, MDefinition* ins);

    // Rewrites a slot based on its depth (same as argument to peek()).
    void rewriteAtDepth(int32_t depth, MDefinition* ins);

    // Tracks an instruction as being pushed onto the operand stack.
    void push(MDefinition* ins);
    void pushArg(uint32_t arg);
    void pushLocal(uint32_t local);
    void pushSlot(uint32_t slot);
    void setEnvironmentChain(MDefinition* ins);
    void setArgumentsObject(MDefinition* ins);

    // Returns the top of the stack, then decrements the virtual stack pointer.
    MDefinition* pop();
    void popn(uint32_t n);

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

    // Marks the last instruction of the block; no further instructions
    // can be added.
    void end(MControlInstruction* 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.
    MOZ_MUST_USE bool addPredecessor(TempAllocator& alloc, MBasicBlock* pred);
    MOZ_MUST_USE 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.
    void addPredecessorSameInputsAs(MBasicBlock* pred, MBasicBlock* existingPred);

    // Stranger utilities used for inlining.
    MOZ_MUST_USE bool addPredecessorWithoutPhis(MBasicBlock* pred);
    void inheritSlots(MBasicBlock* parent);
    MOZ_MUST_USE 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. If the backedge introduces new types for
    // phis at the loop header, returns a disabling abort.
    MOZ_MUST_USE AbortReason setBackedge(TempAllocator& alloc, MBasicBlock* block);
    MOZ_MUST_USE bool setBackedgeWasm(MBasicBlock* block);

    // 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 phis placed in a loop header down to this successor block.
    void inheritPhis(MBasicBlock* header);

    // Propagates backedge slots into phis operands of the loop header.
    MOZ_MUST_USE bool inheritPhisFromBackedge(TempAllocator& alloc, MBasicBlock* backedge,
                                              bool* hadTypeChange);

    // Compute the types for phis in this block according to their inputs.
    MOZ_MUST_USE bool specializePhis(TempAllocator& alloc);

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

    void insertAtEnd(MInstruction* ins);

    // Add an instruction to this block, from elsewhere in the graph.
    void addFromElsewhere(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 discardDef(MDefinition* def);
    void discardAllInstructions();
    void discardAllInstructionsStartingAt(MInstructionIterator iter);
    void discardAllPhiOperands();
    void discardAllPhis();
    void discardAllResumePoints(bool discardEntry = true);

    // 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 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 hasUniqueBackedge() const {
        MOZ_ASSERT(isLoopHeader());
        MOZ_ASSERT(numPredecessors() >= 2);
        if (numPredecessors() == 2)
            return true;
        if (numPredecessors() == 3) // fixup block added by ValueNumbering phase.
            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;
    }

    uint32_t stackDepth() const {
        return stackPosition_;
    }
    void setStackDepth(uint32_t depth) {
        stackPosition_ = depth;
    }
    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);

    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;
    }
    size_t numEntrySlots() const {
        return entryResumePoint()->stackDepth();
    }
    MDefinition* getEntrySlot(size_t i) const {
        MOZ_ASSERT(i < numEntrySlots());
        return entryResumePoint()->getOperand(i);
    }

    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;
    MBasicBlock* getSuccessor(size_t index) const;
    size_t getSuccessorIndex(MBasicBlock*) const;
    size_t getPredecessorIndex(MBasicBlock*) const;

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

    bool strict() const {
        return info_.script()->strict();
    }

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

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

    // Hit count
    enum class HitState {
        // Not hit information is attached to this basic block.
        NotDefined,

        // The hit information is a raw counter. Note that due to inlining this
        // counter is not guaranteed to be consistent over the graph.
        Count,

        // The hit information is a frequency, which is a form of normalized
        // counter, where a hit-count can be compared against any previous block
        // in the graph.
        Frequency
    };
    HitState getHitState() const {
        return hitState_;
    }
    void setHitCount(uint64_t count) {
        hitCount_ = count;
        hitState_ = HitState::Count;
    }
    uint64_t getHitCount() const {
        MOZ_ASSERT(hitState_ == HitState::Count);
        return hitCount_;
    }

    // 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.
    void updateTrackedSite(BytecodeSite* site) {
        MOZ_ASSERT(site->tree() == trackedSite_->tree());
        trackedSite_ = site;
    }
    BytecodeSite* trackedSite() const {
        return trackedSite_;
    }
    jsbytecode* trackedPc() const {
        return trackedSite_ ? trackedSite_->pc() : nullptr;
    }
    InlineScriptTree* trackedTree() const {
        return trackedSite_ ? trackedSite_->tree() : nullptr;
    }

    // This class is used for reverting the graph within IonBuilder.
    class BackupPoint {
        friend MBasicBlock;

        MBasicBlock* current_;
        MBasicBlock* lastBlock_;
        MInstruction* lastIns_;
        uint32_t stackPosition_;
        FixedList<MDefinition*> slots_;
#ifdef DEBUG
        // The following fields should remain identical during IonBuilder
        // construction, these are used for assertions.
        MPhi* lastPhi_;
        uintptr_t predecessorsCheckSum_;
        HashNumber instructionsCheckSum_;
        uint32_t id_;
        MResumePoint* callerResumePoint_;
        MResumePoint* entryResumePoint_;

        size_t computePredecessorsCheckSum(MBasicBlock* block);
        HashNumber computeInstructionsCheckSum(MBasicBlock* block);
#endif
      public:
        explicit BackupPoint(MBasicBlock* current);
        MOZ_MUST_USE bool init(TempAllocator& alloc);
        MBasicBlock* restore();
    };

    friend BackupPoint;

  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_;
    jsbytecode* pc_;
    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_;

    BytecodeSite* trackedSite_;

    // Record the number of times a block got visited. Note, due to inlined
    // scripts these numbers might not be continuous.
    uint64_t hitCount_;
    HitState hitState_;

#if defined(JS_ION_PERF) || defined(DEBUG)
    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_; }
#endif
};

typedef InlineListIterator<MBasicBlock> MBasicBlockIterator;
typedef InlineListIterator<MBasicBlock> ReversePostorderIterator;
typedef InlineListReverseIterator<MBasicBlock> PostorderIterator;

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 renumberBlocksAfter(MBasicBlock* at);

    void unmarkBlocks();

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

    MOZ_MUST_USE 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 removeBlocksAfter(MBasicBlock* block);
    void removeBlock(MBasicBlock* block);
    void removeBlockIncludingPhis(MBasicBlock* block);
    void moveBlockToEnd(MBasicBlock* block) {
        MOZ_ASSERT(block->id());
        blocks_.remove(block);
        blocks_.pushBack(block);
    }
    void moveBlockBefore(MBasicBlock* at, MBasicBlock* block) {
        MOZ_ASSERT(block->id());
        blocks_.remove(block);
        blocks_.insertBefore(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 copyIds(const MIRGraph& other) {
        idGen_ = other.idGen_;
        blockIdGen_ = other.blockIdGen_;
        numBlocks_ = other.numBlocks_;
    }

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

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

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 the instruction which holds it is not
// discarded.
class MNodeIterator
{
  private:
    // Last instruction which holds a resume point. To handle the entry point
    // resume point, it is set to the last instruction, assuming that the last
    // instruction is not discarded before we visit it.
    MInstruction* last_;

    // 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 {
        return last_ && !last_->isDiscarded();
    }

    MNode* getNode() {
        if (!atResumePoint())
            return *defIter_;

        // We use the last instruction as a sentinelle to iterate over the entry
        // resume point of the basic block, before even starting to iterate on
        // the instruction list.  Otherwise, the last_ corresponds to the
        // previous instruction.
        if (last_ != block()->lastIns())
            return last_->resumePoint();
        return block()->entryResumePoint();
    }

    void next() {
        if (!atResumePoint()) {
            if (defIter_->isInstruction() && defIter_->toInstruction()->resumePoint()) {
                // In theory, we could but in practice this does not happen.
                MOZ_ASSERT(*defIter_ != block()->lastIns());
                last_ = defIter_->toInstruction();
            }

            defIter_++;
        } else {
            last_ = nullptr;
        }
    }

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

  public:
    explicit MNodeIterator(MBasicBlock* block)
      : last_(block->entryResumePoint() ? block->lastIns() : nullptr),
        defIter_(block)
    {
        MOZ_ASSERT(bool(block->entryResumePoint()) == atResumePoint());

        // We use the last instruction to check for the entry resume point,
        // assert that no control instruction has any resume point.  If so, then
        // we need to handle this case in this iterator.
        MOZ_ASSERT(!block->lastIns()->resumePoint());
    }

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

};

} // namespace jit
} // namespace js

#endif /* jit_MIRGraph_h */