diff options
Diffstat (limited to 'js/src/jit/MIRGraph.h')
| -rw-r--r-- | js/src/jit/MIRGraph.h | 1060 |
1 files changed, 1060 insertions, 0 deletions
diff --git a/js/src/jit/MIRGraph.h b/js/src/jit/MIRGraph.h new file mode 100644 index 000000000..b986218f4 --- /dev/null +++ b/js/src/jit/MIRGraph.h @@ -0,0 +1,1060 @@ +/* -*- 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); + + // 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 */ |