17#define DEBUG_TYPE "machine-scheduler"
21class GCNILPScheduler {
33 unsigned CurQueueId = 0;
35 std::vector<unsigned> SUNumbers;
38 unsigned CurCycle = 0;
40 unsigned getNodePriority(
const SUnit *SU)
const;
43 Candidate* pickCandidate();
45 void releasePending();
46 void advanceToCycle(
unsigned NextCycle);
47 void releasePredecessors(
const SUnit* SU);
59 unsigned &SethiUllmanNumber = SUNumbers[SU->
NodeNum];
60 if (SethiUllmanNumber != 0)
61 return SethiUllmanNumber;
65 if (Pred.
isCtrl())
continue;
68 if (PredSethiUllman > SethiUllmanNumber) {
69 SethiUllmanNumber = PredSethiUllman;
72 else if (PredSethiUllman == SethiUllmanNumber)
76 SethiUllmanNumber += Extra;
78 if (SethiUllmanNumber == 0)
79 SethiUllmanNumber = 1;
81 return SethiUllmanNumber;
86unsigned GCNILPScheduler::getNodePriority(
const SUnit *SU)
const {
107 unsigned MaxHeight = 0;
109 if (Succ.
isCtrl())
continue;
113 if (Height > MaxHeight)
122 unsigned Scratches = 0;
124 if (Pred.
isCtrl())
continue;
145 if (LHeight != RHeight)
146 return LHeight > RHeight ? 1 : -1;
150 if (LDepth != RDepth) {
152 <<
") depth " << LDepth <<
" vs SU (" << right->
NodeNum
153 <<
") depth " << RDepth <<
"\n");
154 return LDepth < RDepth ? 1 : -1;
162const SUnit *GCNILPScheduler::pickBest(
const SUnit *left,
const SUnit *right)
173 <<
"): " << right->
getDepth() <<
"\n");
186 unsigned LPriority = getNodePriority(left);
187 unsigned RPriority = getNodePriority(right);
189 if (LPriority != RPriority)
190 return LPriority > RPriority ? right : left;
212 return LDist < RDist ? right : left;
217 if (LScratch != RScratch)
218 return LScratch > RScratch ? right : left;
224 return result > 0 ? right : left;
236 "NodeQueueId cannot be zero");
240GCNILPScheduler::Candidate* GCNILPScheduler::pickCandidate() {
241 if (AvailQueue.empty())
243 auto Best = AvailQueue.begin();
244 for (
auto I = std::next(AvailQueue.begin()),
E = AvailQueue.end();
I !=
E; ++
I) {
245 auto NewBestSU = pickBest(Best->SU,
I->SU);
246 if (NewBestSU != Best->SU) {
254void GCNILPScheduler::releasePending() {
257 for(
auto I = PendingQueue.begin(),
E = PendingQueue.end();
I !=
E;) {
259 if (
C.SU->getHeight() <= CurCycle) {
260 PendingQueue.remove(
C);
261 AvailQueue.push_back(
C);
262 C.SU->NodeQueueId = CurQueueId++;
268void GCNILPScheduler::advanceToCycle(
unsigned NextCycle) {
269 if (NextCycle <= CurCycle)
271 CurCycle = NextCycle;
275void GCNILPScheduler::releasePredecessors(
const SUnit* SU) {
276 for (
const auto &PredEdge : SU->
Preds) {
277 auto PredSU = PredEdge.getSUnit();
278 if (PredEdge.isWeak())
280 assert(PredSU->isBoundaryNode() || PredSU->NumSuccsLeft > 0);
282 PredSU->setHeightToAtLeast(SU->
getHeight() + PredEdge.getLatency());
284 if (!PredSU->isBoundaryNode() && --PredSU->NumSuccsLeft == 0)
285 PendingQueue.push_front(*
new (Alloc.
Allocate()) Candidate(PredSU));
289std::vector<const SUnit*>
292 auto &SUnits =
const_cast<ScheduleDAG&
>(DAG).SUnits;
294 std::vector<SUnit> SUSavedCopy;
295 SUSavedCopy.resize(SUnits.size());
299 for (
const SUnit &SU : SUnits)
302 SUNumbers.assign(SUnits.size(), 0);
303 for (
const SUnit &SU : SUnits)
306 for (
const auto *SU : BotRoots) {
307 AvailQueue.push_back(
310 releasePredecessors(&DAG.
ExitSU);
312 std::vector<const SUnit*> Schedule;
313 Schedule.reserve(SUnits.size());
315 if (AvailQueue.empty() && !PendingQueue.empty()) {
316 auto EarliestSU = std::min_element(
317 PendingQueue.begin(), PendingQueue.end(),
318 [=](
const Candidate& C1,
const Candidate& C2) {
319 return C1.SU->getHeight() < C2.SU->getHeight();
321 advanceToCycle(std::max(CurCycle + 1, EarliestSU->getHeight()));
323 if (AvailQueue.empty())
330 <<
' ' <<
C.SU->NodeNum;
333 auto C = pickCandidate();
335 AvailQueue.remove(*
C);
341 releasePredecessors(SU);
342 Schedule.push_back(SU);
345 assert(SUnits.size() == Schedule.size());
347 std::reverse(Schedule.begin(), Schedule.end());
350 for (
auto &SU : SUnits)
360 return S.schedule(BotRoots, DAG);
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static int BUCompareLatency(const SUnit *left, const SUnit *right)
static unsigned closestSucc(const SUnit *SU)
closestSucc - Returns the scheduled cycle of the successor which is closest to the current cycle.
static unsigned calcMaxScratches(const SUnit *SU)
calcMaxScratches - Returns an cost estimate of the worse case requirement for scratch registers,...
static unsigned CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector< unsigned > &SUNumbers)
CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static cl::opt< bool > DisableSchedCycles("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling"))
static cl::opt< bool > DisableSchedCriticalPath("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp"))
static cl::opt< int > MaxReorderWindow("max-sched-reorder", cl::Hidden, cl::init(6), cl::desc("Number of instructions to allow ahead of the critical path " "in sched=list-ilp"))
static cl::opt< bool > DisableSchedHeight("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp"))
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Scheduling unit. This is a node in the scheduling DAG.
unsigned NodeQueueId
Queue id of node.
unsigned NodeNum
Entry # of node in the node vector.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
unsigned short Latency
Node latency.
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...
bool isScheduled
True once scheduled.
SmallVector< SDep, 4 > Succs
All sunit successors.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
virtual void dumpNode(const SUnit &SU) const =0
SUnit ExitSU
Special node for the region exit.
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
A simple intrusive list implementation.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
std::vector< const SUnit * > makeGCNILPScheduler(ArrayRef< const SUnit * > BotRoots, const ScheduleDAG &DAG)