1 //===- GCNMinRegStrategy.cpp ----------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
10 /// This file defines and imlements the class GCNMinRegScheduler, which
11 /// implements an experimental, simple scheduler whose main goal is to learn
12 /// ways about consuming less possible registers for a region.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/ilist_node.h"
20 #include "llvm/ADT/simple_ilist.h"
21 #include "llvm/CodeGen/ScheduleDAG.h"
22 #include "llvm/Support/Allocator.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
32 #define DEBUG_TYPE "machine-scheduler"
36 class GCNMinRegScheduler {
37 struct Candidate : ilist_node<Candidate> {
41 Candidate(const SUnit *SU_, int Priority_ = 0)
42 : SU(SU_), Priority(Priority_) {}
45 SpecificBumpPtrAllocator<Candidate> Alloc;
46 using Queue = simple_ilist<Candidate>;
47 Queue RQ; // Ready queue
49 std::vector<unsigned> NumPreds;
51 bool isScheduled(const SUnit *SU) const {
52 assert(!SU->isBoundaryNode());
53 return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
56 void setIsScheduled(const SUnit *SU) {
57 assert(!SU->isBoundaryNode());
58 NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max();
61 unsigned getNumPreds(const SUnit *SU) const {
62 assert(!SU->isBoundaryNode());
63 assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
64 return NumPreds[SU->NodeNum];
67 unsigned decNumPreds(const SUnit *SU) {
68 assert(!SU->isBoundaryNode());
69 assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
70 return --NumPreds[SU->NodeNum];
73 void initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits);
75 int getReadySuccessors(const SUnit *SU) const;
76 int getNotReadySuccessors(const SUnit *SU) const;
78 template <typename Calc>
79 unsigned findMax(unsigned Num, Calc C);
81 Candidate* pickCandidate();
83 void bumpPredsPriority(const SUnit *SchedSU, int Priority);
84 void releaseSuccessors(const SUnit* SU, int Priority);
87 std::vector<const SUnit*> schedule(ArrayRef<const SUnit*> TopRoots,
88 const ScheduleDAG &DAG);
91 } // end anonymous namespace
93 void GCNMinRegScheduler::initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits) {
94 NumPreds.resize(SUnits.size());
95 for (unsigned I = 0; I < SUnits.size(); ++I)
96 NumPreds[I] = SUnits[I].NumPredsLeft;
99 int GCNMinRegScheduler::getReadySuccessors(const SUnit *SU) const {
100 unsigned NumSchedSuccs = 0;
101 for (auto SDep : SU->Succs) {
102 bool wouldBeScheduled = true;
103 for (auto PDep : SDep.getSUnit()->Preds) {
104 auto PSU = PDep.getSUnit();
105 assert(!PSU->isBoundaryNode());
106 if (PSU != SU && !isScheduled(PSU)) {
107 wouldBeScheduled = false;
111 NumSchedSuccs += wouldBeScheduled ? 1 : 0;
113 return NumSchedSuccs;
116 int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
117 return SU->Succs.size() - getReadySuccessors(SU);
120 template <typename Calc>
121 unsigned GCNMinRegScheduler::findMax(unsigned Num, Calc C) {
122 assert(!RQ.empty() && Num <= RQ.size());
124 using T = decltype(C(*RQ.begin())) ;
126 T Max = std::numeric_limits<T>::min();
128 for (auto I = RQ.begin(); Num; --Num) {
146 GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() {
148 unsigned Num = RQ.size();
151 LLVM_DEBUG(dbgs() << "\nSelecting max priority candidates among " << Num
153 Num = findMax(Num, [=](const Candidate &C) { return C.Priority; });
156 LLVM_DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "
158 Num = findMax(Num, [=](const Candidate &C) {
160 int Res = getNotReadySuccessors(SU);
161 LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would left non-ready "
162 << Res << " successors, metric = " << -Res << '\n');
167 LLVM_DEBUG(dbgs() << "\nSelecting most producing candidate among " << Num
169 Num = findMax(Num, [=](const Candidate &C) {
171 auto Res = getReadySuccessors(SU);
172 LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would make ready " << Res
173 << " successors, metric = " << Res << '\n');
178 Num = Num ? Num : RQ.size();
181 << "\nCan't find best candidate, selecting in program order among "
183 Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
190 void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
191 SmallPtrSet<const SUnit*, 32> Set;
192 for (const auto &S : SchedSU->Succs) {
193 if (S.getSUnit()->isBoundaryNode() || isScheduled(S.getSUnit()) ||
194 S.getKind() != SDep::Data)
196 for (const auto &P : S.getSUnit()->Preds) {
197 auto PSU = P.getSUnit();
198 assert(!PSU->isBoundaryNode());
199 if (PSU != SchedSU && !isScheduled(PSU)) {
204 SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
205 while (!Worklist.empty()) {
206 auto SU = Worklist.pop_back_val();
207 assert(!SU->isBoundaryNode());
208 for (const auto &P : SU->Preds) {
209 if (!P.getSUnit()->isBoundaryNode() && !isScheduled(P.getSUnit()) &&
210 Set.insert(P.getSUnit()).second)
211 Worklist.push_back(P.getSUnit());
214 LLVM_DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNum
215 << ")'s non-ready successors of " << Priority
216 << " priority in ready queue: ");
218 if (Set.count(C.SU)) {
219 C.Priority = Priority;
220 LLVM_DEBUG(dbgs() << " SU(" << C.SU->NodeNum << ')');
223 LLVM_DEBUG(dbgs() << '\n');
226 void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) {
227 for (const auto &S : SU->Succs) {
228 auto SuccSU = S.getSUnit();
231 assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
232 if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0)
233 RQ.push_front(*new (Alloc.Allocate()) Candidate(SuccSU, Priority));
237 std::vector<const SUnit*>
238 GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
239 const ScheduleDAG &DAG) {
240 const auto &SUnits = DAG.SUnits;
241 std::vector<const SUnit*> Schedule;
242 Schedule.reserve(SUnits.size());
244 initNumPreds(SUnits);
248 for (auto SU : TopRoots) {
249 RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
251 releaseSuccessors(&DAG.EntrySU, StepNo);
253 while (!RQ.empty()) {
254 LLVM_DEBUG(dbgs() << "\n=== Picking candidate, Step = " << StepNo
259 << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';
262 auto C = pickCandidate();
266 LLVM_DEBUG(dbgs() << "Selected "; DAG.dumpNode(*SU));
268 releaseSuccessors(SU, StepNo);
269 Schedule.push_back(SU);
272 if (getReadySuccessors(SU) == 0)
273 bumpPredsPriority(SU, StepNo);
277 assert(SUnits.size() == Schedule.size());
284 std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
285 const ScheduleDAG &DAG) {
286 GCNMinRegScheduler S;
287 return S.schedule(TopRoots, DAG);
290 } // end namespace llvm