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
Candidate__anonf32753ba0111::GCNMinRegScheduler::Candidate35 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
isScheduled(const SUnit * SU) const45 bool isScheduled(const SUnit *SU) const {
46 assert(!SU->isBoundaryNode());
47 return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
48 }
49
setIsScheduled(const SUnit * SU)50 void setIsScheduled(const SUnit *SU) {
51 assert(!SU->isBoundaryNode());
52 NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max();
53 }
54
getNumPreds(const SUnit * SU) const55 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
decNumPreds(const SUnit * SU)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
initNumPreds(const decltype(ScheduleDAG::SUnits) & SUnits)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
getReadySuccessors(const SUnit * SU) const93 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
getNotReadySuccessors(const SUnit * SU) const110 int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
111 return SU->Succs.size() - getReadySuccessors(SU);
112 }
113
114 template <typename Calc>
findMax(unsigned Num,Calc C)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
pickCandidate()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
bumpPredsPriority(const SUnit * SchedSU,int Priority)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
releaseSuccessors(const SUnit * SU,int Priority)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*>
schedule(ArrayRef<const SUnit * > TopRoots,const ScheduleDAG & DAG)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 "; SU->dump(&DAG));
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
makeMinRegSchedule(ArrayRef<const SUnit * > TopRoots,const ScheduleDAG & DAG)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