llvm/lib/Target/AMDGPU/GCNMinRegStrategy.cpp

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