LLVM  8.0.0svn
GCNIterativeScheduler.cpp
Go to the documentation of this file.
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 #include "GCNIterativeScheduler.h"
11 #include "AMDGPUSubtarget.h"
12 #include "GCNRegPressure.h"
13 #include "GCNSchedStrategy.h"
14 #include "SIMachineFunctionInfo.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/Config/llvm-config.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
27 #include <algorithm>
28 #include <cassert>
29 #include <iterator>
30 #include <limits>
31 #include <memory>
32 #include <type_traits>
33 #include <vector>
34 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "machine-scheduler"
38 
39 namespace llvm {
40 
41 std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
42  const ScheduleDAG &DAG);
43 
44  std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
45  const ScheduleDAG &DAG);
46 }
47 
48 // shim accessors for different order containers
50  return MI;
51 }
52 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
53  return SU->getInstr();
54 }
55 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
56  return SU.getInstr();
57 }
58 
59 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
61 static void printRegion(raw_ostream &OS,
64  const LiveIntervals *LIS,
65  unsigned MaxInstNum =
67  auto BB = Begin->getParent();
68  OS << BB->getParent()->getName() << ":" << printMBBReference(*BB) << ' '
69  << BB->getName() << ":\n";
70  auto I = Begin;
71  MaxInstNum = std::max(MaxInstNum, 1u);
72  for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
73  if (!I->isDebugInstr() && LIS)
74  OS << LIS->getInstructionIndex(*I);
75  OS << '\t' << *I;
76  }
77  if (I != End) {
78  OS << "\t...\n";
79  I = std::prev(End);
80  if (!I->isDebugInstr() && LIS)
81  OS << LIS->getInstructionIndex(*I);
82  OS << '\t' << *I;
83  }
84  if (End != BB->end()) { // print boundary inst if present
85  OS << "----\n";
86  if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
87  OS << *End;
88  }
89 }
90 
95  const LiveIntervals *LIS) {
96  const auto BB = Begin->getParent();
97  const auto &MRI = BB->getParent()->getRegInfo();
98 
99  const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
100  OS << "LIn RP: ";
101  getRegPressure(MRI, LiveIns).print(OS);
102 
103  const auto BottomMI = End == BB->end() ? std::prev(End) : End;
104  const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
105  OS << "LOt RP: ";
106  getRegPressure(MRI, LiveOuts).print(OS);
107 }
108 
111  const auto &ST = MF.getSubtarget<GCNSubtarget>();
112  for (const auto R : Regions) {
113  OS << "Region to schedule ";
114  printRegion(OS, R->Begin, R->End, LIS, 1);
115  printLivenessInfo(OS, R->Begin, R->End, LIS);
116  OS << "Max RP: ";
117  R->MaxPressure.print(OS, &ST);
118  }
119 }
120 
123  const Region *R,
124  const GCNRegPressure &RP) const {
125  OS << "\nAfter scheduling ";
126  printRegion(OS, R->Begin, R->End, LIS);
127  printSchedRP(OS, R->MaxPressure, RP);
128  OS << '\n';
129 }
130 
133  const GCNRegPressure &Before,
134  const GCNRegPressure &After) const {
135  const auto &ST = MF.getSubtarget<GCNSubtarget>();
136  OS << "RP before: ";
137  Before.print(OS, &ST);
138  OS << "RP after: ";
139  After.print(OS, &ST);
140 }
141 #endif
142 
143 // DAG builder helper
146  SmallVector<SUnit *, 8> TopRoots;
147 
148  SmallVector<SUnit*, 8> BotRoots;
149 public:
151  : Sch(_Sch) {
152  auto BB = R.Begin->getParent();
153  Sch.BaseClass::startBlock(BB);
154  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
155 
156  Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
157  /*TrackLaneMask*/true);
159  Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
160  }
161 
163  Sch.BaseClass::exitRegion();
164  Sch.BaseClass::finishBlock();
165  }
166 
168  return TopRoots;
169  }
171  return BotRoots;
172  }
173 };
174 
177  Region &Rgn;
178  std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
179  GCNRegPressure SaveMaxRP;
180 
181 public:
183  MachineSchedStrategy &OverrideStrategy,
184  GCNIterativeScheduler &_Sch)
185  : Sch(_Sch)
186  , Rgn(R)
187  , SaveSchedImpl(std::move(_Sch.SchedImpl))
188  , SaveMaxRP(R.MaxPressure) {
189  Sch.SchedImpl.reset(&OverrideStrategy);
190  auto BB = R.Begin->getParent();
191  Sch.BaseClass::startBlock(BB);
192  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
193  }
194 
196  Sch.BaseClass::exitRegion();
197  Sch.BaseClass::finishBlock();
198  Sch.SchedImpl.release();
199  Sch.SchedImpl = std::move(SaveSchedImpl);
200  }
201 
202  void schedule() {
203  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
204  LLVM_DEBUG(dbgs() << "\nScheduling ";
205  printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
206  Sch.BaseClass::schedule();
207 
208  // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
209  Sch.RegionEnd = Rgn.End;
210  //assert(Rgn.End == Sch.RegionEnd);
211  Rgn.Begin = Sch.RegionBegin;
212  Rgn.MaxPressure.clear();
213  }
214 
215  void restoreOrder() {
216  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
217  // DAG SUnits are stored using original region's order
218  // so just use SUnits as the restoring schedule
219  Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
220  }
221 };
222 
223 namespace {
224 
225 // just a stub to make base class happy
226 class SchedStrategyStub : public MachineSchedStrategy {
227 public:
228  bool shouldTrackPressure() const override { return false; }
229  bool shouldTrackLaneMasks() const override { return false; }
230  void initialize(ScheduleDAGMI *DAG) override {}
231  SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
232  void schedNode(SUnit *SU, bool IsTopNode) override {}
233  void releaseTopNode(SUnit *SU) override {}
234  void releaseBottomNode(SUnit *SU) override {}
235 };
236 
237 } // end anonymous namespace
238 
240  StrategyKind S)
241  : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
242  , Context(C)
243  , Strategy(S)
244  , UPTracker(*LIS) {
245 }
246 
247 // returns max pressure for a region
251  const {
252  // For the purpose of pressure tracking bottom inst of the region should
253  // be also processed. End is either BB end, BB terminator inst or sched
254  // boundary inst.
255  auto const BBEnd = Begin->getParent()->end();
256  auto const BottomMI = End == BBEnd ? std::prev(End) : End;
257 
258  // scheduleRegions walks bottom to top, so its likely we just get next
259  // instruction to track
260  auto AfterBottomMI = std::next(BottomMI);
261  if (AfterBottomMI == BBEnd ||
262  &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
263  UPTracker.reset(*BottomMI);
264  } else {
266  }
267 
268  for (auto I = BottomMI; I != Begin; --I)
269  UPTracker.recede(*I);
270 
271  UPTracker.recede(*Begin);
272 
274  (dbgs() << "Tracked region ",
275  printRegion(dbgs(), Begin, End, LIS), false));
276  return UPTracker.moveMaxPressure();
277 }
278 
279 // returns max pressure for a tentative schedule
280 template <typename Range> GCNRegPressure
282  Range &&Schedule) const {
283  auto const BBEnd = R.Begin->getParent()->end();
285  if (R.End != BBEnd) {
286  // R.End points to the boundary instruction but the
287  // schedule doesn't include it
288  RPTracker.reset(*R.End);
289  RPTracker.recede(*R.End);
290  } else {
291  // R.End doesn't point to the boundary instruction
292  RPTracker.reset(*std::prev(BBEnd));
293  }
294  for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
295  RPTracker.recede(*getMachineInstr(*--I));
296  }
297  return RPTracker.moveMaxPressure();
298 }
299 
303  unsigned NumRegionInstrs) {
304  BaseClass::enterRegion(BB, Begin, End, NumRegionInstrs);
305  if (NumRegionInstrs > 2) {
306  Regions.push_back(
307  new (Alloc.Allocate())
308  Region { Begin, End, NumRegionInstrs,
309  getRegionPressure(Begin, End), nullptr });
310  }
311 }
312 
313 void GCNIterativeScheduler::schedule() { // overriden
314  // do nothing
316  if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
317  dbgs() << "Max RP: ";
318  Regions.back()->MaxPressure.print(
320  } dbgs()
321  << '\n';);
322 }
323 
325  if (Regions.empty())
326  return;
327  switch (Strategy) {
328  case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
329  case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
331  case SCHEDULE_ILP: scheduleILP(false); break;
332  }
333 }
334 
335 // Detach schedule from SUnits and interleave it with debug values.
336 // Returned schedule becomes independent of DAG state.
337 std::vector<MachineInstr*>
339  std::vector<MachineInstr*> Res;
340  Res.reserve(Schedule.size() * 2);
341 
342  if (FirstDbgValue)
343  Res.push_back(FirstDbgValue);
344 
345  const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
346  for (auto SU : Schedule) {
347  Res.push_back(SU->getInstr());
348  const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
349  return P.second == SU->getInstr();
350  });
351  if (D != DbgE)
352  Res.push_back(D->first);
353  }
354  return Res;
355 }
356 
358  ScheduleRef Schedule,
359  const GCNRegPressure &MaxRP) {
360  R.BestSchedule.reset(
361  new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
362 }
363 
365  assert(R.BestSchedule.get() && "No schedule specified");
366  scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
367  R.BestSchedule.reset();
368 }
369 
370 // minimal required region scheduler, works for ranges of SUnits*,
371 // SUnits or MachineIntrs*
372 template <typename Range>
374  const GCNRegPressure &MaxRP) {
375  assert(RegionBegin == R.Begin && RegionEnd == R.End);
376  assert(LIS != nullptr);
377 #ifndef NDEBUG
378  const auto SchedMaxRP = getSchedulePressure(R, Schedule);
379 #endif
380  auto BB = R.Begin->getParent();
381  auto Top = R.Begin;
382  for (const auto &I : Schedule) {
383  auto MI = getMachineInstr(I);
384  if (MI != &*Top) {
385  BB->remove(MI);
386  BB->insert(Top, MI);
387  if (!MI->isDebugInstr())
388  LIS->handleMove(*MI, true);
389  }
390  if (!MI->isDebugInstr()) {
391  // Reset read - undef flags and update them later.
392  for (auto &Op : MI->operands())
393  if (Op.isReg() && Op.isDef())
394  Op.setIsUndef(false);
395 
396  RegisterOperands RegOpers;
397  RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
398  /*IgnoreDead*/false);
399  // Adjust liveness and add missing dead+read-undef flags.
400  auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
401  RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
402  }
403  Top = std::next(MI->getIterator());
404  }
405  RegionBegin = getMachineInstr(Schedule.front());
406 
407  // Schedule consisting of MachineInstr* is considered 'detached'
408  // and already interleaved with debug values
409  if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
411  // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
412  //assert(R.End == RegionEnd);
413  RegionEnd = R.End;
414  }
415 
416  R.Begin = RegionBegin;
417  R.MaxPressure = MaxRP;
418 
419 #ifndef NDEBUG
420  const auto RegionMaxRP = getRegionPressure(R);
421  const auto &ST = MF.getSubtarget<GCNSubtarget>();
422 #endif
423  assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
424  || (dbgs() << "Max RP mismatch!!!\n"
425  "RP for schedule (calculated): ",
426  SchedMaxRP.print(dbgs(), &ST),
427  dbgs() << "RP for schedule (reported): ",
428  MaxRP.print(dbgs(), &ST),
429  dbgs() << "RP after scheduling: ",
430  RegionMaxRP.print(dbgs(), &ST),
431  false));
432 }
433 
434 // Sort recorded regions by pressure - highest at the front
436  const auto &ST = MF.getSubtarget<GCNSubtarget>();
437  llvm::sort(Regions, [&ST, TargetOcc](const Region *R1, const Region *R2) {
438  return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
439  });
440 }
441 
442 ///////////////////////////////////////////////////////////////////////////////
443 // Legacy MaxOccupancy Strategy
444 
445 // Tries to increase occupancy applying minreg scheduler for a sequence of
446 // most demanding regions. Obtained schedules are saved as BestSchedule for a
447 // region.
448 // TargetOcc is the best achievable occupancy for a kernel.
449 // Returns better occupancy on success or current occupancy on fail.
450 // BestSchedules aren't deleted on fail.
451 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
452  // TODO: assert Regions are sorted descending by pressure
453  const auto &ST = MF.getSubtarget<GCNSubtarget>();
454  const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
455  LLVM_DEBUG(dbgs() << "Trying to improve occupancy, target = " << TargetOcc
456  << ", current = " << Occ << '\n');
457 
458  auto NewOcc = TargetOcc;
459  for (auto R : Regions) {
460  if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
461  break;
462 
463  LLVM_DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
464  printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
465 
466  BuildDAG DAG(*R, *this);
467  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
468  const auto MaxRP = getSchedulePressure(*R, MinSchedule);
469  LLVM_DEBUG(dbgs() << "Occupancy improvement attempt:\n";
470  printSchedRP(dbgs(), R->MaxPressure, MaxRP));
471 
472  NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
473  if (NewOcc <= Occ)
474  break;
475 
476  setBestSchedule(*R, MinSchedule, MaxRP);
477  }
478  LLVM_DEBUG(dbgs() << "New occupancy = " << NewOcc
479  << ", prev occupancy = " << Occ << '\n');
480  if (NewOcc > Occ) {
482  MFI->increaseOccupancy(MF, NewOcc);
483  }
484 
485  return std::max(NewOcc, Occ);
486 }
487 
489  bool TryMaximizeOccupancy) {
490  const auto &ST = MF.getSubtarget<GCNSubtarget>();
492  auto TgtOcc = MFI->getMinAllowedOccupancy();
493 
494  sortRegionsByPressure(TgtOcc);
495  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
496 
497  if (TryMaximizeOccupancy && Occ < TgtOcc)
498  Occ = tryMaximizeOccupancy(TgtOcc);
499 
500  // This is really weird but for some magic scheduling regions twice
501  // gives performance improvement
502  const int NumPasses = Occ < TgtOcc ? 2 : 1;
503 
504  TgtOcc = std::min(Occ, TgtOcc);
505  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
506  "target occupancy = "
507  << TgtOcc << '\n');
509  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
510 
511  for (int I = 0; I < NumPasses; ++I) {
512  // running first pass with TargetOccupancy = 0 mimics previous scheduling
513  // approach and is a performance magic
514  LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
515  for (auto R : Regions) {
516  OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
517 
518  Ovr.schedule();
519  const auto RP = getRegionPressure(*R);
520  LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
521 
522  if (RP.getOccupancy(ST) < TgtOcc) {
523  LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
524  if (R->BestSchedule.get() &&
525  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
526  LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
527  scheduleBest(*R);
528  } else {
529  LLVM_DEBUG(dbgs() << ", restoring\n");
530  Ovr.restoreOrder();
531  assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
532  }
533  }
534  FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
535  }
536  }
537  MFI->limitOccupancy(FinalOccupancy);
538 }
539 
540 ///////////////////////////////////////////////////////////////////////////////
541 // Minimal Register Strategy
542 
544  const auto &ST = MF.getSubtarget<GCNSubtarget>();
546  const auto TgtOcc = MFI->getOccupancy();
547  sortRegionsByPressure(TgtOcc);
548 
549  auto MaxPressure = Regions.front()->MaxPressure;
550  for (auto R : Regions) {
551  if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
552  break;
553 
554  BuildDAG DAG(*R, *this);
555  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
556 
557  const auto RP = getSchedulePressure(*R, MinSchedule);
558  LLVM_DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
559  dbgs() << "\nWarning: Pressure becomes worse after minreg!";
560  printSchedRP(dbgs(), R->MaxPressure, RP);
561  });
562 
563  if (!force && MaxPressure.less(ST, RP, TgtOcc))
564  break;
565 
566  scheduleRegion(*R, MinSchedule, RP);
567  LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
568 
569  MaxPressure = RP;
570  }
571 }
572 
573 ///////////////////////////////////////////////////////////////////////////////
574 // ILP scheduler port
575 
577  bool TryMaximizeOccupancy) {
578  const auto &ST = MF.getSubtarget<GCNSubtarget>();
580  auto TgtOcc = MFI->getMinAllowedOccupancy();
581 
582  sortRegionsByPressure(TgtOcc);
583  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
584 
585  if (TryMaximizeOccupancy && Occ < TgtOcc)
586  Occ = tryMaximizeOccupancy(TgtOcc);
587 
588  TgtOcc = std::min(Occ, TgtOcc);
589  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
590  "target occupancy = "
591  << TgtOcc << '\n');
592 
593  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
594  for (auto R : Regions) {
595  BuildDAG DAG(*R, *this);
596  const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
597 
598  const auto RP = getSchedulePressure(*R, ILPSchedule);
599  LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
600 
601  if (RP.getOccupancy(ST) < TgtOcc) {
602  LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
603  if (R->BestSchedule.get() &&
604  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
605  LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
606  scheduleBest(*R);
607  }
608  } else {
609  scheduleRegion(*R, ILPSchedule, RP);
610  LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
611  FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
612  }
613  }
614  MFI->limitOccupancy(FinalOccupancy);
615 }
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.
GCNRegPressure getRegionPressure(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End) const
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
AMDGPU specific subclass of TargetSubtarget.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This is a minimal scheduler strategy.
void sortRegionsByPressure(unsigned TargetOcc)
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries...
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:1205
#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:564
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:938
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.
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
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:255
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:33
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:377
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:149
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:1070
const MachineFrameInfo & MFI
GCNRPTracker::LiveRegSet getLiveRegsAfter(const MachineInstr &MI, const LiveIntervals &LIS)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:972
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:847
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:133
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:563
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:46
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:565
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:566
#define LLVM_DEBUG(X)
Definition: Debug.h:123
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:246