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     DEBUG(dbgs() << "\nSelecting max priority candidates among " << Num << '\n');
146     Num = findMax(Num, [=](const Candidate &C) { return C.Priority; });
147     if (Num == 1) break;
148 
149     DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "
150                  << Num << '\n');
151     Num = findMax(Num, [=](const Candidate &C) {
152       auto SU = C.SU;
153       int Res = getNotReadySuccessors(SU);
154       DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would left non-ready "
155                    << Res << " successors, metric = " << -Res << '\n');
156       return -Res;
157     });
158     if (Num == 1) break;
159 
160     DEBUG(dbgs() << "\nSelecting most producing candidate among "
161                  << Num << '\n');
162     Num = findMax(Num, [=](const Candidate &C) {
163       auto SU = C.SU;
164       auto Res = getReadySuccessors(SU);
165       DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would make ready "
166                    << Res << " successors, metric = " << Res << '\n');
167       return Res;
168     });
169     if (Num == 1) break;
170 
171     Num = Num ? Num : RQ.size();
172     DEBUG(dbgs() << "\nCan't find best candidate, selecting in program order among "
173                  << Num << '\n');
174     Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
175     assert(Num == 1);
176   } while (false);
177 
178   return &RQ.front();
179 }
180 
181 void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
182   SmallPtrSet<const SUnit*, 32> Set;
183   for (const auto &S : SchedSU->Succs) {
184     if (S.getSUnit()->isBoundaryNode() || isScheduled(S.getSUnit()) ||
185         S.getKind() != SDep::Data)
186       continue;
187     for (const auto &P : S.getSUnit()->Preds) {
188       auto PSU = P.getSUnit();
189       assert(!PSU->isBoundaryNode());
190       if (PSU != SchedSU && !isScheduled(PSU)) {
191         Set.insert(PSU);
192       }
193     }
194   }
195   SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
196   while (!Worklist.empty()) {
197     auto SU = Worklist.pop_back_val();
198     assert(!SU->isBoundaryNode());
199     for (const auto &P : SU->Preds) {
200       if (!P.getSUnit()->isBoundaryNode() && !isScheduled(P.getSUnit()) &&
201           Set.insert(P.getSUnit()).second)
202         Worklist.push_back(P.getSUnit());
203     }
204   }
205   DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNum
206                << ")'s non-ready successors of " << Priority
207                << " priority in ready queue: ");
208   const auto SetEnd = Set.end();
209   for (auto &C : RQ) {
210     if (Set.find(C.SU) != SetEnd) {
211       C.Priority = Priority;
212       DEBUG(dbgs() << " SU(" << C.SU->NodeNum << ')');
213     }
214   }
215   DEBUG(dbgs() << '\n');
216 }
217 
218 void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) {
219   for (const auto &S : SU->Succs) {
220     auto SuccSU = S.getSUnit();
221     if (S.isWeak())
222       continue;
223     assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
224     if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0)
225       RQ.push_front(*new (Alloc.Allocate()) Candidate(SuccSU, Priority));
226   }
227 }
228 
229 std::vector<const SUnit*>
230 GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
231                              const ScheduleDAG &DAG) {
232   const auto &SUnits = DAG.SUnits;
233   std::vector<const SUnit*> Schedule;
234   Schedule.reserve(SUnits.size());
235 
236   initNumPreds(SUnits);
237 
238   int StepNo = 0;
239 
240   for (auto SU : TopRoots) {
241     RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
242   }
243   releaseSuccessors(&DAG.EntrySU, StepNo);
244 
245   while (!RQ.empty()) {
246     DEBUG(
247       dbgs() << "\n=== Picking candidate, Step = " << StepNo << "\n"
248                 "Ready queue:";
249       for (auto &C : RQ)
250         dbgs() << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';
251       dbgs() << '\n';
252     );
253 
254     auto C = pickCandidate();
255     assert(C);
256     RQ.remove(*C);
257     auto SU = C->SU;
258     DEBUG(dbgs() << "Selected "; SU->dump(&DAG));
259 
260     releaseSuccessors(SU, StepNo);
261     Schedule.push_back(SU);
262     setIsScheduled(SU);
263 
264     if (getReadySuccessors(SU) == 0)
265       bumpPredsPriority(SU, StepNo);
266 
267     ++StepNo;
268   }
269   assert(SUnits.size() == Schedule.size());
270 
271   return Schedule;
272 }
273 
274 namespace llvm {
275 
276 std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
277                                              const ScheduleDAG &DAG) {
278   GCNMinRegScheduler S;
279   return S.schedule(TopRoots, DAG);
280 }
281 
282 } // end namespace llvm
283