The Tor Browser: comparison js/src/jit/MIRGraph.h

--1:000000000000
+:6d686434703d
+/* -*- 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 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(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);
+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, 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,
+unsigned loopStateSlots);
+static MBasicBlock *NewSplitEdge(MIRGraph &graph, CompileInfo &info, MBasicBlock *pred);
+static MBasicBlock *NewAbortPar(MIRGraph &graph, CompileInfo &info,
+MBasicBlock *pred, jsbytecode *entryPc,
+MResumePoint *resumePoint);
+static MBasicBlock *NewAsmJS(MIRGraph &graph, CompileInfo &info,
+MBasicBlock *pred, Kind kind);
+bool dominates(const MBasicBlock *other) const;
+void setId(uint32_t id) {
+id_ = id;
+}
+// Mark the current block and all dominated blocks as unreachable.
+void setUnreachable();
+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. |ins| may be
+// nullptr 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(TempAllocator &alloc, MBasicBlock *pred);
+bool addPredecessorPopN(TempAllocator &alloc, MBasicBlock *pred, uint32_t popped);
+// 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.  `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);
+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);
+// 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);
+// 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 discardAllPhiOperands();
+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;
+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 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_;
+jsbytecode *trackedPc_;
+#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_;
+MStart *osrStart_;
+size_t numBlocks_;
+bool hasTryBlock_;
+public:
+MIRGraph(TempAllocator *alloc)
+: alloc_(alloc),
+returnAccumulator_(nullptr),
+blockIdGen_(0),
+idGen_(1),
+osrBlock_(nullptr),
+osrStart_(nullptr),
+numBlocks_(0),
+hasTryBlock_(false)
+{ }
+TempAllocator &alloc() const {
+return *alloc_;
+}
+void addBlock(MBasicBlock *block);
+void insertBlockAfter(MBasicBlock *at, MBasicBlock *block);
+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();
+}
+void clearBlockList() {
+blocks_.clear();
+blockIdGen_ = 0;
+numBlocks_ = 0;
+}
+void resetInstructionNumber() {
+// This intentionally starts above 0. The id 0 is in places used to
+// indicate a failure to perform an operation on an instruction.
+idGen_ = 1;
+}
+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 rpoBegin(MBasicBlock *at) {
+return blocks_.begin(at);
+}
+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) {
+ins->setId(idGen_++);
+}
+uint32_t getNumInstructionIds() {
+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 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;
+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 */

The Tor Browser / file comparison

comparison: js/src/jit/MIRGraph.h

js/src/jit/MIRGraph.h