Go to the documentation of this file.
15 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
16 #define LLVM_CODEGEN_SCHEDULEDAG_H
33 template <
class GraphType>
struct GraphTraits;
105 : Dep(
S, kind), Contents() {
112 "SDep::Anti and SDep::Output must use a non-zero Reg!");
125 Contents.OrdKind = kind;
220 "getReg called on non-register dependence edge!");
230 "setReg called on non-register dependence edge!");
232 "SDep::Anti edge cannot use the zero register!");
234 "SDep::Output edge cannot use the zero register!");
244 enum :
unsigned { BoundaryID = ~0u };
293 bool isDepthCurrent : 1;
294 bool isHeightCurrent : 1;
315 isHeightCurrent(
false) {}
326 isHeightCurrent(
false) {}
335 isDepthCurrent(
false), isHeightCurrent(
false) {}
349 assert(!Instr &&
"Setting SDNode of SUnit with MachineInstr!");
356 assert(!Instr &&
"Reading SDNode of SUnit with MachineInstr!");
367 assert(!
Node &&
"Setting MachineInstr of SUnit with SDNode!");
374 assert(!
Node &&
"Reading MachineInstr of SUnit with SDNode!");
386 unsigned TrueMemOrderLatency =
400 const_cast<SUnit *
>(
this)->ComputeDepth();
407 if (!isHeightCurrent)
408 const_cast<SUnit *
>(
this)->ComputeHeight();
433 if (Pred.getSUnit() ==
N)
441 if (Succ.getSUnit() ==
N)
461 void ComputeHeight();
466 if (Dep !=
Other.Dep)
468 switch (Dep.getInt()) {
472 return Contents.Reg ==
Other.Contents.Reg;
474 return Contents.OrdKind ==
Other.Contents.OrdKind;
497 virtual void anchor();
499 unsigned CurCycle = 0;
509 virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
514 virtual bool empty()
const = 0;
521 assert(!HasReadyFilter &&
"The ready filter must override isReady()");
528 for (
SUnit *SU : Nodes)
582 return getNodeDesc(SU->
getNode());
590 virtual void dump()
const = 0;
630 return Operand ==
x.Operand;
635 return Node->Preds[Operand].getSUnit();
663 return Node->Preds[Operand];
695 std::vector<SUnit> &SUnits;
705 std::vector<int> Index2Node;
707 std::vector<int> Node2Index;
714 void DFS(
const SUnit *SU,
int UpperBound,
bool& HasLoop);
718 void Shift(
BitVector& Visited,
int LowerBound,
int UpperBound);
721 void Allocate(
int n,
int index);
786 #endif // LLVM_CODEGEN_SCHEDULEDAG_H
MachineRegisterInfo & MRI
Virtual/real register map.
virtual void scheduledNode(SUnit *)
As each node is scheduled, this method is invoked.
void RemovePred(SUnit *M, SUnit *N)
Updates the topological ordering to accommodate an an edge to be removed from the specified node N fr...
void dumpAttributes() const
This is an optimization pass for GlobalISel generic memory operations.
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
unsigned OrdKind
Additional information about Order dependencies.
bool isScheduleLow
True if preferable to schedule low.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
@ MustAliasMem
Nonvolatile load/Store instructions that must alias.
const SDep & getSDep() const
@ Artificial
Arbitrary strong DAG edge (no real dependence).
void setReg(unsigned Reg)
Assigns the associated register for this edge.
bool isAvailable
True once available.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual void dump(ScheduleDAG *) const
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
std::vector< int >::const_iterator const_iterator
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
virtual std::string getGraphNodeLabel(const SUnit *SU) const =0
Returns a label for an SUnit node in a visualization of the ScheduleDAG.
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
pointer_iterator< std::vector< SUnit >::iterator > nodes_iterator
@ Anti
A register anti-dependence (aka WAR).
bool isCommutable
Is a commutable instruction.
bool isCall
Is a function call.
Represents one node in the SelectionDAG.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Kind
These are the different kinds of scheduling dependencies.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
virtual void addNode(const SUnit *SU)=0
virtual bool tracksRegPressure() const
static nodes_iterator nodes_end(ScheduleDAG *G)
const_iterator end() const
SmallVector< SDep, 4 > Succs
All sunit successors.
SUnitIterator operator++(int)
pointer operator*() const
unsigned getOperand() const
bool isNormalMemory() const
Tests if this is an Order dependence between two memory accesses where both sides of the dependence a...
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
virtual bool isReady(SUnit *) const
virtual void addCustomGraphFeatures(GraphWriter< ScheduleDAG * > &) const
Adds custom features for a visualization of the ScheduleDAG.
SchedulingPriorityQueue(bool rf=false)
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
unsigned const TargetRegisterInfo * TRI
void AddPredQueued(SUnit *Y, SUnit *X)
Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit...
ScheduleDAG(MachineFunction &mf)
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
unsigned getCurCycle() const
bool isCtrlDep() const
Tests if this is not an SDep::Data dependence.
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
unsigned BotReadyCycle
Cycle relative to end when node is ready.
@ Weak
Arbitrary weak DAG edge.
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
TargetInstrInfo - Interface to description of machine instruction set.
bool overlaps(const SDep &Other) const
Returns true if the specified SDep is equivalent except for latency.
void setDepthDirty()
Sets a flag in this node to indicate that its stored Depth value will require recomputation the next ...
std::ptrdiff_t difference_type
SUnitIterator & operator++()
bool isBottomReady() const
bool isUnbuffered
Uses an unbuffered resource.
static NodeRef getEntryNode(SUnit *N)
bool operator==(const SUnitIterator &x) const
bool isScheduleHigh
True if preferable to schedule high.
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value.
unsigned short Latency
Node latency.
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node's depth value, sets it to be the new depth value.
unsigned NodeNum
Entry # of node in the node vector.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Describe properties that are true of each instruction in the target description file.
virtual bool empty() const =0
void setInstr(MachineInstr *MI)
Assigns the instruction for the SUnit.
void AddPred(SUnit *Y, SUnit *X)
Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y.
A possibly irreducible generalization of a Loop.
pointer operator->() const
@ Output
A register output-dependence (aka WAW).
@ Data
Regular data dependence (aka true-dependence).
const MCInstrDesc * getInstrDesc(const SUnit *SU) const
Returns the MCInstrDesc of this SUnit.
static ChildIteratorType child_begin(NodeRef N)
bool isVRegCycle
May use and def the same vreg.
std::vector< int >::const_reverse_iterator const_reverse_iterator
SUnit * OrigNode
If not this, the node from which this node was cloned.
bool hasPhysRegClobbers
Has any physreg defs, used or not.
bool isCallOp
Is a function call operand.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
std::vector< int >::reverse_iterator reverse_iterator
unsigned VerifyScheduledDAG(bool isBottomUp)
Verifies that all SUnits were scheduled and that their state is consistent.
@ Order
Any other ordering dependency.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
virtual void push(SUnit *U)=0
unsigned TopReadyCycle
Cycle relative to start when node is ready.
ScheduleDAGTopologicalSort(std::vector< SUnit > &SUnits, SUnit *ExitSU)
virtual void viewGraph()
Out-of-line implementation with no arguments is handy for gdb.
bool isPred(const SUnit *N) const
Tests if node N is a predecessor of this node.
bool isPending
True once pending.
SmallVectorImpl< SDep >::iterator succ_iterator
static SUnitIterator end(SUnit *N)
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
Representation of each machine instruction.
virtual ~SchedulingPriorityQueue()=default
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
unsigned short NumRegDefsLeft
virtual bool isBottomUp() const =0
void setNode(SDNode *N)
Assigns the representative SDNode for this SUnit.
static nodes_iterator nodes_begin(ScheduleDAG *G)
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
unsigned getReg() const
Returns the register associated with this edge.
bool isScheduled
True once scheduled.
bool hasReadyFilter() const
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper node
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
std::vector< int >::iterator iterator
SUnit(MachineInstr *instr, unsigned nodenum)
Constructs an SUnit for post-regalloc scheduling to represent a MachineInstr.
bool hasPhysRegUses
Has physreg uses.
void biasCriticalPath()
Orders this node's predecessor edges such that the critical path edge occurs first.
typename SuperClass::const_iterator const_iterator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static SUnitIterator begin(SUnit *N)
const TargetRegisterClass * CopySrcRC
void dumpNodeAll(const SUnit &SU) const
bool operator!=(const SUnitIterator &x) const
bool operator==(const SDep &Other) const
SUnitIterator ChildIteratorType
SmallVectorImpl< SDep >::const_iterator const_succ_iterator
bool isCluster() const
Tests if this is an Order dependence that is marked as "cluster", meaning it is artificial and wants ...
bool operator!=(const SDep &Other) const
SUnit(SDNode *node, unsigned nodenum)
Constructs an SUnit for pre-regalloc scheduling to represent an SDNode and any nodes flagged to it.
const SUnit * getNode() const
virtual void dumpNode(const SUnit &SU) const =0
const TargetRegisterInfo * TRI
Target processor register info.
const_reverse_iterator rend() const
std::forward_iterator_tag iterator_category
const MCSchedClassDesc * SchedClass
nullptr or resolved SchedClass.
MachineFunction & MF
Machine function.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const_iterator begin() const
@ Barrier
An unknown scheduling barrier.
SDep(SUnit *S, OrderKind kind)
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
SUnit EntrySU
Special node for the region entry.
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Sched::Preference SchedulingPref
Scheduling preference.
virtual std::string getDAGName() const =0
Returns a label for the region of code covered by the DAG.
unsigned Reg
For Data, Anti, and Output dependencies, the associated register.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
std::vector< SUnit > SUnits
The scheduling units.
virtual void remove(SUnit *SU)=0
virtual void releaseState()=0
const_reverse_iterator rbegin() const
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
void setHeightDirty()
Sets a flag in this node to indicate that its stored Height value will require recomputation the next...
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
void setLatency(unsigned Lat)
Sets the latency for this edge.
const TargetInstrInfo * TII
Target instruction information.
bool isWeak() const
Tests if this a weak dependence.
void setCurCycle(unsigned Cycle)
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
This class describes a target machine that is implemented with the LLVM target-independent code gener...
bool hasPhysRegDefs
Has physreg defs that are being used.
bool isTwoAddress
Is a two-address instruction.
bool addPredBarrier(SUnit *SU)
Adds a barrier edge to SU by calling addPred(), with latency 0 generally or latency 1 for a store fol...
bool isCloned
True if this node has been cloned.
Kind getKind() const
Returns an enum value representing the kind of the dependence.
const LLVMTargetMachine & TM
Target processor.
bool isNormalMemoryOrBarrier() const
Tests if this is could be any kind of memory dependence.
bool isSucc(const SUnit *N) const
Tests if node N is a successor of this node.
unsigned NodeQueueId
Queue id of node.
PointerIntPair - This class implements a pair of a pointer and small integer.
std::optional< std::vector< StOtherPiece > > Other
bool hasReservedResource
Uses a reserved resource.
static ChildIteratorType child_end(NodeRef N)
bool isInstr() const
Returns true if this SUnit refers to a machine instruction as opposed to an SDNode.
typename SuperClass::iterator iterator
virtual void dump() const =0
void dumpNodeName(const SUnit &SU) const
void push_all(const std::vector< SUnit * > &Nodes)
SUnit()
Constructs a placeholder SUnit.
@ Cluster
Weak DAG edge linking a chain of clustered instrs.
std::vector< int > GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, bool &Success)
Returns an array of SUs that are both in the successor subtree of StartSU and in the predecessor subt...
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Scheduling unit. This is a node in the scheduling DAG.
reverse_iterator rbegin()
SmallVectorImpl< SDep >::iterator pred_iterator
bool isArtificialDep() const
virtual void unscheduledNode(SUnit *)
virtual void updateNode(const SUnit *SU)=0
This interface is used to plug different priorities computation algorithms into the list scheduler.
void dump(const TargetRegisterInfo *TRI=nullptr) const
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
bool isBarrier() const
Tests if this is an Order dependence that is marked as a barrier.
SDep()
Constructs a null SDep.
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
void clearDAG()
Clears the DAG state (between regions).
virtual void initNodes(std::vector< SUnit > &SUnits)=0
SUnit ExitSU
Special node for the region exit.
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
void AddSUnitWithoutPredecessors(const SUnit *SU)
Add a SUnit without predecessors to the end of the topological order.
SDep(SUnit *S, Kind kind, unsigned Reg)
Constructs an SDep with the specified values.
bool isMustAlias() const
Tests if this is an Order dependence that is marked as "must alias", meaning that the SUnits at eithe...