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

   1 //===--------------------- GCNIterativeScheduler.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 "GCNIterativeScheduler.h"
  15 #include "GCNSchedStrategy.h"
  16 #include "SIMachineFunctionInfo.h"
  17
  18 using namespace llvm;
  19
  20 #define DEBUG_TYPE "misched"
  21
  22 namespace llvm {
  23   std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
  24     const ScheduleDAG &DAG);
  25 }
  26
  27 // shim accessors for different order containers
  28 static inline MachineInstr *getMachineInstr(MachineInstr *MI) {
  29   return MI;
  30 }
  31 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
  32   return SU->getInstr();
  33 }
  34 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
  35   return SU.getInstr();
  36 }
  37
  38 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  39 LLVM_DUMP_METHOD
  40 static void printRegion(raw_ostream &OS,
  41                         MachineBasicBlock::iterator Begin,
  42                         MachineBasicBlock::iterator End,
  43                         const LiveIntervals *LIS,
  44                         unsigned MaxInstNum =
  45                           std::numeric_limits<unsigned>::max()) {
  46   auto BB = Begin->getParent();
  47   OS << BB->getParent()->getName() << ":BB#" << BB->getNumber()
  48      << ' ' << BB->getName() << ":\n";
  49   auto I = Begin;
  50   MaxInstNum = std::max(MaxInstNum, 1u);
  51   for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
  52     if (!I->isDebugValue() && LIS)
  53       OS << LIS->getInstructionIndex(*I);
  54     OS << '\t' << *I;
  55   }
  56   if (I != End) {
  57     OS << "\t...\n";
  58     I = std::prev(End);
  59     if (!I->isDebugValue() && LIS)
  60       OS << LIS->getInstructionIndex(*I);
  61     OS << '\t' << *I;
  62   }
  63   if (End != BB->end()) { // print boundary inst if present
  64     OS << "----\n";
  65     if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
  66     OS << *End;
  67   }
  68 }
  69
  70 LLVM_DUMP_METHOD
  71 static void printLivenessInfo(raw_ostream &OS,
  72                               MachineBasicBlock::iterator Begin,
  73                               MachineBasicBlock::iterator End,
  74                               const LiveIntervals *LIS) {
  75   const auto BB = Begin->getParent();
  76   const auto &MRI = BB->getParent()->getRegInfo();
  77
  78   const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
  79   OS << "LIn RP: ";
  80   getRegPressure(MRI, LiveIns).print(OS);
  81
  82   const auto BottomMI = End == BB->end() ? std::prev(End) : End;
  83   const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
  84   OS << "LOt RP: ";
  85   getRegPressure(MRI, LiveOuts).print(OS);
  86 }
  87
  88 LLVM_DUMP_METHOD
  89 void GCNIterativeScheduler::printRegions(raw_ostream &OS) const {
  90   const auto &ST = MF.getSubtarget<SISubtarget>();
  91   for (const auto R : Regions) {
  92     OS << "Region to schedule ";
  93     printRegion(OS, R->Begin, R->End, LIS, 1);
  94     printLivenessInfo(OS, R->Begin, R->End, LIS);
  95     OS << "Max RP: ";
  96     R->MaxPressure.print(OS, &ST);
  97   }
  98 }
  99
 100 LLVM_DUMP_METHOD
 101 void GCNIterativeScheduler::printSchedResult(raw_ostream &OS,
 102                                              const Region *R,
 103                                              const GCNRegPressure &RP) const {
 104   OS << "\nAfter scheduling ";
 105   printRegion(OS, R->Begin, R->End, LIS);
 106   printSchedRP(OS, R->MaxPressure, RP);
 107   OS << '\n';
 108 }
 109
 110 LLVM_DUMP_METHOD
 111 void GCNIterativeScheduler::printSchedRP(raw_ostream &OS,
 112                                          const GCNRegPressure &Before,
 113                                          const GCNRegPressure &After) const {
 114   const auto &ST = MF.getSubtarget<SISubtarget>();
 115   OS << "RP before: ";
 116   Before.print(OS, &ST);
 117   OS << "RP after:  ";
 118   After.print(OS, &ST);
 119 }
 120
 121 #endif
 122
 123 // DAG builder helper
 124 class GCNIterativeScheduler::BuildDAG {
 125   GCNIterativeScheduler &Sch;
 126   SmallVector<SUnit*, 8> TopRoots;
 127 public:
 128   BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
 129     : Sch(_Sch) {
 130     auto BB = R.Begin->getParent();
 131     Sch.BaseClass::startBlock(BB);
 132     Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
 133
 134     Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
 135                         /*TrackLaneMask*/true);
 136     Sch.Topo.InitDAGTopologicalSorting();
 137
 138     SmallVector<SUnit*, 8> BotRoots;
 139     Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
 140   }
 141   ~BuildDAG() {
 142     Sch.BaseClass::exitRegion();
 143     Sch.BaseClass::finishBlock();
 144   }
 145   ArrayRef<const SUnit*> getTopRoots() const {
 146     return TopRoots;
 147   }
 148 };
 149
 150 class GCNIterativeScheduler::OverrideLegacyStrategy {
 151   GCNIterativeScheduler &Sch;
 152   Region &Rgn;
 153   std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
 154   GCNRegPressure SaveMaxRP;
 155 public:
 156   OverrideLegacyStrategy(Region &R,
 157                          MachineSchedStrategy &OverrideStrategy,
 158                          GCNIterativeScheduler &_Sch)
 159     : Sch(_Sch)
 160     , Rgn(R)
 161     , SaveSchedImpl(std::move(_Sch.SchedImpl))
 162     , SaveMaxRP(R.MaxPressure) {
 163     Sch.SchedImpl.reset(&OverrideStrategy);
 164     auto BB = R.Begin->getParent();
 165     Sch.BaseClass::startBlock(BB);
 166     Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
 167   }
 168   ~OverrideLegacyStrategy() {
 169     Sch.BaseClass::exitRegion();
 170     Sch.BaseClass::finishBlock();
 171     Sch.SchedImpl.release();
 172     Sch.SchedImpl = std::move(SaveSchedImpl);
 173   }
 174   void schedule() {
 175     assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
 176     DEBUG(dbgs() << "\nScheduling ";
 177       printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
 178     Sch.BaseClass::schedule();
 179
 180     // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
 181     Sch.RegionEnd = Rgn.End;
 182     //assert(Rgn.End == Sch.RegionEnd);
 183     Rgn.Begin = Sch.RegionBegin;
 184     Rgn.MaxPressure.clear();
 185   }
 186   void restoreOrder() {
 187     assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
 188     // DAG SUnits are stored using original region's order
 189     // so just use SUnits as the restoring schedule
 190     Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
 191   }
 192 };
 193
 194 namespace {
 195 // just a stub to make base class happy
 196 class SchedStrategyStub : public MachineSchedStrategy {
 197 public:
 198   bool shouldTrackPressure() const override { return false; }
 199   bool shouldTrackLaneMasks() const override { return false; }
 200   void initialize(ScheduleDAGMI *DAG) override {}
 201   SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
 202   void schedNode(SUnit *SU, bool IsTopNode) override {}
 203   void releaseTopNode(SUnit *SU) override {}
 204   void releaseBottomNode(SUnit *SU) override {}
 205 };
 206 } // namespace
 207
 208 GCNIterativeScheduler::GCNIterativeScheduler(MachineSchedContext *C,
 209                                              StrategyKind S)
 210   : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
 211   , Context(C)
 212   , Strategy(S)
 213   , UPTracker(*LIS) {
 214 }
 215
 216 // returns max pressure for a region
 217 GCNRegPressure
 218 GCNIterativeScheduler::getRegionPressure(MachineBasicBlock::iterator Begin,
 219                                          MachineBasicBlock::iterator End)
 220   const {
 221   // For the purpose of pressure tracking bottom inst of the region should
 222   // be also processed. End is either BB end, BB terminator inst or sched
 223   // boundary inst.
 224   auto const BBEnd = Begin->getParent()->end();
 225   auto const BottomMI = End == BBEnd ? std::prev(End) : End;
 226
 227   // scheduleRegions walks bottom to top, so its likely we just get next
 228   // instruction to track
 229   auto AfterBottomMI = std::next(BottomMI);
 230   if (AfterBottomMI == BBEnd ||
 231       &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
 232     UPTracker.reset(*BottomMI);
 233   } else {
 234     assert(UPTracker.isValid());
 235   }
 236
 237   for (auto I = BottomMI; I != Begin; --I)
 238     UPTracker.recede(*I);
 239
 240   UPTracker.recede(*Begin);
 241
 242   assert(UPTracker.isValid() ||
 243          (dbgs() << "Tracked region ",
 244           printRegion(dbgs(), Begin, End, LIS), false));
 245   return UPTracker.moveMaxPressure();
 246 }
 247
 248 // returns max pressure for a tentative schedule
 249 template <typename Range> GCNRegPressure
 250 GCNIterativeScheduler::getSchedulePressure(const Region &R,
 251                                            Range &&Schedule) const {
 252   auto const BBEnd = R.Begin->getParent()->end();
 253   GCNUpwardRPTracker RPTracker(*LIS);
 254   if (R.End != BBEnd) {
 255     // R.End points to the boundary instruction but the
 256     // schedule doesn't include it
 257     RPTracker.reset(*R.End);
 258     RPTracker.recede(*R.End);
 259   } else {
 260     // R.End doesn't point to the boundary instruction
 261     RPTracker.reset(*std::prev(BBEnd));
 262   }
 263   for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
 264     RPTracker.recede(*getMachineInstr(*--I));
 265   }
 266   return RPTracker.moveMaxPressure();
 267 }
 268
 269 void GCNIterativeScheduler::enterRegion(MachineBasicBlock *BB, // overriden
 270                                         MachineBasicBlock::iterator Begin,
 271                                         MachineBasicBlock::iterator End,
 272                                         unsigned NumRegionInstrs) {
 273   BaseClass::enterRegion(BB, Begin, End, NumRegionInstrs);
 274   if (NumRegionInstrs > 2) {
 275     Regions.push_back(
 276       new (Alloc.Allocate())
 277       Region { Begin, End, NumRegionInstrs,
 278                getRegionPressure(Begin, End), nullptr });
 279   }
 280 }
 281
 282 void GCNIterativeScheduler::schedule() { // overriden
 283   // do nothing
 284   DEBUG(
 285     printLivenessInfo(dbgs(), RegionBegin, RegionEnd, LIS);
 286     if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
 287       dbgs() << "Max RP: ";
 288       Regions.back()->MaxPressure.print(dbgs(), &MF.getSubtarget<SISubtarget>());
 289     }
 290     dbgs() << '\n';
 291   );
 292 }
 293
 294 void GCNIterativeScheduler::finalizeSchedule() { // overriden
 295   if (Regions.empty())
 296     return;
 297   switch (Strategy) {
 298   case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
 299   case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
 300   case SCHEDULE_LEGACYMAXOCCUPANCY: scheduleLegacyMaxOccupancy(); break;
 301   }
 302 }
 303
 304 // Detach schedule from SUnits and interleave it with debug values.
 305 // Returned schedule becomes independent of DAG state.
 306 std::vector<MachineInstr*>
 307 GCNIterativeScheduler::detachSchedule(ScheduleRef Schedule) const {
 308   std::vector<MachineInstr*> Res;
 309   Res.reserve(Schedule.size() * 2);
 310
 311   if (FirstDbgValue)
 312     Res.push_back(FirstDbgValue);
 313
 314   const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
 315   for (auto SU : Schedule) {
 316     Res.push_back(SU->getInstr());
 317     const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
 318       return P.second == SU->getInstr();
 319     });
 320     if (D != DbgE)
 321       Res.push_back(D->first);
 322   }
 323   return Res;
 324 }
 325
 326 void GCNIterativeScheduler::setBestSchedule(Region &R,
 327                                             ScheduleRef Schedule,
 328                                             const GCNRegPressure &MaxRP) {
 329   R.BestSchedule.reset(
 330     new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
 331 }
 332
 333 void GCNIterativeScheduler::scheduleBest(Region &R) {
 334   assert(R.BestSchedule.get() && "No schedule specified");
 335   scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
 336   R.BestSchedule.reset();
 337 }
 338
 339 // minimal required region scheduler, works for ranges of SUnits*,
 340 // SUnits or MachineIntrs*
 341 template <typename Range>
 342 void GCNIterativeScheduler::scheduleRegion(Region &R, Range &&Schedule,
 343                                            const GCNRegPressure &MaxRP) {
 344   assert(RegionBegin == R.Begin && RegionEnd == R.End);
 345   assert(LIS != nullptr);
 346 #ifndef NDEBUG
 347   const auto SchedMaxRP = getSchedulePressure(R, Schedule);
 348 #endif
 349   auto BB = R.Begin->getParent();
 350   auto Top = R.Begin;
 351   for (const auto &I : Schedule) {
 352     auto MI = getMachineInstr(I);
 353     if (MI != &*Top) {
 354       BB->remove(MI);
 355       BB->insert(Top, MI);
 356       if (!MI->isDebugValue())
 357         LIS->handleMove(*MI, true);
 358     }
 359     if (!MI->isDebugValue()) {
 360       // Reset read - undef flags and update them later.
 361       for (auto &Op : MI->operands())
 362         if (Op.isReg() && Op.isDef())
 363           Op.setIsUndef(false);
 364
 365       RegisterOperands RegOpers;
 366       RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
 367                                        /*IgnoreDead*/false);
 368       // Adjust liveness and add missing dead+read-undef flags.
 369       auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
 370       RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
 371     }
 372     Top = std::next(MI->getIterator());
 373   }
 374   RegionBegin = getMachineInstr(Schedule.front());
 375
 376   // Schedule consisting of MachineInstr* is considered 'detached'
 377   // and already interleaved with debug values
 378   if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
 379     placeDebugValues();
 380     // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
 381     //assert(R.End == RegionEnd);
 382     RegionEnd = R.End;
 383   }
 384
 385   R.Begin = RegionBegin;
 386   R.MaxPressure = MaxRP;
 387
 388 #ifndef NDEBUG
 389   const auto RegionMaxRP = getRegionPressure(R);
 390   const auto &ST = MF.getSubtarget<SISubtarget>();
 391 #endif
 392   assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
 393   || (dbgs() << "Max RP mismatch!!!\n"
 394                 "RP for schedule (calculated): ",
 395       SchedMaxRP.print(dbgs(), &ST),
 396       dbgs() << "RP for schedule (reported): ",
 397       MaxRP.print(dbgs(), &ST),
 398       dbgs() << "RP after scheduling: ",
 399       RegionMaxRP.print(dbgs(), &ST),
 400       false));
 401 }
 402
 403 // Sort recorded regions by pressure - highest at the front
 404 void GCNIterativeScheduler::sortRegionsByPressure(unsigned TargetOcc) {
 405   const auto &ST = MF.getSubtarget<SISubtarget>();
 406   std::sort(Regions.begin(), Regions.end(),
 407     [&ST, TargetOcc](const Region *R1, const Region *R2) {
 408     return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
 409   });
 410 }
 411
 412 ///////////////////////////////////////////////////////////////////////////////
 413 // Legacy MaxOccupancy Strategy
 414
 415 // Tries to increase occupancy applying minreg scheduler for a sequence of
 416 // most demanding regions. Obtained schedules are saved as BestSchedule for a
 417 // region.
 418 // TargetOcc is the best achievable occupancy for a kernel.
 419 // Returns better occupancy on success or current occupancy on fail.
 420 // BestSchedules aren't deleted on fail.
 421 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
 422   // TODO: assert Regions are sorted descending by pressure
 423   const auto &ST = MF.getSubtarget<SISubtarget>();
 424   const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
 425   DEBUG(dbgs() << "Trying to to improve occupancy, target = " << TargetOcc
 426                << ", current = " << Occ << '\n');
 427
 428   auto NewOcc = TargetOcc;
 429   for (auto R : Regions) {
 430     if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
 431       break;
 432
 433     DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
 434           printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
 435
 436     BuildDAG DAG(*R, *this);
 437     const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
 438     const auto MaxRP = getSchedulePressure(*R, MinSchedule);
 439     DEBUG(dbgs() << "Occupancy improvement attempt:\n";
 440           printSchedRP(dbgs(), R->MaxPressure, MaxRP));
 441
 442     NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
 443     if (NewOcc <= Occ)
 444       break;
 445
 446     setBestSchedule(*R, MinSchedule, MaxRP);
 447   }
 448   DEBUG(dbgs() << "New occupancy = " << NewOcc
 449                << ", prev occupancy = " << Occ << '\n');
 450   return std::max(NewOcc, Occ);
 451 }
 452
 453 void GCNIterativeScheduler::scheduleLegacyMaxOccupancy(
 454   bool TryMaximizeOccupancy) {
 455   const auto &ST = MF.getSubtarget<SISubtarget>();
 456   auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
 457
 458   sortRegionsByPressure(TgtOcc);
 459   auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
 460
 461   if (TryMaximizeOccupancy && Occ < TgtOcc)
 462     Occ = tryMaximizeOccupancy(TgtOcc);
 463
 464   // This is really weird but for some magic scheduling regions twice
 465   // gives performance improvement
 466   const int NumPasses = Occ < TgtOcc ? 2 : 1;
 467
 468   TgtOcc = std::min(Occ, TgtOcc);
 469   DEBUG(dbgs() << "Scheduling using default scheduler, "
 470                   "target occupancy = " << TgtOcc << '\n');
 471   GCNMaxOccupancySchedStrategy LStrgy(Context);
 472
 473   for (int I = 0; I < NumPasses; ++I) {
 474     // running first pass with TargetOccupancy = 0 mimics previous scheduling
 475     // approach and is a performance magic
 476     LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
 477     for (auto R : Regions) {
 478       OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
 479
 480       Ovr.schedule();
 481       const auto RP = getRegionPressure(*R);
 482       DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
 483
 484       if (RP.getOccupancy(ST) < TgtOcc) {
 485         DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
 486         if (R->BestSchedule.get() &&
 487             R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
 488           DEBUG(dbgs() << ", scheduling minimal register\n");
 489           scheduleBest(*R);
 490         } else {
 491           DEBUG(dbgs() << ", restoring\n");
 492           Ovr.restoreOrder();
 493           assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
 494         }
 495       }
 496     }
 497   }
 498 }
 499
 500 ///////////////////////////////////////////////////////////////////////////////
 501 // Minimal Register Strategy
 502
 503 void GCNIterativeScheduler::scheduleMinReg(bool force) {
 504   const auto &ST = MF.getSubtarget<SISubtarget>();
 505   const auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
 506   sortRegionsByPressure(TgtOcc);
 507
 508   auto MaxPressure = Regions.front()->MaxPressure;
 509   for (auto R : Regions) {
 510     if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
 511       break;
 512
 513     BuildDAG DAG(*R, *this);
 514     const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
 515
 516     const auto RP = getSchedulePressure(*R, MinSchedule);
 517     DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
 518       dbgs() << "\nWarning: Pressure becomes worse after minreg!";
 519       printSchedRP(dbgs(), R->MaxPressure, RP);
 520     });
 521
 522     if (!force && MaxPressure.less(ST, RP, TgtOcc))
 523       break;
 524
 525     scheduleRegion(*R, MinSchedule, RP);
 526     DEBUG(printSchedResult(dbgs(), R, RP));
 527
 528     MaxPressure = RP;
 529   }
 530 }