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