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