1 //===---------------------------- GCNILPSched.cpp - -----------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
17 #define DEBUG_TYPE "machine-scheduler"
37   /// CurCycle - The current scheduler state corresponds to this cycle.
42   const SUnit *pickBest(const SUnit *left, const SUnit *right);
55 /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
59   unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];  in CalcNodeSethiUllmanNumber()
64   for (const SDep &Pred : SU->Preds) {  in CalcNodeSethiUllmanNumber()
84 // Lower priority means schedule further down. For bottom-up scheduling, lower
87   assert(SU->NodeNum < SUNumbers.size());  in getNodePriority()
88   if (SU->NumSuccs == 0 && SU->NumPreds != 0)  in getNodePriority()
96   if (SU->NumPreds == 0 && SU->NumSuccs != 0)  in getNodePriority()
101   return SUNumbers[SU->NodeNum];  in getNodePriority()
104 /// closestSucc - Returns the scheduled cycle of the successor which is
108   for (const SDep &Succ : SU->Succs) {  in closestSucc()
110     unsigned Height = Succ.getSUnit()->getHeight();  in closestSucc()
119 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
123   for (const SDep &Pred : SU->Preds) {  in calcMaxScratches()
130 // Return -1 if left has higher priority, 1 if right has higher priority.
131 // Return 0 if latency-based priority is equivalent.
132 static int BUCompareLatency(const SUnit *left, const SUnit *right) {  in BUCompareLatency()  argument
135   int LHeight = (int)left->getHeight();  in BUCompareLatency()
136   int RHeight = (int)right->getHeight();  in BUCompareLatency()
146     return LHeight > RHeight ? 1 : -1;  in BUCompareLatency()
148   int LDepth = left->getDepth();  in BUCompareLatency()
149   int RDepth = right->getDepth();  in BUCompareLatency()
151     LLVM_DEBUG(dbgs() << "  Comparing latency of SU (" << left->NodeNum  in BUCompareLatency()
152                       << ") depth " << LDepth << " vs SU (" << right->NodeNum  in BUCompareLatency()
154     return LDepth < RDepth ? 1 : -1;  in BUCompareLatency()
156   if (left->Latency != right->Latency)  in BUCompareLatency()
157     return left->Latency > right->Latency ? 1 : -1;  in BUCompareLatency()
162 const SUnit *GCNILPScheduler::pickBest(const SUnit *left, const SUnit *right)  in pickBest()  argument
169     int spread = (int)left->getDepth() - (int)right->getDepth();  in pickBest()
171       LLVM_DEBUG(dbgs() << "Depth of SU(" << left->NodeNum << "): "  in pickBest()
172                         << left->getDepth() << " != SU(" << right->NodeNum  in pickBest()
173                         << "): " << right->getDepth() << "\n");  in pickBest()
174       return left->getDepth() < right->getDepth() ? right : left;  in pickBest()
179   if (!DisableSchedHeight && left->getHeight() != right->getHeight()) {  in pickBest()
180     int spread = (int)left->getHeight() - (int)right->getHeight();  in pickBest()
182       return left->getHeight() > right->getHeight() ? right : left;  in pickBest()
185   // Prioritize by Sethi-Ulmann number and push CopyToReg nodes down.  in pickBest()
186   unsigned LPriority = getNodePriority(left);  in pickBest()
190     return LPriority > RPriority ? right : left;  in pickBest()
192   // Try schedule def + use closer when Sethi-Ullman numbers are the same.  in pickBest()
209   unsigned LDist = closestSucc(left);  in pickBest()
212     return LDist < RDist ? right : left;  in pickBest()
215   unsigned LScratch = calcMaxScratches(left);  in pickBest()
218     return LScratch > RScratch ? right : left;  in pickBest()
222     int result = BUCompareLatency(left, right);  in pickBest()
224       return result > 0 ? right : left;  in pickBest()
225     return left;  in pickBest()
227   if (left->getHeight() != right->getHeight())  in pickBest()
228     return (left->getHeight() > right->getHeight()) ? right : left;  in pickBest()
230   if (left->getDepth() != right->getDepth())  in pickBest()
231     return (left->getDepth() < right->getDepth()) ? right : left;  in pickBest()
233   assert(left->NodeQueueId && right->NodeQueueId &&  in pickBest()
235   return (left->NodeQueueId > right->NodeQueueId) ? right : left;  in pickBest()
243     auto NewBestSU = pickBest(Best->SU, I->SU);  in pickCandidate()
244     if (NewBestSU != Best->SU) {  in pickCandidate()
245       assert(NewBestSU == I->SU);  in pickCandidate()
257     if (C.SU->getHeight() <= CurCycle) {  in releasePending()
260       C.SU->NodeQueueId = CurQueueId++;  in releasePending()
274   for (const auto &PredEdge : SU->Preds) {  in releasePredecessors()
278     assert(PredSU->isBoundaryNode() || PredSU->NumSuccsLeft > 0);  in releasePredecessors()
280     PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge.getLatency());  in releasePredecessors()
282     if (!PredSU->isBoundaryNode() && --PredSU->NumSuccsLeft == 0)  in releasePredecessors()
317             return C1.SU->getHeight() < C2.SU->getHeight();  in schedule()
318           })->SU;  in schedule()
319       advanceToCycle(std::max(CurCycle + 1, EarliestSU->getHeight()));  in schedule()
328                << ' ' << C.SU->NodeNum;  in schedule()
334     auto SU = C->SU;  in schedule()
337     advanceToCycle(SU->getHeight());  in schedule()
341     SU->isScheduled = true;  in schedule()