Go to the documentation of this file.
37 #define DEBUG_TYPE "scheduler"
41 cl::desc(
"Disable use of DFA during scheduling"));
45 cl::desc(
"Track reg pressure and switch priority to in-depth"));
48 : Picker(
this), InstrItins(IS->MF->getSubtarget().getInstrItineraryData()) {
56 assert(ResourcesModel &&
"Unimplemented CreateTargetScheduleState.");
59 RegLimit.resize(NumRC);
60 RegPressure.resize(NumRC);
61 std::fill(RegLimit.begin(), RegLimit.end(), 0);
62 std::fill(RegPressure.begin(), RegPressure.end(), 0);
66 ParallelLiveRanges = 0;
67 HorizontalVerticalBalance = 0;
71 ResourcePriorityQueue::numberRCValPredInSU(
SUnit *SU,
unsigned RCId) {
72 unsigned NumberDeps = 0;
108 unsigned ResourcePriorityQueue::numberRCValSuccInSU(
SUnit *SU,
110 unsigned NumberDeps = 0;
135 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
147 unsigned NumberDeps = 0;
156 unsigned NumberDeps = 0;
169 NumNodesSolelyBlocking.resize(SUnits->size(), 0);
171 for (
unsigned i = 0,
e = SUnits->size();
i !=
e; ++
i) {
172 SUnit *SU = &(*SUnits)[
i];
190 unsigned LHSNum = LHS->
NodeNum;
191 unsigned RHSNum = RHS->
NodeNum;
196 if (LHSLatency < RHSLatency)
return true;
197 if (LHSLatency > RHSLatency)
return false;
203 if (LHSBlocked < RHSBlocked)
return true;
204 if (LHSBlocked > RHSBlocked)
return false;
208 return LHSNum < RHSNum;
214 SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(
SUnit *SU) {
215 SUnit *OnlyAvailablePred =
nullptr;
221 if (OnlyAvailablePred && OnlyAvailablePred != &PredSU)
223 OnlyAvailablePred = &PredSU;
226 return OnlyAvailablePred;
232 unsigned NumNodesBlocking = 0;
234 if (getSingleUnscheduledPred(Succ.
getSUnit()) == SU)
237 NumNodesSolelyBlocking[SU->
NodeNum] = NumNodesBlocking;
257 if (!ResourcesModel->canReserveResources(&TII->
get(
261 case TargetOpcode::EXTRACT_SUBREG:
262 case TargetOpcode::INSERT_SUBREG:
263 case TargetOpcode::SUBREG_TO_REG:
264 case TargetOpcode::REG_SEQUENCE:
265 case TargetOpcode::IMPLICIT_DEF:
271 for (
unsigned i = 0,
e = Packet.size();
i !=
e; ++
i)
272 for (
const SDep &Succ : Packet[
i]->Succs) {
290 ResourcesModel->clearResources();
297 ResourcesModel->reserveResources(&TII->
get(
300 case TargetOpcode::EXTRACT_SUBREG:
301 case TargetOpcode::INSERT_SUBREG:
302 case TargetOpcode::SUBREG_TO_REG:
303 case TargetOpcode::REG_SEQUENCE:
304 case TargetOpcode::IMPLICIT_DEF:
307 Packet.push_back(SU);
311 ResourcesModel->clearResources();
318 ResourcesModel->clearResources();
335 RegBalance += numberRCValSuccInSU(SU, RCId);
340 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
341 if (isa<ConstantSDNode>(
Op.getNode()))
346 RegBalance -= numberRCValPredInSU(SU, RCId);
369 if ((RegPressure[RC->getID()] +
371 (RegPressure[RC->getID()] +
439 if (
N->isMachineOpcode()) {
445 switch (
N->getOpcode()) {
468 ResourcesModel->clearResources();
484 RegPressure[RC->
getID()] += numberRCValSuccInSU(SU, RC->
getID());
490 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
495 if (RegPressure[RC->
getID()] >
496 (numberRCValPredInSU(SU, RC->
getID())))
497 RegPressure[RC->
getID()] -= numberRCValPredInSU(SU, RC->
getID());
498 else RegPressure[RC->
getID()] = 0;
515 unsigned NumberNonControlDeps = 0;
518 adjustPriorityOfUnscheduledPreds(Succ.
getSUnit());
520 NumberNonControlDeps++;
523 if (!NumberNonControlDeps) {
524 if (ParallelLiveRanges >= SU->
NumPreds)
527 ParallelLiveRanges = 0;
539 unsigned NodeNumDefs = 0;
541 if (
N->isMachineOpcode()) {
544 if (
N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {
551 switch(
N->getOpcode()) {
571 void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(
SUnit *SU) {
574 SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
575 if (!OnlyAvailablePred || !OnlyAvailablePred->
isAvailable)
580 remove(OnlyAvailablePred);
584 push(OnlyAvailablePred);
594 std::vector<SUnit *>::iterator Best = Queue.begin();
597 for (
auto I = std::next(Queue.begin()),
E = Queue.end();
I !=
E; ++
I) {
607 for (
auto I = std::next(Queue.begin()),
E = Queue.end();
I !=
E; ++
I)
608 if (Picker(*Best, *
I))
613 if (Best != std::prev(Queue.end()))
623 assert(!Queue.empty() &&
"Queue is empty!");
624 std::vector<SUnit *>::iterator
I =
find(Queue, SU);
625 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.
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
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.