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