LLVM  7.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 "llvm/ADT/ArrayRef.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Support/Compiler.h"
23 #include "llvm/Support/Debug.h"
25 #include <algorithm>
26 #include <cassert>
27 #include <iterator>
28 #include <limits>
29 #include <memory>
30 #include <type_traits>
31 #include <vector>
32 
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "machine-scheduler"
36 
37 namespace llvm {
38 
39 std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
40  const ScheduleDAG &DAG);
41 
42  std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
43  const ScheduleDAG &DAG);
44 }
45 
46 // shim accessors for different order containers
48  return MI;
49 }
50 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
51  return SU->getInstr();
52 }
53 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
54  return SU.getInstr();
55 }
56 
57 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
59 static void printRegion(raw_ostream &OS,
62  const LiveIntervals *LIS,
63  unsigned MaxInstNum =
65  auto BB = Begin->getParent();
66  OS << BB->getParent()->getName() << ":" << printMBBReference(*BB) << ' '
67  << BB->getName() << ":\n";
68  auto I = Begin;
69  MaxInstNum = std::max(MaxInstNum, 1u);
70  for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
71  if (!I->isDebugValue() && LIS)
72  OS << LIS->getInstructionIndex(*I);
73  OS << '\t' << *I;
74  }
75  if (I != End) {
76  OS << "\t...\n";
77  I = std::prev(End);
78  if (!I->isDebugValue() && LIS)
79  OS << LIS->getInstructionIndex(*I);
80  OS << '\t' << *I;
81  }
82  if (End != BB->end()) { // print boundary inst if present
83  OS << "----\n";
84  if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
85  OS << *End;
86  }
87 }
88 
93  const LiveIntervals *LIS) {
94  const auto BB = Begin->getParent();
95  const auto &MRI = BB->getParent()->getRegInfo();
96 
97  const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
98  OS << "LIn RP: ";
99  getRegPressure(MRI, LiveIns).print(OS);
100 
101  const auto BottomMI = End == BB->end() ? std::prev(End) : End;
102  const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
103  OS << "LOt RP: ";
104  getRegPressure(MRI, LiveOuts).print(OS);
105 }
106 
109  const auto &ST = MF.getSubtarget<SISubtarget>();
110  for (const auto R : Regions) {
111  OS << "Region to schedule ";
112  printRegion(OS, R->Begin, R->End, LIS, 1);
113  printLivenessInfo(OS, R->Begin, R->End, LIS);
114  OS << "Max RP: ";
115  R->MaxPressure.print(OS, &ST);
116  }
117 }
118 
121  const Region *R,
122  const GCNRegPressure &RP) const {
123  OS << "\nAfter scheduling ";
124  printRegion(OS, R->Begin, R->End, LIS);
125  printSchedRP(OS, R->MaxPressure, RP);
126  OS << '\n';
127 }
128 
131  const GCNRegPressure &Before,
132  const GCNRegPressure &After) const {
133  const auto &ST = MF.getSubtarget<SISubtarget>();
134  OS << "RP before: ";
135  Before.print(OS, &ST);
136  OS << "RP after: ";
137  After.print(OS, &ST);
138 }
139 #endif
140 
141 // DAG builder helper
144  SmallVector<SUnit *, 8> TopRoots;
145 
146  SmallVector<SUnit*, 8> BotRoots;
147 public:
149  : Sch(_Sch) {
150  auto BB = R.Begin->getParent();
151  Sch.BaseClass::startBlock(BB);
152  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
153 
154  Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
155  /*TrackLaneMask*/true);
157  Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
158  }
159 
161  Sch.BaseClass::exitRegion();
162  Sch.BaseClass::finishBlock();
163  }
164 
166  return TopRoots;
167  }
169  return BotRoots;
170  }
171 };
172 
175  Region &Rgn;
176  std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
177  GCNRegPressure SaveMaxRP;
178 
179 public:
181  MachineSchedStrategy &OverrideStrategy,
182  GCNIterativeScheduler &_Sch)
183  : Sch(_Sch)
184  , Rgn(R)
185  , SaveSchedImpl(std::move(_Sch.SchedImpl))
186  , SaveMaxRP(R.MaxPressure) {
187  Sch.SchedImpl.reset(&OverrideStrategy);
188  auto BB = R.Begin->getParent();
189  Sch.BaseClass::startBlock(BB);
190  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
191  }
192 
194  Sch.BaseClass::exitRegion();
195  Sch.BaseClass::finishBlock();
196  Sch.SchedImpl.release();
197  Sch.SchedImpl = std::move(SaveSchedImpl);
198  }
199 
200  void schedule() {
201  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
202  DEBUG(dbgs() << "\nScheduling ";
203  printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
204  Sch.BaseClass::schedule();
205 
206  // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
207  Sch.RegionEnd = Rgn.End;
208  //assert(Rgn.End == Sch.RegionEnd);
209  Rgn.Begin = Sch.RegionBegin;
210  Rgn.MaxPressure.clear();
211  }
212 
213  void restoreOrder() {
214  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
215  // DAG SUnits are stored using original region's order
216  // so just use SUnits as the restoring schedule
217  Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
218  }
219 };
220 
221 namespace {
222 
223 // just a stub to make base class happy
224 class SchedStrategyStub : public MachineSchedStrategy {
225 public:
226  bool shouldTrackPressure() const override { return false; }
227  bool shouldTrackLaneMasks() const override { return false; }
228  void initialize(ScheduleDAGMI *DAG) override {}
229  SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
230  void schedNode(SUnit *SU, bool IsTopNode) override {}
231  void releaseTopNode(SUnit *SU) override {}
232  void releaseBottomNode(SUnit *SU) override {}
233 };
234 
235 } // end anonymous namespace
236 
238  StrategyKind S)
239  : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
240  , Context(C)
241  , Strategy(S)
242  , UPTracker(*LIS) {
243 }
244 
245 // returns max pressure for a region
249  const {
250  // For the purpose of pressure tracking bottom inst of the region should
251  // be also processed. End is either BB end, BB terminator inst or sched
252  // boundary inst.
253  auto const BBEnd = Begin->getParent()->end();
254  auto const BottomMI = End == BBEnd ? std::prev(End) : End;
255 
256  // scheduleRegions walks bottom to top, so its likely we just get next
257  // instruction to track
258  auto AfterBottomMI = std::next(BottomMI);
259  if (AfterBottomMI == BBEnd ||
260  &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
261  UPTracker.reset(*BottomMI);
262  } else {
264  }
265 
266  for (auto I = BottomMI; I != Begin; --I)
267  UPTracker.recede(*I);
268 
269  UPTracker.recede(*Begin);
270 
272  (dbgs() << "Tracked region ",
273  printRegion(dbgs(), Begin, End, LIS), false));
274  return UPTracker.moveMaxPressure();
275 }
276 
277 // returns max pressure for a tentative schedule
278 template <typename Range> GCNRegPressure
280  Range &&Schedule) const {
281  auto const BBEnd = R.Begin->getParent()->end();
283  if (R.End != BBEnd) {
284  // R.End points to the boundary instruction but the
285  // schedule doesn't include it
286  RPTracker.reset(*R.End);
287  RPTracker.recede(*R.End);
288  } else {
289  // R.End doesn't point to the boundary instruction
290  RPTracker.reset(*std::prev(BBEnd));
291  }
292  for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
293  RPTracker.recede(*getMachineInstr(*--I));
294  }
295  return RPTracker.moveMaxPressure();
296 }
297 
301  unsigned NumRegionInstrs) {
302  BaseClass::enterRegion(BB, Begin, End, NumRegionInstrs);
303  if (NumRegionInstrs > 2) {
304  Regions.push_back(
305  new (Alloc.Allocate())
306  Region { Begin, End, NumRegionInstrs,
307  getRegionPressure(Begin, End), nullptr });
308  }
309 }
310 
311 void GCNIterativeScheduler::schedule() { // overriden
312  // do nothing
313  DEBUG(
315  if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
316  dbgs() << "Max RP: ";
317  Regions.back()->MaxPressure.print(dbgs(), &MF.getSubtarget<SISubtarget>());
318  }
319  dbgs() << '\n';
320  );
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->isDebugValue())
387  LIS->handleMove(*MI, true);
388  }
389  if (!MI->isDebugValue()) {
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<SISubtarget>();
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<SISubtarget>();
436  std::sort(Regions.begin(), Regions.end(),
437  [&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<SISubtarget>();
454  const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
455  DEBUG(dbgs() << "Trying to 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  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  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  DEBUG(dbgs() << "New occupancy = " << NewOcc
479  << ", prev occupancy = " << Occ << '\n');
480  return std::max(NewOcc, Occ);
481 }
482 
484  bool TryMaximizeOccupancy) {
485  const auto &ST = MF.getSubtarget<SISubtarget>();
486  auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
487 
488  sortRegionsByPressure(TgtOcc);
489  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
490 
491  if (TryMaximizeOccupancy && Occ < TgtOcc)
492  Occ = tryMaximizeOccupancy(TgtOcc);
493 
494  // This is really weird but for some magic scheduling regions twice
495  // gives performance improvement
496  const int NumPasses = Occ < TgtOcc ? 2 : 1;
497 
498  TgtOcc = std::min(Occ, TgtOcc);
499  DEBUG(dbgs() << "Scheduling using default scheduler, "
500  "target occupancy = " << TgtOcc << '\n');
502 
503  for (int I = 0; I < NumPasses; ++I) {
504  // running first pass with TargetOccupancy = 0 mimics previous scheduling
505  // approach and is a performance magic
506  LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
507  for (auto R : Regions) {
508  OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
509 
510  Ovr.schedule();
511  const auto RP = getRegionPressure(*R);
512  DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
513 
514  if (RP.getOccupancy(ST) < TgtOcc) {
515  DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
516  if (R->BestSchedule.get() &&
517  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
518  DEBUG(dbgs() << ", scheduling minimal register\n");
519  scheduleBest(*R);
520  } else {
521  DEBUG(dbgs() << ", restoring\n");
522  Ovr.restoreOrder();
523  assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
524  }
525  }
526  }
527  }
528 }
529 
530 ///////////////////////////////////////////////////////////////////////////////
531 // Minimal Register Strategy
532 
534  const auto &ST = MF.getSubtarget<SISubtarget>();
535  const auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
536  sortRegionsByPressure(TgtOcc);
537 
538  auto MaxPressure = Regions.front()->MaxPressure;
539  for (auto R : Regions) {
540  if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
541  break;
542 
543  BuildDAG DAG(*R, *this);
544  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
545 
546  const auto RP = getSchedulePressure(*R, MinSchedule);
547  DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
548  dbgs() << "\nWarning: Pressure becomes worse after minreg!";
549  printSchedRP(dbgs(), R->MaxPressure, RP);
550  });
551 
552  if (!force && MaxPressure.less(ST, RP, TgtOcc))
553  break;
554 
555  scheduleRegion(*R, MinSchedule, RP);
556  DEBUG(printSchedResult(dbgs(), R, RP));
557 
558  MaxPressure = RP;
559  }
560 }
561 
562 ///////////////////////////////////////////////////////////////////////////////
563 // ILP scheduler port
564 
566  bool TryMaximizeOccupancy) {
567  const auto &ST = MF.getSubtarget<SISubtarget>();
568  auto TgtOcc = std::min(ST.getOccupancyWithLocalMemSize(MF),
569  ST.getWavesPerEU(MF.getFunction()).second);
570 
571  sortRegionsByPressure(TgtOcc);
572  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
573 
574  if (TryMaximizeOccupancy && Occ < TgtOcc)
575  Occ = tryMaximizeOccupancy(TgtOcc);
576 
577  TgtOcc = std::min(Occ, TgtOcc);
578  DEBUG(dbgs() << "Scheduling using default scheduler, "
579  "target occupancy = " << TgtOcc << '\n');
580 
581  for (auto R : Regions) {
582  BuildDAG DAG(*R, *this);
583  const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
584 
585  const auto RP = getSchedulePressure(*R, ILPSchedule);
586  DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
587 
588  if (RP.getOccupancy(ST) < TgtOcc) {
589  DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
590  if (R->BestSchedule.get() &&
591  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
592  DEBUG(dbgs() << ", scheduling minimal register\n");
593  scheduleBest(*R);
594  }
595  } else {
596  scheduleRegion(*R, ILPSchedule, RP);
597  DEBUG(printSchedResult(dbgs(), R, RP));
598  }
599  }
600 }
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
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
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
unsigned second
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:950
#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:570
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:920
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:255
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.
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)
void print(raw_ostream &OS, const SISubtarget *ST=nullptr) const
#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:378
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
static const unsigned End
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:842
GCNRPTracker::LiveRegSet getLiveRegsAfter(const MachineInstr &MI, const LiveIntervals &LIS)
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:862
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.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
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:60
LiveIntervals * LIS
BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:569
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 scheduleMinReg(bool force=false)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
MachineBasicBlock * BB
The block in which to insert instructions.
IRTranslator LLVM IR MI
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
void scheduleILP(bool TryMaximizeOccupancy=true)
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:571
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:572
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:247