LLVM  16.0.0git
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 ///
9 /// \file
10 /// This file implements the class GCNIterativeScheduler.
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 "machine-scheduler"
21 
22 namespace llvm {
23 
24 std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
25  const ScheduleDAG &DAG);
26 
27  std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
28  const ScheduleDAG &DAG);
29 }
30 
31 // shim accessors for different order containers
33  return MI;
34 }
35 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
36  return SU->getInstr();
37 }
38 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
39  return SU.getInstr();
40 }
41 
42 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
44 static void printRegion(raw_ostream &OS,
47  const LiveIntervals *LIS,
48  unsigned MaxInstNum =
50  auto BB = Begin->getParent();
51  OS << BB->getParent()->getName() << ":" << printMBBReference(*BB) << ' '
52  << BB->getName() << ":\n";
53  auto I = Begin;
54  MaxInstNum = std::max(MaxInstNum, 1u);
55  for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
56  if (!I->isDebugInstr() && LIS)
57  OS << LIS->getInstructionIndex(*I);
58  OS << '\t' << *I;
59  }
60  if (I != End) {
61  OS << "\t...\n";
62  I = std::prev(End);
63  if (!I->isDebugInstr() && LIS)
64  OS << LIS->getInstructionIndex(*I);
65  OS << '\t' << *I;
66  }
67  if (End != BB->end()) { // print boundary inst if present
68  OS << "----\n";
69  if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
70  OS << *End;
71  }
72 }
73 
78  const LiveIntervals *LIS) {
79  const auto BB = Begin->getParent();
80  const auto &MRI = BB->getParent()->getRegInfo();
81 
82  const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
83  OS << "LIn RP: " << print(getRegPressure(MRI, LiveIns));
84 
85  const auto BottomMI = End == BB->end() ? std::prev(End) : End;
86  const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
87  OS << "LOt RP: " << print(getRegPressure(MRI, LiveOuts));
88 }
89 
92  const auto &ST = MF.getSubtarget<GCNSubtarget>();
93  for (const auto R : Regions) {
94  OS << "Region to schedule ";
95  printRegion(OS, R->Begin, R->End, LIS, 1);
96  printLivenessInfo(OS, R->Begin, R->End, LIS);
97  OS << "Max RP: " << print(R->MaxPressure, &ST);
98  }
99 }
100 
103  const Region *R,
104  const GCNRegPressure &RP) const {
105  OS << "\nAfter scheduling ";
106  printRegion(OS, R->Begin, R->End, LIS);
107  printSchedRP(OS, R->MaxPressure, RP);
108  OS << '\n';
109 }
110 
113  const GCNRegPressure &Before,
114  const GCNRegPressure &After) const {
115  const auto &ST = MF.getSubtarget<GCNSubtarget>();
116  OS << "RP before: " << print(Before, &ST)
117  << "RP after: " << print(After, &ST);
118 }
119 #endif
120 
121 // DAG builder helper
124  SmallVector<SUnit *, 8> TopRoots;
125 
126  SmallVector<SUnit*, 8> BotRoots;
127 public:
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);
137  Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
138  }
139 
141  Sch.BaseClass::exitRegion();
142  Sch.BaseClass::finishBlock();
143  }
144 
146  return TopRoots;
147  }
149  return BotRoots;
150  }
151 };
152 
155  Region &Rgn;
156  std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
157  GCNRegPressure SaveMaxRP;
158 
159 public:
161  MachineSchedStrategy &OverrideStrategy,
162  GCNIterativeScheduler &_Sch)
163  : Sch(_Sch)
164  , Rgn(R)
165  , SaveSchedImpl(std::move(_Sch.SchedImpl))
166  , SaveMaxRP(R.MaxPressure) {
167  Sch.SchedImpl.reset(&OverrideStrategy);
168  auto BB = R.Begin->getParent();
169  Sch.BaseClass::startBlock(BB);
170  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
171  }
172 
174  Sch.BaseClass::exitRegion();
175  Sch.BaseClass::finishBlock();
176  Sch.SchedImpl.release();
177  Sch.SchedImpl = std::move(SaveSchedImpl);
178  }
179 
180  void schedule() {
181  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
182  LLVM_DEBUG(dbgs() << "\nScheduling ";
183  printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
184  Sch.BaseClass::schedule();
185 
186  // Unfortunately placeDebugValues incorrectly modifies RegionEnd, restore
187  Sch.RegionEnd = Rgn.End;
188  //assert(Rgn.End == Sch.RegionEnd);
189  Rgn.Begin = Sch.RegionBegin;
190  Rgn.MaxPressure.clear();
191  }
192 
193  void restoreOrder() {
194  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
195  // DAG SUnits are stored using original region's order
196  // so just use SUnits as the restoring schedule
197  Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
198  }
199 };
200 
201 namespace {
202 
203 // just a stub to make base class happy
204 class SchedStrategyStub : public MachineSchedStrategy {
205 public:
206  bool shouldTrackPressure() const override { return false; }
207  bool shouldTrackLaneMasks() const override { return false; }
208  void initialize(ScheduleDAGMI *DAG) override {}
209  SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
210  void schedNode(SUnit *SU, bool IsTopNode) override {}
211  void releaseTopNode(SUnit *SU) override {}
212  void releaseBottomNode(SUnit *SU) override {}
213 };
214 
215 } // end anonymous namespace
216 
218  StrategyKind S)
219  : BaseClass(C, std::make_unique<SchedStrategyStub>())
220  , Context(C)
221  , Strategy(S)
222  , UPTracker(*LIS) {
223 }
224 
225 // returns max pressure for a region
229  const {
230  // For the purpose of pressure tracking bottom inst of the region should
231  // be also processed. End is either BB end, BB terminator inst or sched
232  // boundary inst.
233  auto const BBEnd = Begin->getParent()->end();
234  auto const BottomMI = End == BBEnd ? std::prev(End) : End;
235 
236  // scheduleRegions walks bottom to top, so its likely we just get next
237  // instruction to track
238  auto AfterBottomMI = std::next(BottomMI);
239  if (AfterBottomMI == BBEnd ||
240  &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
241  UPTracker.reset(*BottomMI);
242  } else {
244  }
245 
246  for (auto I = BottomMI; I != Begin; --I)
247  UPTracker.recede(*I);
248 
249  UPTracker.recede(*Begin);
250 
252  (dbgs() << "Tracked region ",
253  printRegion(dbgs(), Begin, End, LIS), false));
254  return UPTracker.moveMaxPressure();
255 }
256 
257 // returns max pressure for a tentative schedule
258 template <typename Range> GCNRegPressure
260  Range &&Schedule) const {
261  auto const BBEnd = R.Begin->getParent()->end();
263  if (R.End != BBEnd) {
264  // R.End points to the boundary instruction but the
265  // schedule doesn't include it
266  RPTracker.reset(*R.End);
267  RPTracker.recede(*R.End);
268  } else {
269  // R.End doesn't point to the boundary instruction
270  RPTracker.reset(*std::prev(BBEnd));
271  }
272  for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
274  }
275  return RPTracker.moveMaxPressure();
276 }
277 
281  unsigned NumRegionInstrs) {
283  if (NumRegionInstrs > 2) {
284  Regions.push_back(
285  new (Alloc.Allocate())
286  Region { Begin, End, NumRegionInstrs,
287  getRegionPressure(Begin, End), nullptr });
288  }
289 }
290 
291 void GCNIterativeScheduler::schedule() { // overridden
292  // do nothing
294  if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
295  dbgs() << "Max RP: "
296  << print(Regions.back()->MaxPressure,
297  &MF.getSubtarget<GCNSubtarget>());
298  } dbgs()
299  << '\n';);
300 }
301 
303  if (Regions.empty())
304  return;
305  switch (Strategy) {
306  case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
307  case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
309  case SCHEDULE_ILP: scheduleILP(false); break;
310  }
311 }
312 
313 // Detach schedule from SUnits and interleave it with debug values.
314 // Returned schedule becomes independent of DAG state.
315 std::vector<MachineInstr*>
317  std::vector<MachineInstr*> Res;
318  Res.reserve(Schedule.size() * 2);
319 
320  if (FirstDbgValue)
321  Res.push_back(FirstDbgValue);
322 
323  const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
324  for (const auto *SU : Schedule) {
325  Res.push_back(SU->getInstr());
326  const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
327  return P.second == SU->getInstr();
328  });
329  if (D != DbgE)
330  Res.push_back(D->first);
331  }
332  return Res;
333 }
334 
336  ScheduleRef Schedule,
337  const GCNRegPressure &MaxRP) {
338  R.BestSchedule.reset(
339  new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
340 }
341 
343  assert(R.BestSchedule.get() && "No schedule specified");
344  scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
345  R.BestSchedule.reset();
346 }
347 
348 // minimal required region scheduler, works for ranges of SUnits*,
349 // SUnits or MachineIntrs*
350 template <typename Range>
352  const GCNRegPressure &MaxRP) {
353  assert(RegionBegin == R.Begin && RegionEnd == R.End);
354  assert(LIS != nullptr);
355 #ifndef NDEBUG
356  const auto SchedMaxRP = getSchedulePressure(R, Schedule);
357 #endif
358  auto BB = R.Begin->getParent();
359  auto Top = R.Begin;
360  for (const auto &I : Schedule) {
361  auto MI = getMachineInstr(I);
362  if (MI != &*Top) {
363  BB->remove(MI);
364  BB->insert(Top, MI);
365  if (!MI->isDebugInstr())
366  LIS->handleMove(*MI, true);
367  }
368  if (!MI->isDebugInstr()) {
369  // Reset read - undef flags and update them later.
370  for (auto &Op : MI->operands())
371  if (Op.isReg() && Op.isDef())
372  Op.setIsUndef(false);
373 
374  RegisterOperands RegOpers;
375  RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
376  /*IgnoreDead*/false);
377  // Adjust liveness and add missing dead+read-undef flags.
378  auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
379  RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
380  }
381  Top = std::next(MI->getIterator());
382  }
383  RegionBegin = getMachineInstr(Schedule.front());
384 
385  // Schedule consisting of MachineInstr* is considered 'detached'
386  // and already interleaved with debug values
387  if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
389  // Unfortunately placeDebugValues incorrectly modifies RegionEnd, restore
390  // assert(R.End == RegionEnd);
391  RegionEnd = R.End;
392  }
393 
394  R.Begin = RegionBegin;
395  R.MaxPressure = MaxRP;
396 
397 #ifndef NDEBUG
398  const auto RegionMaxRP = getRegionPressure(R);
399  const auto &ST = MF.getSubtarget<GCNSubtarget>();
400 #endif
401  assert(
402  (SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP)) ||
403  (dbgs() << "Max RP mismatch!!!\n"
404  "RP for schedule (calculated): "
405  << print(SchedMaxRP, &ST)
406  << "RP for schedule (reported): " << print(MaxRP, &ST)
407  << "RP after scheduling: " << print(RegionMaxRP, &ST),
408  false));
409 }
410 
411 // Sort recorded regions by pressure - highest at the front
413  const auto &ST = MF.getSubtarget<GCNSubtarget>();
414  llvm::sort(Regions, [&ST, TargetOcc](const Region *R1, const Region *R2) {
415  return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
416  });
417 }
418 
419 ///////////////////////////////////////////////////////////////////////////////
420 // Legacy MaxOccupancy Strategy
421 
422 // Tries to increase occupancy applying minreg scheduler for a sequence of
423 // most demanding regions. Obtained schedules are saved as BestSchedule for a
424 // region.
425 // TargetOcc is the best achievable occupancy for a kernel.
426 // Returns better occupancy on success or current occupancy on fail.
427 // BestSchedules aren't deleted on fail.
428 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
429  // TODO: assert Regions are sorted descending by pressure
430  const auto &ST = MF.getSubtarget<GCNSubtarget>();
431  const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
432  LLVM_DEBUG(dbgs() << "Trying to improve occupancy, target = " << TargetOcc
433  << ", current = " << Occ << '\n');
434 
435  auto NewOcc = TargetOcc;
436  for (auto *R : Regions) {
437  if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
438  break;
439 
440  LLVM_DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
441  printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
442 
443  BuildDAG DAG(*R, *this);
444  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
445  const auto MaxRP = getSchedulePressure(*R, MinSchedule);
446  LLVM_DEBUG(dbgs() << "Occupancy improvement attempt:\n";
447  printSchedRP(dbgs(), R->MaxPressure, MaxRP));
448 
449  NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
450  if (NewOcc <= Occ)
451  break;
452 
453  setBestSchedule(*R, MinSchedule, MaxRP);
454  }
455  LLVM_DEBUG(dbgs() << "New occupancy = " << NewOcc
456  << ", prev occupancy = " << Occ << '\n');
457  if (NewOcc > Occ) {
459  MFI->increaseOccupancy(MF, NewOcc);
460  }
461 
462  return std::max(NewOcc, Occ);
463 }
464 
466  bool TryMaximizeOccupancy) {
467  const auto &ST = MF.getSubtarget<GCNSubtarget>();
469  auto TgtOcc = MFI->getMinAllowedOccupancy();
470 
471  sortRegionsByPressure(TgtOcc);
472  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
473 
474  if (TryMaximizeOccupancy && Occ < TgtOcc)
475  Occ = tryMaximizeOccupancy(TgtOcc);
476 
477  // This is really weird but for some magic scheduling regions twice
478  // gives performance improvement
479  const int NumPasses = Occ < TgtOcc ? 2 : 1;
480 
481  TgtOcc = std::min(Occ, TgtOcc);
482  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
483  "target occupancy = "
484  << TgtOcc << '\n');
486  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
487 
488  for (int I = 0; I < NumPasses; ++I) {
489  // running first pass with TargetOccupancy = 0 mimics previous scheduling
490  // approach and is a performance magic
491  LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
492  for (auto *R : Regions) {
493  OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
494 
495  Ovr.schedule();
496  const auto RP = getRegionPressure(*R);
497  LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
498 
499  if (RP.getOccupancy(ST) < TgtOcc) {
500  LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
501  if (R->BestSchedule.get() &&
502  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
503  LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
504  scheduleBest(*R);
505  } else {
506  LLVM_DEBUG(dbgs() << ", restoring\n");
507  Ovr.restoreOrder();
508  assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
509  }
510  }
511  FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
512  }
513  }
514  MFI->limitOccupancy(FinalOccupancy);
515 }
516 
517 ///////////////////////////////////////////////////////////////////////////////
518 // Minimal Register Strategy
519 
521  const auto &ST = MF.getSubtarget<GCNSubtarget>();
523  const auto TgtOcc = MFI->getOccupancy();
524  sortRegionsByPressure(TgtOcc);
525 
526  auto MaxPressure = Regions.front()->MaxPressure;
527  for (auto *R : Regions) {
528  if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
529  break;
530 
531  BuildDAG DAG(*R, *this);
532  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
533 
534  const auto RP = getSchedulePressure(*R, MinSchedule);
535  LLVM_DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
536  dbgs() << "\nWarning: Pressure becomes worse after minreg!";
537  printSchedRP(dbgs(), R->MaxPressure, RP);
538  });
539 
540  if (!force && MaxPressure.less(ST, RP, TgtOcc))
541  break;
542 
543  scheduleRegion(*R, MinSchedule, RP);
545 
546  MaxPressure = RP;
547  }
548 }
549 
550 ///////////////////////////////////////////////////////////////////////////////
551 // ILP scheduler port
552 
554  bool TryMaximizeOccupancy) {
555  const auto &ST = MF.getSubtarget<GCNSubtarget>();
557  auto TgtOcc = MFI->getMinAllowedOccupancy();
558 
559  sortRegionsByPressure(TgtOcc);
560  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
561 
562  if (TryMaximizeOccupancy && Occ < TgtOcc)
563  Occ = tryMaximizeOccupancy(TgtOcc);
564 
565  TgtOcc = std::min(Occ, TgtOcc);
566  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
567  "target occupancy = "
568  << TgtOcc << '\n');
569 
570  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
571  for (auto *R : Regions) {
572  BuildDAG DAG(*R, *this);
573  const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
574 
575  const auto RP = getSchedulePressure(*R, ILPSchedule);
576  LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
577 
578  if (RP.getOccupancy(ST) < TgtOcc) {
579  LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
580  if (R->BestSchedule.get() &&
581  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
582  LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
583  scheduleBest(*R);
584  }
585  } else {
586  scheduleRegion(*R, ILPSchedule, RP);
588  FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
589  }
590  }
591  MFI->limitOccupancy(FinalOccupancy);
592 }
llvm::ScheduleDAGInstrs::FirstDbgValue
MachineInstr * FirstDbgValue
Definition: ScheduleDAGInstrs.h:250
llvm::GCNIterativeScheduler::TentativeSchedule
Definition: GCNIterativeScheduler.h:55
llvm::ScheduleDAG::MRI
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:560
llvm::GCNUpwardRPTracker::reset
void reset(const MachineInstr &MI, const LiveRegSet *LiveRegs=nullptr)
Definition: GCNRegPressure.cpp:265
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::GCNRegPressure
Definition: GCNRegPressure.h:30
llvm::GCNIterativeScheduler::tryMaximizeOccupancy
unsigned tryMaximizeOccupancy(unsigned TargetOcc=std::numeric_limits< unsigned >::max())
Definition: GCNIterativeScheduler.cpp:428
llvm::getLiveRegsBefore
GCNRPTracker::LiveRegSet getLiveRegsBefore(const MachineInstr &MI, const LiveIntervals &LIS)
Definition: GCNRegPressure.h:253
SIMachineFunctionInfo.h
llvm::getRegPressure
GCNRegPressure getRegPressure(const MachineRegisterInfo &MRI, Range &&LiveRegs)
Definition: GCNRegPressure.h:260
llvm::ScheduleDAGInstrs::buildSchedGraph
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
Definition: ScheduleDAGInstrs.cpp:720
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::RegisterOperands
List of registers defined and used by a machine instruction.
Definition: RegisterPressure.h:166
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::ScheduleDAGInstrs::NumRegionInstrs
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
Definition: ScheduleDAGInstrs.h:155
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:117
GCNSchedStrategy.h
llvm::GCNIterativeScheduler::SCHEDULE_ILP
@ SCHEDULE_ILP
Definition: GCNIterativeScheduler.h:37
llvm::GCNIterativeScheduler::SCHEDULE_MINREGONLY
@ SCHEDULE_MINREGONLY
Definition: GCNIterativeScheduler.h:34
llvm::GCNIterativeScheduler::SCHEDULE_LEGACYMAXOCCUPANCY
@ SCHEDULE_LEGACYMAXOCCUPANCY
Definition: GCNIterativeScheduler.h:36
llvm::ScheduleDAGInstrs::Topo
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
Definition: ScheduleDAGInstrs.h:242
llvm::GCNIterativeScheduler::getRegionPressure
GCNRegPressure getRegionPressure(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End) const
Definition: GCNIterativeScheduler.cpp:227
llvm::GCNIterativeScheduler::BuildDAG::getTopRoots
ArrayRef< const SUnit * > getTopRoots() const
Definition: GCNIterativeScheduler.cpp:145
llvm::GCNIterativeScheduler::Region::End
const MachineBasicBlock::iterator End
Definition: GCNIterativeScheduler.h:65
llvm::GCNSubtarget
Definition: GCNSubtarget.h:31
llvm::GCNIterativeScheduler::Regions
std::vector< Region * > Regions
Definition: GCNIterativeScheduler.h:74
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::GCNIterativeScheduler::schedule
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
Definition: GCNIterativeScheduler.cpp:291
initialize
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
Definition: TargetLibraryInfo.cpp:150
llvm::getLiveRegsAfter
GCNRPTracker::LiveRegSet getLiveRegsAfter(const MachineInstr &MI, const LiveIntervals &LIS)
Definition: GCNRegPressure.h:247
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
getMachineInstr
static MachineInstr * getMachineInstr(MachineInstr *MI)
Definition: GCNIterativeScheduler.cpp:32
llvm::LiveIntervals::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
Definition: LiveIntervals.h:220
llvm::LiveIntervals::handleMove
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
Definition: LiveIntervals.cpp:1508
llvm::GCNIterativeScheduler::printRegions
void printRegions(raw_ostream &OS) const
Definition: GCNIterativeScheduler.cpp:91
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::GCNUpwardRPTracker::recede
void recede(const MachineInstr &MI)
Definition: GCNRegPressure.cpp:270
llvm::GCNRPTracker::moveMaxPressure
decltype(MaxPressure) moveMaxPressure()
Definition: GCNRegPressure.h:132
GCNIterativeScheduler.h
R2
#define R2(n)
llvm::MachineSchedStrategy
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
Definition: MachineScheduler.h:208
llvm::GCNIterativeScheduler::finalizeSchedule
void finalizeSchedule() override
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
Definition: GCNIterativeScheduler.cpp:302
llvm::MachineBasicBlock::remove
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
Definition: MachineBasicBlock.h:989
llvm::GCNRPTracker::getLastTrackedMI
const MachineInstr * getLastTrackedMI() const
Definition: GCNRegPressure.h:127
llvm::GCNMaxOccupancySchedStrategy
The goal of this scheduling strategy is to maximize kernel occupancy (i.e.
Definition: GCNSchedStrategy.h:113
llvm::AArch64::RP
@ RP
Definition: AArch64ISelLowering.h:486
llvm::MachineFunction::getInfo
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
Definition: MachineFunction.h:755
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::GCNIterativeScheduler::OverrideLegacyStrategy::~OverrideLegacyStrategy
~OverrideLegacyStrategy()
Definition: GCNIterativeScheduler.cpp:173
llvm::GCNIterativeScheduler::printSchedResult
void printSchedResult(raw_ostream &OS, const Region *R, const GCNRegPressure &RP) const
Definition: GCNIterativeScheduler.cpp:102
llvm::GCNIterativeScheduler::OverrideLegacyStrategy::restoreOrder
void restoreOrder()
Definition: GCNIterativeScheduler.cpp:193
llvm::ScheduleDAGMI::findRootsAndBiasEdges
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
Definition: MachineScheduler.cpp:847
llvm::GCNIterativeScheduler::getSchedulePressure
GCNRegPressure getSchedulePressure(const Region &R, Range &&Schedule) const
Definition: GCNIterativeScheduler.cpp:259
llvm::GCNIterativeScheduler::Context
MachineSchedContext * Context
Definition: GCNIterativeScheduler.h:76
llvm::GCNIterativeScheduler::OverrideLegacyStrategy
Definition: GCNIterativeScheduler.cpp:153
llvm::GCNIterativeScheduler::BuildDAG::~BuildDAG
~BuildDAG()
Definition: GCNIterativeScheduler.cpp:140
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::makeMinRegSchedule
std::vector< const SUnit * > makeMinRegSchedule(ArrayRef< const SUnit * > TopRoots, const ScheduleDAG &DAG)
Definition: GCNMinRegStrategy.cpp:271
llvm::GCNIterativeScheduler::UPTracker
GCNUpwardRPTracker UPTracker
Definition: GCNIterativeScheduler.h:78
llvm::GCNIterativeScheduler::OverrideLegacyStrategy::schedule
void schedule()
Definition: GCNIterativeScheduler.cpp:180
llvm::GCNIterativeScheduler
Definition: GCNIterativeScheduler.h:29
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::GCNUpwardRPTracker
Definition: GCNRegPressure.h:143
llvm::GCNIterativeScheduler::scheduleRegion
void scheduleRegion(Region &R, Range &&Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
Definition: GCNIterativeScheduler.cpp:351
llvm::ScheduleDAGInstrs::RegionEnd
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
Definition: ScheduleDAGInstrs.h:152
force
therefore end up llgh r3 lr r0 br r14 but truncating the load would lh r3 br r14 Functions ret i64 and ought to be implemented ngr r0 br r14 but two address optimizations reverse the order of the AND and force
Definition: README.txt:112
llvm::ScheduleDAGMILive::RPTracker
RegPressureTracker RPTracker
Definition: MachineScheduler.h:415
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::RegisterOperands::collect
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...
Definition: RegisterPressure.cpp:570
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1657
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::ScheduleDAGMI::LIS
LiveIntervals * LIS
Definition: MachineScheduler.h:276
llvm::GCNIterativeScheduler::scheduleBest
void scheduleBest(Region &R)
Definition: GCNIterativeScheduler.cpp:342
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::GCNIterativeScheduler::BuildDAG::BuildDAG
BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
Definition: GCNIterativeScheduler.cpp:128
llvm::GCNIterativeScheduler::sortRegionsByPressure
void sortRegionsByPressure(unsigned TargetOcc)
Definition: GCNIterativeScheduler.cpp:412
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::RegPressureTracker::reset
void reset()
Definition: RegisterPressure.cpp:243
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::MachineSchedContext
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
Definition: MachineScheduler.h:127
llvm::GCNIterativeScheduler::SCHEDULE_MINREGFORCED
@ SCHEDULE_MINREGFORCED
Definition: GCNIterativeScheduler.h:35
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SUnit::getInstr
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
llvm::GCNRegPressure::empty
bool empty() const
Definition: GCNRegPressure.h:45
printLivenessInfo
static LLVM_DUMP_METHOD void printLivenessInfo(raw_ostream &OS, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, const LiveIntervals *LIS)
Definition: GCNIterativeScheduler.cpp:75
llvm::ScheduleDAGInstrs::MFI
const MachineFrameInfo & MFI
Definition: ScheduleDAGInstrs.h:123
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1836
llvm::ScheduleDAGMI::SchedImpl
std::unique_ptr< MachineSchedStrategy > SchedImpl
Definition: MachineScheduler.h:277
llvm::GCNIterativeScheduler::Alloc
SpecificBumpPtrAllocator< Region > Alloc
Definition: GCNIterativeScheduler.h:73
llvm::ScheduleDAGInstrs::DbgValues
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
Definition: ScheduleDAGInstrs.h:249
llvm::ScheduleDAGMI
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
Definition: MachineScheduler.h:273
llvm::ScheduleDAGMI::placeDebugValues
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
Definition: MachineScheduler.cpp:907
llvm::GCNSchedStrategy::setTargetOccupancy
void setTargetOccupancy(unsigned Occ)
Definition: GCNSchedStrategy.h:99
llvm::SlotIndex::getRegSlot
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:259
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
llvm::GCNIterativeScheduler::Region
Definition: GCNIterativeScheduler.h:60
llvm::ScheduleDAG
Definition: ScheduleDAG.h:554
llvm::GCNIterativeScheduler::Strategy
const StrategyKind Strategy
Definition: GCNIterativeScheduler.h:77
llvm::ScheduleDAG::TRI
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:558
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::ScheduleDAGMILive::enterRegion
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
Definition: MachineScheduler.cpp:989
llvm::GCNIterativeScheduler::scheduleLegacyMaxOccupancy
void scheduleLegacyMaxOccupancy(bool TryMaximizeOccupancy=true)
Definition: GCNIterativeScheduler.cpp:465
llvm::ScheduleDAG::MF
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:559
printRegion
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())
Definition: GCNIterativeScheduler.cpp:44
llvm::GCNIterativeScheduler::Region::MaxPressure
GCNRegPressure MaxPressure
Definition: GCNIterativeScheduler.h:67
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::makeGCNILPScheduler
std::vector< const SUnit * > makeGCNILPScheduler(ArrayRef< const SUnit * > BotRoots, const ScheduleDAG &DAG)
Definition: GCNILPSched.cpp:357
llvm::GCNIterativeScheduler::setBestSchedule
void setBestSchedule(Region &R, ScheduleRef Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
Definition: GCNIterativeScheduler.cpp:335
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1736
llvm::GCNIterativeScheduler::Region::Begin
MachineBasicBlock::iterator Begin
Definition: GCNIterativeScheduler.h:63
llvm::GCNIterativeScheduler::OverrideLegacyStrategy::OverrideLegacyStrategy
OverrideLegacyStrategy(Region &R, MachineSchedStrategy &OverrideStrategy, GCNIterativeScheduler &_Sch)
Definition: GCNIterativeScheduler.cpp:160
llvm::ScheduleDAG::SUnits
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:561
llvm::ScheduleDAGInstrs::RegionBegin
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
Definition: ScheduleDAGInstrs.h:149
std
Definition: BitVector.h:851
llvm::ScheduleDAGMI::AA
AAResults * AA
Definition: MachineScheduler.h:275
llvm::GCNIterativeScheduler::BuildDAG::getBottomRoots
ArrayRef< SUnit * > getBottomRoots() const
Definition: GCNIterativeScheduler.cpp:148
llvm::GCNIterativeScheduler::StrategyKind
StrategyKind
Definition: GCNIterativeScheduler.h:33
llvm::GCNUpwardRPTracker::isValid
bool isValid() const
Definition: GCNRegPressure.cpp:433
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1327
llvm::GCNIterativeScheduler::BuildDAG
Definition: GCNIterativeScheduler.cpp:122
llvm::ScheduleDAGTopologicalSort::InitDAGTopologicalSorting
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
Definition: ScheduleDAG.cpp:438
llvm::LiveIntervals
Definition: LiveIntervals.h:53
llvm::RegisterOperands::adjustLaneLiveness
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...
Definition: RegisterPressure.cpp:601
llvm::GCNIterativeScheduler::detachSchedule
std::vector< MachineInstr * > detachSchedule(ScheduleRef Schedule) const
Definition: GCNIterativeScheduler.cpp:316
llvm::ScheduleDAGInstrs::BB
MachineBasicBlock * BB
The block in which to insert instructions.
Definition: ScheduleDAGInstrs.h:146
llvm::GCNIterativeScheduler::enterRegion
void enterRegion(MachineBasicBlock *BB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned RegionInstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
Definition: GCNIterativeScheduler.cpp:278
llvm::GCNRegPressure::clear
void clear()
Definition: GCNRegPressure.h:47
llvm::GCNIterativeScheduler::scheduleILP
void scheduleILP(bool TryMaximizeOccupancy=true)
Definition: GCNIterativeScheduler.cpp:553
llvm::SIMachineFunctionInfo
This class keeps track of the SPI_SP_INPUT_ADDR config register, which tells the hardware which inter...
Definition: SIMachineFunctionInfo.h:338
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::GCNIterativeScheduler::GCNIterativeScheduler
GCNIterativeScheduler(MachineSchedContext *C, StrategyKind S)
Definition: GCNIterativeScheduler.cpp:217
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::ScheduleDAGMILive
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
Definition: MachineScheduler.h:392
llvm::GCNIterativeScheduler::scheduleMinReg
void scheduleMinReg(bool force=false)
Definition: GCNIterativeScheduler.cpp:520
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::GCNIterativeScheduler::printSchedRP
void printSchedRP(raw_ostream &OS, const GCNRegPressure &Before, const GCNRegPressure &After) const
Definition: GCNIterativeScheduler.cpp:112
llvm::RegPressureTracker::recede
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
Definition: RegisterPressure.cpp:874