LLVM  10.0.0svn
GCNIterativeScheduler.cpp
Go to the documentation of this file.
1 //===- GCNIterativeScheduler.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 
10 #include "AMDGPUSubtarget.h"
11 #include "GCNRegPressure.h"
12 #include "GCNSchedStrategy.h"
13 #include "SIMachineFunctionInfo.h"
14 #include "llvm/ADT/ArrayRef.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/Support/Compiler.h"
24 #include "llvm/Support/Debug.h"
26 #include <algorithm>
27 #include <cassert>
28 #include <iterator>
29 #include <limits>
30 #include <memory>
31 #include <type_traits>
32 #include <vector>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "machine-scheduler"
37 
38 namespace llvm {
39 
40 std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
41  const ScheduleDAG &DAG);
42 
43  std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
44  const ScheduleDAG &DAG);
45 }
46 
47 // shim accessors for different order containers
49  return MI;
50 }
51 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
52  return SU->getInstr();
53 }
54 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
55  return SU.getInstr();
56 }
57 
58 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
60 static void printRegion(raw_ostream &OS,
63  const LiveIntervals *LIS,
64  unsigned MaxInstNum =
66  auto BB = Begin->getParent();
67  OS << BB->getParent()->getName() << ":" << printMBBReference(*BB) << ' '
68  << BB->getName() << ":\n";
69  auto I = Begin;
70  MaxInstNum = std::max(MaxInstNum, 1u);
71  for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
72  if (!I->isDebugInstr() && LIS)
73  OS << LIS->getInstructionIndex(*I);
74  OS << '\t' << *I;
75  }
76  if (I != End) {
77  OS << "\t...\n";
78  I = std::prev(End);
79  if (!I->isDebugInstr() && LIS)
80  OS << LIS->getInstructionIndex(*I);
81  OS << '\t' << *I;
82  }
83  if (End != BB->end()) { // print boundary inst if present
84  OS << "----\n";
85  if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
86  OS << *End;
87  }
88 }
89 
94  const LiveIntervals *LIS) {
95  const auto BB = Begin->getParent();
96  const auto &MRI = BB->getParent()->getRegInfo();
97 
98  const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
99  OS << "LIn RP: ";
100  getRegPressure(MRI, LiveIns).print(OS);
101 
102  const auto BottomMI = End == BB->end() ? std::prev(End) : End;
103  const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
104  OS << "LOt RP: ";
105  getRegPressure(MRI, LiveOuts).print(OS);
106 }
107 
110  const auto &ST = MF.getSubtarget<GCNSubtarget>();
111  for (const auto R : Regions) {
112  OS << "Region to schedule ";
113  printRegion(OS, R->Begin, R->End, LIS, 1);
114  printLivenessInfo(OS, R->Begin, R->End, LIS);
115  OS << "Max RP: ";
116  R->MaxPressure.print(OS, &ST);
117  }
118 }
119 
122  const Region *R,
123  const GCNRegPressure &RP) const {
124  OS << "\nAfter scheduling ";
125  printRegion(OS, R->Begin, R->End, LIS);
126  printSchedRP(OS, R->MaxPressure, RP);
127  OS << '\n';
128 }
129 
132  const GCNRegPressure &Before,
133  const GCNRegPressure &After) const {
134  const auto &ST = MF.getSubtarget<GCNSubtarget>();
135  OS << "RP before: ";
136  Before.print(OS, &ST);
137  OS << "RP after: ";
138  After.print(OS, &ST);
139 }
140 #endif
141 
142 // DAG builder helper
145  SmallVector<SUnit *, 8> TopRoots;
146 
147  SmallVector<SUnit*, 8> BotRoots;
148 public:
150  : Sch(_Sch) {
151  auto BB = R.Begin->getParent();
152  Sch.BaseClass::startBlock(BB);
153  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
154 
155  Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
156  /*TrackLaneMask*/true);
158  Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
159  }
160 
162  Sch.BaseClass::exitRegion();
163  Sch.BaseClass::finishBlock();
164  }
165 
167  return TopRoots;
168  }
170  return BotRoots;
171  }
172 };
173 
176  Region &Rgn;
177  std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
178  GCNRegPressure SaveMaxRP;
179 
180 public:
182  MachineSchedStrategy &OverrideStrategy,
183  GCNIterativeScheduler &_Sch)
184  : Sch(_Sch)
185  , Rgn(R)
186  , SaveSchedImpl(std::move(_Sch.SchedImpl))
187  , SaveMaxRP(R.MaxPressure) {
188  Sch.SchedImpl.reset(&OverrideStrategy);
189  auto BB = R.Begin->getParent();
190  Sch.BaseClass::startBlock(BB);
191  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
192  }
193 
195  Sch.BaseClass::exitRegion();
196  Sch.BaseClass::finishBlock();
197  Sch.SchedImpl.release();
198  Sch.SchedImpl = std::move(SaveSchedImpl);
199  }
200 
201  void schedule() {
202  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
203  LLVM_DEBUG(dbgs() << "\nScheduling ";
204  printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
205  Sch.BaseClass::schedule();
206 
207  // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
208  Sch.RegionEnd = Rgn.End;
209  //assert(Rgn.End == Sch.RegionEnd);
210  Rgn.Begin = Sch.RegionBegin;
211  Rgn.MaxPressure.clear();
212  }
213 
214  void restoreOrder() {
215  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
216  // DAG SUnits are stored using original region's order
217  // so just use SUnits as the restoring schedule
218  Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
219  }
220 };
221 
222 namespace {
223 
224 // just a stub to make base class happy
225 class SchedStrategyStub : public MachineSchedStrategy {
226 public:
227  bool shouldTrackPressure() const override { return false; }
228  bool shouldTrackLaneMasks() const override { return false; }
229  void initialize(ScheduleDAGMI *DAG) override {}
230  SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
231  void schedNode(SUnit *SU, bool IsTopNode) override {}
232  void releaseTopNode(SUnit *SU) override {}
233  void releaseBottomNode(SUnit *SU) override {}
234 };
235 
236 } // end anonymous namespace
237 
239  StrategyKind S)
240  : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
241  , Context(C)
242  , Strategy(S)
243  , UPTracker(*LIS) {
244 }
245 
246 // returns max pressure for a region
250  const {
251  // For the purpose of pressure tracking bottom inst of the region should
252  // be also processed. End is either BB end, BB terminator inst or sched
253  // boundary inst.
254  auto const BBEnd = Begin->getParent()->end();
255  auto const BottomMI = End == BBEnd ? std::prev(End) : End;
256 
257  // scheduleRegions walks bottom to top, so its likely we just get next
258  // instruction to track
259  auto AfterBottomMI = std::next(BottomMI);
260  if (AfterBottomMI == BBEnd ||
261  &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
262  UPTracker.reset(*BottomMI);
263  } else {
265  }
266 
267  for (auto I = BottomMI; I != Begin; --I)
268  UPTracker.recede(*I);
269 
270  UPTracker.recede(*Begin);
271 
273  (dbgs() << "Tracked region ",
274  printRegion(dbgs(), Begin, End, LIS), false));
275  return UPTracker.moveMaxPressure();
276 }
277 
278 // returns max pressure for a tentative schedule
279 template <typename Range> GCNRegPressure
281  Range &&Schedule) const {
282  auto const BBEnd = R.Begin->getParent()->end();
284  if (R.End != BBEnd) {
285  // R.End points to the boundary instruction but the
286  // schedule doesn't include it
287  RPTracker.reset(*R.End);
288  RPTracker.recede(*R.End);
289  } else {
290  // R.End doesn't point to the boundary instruction
291  RPTracker.reset(*std::prev(BBEnd));
292  }
293  for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
294  RPTracker.recede(*getMachineInstr(*--I));
295  }
296  return RPTracker.moveMaxPressure();
297 }
298 
302  unsigned NumRegionInstrs) {
303  BaseClass::enterRegion(BB, Begin, End, NumRegionInstrs);
304  if (NumRegionInstrs > 2) {
305  Regions.push_back(
306  new (Alloc.Allocate())
307  Region { Begin, End, NumRegionInstrs,
308  getRegionPressure(Begin, End), nullptr });
309  }
310 }
311 
312 void GCNIterativeScheduler::schedule() { // overriden
313  // do nothing
315  if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
316  dbgs() << "Max RP: ";
317  Regions.back()->MaxPressure.print(
319  } dbgs()
320  << '\n';);
321 }
322 
324  if (Regions.empty())
325  return;
326  switch (Strategy) {
327  case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
328  case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
330  case SCHEDULE_ILP: scheduleILP(false); break;
331  }
332 }
333 
334 // Detach schedule from SUnits and interleave it with debug values.
335 // Returned schedule becomes independent of DAG state.
336 std::vector<MachineInstr*>
338  std::vector<MachineInstr*> Res;
339  Res.reserve(Schedule.size() * 2);
340 
341  if (FirstDbgValue)
342  Res.push_back(FirstDbgValue);
343 
344  const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
345  for (auto SU : Schedule) {
346  Res.push_back(SU->getInstr());
347  const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
348  return P.second == SU->getInstr();
349  });
350  if (D != DbgE)
351  Res.push_back(D->first);
352  }
353  return Res;
354 }
355 
357  ScheduleRef Schedule,
358  const GCNRegPressure &MaxRP) {
359  R.BestSchedule.reset(
360  new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
361 }
362 
364  assert(R.BestSchedule.get() && "No schedule specified");
365  scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
366  R.BestSchedule.reset();
367 }
368 
369 // minimal required region scheduler, works for ranges of SUnits*,
370 // SUnits or MachineIntrs*
371 template <typename Range>
373  const GCNRegPressure &MaxRP) {
374  assert(RegionBegin == R.Begin && RegionEnd == R.End);
375  assert(LIS != nullptr);
376 #ifndef NDEBUG
377  const auto SchedMaxRP = getSchedulePressure(R, Schedule);
378 #endif
379  auto BB = R.Begin->getParent();
380  auto Top = R.Begin;
381  for (const auto &I : Schedule) {
382  auto MI = getMachineInstr(I);
383  if (MI != &*Top) {
384  BB->remove(MI);
385  BB->insert(Top, MI);
386  if (!MI->isDebugInstr())
387  LIS->handleMove(*MI, true);
388  }
389  if (!MI->isDebugInstr()) {
390  // Reset read - undef flags and update them later.
391  for (auto &Op : MI->operands())
392  if (Op.isReg() && Op.isDef())
393  Op.setIsUndef(false);
394 
395  RegisterOperands RegOpers;
396  RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
397  /*IgnoreDead*/false);
398  // Adjust liveness and add missing dead+read-undef flags.
399  auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
400  RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
401  }
402  Top = std::next(MI->getIterator());
403  }
404  RegionBegin = getMachineInstr(Schedule.front());
405 
406  // Schedule consisting of MachineInstr* is considered 'detached'
407  // and already interleaved with debug values
408  if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
410  // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
411  //assert(R.End == RegionEnd);
412  RegionEnd = R.End;
413  }
414 
415  R.Begin = RegionBegin;
416  R.MaxPressure = MaxRP;
417 
418 #ifndef NDEBUG
419  const auto RegionMaxRP = getRegionPressure(R);
420  const auto &ST = MF.getSubtarget<GCNSubtarget>();
421 #endif
422  assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
423  || (dbgs() << "Max RP mismatch!!!\n"
424  "RP for schedule (calculated): ",
425  SchedMaxRP.print(dbgs(), &ST),
426  dbgs() << "RP for schedule (reported): ",
427  MaxRP.print(dbgs(), &ST),
428  dbgs() << "RP after scheduling: ",
429  RegionMaxRP.print(dbgs(), &ST),
430  false));
431 }
432 
433 // Sort recorded regions by pressure - highest at the front
435  const auto &ST = MF.getSubtarget<GCNSubtarget>();
436  llvm::sort(Regions, [&ST, TargetOcc](const Region *R1, const Region *R2) {
437  return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
438  });
439 }
440 
441 ///////////////////////////////////////////////////////////////////////////////
442 // Legacy MaxOccupancy Strategy
443 
444 // Tries to increase occupancy applying minreg scheduler for a sequence of
445 // most demanding regions. Obtained schedules are saved as BestSchedule for a
446 // region.
447 // TargetOcc is the best achievable occupancy for a kernel.
448 // Returns better occupancy on success or current occupancy on fail.
449 // BestSchedules aren't deleted on fail.
450 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
451  // TODO: assert Regions are sorted descending by pressure
452  const auto &ST = MF.getSubtarget<GCNSubtarget>();
453  const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
454  LLVM_DEBUG(dbgs() << "Trying to improve occupancy, target = " << TargetOcc
455  << ", current = " << Occ << '\n');
456 
457  auto NewOcc = TargetOcc;
458  for (auto R : Regions) {
459  if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
460  break;
461 
462  LLVM_DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
463  printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
464 
465  BuildDAG DAG(*R, *this);
466  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
467  const auto MaxRP = getSchedulePressure(*R, MinSchedule);
468  LLVM_DEBUG(dbgs() << "Occupancy improvement attempt:\n";
469  printSchedRP(dbgs(), R->MaxPressure, MaxRP));
470 
471  NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
472  if (NewOcc <= Occ)
473  break;
474 
475  setBestSchedule(*R, MinSchedule, MaxRP);
476  }
477  LLVM_DEBUG(dbgs() << "New occupancy = " << NewOcc
478  << ", prev occupancy = " << Occ << '\n');
479  if (NewOcc > Occ) {
481  MFI->increaseOccupancy(MF, NewOcc);
482  }
483 
484  return std::max(NewOcc, Occ);
485 }
486 
488  bool TryMaximizeOccupancy) {
489  const auto &ST = MF.getSubtarget<GCNSubtarget>();
491  auto TgtOcc = MFI->getMinAllowedOccupancy();
492 
493  sortRegionsByPressure(TgtOcc);
494  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
495 
496  if (TryMaximizeOccupancy && Occ < TgtOcc)
497  Occ = tryMaximizeOccupancy(TgtOcc);
498 
499  // This is really weird but for some magic scheduling regions twice
500  // gives performance improvement
501  const int NumPasses = Occ < TgtOcc ? 2 : 1;
502 
503  TgtOcc = std::min(Occ, TgtOcc);
504  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
505  "target occupancy = "
506  << TgtOcc << '\n');
508  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
509 
510  for (int I = 0; I < NumPasses; ++I) {
511  // running first pass with TargetOccupancy = 0 mimics previous scheduling
512  // approach and is a performance magic
513  LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
514  for (auto R : Regions) {
515  OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
516 
517  Ovr.schedule();
518  const auto RP = getRegionPressure(*R);
519  LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
520 
521  if (RP.getOccupancy(ST) < TgtOcc) {
522  LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
523  if (R->BestSchedule.get() &&
524  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
525  LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
526  scheduleBest(*R);
527  } else {
528  LLVM_DEBUG(dbgs() << ", restoring\n");
529  Ovr.restoreOrder();
530  assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
531  }
532  }
533  FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
534  }
535  }
536  MFI->limitOccupancy(FinalOccupancy);
537 }
538 
539 ///////////////////////////////////////////////////////////////////////////////
540 // Minimal Register Strategy
541 
543  const auto &ST = MF.getSubtarget<GCNSubtarget>();
545  const auto TgtOcc = MFI->getOccupancy();
546  sortRegionsByPressure(TgtOcc);
547 
548  auto MaxPressure = Regions.front()->MaxPressure;
549  for (auto R : Regions) {
550  if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
551  break;
552 
553  BuildDAG DAG(*R, *this);
554  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
555 
556  const auto RP = getSchedulePressure(*R, MinSchedule);
557  LLVM_DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
558  dbgs() << "\nWarning: Pressure becomes worse after minreg!";
559  printSchedRP(dbgs(), R->MaxPressure, RP);
560  });
561 
562  if (!force && MaxPressure.less(ST, RP, TgtOcc))
563  break;
564 
565  scheduleRegion(*R, MinSchedule, RP);
566  LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
567 
568  MaxPressure = RP;
569  }
570 }
571 
572 ///////////////////////////////////////////////////////////////////////////////
573 // ILP scheduler port
574 
576  bool TryMaximizeOccupancy) {
577  const auto &ST = MF.getSubtarget<GCNSubtarget>();
579  auto TgtOcc = MFI->getMinAllowedOccupancy();
580 
581  sortRegionsByPressure(TgtOcc);
582  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
583 
584  if (TryMaximizeOccupancy && Occ < TgtOcc)
585  Occ = tryMaximizeOccupancy(TgtOcc);
586 
587  TgtOcc = std::min(Occ, TgtOcc);
588  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
589  "target occupancy = "
590  << TgtOcc << '\n');
591 
592  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
593  for (auto R : Regions) {
594  BuildDAG DAG(*R, *this);
595  const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
596 
597  const auto RP = getSchedulePressure(*R, ILPSchedule);
598  LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
599 
600  if (RP.getOccupancy(ST) < TgtOcc) {
601  LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
602  if (R->BestSchedule.get() &&
603  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
604  LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
605  scheduleBest(*R);
606  }
607  } else {
608  scheduleRegion(*R, ILPSchedule, RP);
609  LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
610  FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
611  }
612  }
613  MFI->limitOccupancy(FinalOccupancy);
614 }
unsigned tryMaximizeOccupancy(unsigned TargetOcc=std::numeric_limits< unsigned >::max())
uint64_t CallInst * C
void enterRegion(MachineBasicBlock *BB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned RegionInstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries...
GCNRegPressure getRegionPressure(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End) const
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
AMDGPU specific subclass of TargetSubtarget.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
This is a minimal scheduler strategy.
void sortRegionsByPressure(unsigned TargetOcc)
decltype(MaxPressure) moveMaxPressure()
SpecificBumpPtrAllocator< Region > Alloc
std::vector< Region * > Regions
std::vector< MachineInstr * > detachSchedule(ScheduleRef Schedule) const
std::enable_if<!std::is_array< T >::value, std::unique_ptr< T > >::type make_unique(Args &&... args)
Constructs a new T() with the given args and returns a unique_ptr<T> which owns the object...
Definition: STLExtras.h:1405
#define R2(n)
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
std::unique_ptr< MachineSchedStrategy > SchedImpl
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:560
void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
void printRegions(raw_ostream &OS) const
Definition: BitVector.h:937
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void finalizeSchedule() override
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
void scheduleLegacyMaxOccupancy(bool TryMaximizeOccupancy=true)
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
Definition: SlotIndexes.h:254
void increaseOccupancy(const MachineFunction &MF, unsigned Limit)
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
static LLVM_DUMP_METHOD void printLivenessInfo(raw_ostream &OS, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, const LiveIntervals *LIS)
std::vector< const SUnit * > makeMinRegSchedule(ArrayRef< const SUnit *> TopRoots, const ScheduleDAG &DAG)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
GCNRPTracker::LiveRegSet getLiveRegsBefore(const MachineInstr &MI, const LiveIntervals &LIS)
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
static MachineInstr * getMachineInstr(MachineInstr *MI)
List of registers defined and used by a machine instruction.
bool less(const GCNSubtarget &ST, const GCNRegPressure &O, unsigned MaxOccupancy=std::numeric_limits< unsigned >::max()) const
void printSchedRP(raw_ostream &OS, const GCNRegPressure &Before, const GCNRegPressure &After) const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
void reset(const MachineInstr &MI, const LiveRegSet *LiveRegs=nullptr)
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
void setBestSchedule(Region &R, ScheduleRef Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
unsigned const MachineRegisterInfo * MRI
const MachineInstr * getLastTrackedMI() const
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1220
const MachineFrameInfo & MFI
GCNRPTracker::LiveRegSet getLiveRegsAfter(const MachineInstr &MI, const LiveIntervals &LIS)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1122
void adjustLaneLiveness(const LiveIntervals &LIS, const MachineRegisterInfo &MRI, SlotIndex Pos, MachineInstr *AddFlagsMI=nullptr)
Use liveness information to find out which uses/defs are partially undefined/dead and adjust the Regi...
GCNRegPressure getSchedulePressure(const Region &R, Range &&Schedule) const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
OverrideLegacyStrategy(Region &R, MachineSchedStrategy &OverrideStrategy, GCNIterativeScheduler &_Sch)
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
const MachineBasicBlock::iterator End
static LLVM_DUMP_METHOD void printRegion(raw_ostream &OS, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, const LiveIntervals *LIS, unsigned MaxInstNum=std::numeric_limits< unsigned >::max())
ArrayRef< const SUnit * > getTopRoots() const
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
GCNRegPressure getRegPressure(const MachineRegisterInfo &MRI, Range &&LiveRegs)
Representation of each machine instruction.
Definition: MachineInstr.h:64
LiveIntervals * LIS
This class keeps track of the SPI_SP_INPUT_ADDR config register, which tells the hardware which inter...
BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:559
void findRootsAndBiasEdges(SmallVectorImpl< SUnit *> &TopRoots, SmallVectorImpl< SUnit *> &BotRoots)
void printSchedResult(raw_ostream &OS, const Region *R, const GCNRegPressure &RP) const
GCNIterativeScheduler(MachineSchedContext *C, StrategyKind S)
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
#define I(x, y, z)
Definition: MD5.cpp:58
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
void scheduleRegion(Region &R, Range &&Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
std::vector< const SUnit * > makeGCNILPScheduler(ArrayRef< const SUnit *> BotRoots, const ScheduleDAG &DAG)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void print(raw_ostream &OS, const GCNSubtarget *ST=nullptr) const
void scheduleMinReg(bool force=false)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
MachineBasicBlock * BB
The block in which to insert instructions.
IRTranslator LLVM IR MI
void scheduleILP(bool TryMaximizeOccupancy=true)
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:561
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
#define LLVM_DEBUG(X)
Definition: Debug.h:122
void recede(const MachineInstr &MI)
AliasAnalysis * AA
RegPressureTracker RPTracker
std::unique_ptr< TentativeSchedule > BestSchedule
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block...
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242