contrib/llvm/lib/Target/AMDGPU/GCNMinRegStrategy.cpp

   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       : 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   bool isScheduled(const SUnit *SU) const {
  46     assert(!SU->isBoundaryNode());
  47     return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
  48   }
  49
  50   void setIsScheduled(const SUnit *SU)  {
  51     assert(!SU->isBoundaryNode());
  52     NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max();
  53   }
  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   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
  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
  93 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
 110 int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
 111   return SU->Succs.size() - getReadySuccessors(SU);
 112 }
 113
 114 template <typename Calc>
 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
 140 GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() {
 141   do {
 142     unsigned Num = RQ.size();
 143     if (Num == 1) break;
 144
 145     DEBUG(dbgs() << "\nSelecting max priority candidates among " << Num << '\n');
 146     Num = findMax(Num, [=](const Candidate &C) { return C.Priority; });
 147     if (Num == 1) break;
 148
 149     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       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     DEBUG(dbgs() << "\nSelecting most producing candidate among "
 161                  << Num << '\n');
 162     Num = findMax(Num, [=](const Candidate &C) {
 163       auto SU = C.SU;
 164       auto Res = getReadySuccessors(SU);
 165       DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would make ready "
 166                    << Res << " successors, metric = " << Res << '\n');
 167       return Res;
 168     });
 169     if (Num == 1) break;
 170
 171     Num = Num ? Num : RQ.size();
 172     DEBUG(dbgs() << "\nCan't find best candidate, selecting in program order among "
 173                  << Num << '\n');
 174     Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
 175     assert(Num == 1);
 176   } while (false);
 177
 178   return &RQ.front();
 179 }
 180
 181 void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
 182   SmallPtrSet<const SUnit*, 32> Set;
 183   for (const auto &S : SchedSU->Succs) {
 184     if (S.getSUnit()->isBoundaryNode() || isScheduled(S.getSUnit()) ||
 185         S.getKind() != SDep::Data)
 186       continue;
 187     for (const auto &P : S.getSUnit()->Preds) {
 188       auto PSU = P.getSUnit();
 189       assert(!PSU->isBoundaryNode());
 190       if (PSU != SchedSU && !isScheduled(PSU)) {
 191         Set.insert(PSU);
 192       }
 193     }
 194   }
 195   SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
 196   while (!Worklist.empty()) {
 197     auto SU = Worklist.pop_back_val();
 198     assert(!SU->isBoundaryNode());
 199     for (const auto &P : SU->Preds) {
 200       if (!P.getSUnit()->isBoundaryNode() && !isScheduled(P.getSUnit()) &&
 201           Set.insert(P.getSUnit()).second)
 202         Worklist.push_back(P.getSUnit());
 203     }
 204   }
 205   DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNum
 206                << ")'s non-ready successors of " << Priority
 207                << " priority in ready queue: ");
 208   const auto SetEnd = Set.end();
 209   for (auto &C : RQ) {
 210     if (Set.find(C.SU) != SetEnd) {
 211       C.Priority = Priority;
 212       DEBUG(dbgs() << " SU(" << C.SU->NodeNum << ')');
 213     }
 214   }
 215   DEBUG(dbgs() << '\n');
 216 }
 217
 218 void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) {
 219   for (const auto &S : SU->Succs) {
 220     auto SuccSU = S.getSUnit();
 221     if (S.isWeak())
 222       continue;
 223     assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
 224     if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0)
 225       RQ.push_front(*new (Alloc.Allocate()) Candidate(SuccSU, Priority));
 226   }
 227 }
 228
 229 std::vector<const SUnit*>
 230 GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
 231                              const ScheduleDAG &DAG) {
 232   const auto &SUnits = DAG.SUnits;
 233   std::vector<const SUnit*> Schedule;
 234   Schedule.reserve(SUnits.size());
 235
 236   initNumPreds(SUnits);
 237
 238   int StepNo = 0;
 239
 240   for (auto SU : TopRoots) {
 241     RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
 242   }
 243   releaseSuccessors(&DAG.EntrySU, StepNo);
 244
 245   while (!RQ.empty()) {
 246     DEBUG(
 247       dbgs() << "\n=== Picking candidate, Step = " << StepNo << "\n"
 248                 "Ready queue:";
 249       for (auto &C : RQ)
 250         dbgs() << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';
 251       dbgs() << '\n';
 252     );
 253
 254     auto C = pickCandidate();
 255     assert(C);
 256     RQ.remove(*C);
 257     auto SU = C->SU;
 258     DEBUG(dbgs() << "Selected "; SU->dump(&DAG));
 259
 260     releaseSuccessors(SU, StepNo);
 261     Schedule.push_back(SU);
 262     setIsScheduled(SU);
 263
 264     if (getReadySuccessors(SU) == 0)
 265       bumpPredsPriority(SU, StepNo);
 266
 267     ++StepNo;
 268   }
 269   assert(SUnits.size() == Schedule.size());
 270
 271   return Schedule;
 272 }
 273
 274 namespace llvm {
 275
 276 std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
 277                                              const ScheduleDAG &DAG) {
 278   GCNMinRegScheduler S;
 279   return S.schedule(TopRoots, DAG);
 280 }
 281
 282 } // end namespace llvm