blob: 60c2ef4c794d12a23f6be17cccba7fe3f4c2d9eb [file] [log] [blame]
/* -*- 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 */