js/src/jit/MIRGraph.h
author Dan Gohman <sunfish@mozilla.com>
Mon, 25 Aug 2014 15:03:24 -0700
changeset 201600 949cf26ba3d5cb6ed17ba5fb626be29051a099ab
parent 200934 e4886c5bea1c57934bab47e424894356a2fa8670
child 205879 69858bc21e7cde39be9d7bb9a1d43191b1f55d90
permissions -rw-r--r--
Bug 1058077 - IonMonkey: Eliminate the unused osrStart_ field form MIRGraph r=sstangl

/* -*- 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/IonAllocPolicy.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, CompileInfo &info, const BytecodeSite &site, Kind kind);
    bool init();
    void copySlots(MBasicBlock *from);
    bool inherit(TempAllocator &alloc, BytecodeAnalysis *analysis, MBasicBlock *pred,
                 uint32_t popped, unsigned stackPhiCount = 0);
    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, CompileInfo &info,
                            MBasicBlock *pred, const BytecodeSite &site, Kind kind);
    static MBasicBlock *NewPopN(MIRGraph &graph, CompileInfo &info,
                                MBasicBlock *pred, const BytecodeSite &site, Kind kind, uint32_t popn);
    static MBasicBlock *NewWithResumePoint(MIRGraph &graph, CompileInfo &info,
                                           MBasicBlock *pred, const BytecodeSite &site,
                                           MResumePoint *resumePoint);
    static MBasicBlock *NewPendingLoopHeader(MIRGraph &graph, CompileInfo &info,
                                             MBasicBlock *pred, const BytecodeSite &site,
                                             unsigned loopStateSlots);
    static MBasicBlock *NewSplitEdge(MIRGraph &graph, CompileInfo &info, MBasicBlock *pred);
    static MBasicBlock *NewAsmJS(MIRGraph &graph, CompileInfo &info,
                                 MBasicBlock *pred, Kind kind);

    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() {
        JS_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);

    // 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 *scopeChain();
    MDefinition *argumentsObject();

    // Increase the number of slots available
    bool increaseSlots(size_t num);
    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.
    void 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 setScopeChain(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.
    bool addPredecessor(TempAllocator &alloc, MBasicBlock *pred);
    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.
    bool addPredecessorWithoutPhis(MBasicBlock *pred);
    void inheritSlots(MBasicBlock *parent);
    bool initEntrySlots(TempAllocator &alloc);

    // Replaces an edge for a given block with a new block. This is
    // used for critical edge splitting and also for inserting
    // bailouts during ParallelSafetyAnalysis.
    //
    // 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);

    // 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.
    AbortReason setBackedge(MBasicBlock *block);
    bool setBackedgeAsmJS(MBasicBlock *block);

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

    // 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.
    bool inheritPhisFromBackedge(MBasicBlock *backedge, bool *hadTypeChange);

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

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

    // Removes an instruction with the intention to discard it.
    void discard(MInstruction *ins);
    void discardLastIns();
    MInstructionIterator discardAt(MInstructionIterator &iter);
    MInstructionReverseIterator discardAt(MInstructionReverseIterator &iter);
    MDefinitionIterator discardDefAt(MDefinitionIterator &iter);
    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.
    MPhiIterator discardPhiAt(MPhiIterator &at);

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

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

    MIRGraph &graph() {
        return graph_;
    }
    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 {
        JS_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.
        JS_ASSERT(!block->successorWithPhis());

        for (size_t i = 0; i < predecessors_.length(); i++) {
            if (predecessors_[i] == block)
                return i;
        }
        MOZ_CRASH();
    }
    bool hasLastIns() const {
        return !instructions_.empty() && instructions_.rbegin()->isControlInstruction();
    }
    MControlInstruction *lastIns() const {
        JS_ASSERT(hasLastIns());
        return instructions_.rbegin()->toControlInstruction();
    }
    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) {
        JS_ASSERT(at->block() == this);
        return instructions_.begin(at);
    }
    MInstructionIterator end() {
        return instructions_.end();
    }
    MInstructionReverseIterator rbegin() {
        return instructions_.rbegin();
    }
    MInstructionReverseIterator rbegin(MInstruction *at) {
        JS_ASSERT(at->block() == this);
        return instructions_.rbegin(at);
    }
    MInstructionReverseIterator rend() {
        return instructions_.rend();
    }
    bool isLoopHeader() const {
        return kind_ == LOOP_HEADER;
    }
    bool hasUniqueBackedge() const {
        JS_ASSERT(isLoopHeader());
        JS_ASSERT(numPredecessors() >= 2);
        return numPredecessors() == 2;
    }
    MBasicBlock *backedge() const {
        JS_ASSERT(hasUniqueBackedge());
        return getPredecessor(numPredecessors() - 1);
    }
    MBasicBlock *loopHeaderOfBackedge() const {
        JS_ASSERT(isLoopBackedge());
        return getSuccessor(numSuccessors() - 1);
    }
    MBasicBlock *loopPredecessor() const {
        JS_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");
        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 {
        JS_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;
    }
    MResumePoint *callerResumePoint() {
        return entryResumePoint() ? entryResumePoint()->caller() : nullptr;
    }
    void setCallerResumePoint(MResumePoint *caller) {
        entryResumePoint()->setCaller(caller);
    }
    size_t numEntrySlots() const {
        return entryResumePoint()->numOperands();
    }
    MDefinition *getEntrySlot(size_t i) const {
        JS_ASSERT(i < numEntrySlots());
        return entryResumePoint()->getOperand(i);
    }

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

    MBasicBlock *successorWithPhis() const {
        return successorWithPhis_;
    }
    uint32_t positionInPhiSuccessor() const {
        return positionInPhiSuccessor_;
    }
    void setSuccessorWithPhis(MBasicBlock *successor, uint32_t id) {
        successorWithPhis_ = successor;
        positionInPhiSuccessor_ = id;
    }
    size_t numSuccessors() const;
    MBasicBlock *getSuccessor(size_t index) const;
    size_t getSuccessorIndex(MBasicBlock *) const;

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

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

    void dumpStack(FILE *fp);

    void dump(FILE *fp);
    void dump();

    // Track bailouts by storing the current pc in MIR instruction added at this
    // cycle. This is also used for tracking calls when profiling.
    void updateTrackedSite(const BytecodeSite &site) {
        JS_ASSERT(site.tree() == trackedSite_.tree());
        trackedSite_ = site;
    }
    const BytecodeSite &trackedSite() const {
        return trackedSite_;
    }
    jsbytecode *trackedPc() const {
        return trackedSite_.pc();
    }
    InlineScriptTree *trackedTree() const {
        return trackedSite_.tree();
    }

  private:
    MIRGraph &graph_;
    CompileInfo &info_; // Each block originates from a particular script.
    InlineList<MInstruction> instructions_;
    Vector<MBasicBlock *, 1, IonAllocPolicy> 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_;

    // 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, IonAllocPolicy> immediatelyDominated_;
    MBasicBlock *immediateDominator_;

    BytecodeSite trackedSite_;

#if defined (JS_ION_PERF)
    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, IonAllocPolicy> MIRGraphReturns;

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

    size_t numBlocks_;
    bool hasTryBlock_;

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

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

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

    void renumberBlocksAfter(MBasicBlock *at);

    void unmarkBlocks();

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

    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) {
        JS_ASSERT(block->id());
        blocks_.remove(block);
        blocks_.pushBack(block);
    }
    void moveBlockBefore(MBasicBlock *at, MBasicBlock *block) {
        JS_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) {
        JS_ASSERT(!osrBlock_);
        osrBlock_ = osrBlock;
    }
    MBasicBlock *osrBlock() {
        return osrBlock_;
    }

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

    // The per-thread context. So as not to modify the calling convention for
    // parallel code, we obtain the current ForkJoinContext from thread-local
    // storage.  This helper method will lazilly insert an MForkJoinContext
    // instruction in the entry block and return the definition.
    MDefinition *forkJoinContext();

    void dump(FILE *fp);
    void dump();
};

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

    void next() {
        if (atPhi())
            phiIter_++;
        else
            iter_++;
    }

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

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

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

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

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

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

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

};

} // namespace jit
} // namespace js

#endif /* jit_MIRGraph_h */