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