Line data Source code
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 3924 : : 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 0 : bool isScheduled(const SUnit *SU) const {
46 : assert(!SU->isBoundaryNode());
47 246990 : return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
48 : }
49 :
50 0 : void setIsScheduled(const SUnit *SU) {
51 : assert(!SU->isBoundaryNode());
52 3940 : NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max();
53 0 : }
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 0 : unsigned decNumPreds(const SUnit *SU) {
62 : assert(!SU->isBoundaryNode());
63 : assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
64 14634 : 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 6 : void GCNMinRegScheduler::initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits) {
88 12 : NumPreds.resize(SUnits.size());
89 3952 : for (unsigned I = 0; I < SUnits.size(); ++I)
90 3940 : NumPreds[I] = SUnits[I].NumPredsLeft;
91 6 : }
92 :
93 22354 : int GCNMinRegScheduler::getReadySuccessors(const SUnit *SU) const {
94 : unsigned NumSchedSuccs = 0;
95 212450 : for (auto SDep : SU->Succs) {
96 : bool wouldBeScheduled = true;
97 264150 : for (auto PDep : SDep.getSUnit()->Preds) {
98 : auto PSU = PDep.getSUnit();
99 : assert(!PSU->isBoundaryNode());
100 249182 : if (PSU != SU && !isScheduled(PSU)) {
101 : wouldBeScheduled = false;
102 : break;
103 : }
104 : }
105 365224 : NumSchedSuccs += wouldBeScheduled ? 1 : 0;
106 : }
107 22354 : return NumSchedSuccs;
108 : }
109 :
110 : int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
111 24884 : return SU->Succs.size() - getReadySuccessors(SU);
112 : }
113 :
114 : template <typename Calc>
115 780 : 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 21164 : for (auto I = RQ.begin(); Num; --Num) {
123 20384 : T Cur = C(*I);
124 20384 : if (Cur >= Max) {
125 17128 : if (Cur > Max) {
126 : Max = Cur;
127 : NumMax = 1;
128 : } else
129 16126 : ++NumMax;
130 : auto &Cand = *I++;
131 : RQ.remove(Cand);
132 : RQ.push_front(Cand);
133 17128 : continue;
134 : }
135 : ++I;
136 : }
137 780 : return NumMax;
138 : }
139 0 :
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 0 : << '\n');
147 0 : Num = findMax(Num, [=](const Candidate &C) { return C.Priority; });
148 0 : if (Num == 1) break;
149 0 :
150 : LLVM_DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "
151 : << Num << '\n');
152 : Num = findMax(Num, [=](const Candidate &C) {
153 0 : 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 0 : return -Res;
158 : });
159 : if (Num == 1) break;
160 :
161 0 : LLVM_DEBUG(dbgs() << "\nSelecting most producing candidate among " << Num
162 : << '\n');
163 308 : 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 8250 : if (Num == 1) break;
171 7942 :
172 7942 : Num = Num ? Num : RQ.size();
173 7942 : LLVM_DEBUG(
174 : dbgs()
175 : << "\nCan't find best candidate, selecting in program order among "
176 : << Num << '\n');
177 7634 : Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
178 : assert(Num == 1);
179 : } while (false);
180 :
181 7942 : return &RQ.front();
182 : }
183 :
184 : void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
185 308 : SmallPtrSet<const SUnit*, 32> Set;
186 : for (const auto &S : SchedSU->Succs) {
187 472 : 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 12914 : Set.insert(PSU);
195 12442 : }
196 12442 : }
197 9186 : }
198 : SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
199 : while (!Worklist.empty()) {
200 : auto SU = Worklist.pop_back_val();
201 8492 : 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 9186 : Worklist.push_back(P.getSUnit());
206 : }
207 : }
208 : LLVM_DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNum
209 472 : << ")'s non-ready successors of " << Priority
210 : << " priority in ready queue: ");
211 0 : 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 0 : LLVM_DEBUG(dbgs() << '\n');
219 0 : }
220 0 :
221 0 : 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 0 : 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 0 : }
230 : }
231 :
232 : std::vector<const SUnit*>
233 0 : GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
234 : const ScheduleDAG &DAG) {
235 : const auto &SUnits = DAG.SUnits;
236 1970 : std::vector<const SUnit*> Schedule;
237 : Schedule.reserve(SUnits.size());
238 1970 :
239 1970 : initNumPreds(SUnits);
240 :
241 : int StepNo = 0;
242 :
243 1772 : for (auto SU : TopRoots) {
244 1772 : RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
245 : }
246 : releaseSuccessors(&DAG.EntrySU, StepNo);
247 :
248 472 : while (!RQ.empty()) {
249 : LLVM_DEBUG(dbgs() << "\n=== Picking candidate, Step = " << StepNo
250 : << "\n"
251 : "Ready queue:";
252 : for (auto &C
253 12442 : : RQ) dbgs()
254 : << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';
255 472 : dbgs() << '\n';);
256 :
257 : auto C = pickCandidate();
258 : assert(C);
259 308 : RQ.remove(*C);
260 : auto SU = C->SU;
261 7942 : LLVM_DEBUG(dbgs() << "Selected "; DAG.dumpNode(*SU));
262 :
263 : releaseSuccessors(SU, StepNo);
264 : Schedule.push_back(SU);
265 : setIsScheduled(SU);
266 308 :
267 : if (getReadySuccessors(SU) == 0)
268 308 : bumpPredsPriority(SU, StepNo);
269 :
270 : ++StepNo;
271 : }
272 : assert(SUnits.size() == Schedule.size());
273 308 :
274 : return Schedule;
275 : }
276 :
277 1970 : namespace llvm {
278 :
279 : std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
280 656 : const ScheduleDAG &DAG) {
281 : GCNMinRegScheduler S;
282 7960 : return S.schedule(TopRoots, DAG);
283 7304 : }
284 :
285 : } // end namespace llvm
|
