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