Go to the documentation of this file.
33 #define DEBUG_TYPE "scheduler"
37 cl::desc(
"Disable use of DFA during scheduling"));
41 cl::desc(
"Track reg pressure and switch priority to in-depth"));
44 : Picker(
this), InstrItins(IS->MF->getSubtarget().getInstrItineraryData()) {
52 assert(ResourcesModel &&
"Unimplemented CreateTargetScheduleState.");
55 RegLimit.resize(NumRC);
56 RegPressure.resize(NumRC);
57 std::fill(RegLimit.begin(), RegLimit.end(), 0);
58 std::fill(RegPressure.begin(), RegPressure.end(), 0);
62 ParallelLiveRanges = 0;
63 HorizontalVerticalBalance = 0;
67 ResourcePriorityQueue::numberRCValPredInSU(
SUnit *SU,
unsigned RCId) {
68 unsigned NumberDeps = 0;
104 unsigned ResourcePriorityQueue::numberRCValSuccInSU(
SUnit *SU,
106 unsigned NumberDeps = 0;
131 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
143 unsigned NumberDeps = 0;
152 unsigned NumberDeps = 0;
165 NumNodesSolelyBlocking.resize(SUnits->size(), 0);
167 for (
SUnit &SU : *SUnits) {
179 if (
LHS->isScheduleHigh && !
RHS->isScheduleHigh)
182 if (!
LHS->isScheduleHigh &&
RHS->isScheduleHigh)
185 unsigned LHSNum =
LHS->NodeNum;
186 unsigned RHSNum =
RHS->NodeNum;
191 if (LHSLatency < RHSLatency)
return true;
192 if (LHSLatency > RHSLatency)
return false;
198 if (LHSBlocked < RHSBlocked)
return true;
199 if (LHSBlocked > RHSBlocked)
return false;
203 return LHSNum < RHSNum;
209 SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(
SUnit *SU) {
210 SUnit *OnlyAvailablePred =
nullptr;
216 if (OnlyAvailablePred && OnlyAvailablePred != &PredSU)
218 OnlyAvailablePred = &PredSU;
221 return OnlyAvailablePred;
227 unsigned NumNodesBlocking = 0;
229 if (getSingleUnscheduledPred(Succ.
getSUnit()) == SU)
232 NumNodesSolelyBlocking[SU->
NodeNum] = NumNodesBlocking;
252 if (!ResourcesModel->canReserveResources(&TII->
get(
256 case TargetOpcode::EXTRACT_SUBREG:
257 case TargetOpcode::INSERT_SUBREG:
258 case TargetOpcode::SUBREG_TO_REG:
259 case TargetOpcode::REG_SEQUENCE:
260 case TargetOpcode::IMPLICIT_DEF:
266 for (
const SUnit *
S : Packet)
267 for (
const SDep &Succ :
S->Succs) {
285 ResourcesModel->clearResources();
292 ResourcesModel->reserveResources(&TII->
get(
295 case TargetOpcode::EXTRACT_SUBREG:
296 case TargetOpcode::INSERT_SUBREG:
297 case TargetOpcode::SUBREG_TO_REG:
298 case TargetOpcode::REG_SEQUENCE:
299 case TargetOpcode::IMPLICIT_DEF:
302 Packet.push_back(SU);
306 ResourcesModel->clearResources();
313 ResourcesModel->clearResources();
330 RegBalance += numberRCValSuccInSU(SU, RCId);
335 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
336 if (isa<ConstantSDNode>(
Op.getNode()))
341 RegBalance -= numberRCValPredInSU(SU, RCId);
364 if ((RegPressure[RC->getID()] +
366 (RegPressure[RC->getID()] +
434 if (
N->isMachineOpcode()) {
440 switch (
N->getOpcode()) {
463 ResourcesModel->clearResources();
479 RegPressure[RC->
getID()] += numberRCValSuccInSU(SU, RC->
getID());
485 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
490 if (RegPressure[RC->
getID()] >
491 (numberRCValPredInSU(SU, RC->
getID())))
492 RegPressure[RC->
getID()] -= numberRCValPredInSU(SU, RC->
getID());
493 else RegPressure[RC->
getID()] = 0;
510 unsigned NumberNonControlDeps = 0;
513 adjustPriorityOfUnscheduledPreds(Succ.
getSUnit());
515 NumberNonControlDeps++;
518 if (!NumberNonControlDeps) {
519 if (ParallelLiveRanges >= SU->
NumPreds)
522 ParallelLiveRanges = 0;
534 unsigned NodeNumDefs = 0;
536 if (
N->isMachineOpcode()) {
539 if (
N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {
546 switch(
N->getOpcode()) {
566 void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(
SUnit *SU) {
569 SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
570 if (!OnlyAvailablePred || !OnlyAvailablePred->
isAvailable)
575 remove(OnlyAvailablePred);
579 push(OnlyAvailablePred);
589 std::vector<SUnit *>::iterator Best = Queue.begin();
592 for (
auto I = std::next(Queue.begin()),
E = Queue.end();
I !=
E; ++
I) {
602 for (
auto I = std::next(Queue.begin()),
E = Queue.end();
I !=
E; ++
I)
603 if (Picker(*Best, *
I))
608 if (Best != std::prev(Queue.end()))
618 assert(!Queue.empty() &&
"Queue is empty!");
619 std::vector<SUnit *>::iterator
I =
find(Queue, SU);
620 if (
I != std::prev(Queue.end()))
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
const TargetLowering * TLI
unsigned getID() const
Return the register class ID number.
This is an optimization pass for GlobalISel generic memory operations.
void initNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
unsigned getLatency(unsigned NodeNum) const
int SUSchedulingCost(SUnit *SU)
Single cost function reflecting benefit of scheduling SU in the current cycle.
static unsigned numberCtrlPredInSU(SUnit *SU)
bool isAvailable
True once available.
virtual const TargetInstrInfo * getInstrInfo() const
ResourcePriorityQueue * PQ
Represents one node in the SelectionDAG.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
static const unsigned PriorityOne
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
SUnit * pop() override
Main access point - returns next instructions to be placed in scheduling sequence.
SmallVector< SDep, 4 > Succs
All sunit successors.
@ INLINEASM
INLINEASM - Represents an inline asm block.
bool operator()(const SUnit *LHS, const SUnit *RHS) const
This heuristic is used if DFA scheduling is not desired for some VLIW platform.
static cl::opt< int > RegPressureThreshold("dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5), cl::desc("Track reg pressure and switch priority to in-depth"))
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
static const unsigned ScaleThree
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool isScheduleHigh
True if preferable to schedule high.
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
unsigned NodeNum
Entry # of node in the node vector.
Describe properties that are true of each instruction in the target description file.
bool empty() const override
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
iterator_range< regclass_iterator > regclasses() const
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
int rawRegPressureDelta(SUnit *SU, unsigned RCId)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
int regPressureDelta(SUnit *SU, bool RawPressure=false)
Estimates change in reg pressure from this SU.
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
unsigned short NumRegDefsLeft
bool isCall() const
Return true if the instruction is a call.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
static unsigned numberCtrlDepsInSU(SUnit *SU)
const SDValue & getOperand(unsigned Num) const
bool isScheduled
True once scheduled.
initializer< Ty > init(const Ty &Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
bool isResourceAvailable(SUnit *SU)
Check if scheduling of this SU is possible in the current packet.
MVT getSimpleValueType(unsigned ResNo) const
Return the type of a specified result as a simple type.
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Analysis the ScalarEvolution expression for r is this
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
ResourcePriorityQueue(SelectionDAGISel *IS)
TargetSubtargetInfo - Generic base class for all target subtargets.
static const unsigned PriorityThree
static const unsigned PriorityTwo
static const unsigned ScaleOne
void push(SUnit *U) override
unsigned getNumOperands() const
Return the number of values used by this operation.
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
unsigned getNumRegClasses() const
unsigned getNumSolelyBlockNodes(unsigned NodeNum) const
unsigned getMachineOpcode() const
This may only be called if isMachineOpcode returns true.
unsigned NodeQueueId
Queue id of node.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
void scheduledNode(SUnit *SU) override
scheduledNode - Main resource tracking point.
static cl::opt< bool > DisableDFASched("disable-dfa-sched", cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::desc("Disable use of DFA during scheduling"))
void remove(SUnit *SU) override
virtual const TargetRegisterClass * getRegClassFor(MVT VT, bool isDivergent=false) const
Return the register class that should be used for the specified value type.
static const unsigned FactorOne
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Scheduling unit. This is a node in the scheduling DAG.
void initNodes(std::vector< SUnit > &sunits) override
Initialize nodes.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
static const unsigned PriorityFour
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
static const unsigned ScaleTwo
MCSchedModel SchedModel
Basic machine properties.
virtual unsigned getRegPressureLimit(const TargetRegisterClass *RC, MachineFunction &MF) const
Return the register pressure "high water mark" for the specific register class.
@ TokenFactor
TokenFactor - This node takes multiple tokens as input and produces a single token result.
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
void reserveResources(SUnit *SU)
Keep track of available resources.