1 //===- GCNMinRegStrategy.cpp ----------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/ADT/SmallPtrSet.h"
12 #include "llvm/ADT/SmallVector.h"
13 #include "llvm/ADT/ilist_node.h"
14 #include "llvm/ADT/simple_ilist.h"
15 #include "llvm/CodeGen/ScheduleDAG.h"
16 #include "llvm/Support/Allocator.h"
17 #include "llvm/Support/Debug.h"
18 #include "llvm/Support/raw_ostream.h"
19 #include <cassert>
20 #include <cstdint>
21 #include <limits>
22 #include <vector>
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "machine-scheduler"
27 
28 namespace {
29 
30 class GCNMinRegScheduler {
31   struct Candidate : ilist_node<Candidate> {
32     const SUnit *SU;
33     int Priority;
34 
35     Candidate(const SUnit *SU_, int Priority_ = 0)
36       : SU(SU_), Priority(Priority_) {}
37   };
38 
39   SpecificBumpPtrAllocator<Candidate> Alloc;
40   using Queue = simple_ilist<Candidate>;
41   Queue RQ; // Ready queue
42 
43   std::vector<unsigned> NumPreds;
44 
45   bool isScheduled(const SUnit *SU) const {
46     assert(!SU->isBoundaryNode());
47     return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
48   }
49 
50   void setIsScheduled(const SUnit *SU)  {
51     assert(!SU->isBoundaryNode());
52     NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max();
53   }
54 
55   unsigned getNumPreds(const SUnit *SU) const {
56     assert(!SU->isBoundaryNode());
57     assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
58     return NumPreds[SU->NodeNum];
59   }
60 
61   unsigned decNumPreds(const SUnit *SU) {
62     assert(!SU->isBoundaryNode());
63     assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
64     return --NumPreds[SU->NodeNum];
65   }
66 
67   void initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits);
68 
69   int getReadySuccessors(const SUnit *SU) const;
70   int getNotReadySuccessors(const SUnit *SU) const;
71 
72   template <typename Calc>
73   unsigned findMax(unsigned Num, Calc C);
74 
75   Candidate* pickCandidate();
76 
77   void bumpPredsPriority(const SUnit *SchedSU, int Priority);
78   void releaseSuccessors(const SUnit* SU, int Priority);
79 
80 public:
81   std::vector<const SUnit*> schedule(ArrayRef<const SUnit*> TopRoots,
82                                      const ScheduleDAG &DAG);
83 };
84 
85 } // end anonymous namespace
86 
87 void GCNMinRegScheduler::initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits) {
88   NumPreds.resize(SUnits.size());
89   for (unsigned I = 0; I < SUnits.size(); ++I)
90     NumPreds[I] = SUnits[I].NumPredsLeft;
91 }
92 
93 int GCNMinRegScheduler::getReadySuccessors(const SUnit *SU) const {
94   unsigned NumSchedSuccs = 0;
95   for (auto SDep : SU->Succs) {
96     bool wouldBeScheduled = true;
97     for (auto PDep : SDep.getSUnit()->Preds) {
98       auto PSU = PDep.getSUnit();
99       assert(!PSU->isBoundaryNode());
100       if (PSU != SU && !isScheduled(PSU)) {
101         wouldBeScheduled = false;
102         break;
103       }
104     }
105     NumSchedSuccs += wouldBeScheduled ? 1 : 0;
106   }
107   return NumSchedSuccs;
108 }
109 
110 int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
111   return SU->Succs.size() - getReadySuccessors(SU);
112 }
113 
114 template <typename Calc>
115 unsigned GCNMinRegScheduler::findMax(unsigned Num, Calc C) {
116   assert(!RQ.empty() && Num <= RQ.size());
117 
118   using T = decltype(C(*RQ.begin())) ;
119 
120   T Max = std::numeric_limits<T>::min();
121   unsigned NumMax = 0;
122   for (auto I = RQ.begin(); Num; --Num) {
123     T Cur = C(*I);
124     if (Cur >= Max) {
125       if (Cur > Max) {
126         Max = Cur;
127         NumMax = 1;
128       } else
129         ++NumMax;
130       auto &Cand = *I++;
131       RQ.remove(Cand);
132       RQ.push_front(Cand);
133       continue;
134     }
135     ++I;
136   }
137   return NumMax;
138 }
139 
140 GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() {
141   do {
142     unsigned Num = RQ.size();
143     if (Num == 1) break;
144 
145     LLVM_DEBUG(dbgs() << "\nSelecting max priority candidates among " << Num
146                       << '\n');
147     Num = findMax(Num, [=](const Candidate &C) { return C.Priority; });
148     if (Num == 1) break;
149 
150     LLVM_DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "
151                       << Num << '\n');
152     Num = findMax(Num, [=](const Candidate &C) {
153       auto SU = C.SU;
154       int Res = getNotReadySuccessors(SU);
155       LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would left non-ready "
156                         << Res << " successors, metric = " << -Res << '\n');
157       return -Res;
158     });
159     if (Num == 1) break;
160 
161     LLVM_DEBUG(dbgs() << "\nSelecting most producing candidate among " << Num
162                       << '\n');
163     Num = findMax(Num, [=](const Candidate &C) {
164       auto SU = C.SU;
165       auto Res = getReadySuccessors(SU);
166       LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would make ready " << Res
167                         << " successors, metric = " << Res << '\n');
168       return Res;
169     });
170     if (Num == 1) break;
171 
172     Num = Num ? Num : RQ.size();
173     LLVM_DEBUG(
174         dbgs()
175         << "\nCan't find best candidate, selecting in program order among "
176         << Num << '\n');
177     Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
178     assert(Num == 1);
179   } while (false);
180 
181   return &RQ.front();
182 }
183 
184 void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
185   SmallPtrSet<const SUnit*, 32> Set;
186   for (const auto &S : SchedSU->Succs) {
187     if (S.getSUnit()->isBoundaryNode() || isScheduled(S.getSUnit()) ||
188         S.getKind() != SDep::Data)
189       continue;
190     for (const auto &P : S.getSUnit()->Preds) {
191       auto PSU = P.getSUnit();
192       assert(!PSU->isBoundaryNode());
193       if (PSU != SchedSU && !isScheduled(PSU)) {
194         Set.insert(PSU);
195       }
196     }
197   }
198   SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
199   while (!Worklist.empty()) {
200     auto SU = Worklist.pop_back_val();
201     assert(!SU->isBoundaryNode());
202     for (const auto &P : SU->Preds) {
203       if (!P.getSUnit()->isBoundaryNode() && !isScheduled(P.getSUnit()) &&
204           Set.insert(P.getSUnit()).second)
205         Worklist.push_back(P.getSUnit());
206     }
207   }
208   LLVM_DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNum
209                     << ")'s non-ready successors of " << Priority
210                     << " priority in ready queue: ");
211   const auto SetEnd = Set.end();
212   for (auto &C : RQ) {
213     if (Set.find(C.SU) != SetEnd) {
214       C.Priority = Priority;
215       LLVM_DEBUG(dbgs() << " SU(" << C.SU->NodeNum << ')');
216     }
217   }
218   LLVM_DEBUG(dbgs() << '\n');
219 }
220 
221 void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) {
222   for (const auto &S : SU->Succs) {
223     auto SuccSU = S.getSUnit();
224     if (S.isWeak())
225       continue;
226     assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
227     if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0)
228       RQ.push_front(*new (Alloc.Allocate()) Candidate(SuccSU, Priority));
229   }
230 }
231 
232 std::vector<const SUnit*>
233 GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
234                              const ScheduleDAG &DAG) {
235   const auto &SUnits = DAG.SUnits;
236   std::vector<const SUnit*> Schedule;
237   Schedule.reserve(SUnits.size());
238 
239   initNumPreds(SUnits);
240 
241   int StepNo = 0;
242 
243   for (auto SU : TopRoots) {
244     RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
245   }
246   releaseSuccessors(&DAG.EntrySU, StepNo);
247 
248   while (!RQ.empty()) {
249     LLVM_DEBUG(dbgs() << "\n=== Picking candidate, Step = " << StepNo
250                       << "\n"
251                          "Ready queue:";
252                for (auto &C
253                     : RQ) dbgs()
254                << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';
255                dbgs() << '\n';);
256 
257     auto C = pickCandidate();
258     assert(C);
259     RQ.remove(*C);
260     auto SU = C->SU;
261     LLVM_DEBUG(dbgs() << "Selected "; DAG.dumpNode(*SU));
262 
263     releaseSuccessors(SU, StepNo);
264     Schedule.push_back(SU);
265     setIsScheduled(SU);
266 
267     if (getReadySuccessors(SU) == 0)
268       bumpPredsPriority(SU, StepNo);
269 
270     ++StepNo;
271   }
272   assert(SUnits.size() == Schedule.size());
273 
274   return Schedule;
275 }
276 
277 namespace llvm {
278 
279 std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
280                                              const ScheduleDAG &DAG) {
281   GCNMinRegScheduler S;
282   return S.schedule(TopRoots, DAG);
283 }
284 
285 } // end namespace llvm
286