src/third_party/mozjs/js/src/jit/MIRGraph.h - cobalt - Git at Google

 /* -*- 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 "IonAllocPolicy.h"
 #include "MIRGenerator.h"
 #include "FixedList.h"

 namespace js {
 namespace jit {

 class MBasicBlock;
 class MIRGraph;
 class MStart;

 class MDefinitionIterator;

 typedef InlineListIterator<MInstruction> MInstructionIterator;
 typedef InlineListReverseIterator<MInstruction> MInstructionReverseIterator;
 typedef InlineForwardListIterator<MPhi> MPhiIterator;
 typedef InlineForwardListIterator<MResumePoint> MResumePointIterator;

 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, jsbytecode *pc, Kind kind);
     bool init();
     void copySlots(MBasicBlock *from);
     bool inherit(MBasicBlock *pred, uint32_t popped);
     bool inheritResumePoint(MBasicBlock *pred);
     void assertUsesAreNotWithin(MUseIterator use, MUseIterator end);

     // Does this block do something that forces it to terminate early?
     bool earlyAbort_;

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

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

     // Creates a new basic block for a MIR generator. If |pred| is not NULL,
     // its slots and stack depth are initialized from |pred|.
     static MBasicBlock *New(MIRGraph &graph, CompileInfo &info,
                             MBasicBlock *pred, jsbytecode *entryPc, Kind kind);
     static MBasicBlock *NewPopN(MIRGraph &graph, CompileInfo &info,
                                 MBasicBlock *pred, jsbytecode *entryPc, Kind kind, uint32_t popn);
     static MBasicBlock *NewWithResumePoint(MIRGraph &graph, CompileInfo &info,
                                            MBasicBlock *pred, jsbytecode *entryPc,
                                            MResumePoint *resumePoint);
     static MBasicBlock *NewPendingLoopHeader(MIRGraph &graph, CompileInfo &info,
                                              MBasicBlock *pred, jsbytecode *entryPc);
     static MBasicBlock *NewSplitEdge(MIRGraph &graph, CompileInfo &info, MBasicBlock *pred);
     static MBasicBlock *NewParBailout(MIRGraph &graph, CompileInfo &info,
                                       MBasicBlock *pred, jsbytecode *entryPc,
                                       MResumePoint *resumePoint);

     bool dominates(MBasicBlock *other);

     void setId(uint32_t id) {
         id_ = id;
     }
     void setEarlyAbort() {
         earlyAbort_ = true;
     }
     void clearEarlyAbort() {
         earlyAbort_ = false;
     }
     bool earlyAbort() {
         return earlyAbort_;
     }
     // 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);

     // 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. |ins| may be NULL
     // to simplify OOM checking.
     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) {
         resumePoints_.pushFront(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(MBasicBlock *pred);
     bool addPredecessorPopN(MBasicBlock *pred, uint32_t popped);

     // Stranger utilities used for inlining.
     bool addPredecessorWithoutPhis(MBasicBlock *pred);
     void inheritSlots(MBasicBlock *parent);
     bool initEntrySlots();

     // Replaces an edge for a given block with a new block. This is
     // used for critical edge splitting and also for inserting
     // bailouts during ParallelArrayAnalysis.
     //
     // 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.  `pred` should not be
     // the final predecessor. 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);

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

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

     void insertBefore(MInstruction *at, MInstruction *ins);
     void insertAfter(MInstruction *at, 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 discardAllPhis();
     void discardAllResumePoints(bool discardEntry = true);

     // 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];
     }
     MControlInstruction *lastIns() const {
         return lastIns_;
     }
     MPhiIterator phisBegin() const {
         return phis_.begin();
     }
     MPhiIterator phisEnd() const {
         return phis_.end();
     }
     bool phisEmpty() const {
         return phis_.empty();
     }
     MResumePointIterator resumePointsBegin() const {
         return resumePoints_.begin();
     }
     MResumePointIterator resumePointsEnd() const {
         return resumePoints_.end();
     }
     bool resumePointsEmpty() const {
         return resumePoints_.empty();
     }
     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() {
         mark_ = true;
     }
     void unmark() {
         mark_ = false;
     }
     void makeStart(MStart *start) {
         add(start);
         start_ = start;
     }
     MStart *start() const {
         return start_;
     }

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

     size_t numDominated() const {
         return numDominated_;
     }

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

     bool addImmediatelyDominatedBlock(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_;
     }
     MResumePoint *callerResumePoint() {
         return entryResumePoint()->caller();
     }
     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;

     // Specifies the closest loop header dominating this block.
     void setLoopHeader(MBasicBlock *loop) {
         JS_ASSERT(loop->isLoopHeader());
         loopHeader_ = loop;
     }
     MBasicBlock *loopHeader() const {
         return loopHeader_;
     }

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

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

     void dumpStack(FILE *fp);

     // Track bailouts by storing the current pc in MIR instruction added at this
     // cycle. This is also used for tracking calls when profiling.
     void updateTrackedPc(jsbytecode *pc) {
         trackedPc_ = pc;
     }

     jsbytecode *trackedPc() {
         return trackedPc_;
     }

   private:
     MIRGraph &graph_;
     CompileInfo &info_; // Each block originates from a particular script.
     InlineList<MInstruction> instructions_;
     Vector<MBasicBlock *, 1, IonAllocPolicy> predecessors_;
     InlineForwardList<MPhi> phis_;
     InlineForwardList<MResumePoint> resumePoints_;
     FixedList<MDefinition *> slots_;
     uint32_t stackPosition_;
     MControlInstruction *lastIns_;
     jsbytecode *pc_;
     uint32_t id_;
     uint32_t domIndex_; // Index in the dominator tree.
     LBlock *lir_;
     MStart *start_;
     MResumePoint *entryResumePoint_;
     MBasicBlock *successorWithPhis_;
     uint32_t positionInPhiSuccessor_;
     Kind kind_;
     uint32_t loopDepth_;

     // Utility mark for traversal algorithms.
     bool mark_;

     Vector<MBasicBlock *, 1, IonAllocPolicy> immediatelyDominated_;
     MBasicBlock *immediateDominator_;
     size_t numDominated_;
     MBasicBlock *loopHeader_;

     jsbytecode *trackedPc_;
 };

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

 typedef Vector<MBasicBlock *, 1, IonAllocPolicy> MIRGraphExits;

 class MIRGraph
 {
     InlineList<MBasicBlock> blocks_;
     TempAllocator *alloc_;
     MIRGraphExits *exitAccumulator_;
     uint32_t blockIdGen_;
     uint32_t idGen_;
     MBasicBlock *osrBlock_;
     MStart *osrStart_;

     // List of compiled/inlined scripts.
     Vector<JSScript *, 4, IonAllocPolicy> scripts_;

     size_t numBlocks_;

   public:
     MIRGraph(TempAllocator *alloc)
       : alloc_(alloc),
         exitAccumulator_(NULL),
         blockIdGen_(0),
         idGen_(0),
         osrBlock_(NULL),
         osrStart_(NULL),
         numBlocks_(0)
     { }

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

     void unmarkBlocks();

     void setExitAccumulator(MIRGraphExits *accum) {
         exitAccumulator_ = accum;
     }
     MIRGraphExits *exitAccumulator() const {
         return exitAccumulator_;
     }

     bool addExit(MBasicBlock *exitBlock) {
         if (!exitAccumulator_)
             return true;

         return exitAccumulator_->append(exitBlock);
     }

     MBasicBlock *entryBlock() {
         return *blocks_.begin();
     }

     void clearBlockList() {
         blocks_.clear();
         blockIdGen_ = 0;
         numBlocks_ = 0;
     }
     void resetInstructionNumber() {
         idGen_ = 0;
     }
     MBasicBlockIterator begin() {
         return blocks_.begin();
     }
     MBasicBlockIterator begin(MBasicBlock *at) {
         return blocks_.begin(at);
     }
     MBasicBlockIterator end() {
         return blocks_.end();
     }
     PostorderIterator poBegin() {
         return blocks_.rbegin();
     }
     PostorderIterator poEnd() {
         return blocks_.rend();
     }
     ReversePostorderIterator rpoBegin() {
         return blocks_.begin();
     }
     ReversePostorderIterator rpoEnd() {
         return blocks_.end();
     }
     void removeBlocksAfter(MBasicBlock *block);
     void removeBlock(MBasicBlock *block);
     void moveBlockToEnd(MBasicBlock *block) {
         JS_ASSERT(block->id());
         blocks_.remove(block);
         blocks_.pushBack(block);
     }
     size_t numBlocks() const {
         return numBlocks_;
     }
     uint32_t numBlockIds() const {
         return blockIdGen_;
     }
     void allocDefinitionId(MDefinition *ins) {
         // This intentionally starts above 0. The id 0 is in places used to
         // indicate a failure to perform an operation on an instruction.
         idGen_ += 2;
         ins->setId(idGen_);
     }
     uint32_t getMaxInstructionId() {
         return idGen_;
     }
     MResumePoint *entryResumePoint() {
         return blocks_.begin()->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_;
     }
     void setOsrStart(MStart *osrStart) {
         osrStart_ = osrStart;
     }
     MStart *osrStart() {
         return osrStart_;
     }
     bool addScript(JSScript *script) {
         // The same script may be inlined multiple times, add it only once.
         for (size_t i = 0; i < scripts_.length(); i++) {
             if (scripts_[i] == script)
                 return true;
         }
         return scripts_.append(script);
     }
     size_t numScripts() const {
         return scripts_.length();
     }
     JSScript **scripts() {
         return scripts_.begin();
     }

     // The ParSlice is an instance of ForkJoinSlice*, it carries
     // "per-helper-thread" information.  So as not to modify the
     // calling convention for parallel code, we obtain the current
     // slice from thread-local storage.  This helper method will
     // lazilly insert an MParSlice instruction in the entry block and
     // return the definition.
     MDefinition *parSlice();
 };

 class MDefinitionIterator
 {

   friend class MBasicBlock;

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

 };

 } // namespace jit
 } // namespace js

 #endif /* 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 "IonAllocPolicy.h"
	#include "MIRGenerator.h"
	#include "FixedList.h"

	namespace js {
	namespace jit {

	class MBasicBlock;
	class MIRGraph;
	class MStart;

	class MDefinitionIterator;

	typedef InlineListIterator<MInstruction> MInstructionIterator;
	typedef InlineListReverseIterator<MInstruction> MInstructionReverseIterator;
	typedef InlineForwardListIterator<MPhi> MPhiIterator;
	typedef InlineForwardListIterator<MResumePoint> MResumePointIterator;

	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, jsbytecode *pc, Kind kind);
	bool init();
	void copySlots(MBasicBlock *from);
	bool inherit(MBasicBlock *pred, uint32_t popped);
	bool inheritResumePoint(MBasicBlock *pred);
	void assertUsesAreNotWithin(MUseIterator use, MUseIterator end);

	// Does this block do something that forces it to terminate early?
	bool earlyAbort_;

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

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

	// Creates a new basic block for a MIR generator. If \|pred\| is not NULL,
	// its slots and stack depth are initialized from \|pred\|.
	static MBasicBlock *New(MIRGraph &graph, CompileInfo &info,
	MBasicBlock pred, jsbytecode entryPc, Kind kind);
	static MBasicBlock *NewPopN(MIRGraph &graph, CompileInfo &info,
	MBasicBlock pred, jsbytecode entryPc, Kind kind, uint32_t popn);
	static MBasicBlock *NewWithResumePoint(MIRGraph &graph, CompileInfo &info,
	MBasicBlock pred, jsbytecode entryPc,
	MResumePoint *resumePoint);
	static MBasicBlock *NewPendingLoopHeader(MIRGraph &graph, CompileInfo &info,
	MBasicBlock pred, jsbytecode entryPc);
	static MBasicBlock NewSplitEdge(MIRGraph &graph, CompileInfo &info, MBasicBlock pred);
	static MBasicBlock *NewParBailout(MIRGraph &graph, CompileInfo &info,
	MBasicBlock pred, jsbytecode entryPc,
	MResumePoint *resumePoint);

	bool dominates(MBasicBlock *other);

	void setId(uint32_t id) {
	id_ = id;
	}
	void setEarlyAbort() {
	earlyAbort_ = true;
	}
	void clearEarlyAbort() {
	earlyAbort_ = false;
	}
	bool earlyAbort() {
	return earlyAbort_;
	}
	// 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);

	// 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. \|ins\| may be NULL
	// to simplify OOM checking.
	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) {
	resumePoints_.pushFront(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(MBasicBlock *pred);
	bool addPredecessorPopN(MBasicBlock *pred, uint32_t popped);

	// Stranger utilities used for inlining.
	bool addPredecessorWithoutPhis(MBasicBlock *pred);
	void inheritSlots(MBasicBlock *parent);
	bool initEntrySlots();

	// Replaces an edge for a given block with a new block. This is
	// used for critical edge splitting and also for inserting
	// bailouts during ParallelArrayAnalysis.
	//
	// 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. `pred` should not be
	// the final predecessor. 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);

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

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

	void insertBefore(MInstruction at, MInstruction ins);
	void insertAfter(MInstruction at, 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 discardAllPhis();
	void discardAllResumePoints(bool discardEntry = true);

	// 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];
	}
	MControlInstruction *lastIns() const {
	return lastIns_;
	}
	MPhiIterator phisBegin() const {
	return phis_.begin();
	}
	MPhiIterator phisEnd() const {
	return phis_.end();
	}
	bool phisEmpty() const {
	return phis_.empty();
	}
	MResumePointIterator resumePointsBegin() const {
	return resumePoints_.begin();
	}
	MResumePointIterator resumePointsEnd() const {
	return resumePoints_.end();
	}
	bool resumePointsEmpty() const {
	return resumePoints_.empty();
	}
	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() {
	mark_ = true;
	}
	void unmark() {
	mark_ = false;
	}
	void makeStart(MStart *start) {
	add(start);
	start_ = start;
	}
	MStart *start() const {
	return start_;
	}

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

	size_t numDominated() const {
	return numDominated_;
	}

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

	bool addImmediatelyDominatedBlock(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_;
	}
	MResumePoint *callerResumePoint() {
	return entryResumePoint()->caller();
	}
	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;

	// Specifies the closest loop header dominating this block.
	void setLoopHeader(MBasicBlock *loop) {
	JS_ASSERT(loop->isLoopHeader());
	loopHeader_ = loop;
	}
	MBasicBlock *loopHeader() const {
	return loopHeader_;
	}

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

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

	void dumpStack(FILE *fp);

	// Track bailouts by storing the current pc in MIR instruction added at this
	// cycle. This is also used for tracking calls when profiling.
	void updateTrackedPc(jsbytecode *pc) {
	trackedPc_ = pc;
	}

	jsbytecode *trackedPc() {
	return trackedPc_;
	}

	private:
	MIRGraph &graph_;
	CompileInfo &info_; // Each block originates from a particular script.
	InlineList<MInstruction> instructions_;
	Vector<MBasicBlock *, 1, IonAllocPolicy> predecessors_;
	InlineForwardList<MPhi> phis_;
	InlineForwardList<MResumePoint> resumePoints_;
	FixedList<MDefinition *> slots_;
	uint32_t stackPosition_;
	MControlInstruction *lastIns_;
	jsbytecode *pc_;
	uint32_t id_;
	uint32_t domIndex_; // Index in the dominator tree.
	LBlock *lir_;
	MStart *start_;
	MResumePoint *entryResumePoint_;
	MBasicBlock *successorWithPhis_;
	uint32_t positionInPhiSuccessor_;
	Kind kind_;
	uint32_t loopDepth_;

	// Utility mark for traversal algorithms.
	bool mark_;

	Vector<MBasicBlock *, 1, IonAllocPolicy> immediatelyDominated_;
	MBasicBlock *immediateDominator_;
	size_t numDominated_;
	MBasicBlock *loopHeader_;

	jsbytecode *trackedPc_;
	};

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

	typedef Vector<MBasicBlock *, 1, IonAllocPolicy> MIRGraphExits;

	class MIRGraph
	{
	InlineList<MBasicBlock> blocks_;
	TempAllocator *alloc_;
	MIRGraphExits *exitAccumulator_;
	uint32_t blockIdGen_;
	uint32_t idGen_;
	MBasicBlock *osrBlock_;
	MStart *osrStart_;

	// List of compiled/inlined scripts.
	Vector<JSScript *, 4, IonAllocPolicy> scripts_;

	size_t numBlocks_;

	public:
	MIRGraph(TempAllocator *alloc)
	: alloc_(alloc),
	exitAccumulator_(NULL),
	blockIdGen_(0),
	idGen_(0),
	osrBlock_(NULL),
	osrStart_(NULL),
	numBlocks_(0)
	{ }

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

	void unmarkBlocks();

	void setExitAccumulator(MIRGraphExits *accum) {
	exitAccumulator_ = accum;
	}
	MIRGraphExits *exitAccumulator() const {
	return exitAccumulator_;
	}

	bool addExit(MBasicBlock *exitBlock) {
	if (!exitAccumulator_)
	return true;

	return exitAccumulator_->append(exitBlock);
	}

	MBasicBlock *entryBlock() {
	return *blocks_.begin();
	}

	void clearBlockList() {
	blocks_.clear();
	blockIdGen_ = 0;
	numBlocks_ = 0;
	}
	void resetInstructionNumber() {
	idGen_ = 0;
	}
	MBasicBlockIterator begin() {
	return blocks_.begin();
	}
	MBasicBlockIterator begin(MBasicBlock *at) {
	return blocks_.begin(at);
	}
	MBasicBlockIterator end() {
	return blocks_.end();
	}
	PostorderIterator poBegin() {
	return blocks_.rbegin();
	}
	PostorderIterator poEnd() {
	return blocks_.rend();
	}
	ReversePostorderIterator rpoBegin() {
	return blocks_.begin();
	}
	ReversePostorderIterator rpoEnd() {
	return blocks_.end();
	}
	void removeBlocksAfter(MBasicBlock *block);
	void removeBlock(MBasicBlock *block);
	void moveBlockToEnd(MBasicBlock *block) {
	JS_ASSERT(block->id());
	blocks_.remove(block);
	blocks_.pushBack(block);
	}
	size_t numBlocks() const {
	return numBlocks_;
	}
	uint32_t numBlockIds() const {
	return blockIdGen_;
	}
	void allocDefinitionId(MDefinition *ins) {
	// This intentionally starts above 0. The id 0 is in places used to
	// indicate a failure to perform an operation on an instruction.
	idGen_ += 2;
	ins->setId(idGen_);
	}
	uint32_t getMaxInstructionId() {
	return idGen_;
	}
	MResumePoint *entryResumePoint() {
	return blocks_.begin()->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_;
	}
	void setOsrStart(MStart *osrStart) {
	osrStart_ = osrStart;
	}
	MStart *osrStart() {
	return osrStart_;
	}
	bool addScript(JSScript *script) {
	// The same script may be inlined multiple times, add it only once.
	for (size_t i = 0; i < scripts_.length(); i++) {
	if (scripts_[i] == script)
	return true;
	}
	return scripts_.append(script);
	}
	size_t numScripts() const {
	return scripts_.length();
	}
	JSScript **scripts() {
	return scripts_.begin();
	}

	// The ParSlice is an instance of ForkJoinSlice*, it carries
	// "per-helper-thread" information. So as not to modify the
	// calling convention for parallel code, we obtain the current
	// slice from thread-local storage. This helper method will
	// lazilly insert an MParSlice instruction in the entry block and
	// return the definition.
	MDefinition *parSlice();
	};

	class MDefinitionIterator
	{

	friend class MBasicBlock;

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

	};

	} // namespace jit
	} // namespace js

	#endif /* jit_MIRGraph_h */