LLVM  14.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: ";
84  getRegPressure(MRI, LiveIns).print(OS);
85 
86  const auto BottomMI = End == BB->end() ? std::prev(End) : End;
87  const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
88  OS << "LOt RP: ";
89  getRegPressure(MRI, LiveOuts).print(OS);
90 }
91 
94  const auto &ST = MF.getSubtarget<GCNSubtarget>();
95  for (const auto R : Regions) {
96  OS << "Region to schedule ";
97  printRegion(OS, R->Begin, R->End, LIS, 1);
98  printLivenessInfo(OS, R->Begin, R->End, LIS);
99  OS << "Max RP: ";
100  R->MaxPressure.print(OS, &ST);
101  }
102 }
103 
106  const Region *R,
107  const GCNRegPressure &RP) const {
108  OS << "\nAfter scheduling ";
109  printRegion(OS, R->Begin, R->End, LIS);
110  printSchedRP(OS, R->MaxPressure, RP);
111  OS << '\n';
112 }
113 
116  const GCNRegPressure &Before,
117  const GCNRegPressure &After) const {
118  const auto &ST = MF.getSubtarget<GCNSubtarget>();
119  OS << "RP before: ";
120  Before.print(OS, &ST);
121  OS << "RP after: ";
122  After.print(OS, &ST);
123 }
124 #endif
125 
126 // DAG builder helper
129  SmallVector<SUnit *, 8> TopRoots;
130 
131  SmallVector<SUnit*, 8> BotRoots;
132 public:
134  : Sch(_Sch) {
135  auto BB = R.Begin->getParent();
136  Sch.BaseClass::startBlock(BB);
137  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
138 
139  Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
140  /*TrackLaneMask*/true);
142  Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
143  }
144 
146  Sch.BaseClass::exitRegion();
147  Sch.BaseClass::finishBlock();
148  }
149 
151  return TopRoots;
152  }
154  return BotRoots;
155  }
156 };
157 
160  Region &Rgn;
161  std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
162  GCNRegPressure SaveMaxRP;
163 
164 public:
166  MachineSchedStrategy &OverrideStrategy,
167  GCNIterativeScheduler &_Sch)
168  : Sch(_Sch)
169  , Rgn(R)
170  , SaveSchedImpl(std::move(_Sch.SchedImpl))
171  , SaveMaxRP(R.MaxPressure) {
172  Sch.SchedImpl.reset(&OverrideStrategy);
173  auto BB = R.Begin->getParent();
174  Sch.BaseClass::startBlock(BB);
175  Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
176  }
177 
179  Sch.BaseClass::exitRegion();
180  Sch.BaseClass::finishBlock();
181  Sch.SchedImpl.release();
182  Sch.SchedImpl = std::move(SaveSchedImpl);
183  }
184 
185  void schedule() {
186  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
187  LLVM_DEBUG(dbgs() << "\nScheduling ";
188  printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
189  Sch.BaseClass::schedule();
190 
191  // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
192  Sch.RegionEnd = Rgn.End;
193  //assert(Rgn.End == Sch.RegionEnd);
194  Rgn.Begin = Sch.RegionBegin;
195  Rgn.MaxPressure.clear();
196  }
197 
198  void restoreOrder() {
199  assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
200  // DAG SUnits are stored using original region's order
201  // so just use SUnits as the restoring schedule
202  Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
203  }
204 };
205 
206 namespace {
207 
208 // just a stub to make base class happy
209 class SchedStrategyStub : public MachineSchedStrategy {
210 public:
211  bool shouldTrackPressure() const override { return false; }
212  bool shouldTrackLaneMasks() const override { return false; }
213  void initialize(ScheduleDAGMI *DAG) override {}
214  SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
215  void schedNode(SUnit *SU, bool IsTopNode) override {}
216  void releaseTopNode(SUnit *SU) override {}
217  void releaseBottomNode(SUnit *SU) override {}
218 };
219 
220 } // end anonymous namespace
221 
223  StrategyKind S)
224  : BaseClass(C, std::make_unique<SchedStrategyStub>())
225  , Context(C)
226  , Strategy(S)
227  , UPTracker(*LIS) {
228 }
229 
230 // returns max pressure for a region
234  const {
235  // For the purpose of pressure tracking bottom inst of the region should
236  // be also processed. End is either BB end, BB terminator inst or sched
237  // boundary inst.
238  auto const BBEnd = Begin->getParent()->end();
239  auto const BottomMI = End == BBEnd ? std::prev(End) : End;
240 
241  // scheduleRegions walks bottom to top, so its likely we just get next
242  // instruction to track
243  auto AfterBottomMI = std::next(BottomMI);
244  if (AfterBottomMI == BBEnd ||
245  &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
246  UPTracker.reset(*BottomMI);
247  } else {
249  }
250 
251  for (auto I = BottomMI; I != Begin; --I)
252  UPTracker.recede(*I);
253 
254  UPTracker.recede(*Begin);
255 
257  (dbgs() << "Tracked region ",
258  printRegion(dbgs(), Begin, End, LIS), false));
259  return UPTracker.moveMaxPressure();
260 }
261 
262 // returns max pressure for a tentative schedule
263 template <typename Range> GCNRegPressure
265  Range &&Schedule) const {
266  auto const BBEnd = R.Begin->getParent()->end();
268  if (R.End != BBEnd) {
269  // R.End points to the boundary instruction but the
270  // schedule doesn't include it
271  RPTracker.reset(*R.End);
272  RPTracker.recede(*R.End);
273  } else {
274  // R.End doesn't point to the boundary instruction
275  RPTracker.reset(*std::prev(BBEnd));
276  }
277  for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
279  }
280  return RPTracker.moveMaxPressure();
281 }
282 
286  unsigned NumRegionInstrs) {
288  if (NumRegionInstrs > 2) {
289  Regions.push_back(
290  new (Alloc.Allocate())
291  Region { Begin, End, NumRegionInstrs,
292  getRegionPressure(Begin, End), nullptr });
293  }
294 }
295 
296 void GCNIterativeScheduler::schedule() { // overriden
297  // do nothing
299  if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
300  dbgs() << "Max RP: ";
301  Regions.back()->MaxPressure.print(
302  dbgs(), &MF.getSubtarget<GCNSubtarget>());
303  } dbgs()
304  << '\n';);
305 }
306 
308  if (Regions.empty())
309  return;
310  switch (Strategy) {
311  case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
312  case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
314  case SCHEDULE_ILP: scheduleILP(false); break;
315  }
316 }
317 
318 // Detach schedule from SUnits and interleave it with debug values.
319 // Returned schedule becomes independent of DAG state.
320 std::vector<MachineInstr*>
322  std::vector<MachineInstr*> Res;
323  Res.reserve(Schedule.size() * 2);
324 
325  if (FirstDbgValue)
326  Res.push_back(FirstDbgValue);
327 
328  const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
329  for (auto SU : Schedule) {
330  Res.push_back(SU->getInstr());
331  const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
332  return P.second == SU->getInstr();
333  });
334  if (D != DbgE)
335  Res.push_back(D->first);
336  }
337  return Res;
338 }
339 
341  ScheduleRef Schedule,
342  const GCNRegPressure &MaxRP) {
343  R.BestSchedule.reset(
344  new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
345 }
346 
348  assert(R.BestSchedule.get() && "No schedule specified");
349  scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
350  R.BestSchedule.reset();
351 }
352 
353 // minimal required region scheduler, works for ranges of SUnits*,
354 // SUnits or MachineIntrs*
355 template <typename Range>
357  const GCNRegPressure &MaxRP) {
358  assert(RegionBegin == R.Begin && RegionEnd == R.End);
359  assert(LIS != nullptr);
360 #ifndef NDEBUG
361  const auto SchedMaxRP = getSchedulePressure(R, Schedule);
362 #endif
363  auto BB = R.Begin->getParent();
364  auto Top = R.Begin;
365  for (const auto &I : Schedule) {
366  auto MI = getMachineInstr(I);
367  if (MI != &*Top) {
368  BB->remove(MI);
369  BB->insert(Top, MI);
370  if (!MI->isDebugInstr())
371  LIS->handleMove(*MI, true);
372  }
373  if (!MI->isDebugInstr()) {
374  // Reset read - undef flags and update them later.
375  for (auto &Op : MI->operands())
376  if (Op.isReg() && Op.isDef())
377  Op.setIsUndef(false);
378 
379  RegisterOperands RegOpers;
380  RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
381  /*IgnoreDead*/false);
382  // Adjust liveness and add missing dead+read-undef flags.
383  auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
384  RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
385  }
386  Top = std::next(MI->getIterator());
387  }
388  RegionBegin = getMachineInstr(Schedule.front());
389 
390  // Schedule consisting of MachineInstr* is considered 'detached'
391  // and already interleaved with debug values
392  if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
394  // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
395  //assert(R.End == RegionEnd);
396  RegionEnd = R.End;
397  }
398 
399  R.Begin = RegionBegin;
400  R.MaxPressure = MaxRP;
401 
402 #ifndef NDEBUG
403  const auto RegionMaxRP = getRegionPressure(R);
404  const auto &ST = MF.getSubtarget<GCNSubtarget>();
405 #endif
406  assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
407  || (dbgs() << "Max RP mismatch!!!\n"
408  "RP for schedule (calculated): ",
409  SchedMaxRP.print(dbgs(), &ST),
410  dbgs() << "RP for schedule (reported): ",
411  MaxRP.print(dbgs(), &ST),
412  dbgs() << "RP after scheduling: ",
413  RegionMaxRP.print(dbgs(), &ST),
414  false));
415 }
416 
417 // Sort recorded regions by pressure - highest at the front
419  const auto &ST = MF.getSubtarget<GCNSubtarget>();
420  llvm::sort(Regions, [&ST, TargetOcc](const Region *R1, const Region *R2) {
421  return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
422  });
423 }
424 
425 ///////////////////////////////////////////////////////////////////////////////
426 // Legacy MaxOccupancy Strategy
427 
428 // Tries to increase occupancy applying minreg scheduler for a sequence of
429 // most demanding regions. Obtained schedules are saved as BestSchedule for a
430 // region.
431 // TargetOcc is the best achievable occupancy for a kernel.
432 // Returns better occupancy on success or current occupancy on fail.
433 // BestSchedules aren't deleted on fail.
434 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
435  // TODO: assert Regions are sorted descending by pressure
436  const auto &ST = MF.getSubtarget<GCNSubtarget>();
437  const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
438  LLVM_DEBUG(dbgs() << "Trying to improve occupancy, target = " << TargetOcc
439  << ", current = " << Occ << '\n');
440 
441  auto NewOcc = TargetOcc;
442  for (auto R : Regions) {
443  if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
444  break;
445 
446  LLVM_DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
447  printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
448 
449  BuildDAG DAG(*R, *this);
450  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
451  const auto MaxRP = getSchedulePressure(*R, MinSchedule);
452  LLVM_DEBUG(dbgs() << "Occupancy improvement attempt:\n";
453  printSchedRP(dbgs(), R->MaxPressure, MaxRP));
454 
455  NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
456  if (NewOcc <= Occ)
457  break;
458 
459  setBestSchedule(*R, MinSchedule, MaxRP);
460  }
461  LLVM_DEBUG(dbgs() << "New occupancy = " << NewOcc
462  << ", prev occupancy = " << Occ << '\n');
463  if (NewOcc > Occ) {
465  MFI->increaseOccupancy(MF, NewOcc);
466  }
467 
468  return std::max(NewOcc, Occ);
469 }
470 
472  bool TryMaximizeOccupancy) {
473  const auto &ST = MF.getSubtarget<GCNSubtarget>();
475  auto TgtOcc = MFI->getMinAllowedOccupancy();
476 
477  sortRegionsByPressure(TgtOcc);
478  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
479 
480  if (TryMaximizeOccupancy && Occ < TgtOcc)
481  Occ = tryMaximizeOccupancy(TgtOcc);
482 
483  // This is really weird but for some magic scheduling regions twice
484  // gives performance improvement
485  const int NumPasses = Occ < TgtOcc ? 2 : 1;
486 
487  TgtOcc = std::min(Occ, TgtOcc);
488  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
489  "target occupancy = "
490  << TgtOcc << '\n');
492  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
493 
494  for (int I = 0; I < NumPasses; ++I) {
495  // running first pass with TargetOccupancy = 0 mimics previous scheduling
496  // approach and is a performance magic
497  LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
498  for (auto R : Regions) {
499  OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
500 
501  Ovr.schedule();
502  const auto RP = getRegionPressure(*R);
503  LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
504 
505  if (RP.getOccupancy(ST) < TgtOcc) {
506  LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
507  if (R->BestSchedule.get() &&
508  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
509  LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
510  scheduleBest(*R);
511  } else {
512  LLVM_DEBUG(dbgs() << ", restoring\n");
513  Ovr.restoreOrder();
514  assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
515  }
516  }
517  FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
518  }
519  }
520  MFI->limitOccupancy(FinalOccupancy);
521 }
522 
523 ///////////////////////////////////////////////////////////////////////////////
524 // Minimal Register Strategy
525 
527  const auto &ST = MF.getSubtarget<GCNSubtarget>();
529  const auto TgtOcc = MFI->getOccupancy();
530  sortRegionsByPressure(TgtOcc);
531 
532  auto MaxPressure = Regions.front()->MaxPressure;
533  for (auto R : Regions) {
534  if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
535  break;
536 
537  BuildDAG DAG(*R, *this);
538  const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
539 
540  const auto RP = getSchedulePressure(*R, MinSchedule);
541  LLVM_DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
542  dbgs() << "\nWarning: Pressure becomes worse after minreg!";
543  printSchedRP(dbgs(), R->MaxPressure, RP);
544  });
545 
546  if (!force && MaxPressure.less(ST, RP, TgtOcc))
547  break;
548 
549  scheduleRegion(*R, MinSchedule, RP);
551 
552  MaxPressure = RP;
553  }
554 }
555 
556 ///////////////////////////////////////////////////////////////////////////////
557 // ILP scheduler port
558 
560  bool TryMaximizeOccupancy) {
561  const auto &ST = MF.getSubtarget<GCNSubtarget>();
563  auto TgtOcc = MFI->getMinAllowedOccupancy();
564 
565  sortRegionsByPressure(TgtOcc);
566  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
567 
568  if (TryMaximizeOccupancy && Occ < TgtOcc)
569  Occ = tryMaximizeOccupancy(TgtOcc);
570 
571  TgtOcc = std::min(Occ, TgtOcc);
572  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
573  "target occupancy = "
574  << TgtOcc << '\n');
575 
576  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
577  for (auto R : Regions) {
578  BuildDAG DAG(*R, *this);
579  const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
580 
581  const auto RP = getSchedulePressure(*R, ILPSchedule);
582  LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
583 
584  if (RP.getOccupancy(ST) < TgtOcc) {
585  LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
586  if (R->BestSchedule.get() &&
587  R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
588  LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
589  scheduleBest(*R);
590  }
591  } else {
592  scheduleRegion(*R, ILPSchedule, RP);
594  FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
595  }
596  }
597  MFI->limitOccupancy(FinalOccupancy);
598 }
llvm::ScheduleDAGInstrs::FirstDbgValue
MachineInstr * FirstDbgValue
Definition: ScheduleDAGInstrs.h:249
llvm::GCNIterativeScheduler::TentativeSchedule
Definition: GCNIterativeScheduler.h:55
llvm::ScheduleDAG::MRI
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:561
llvm::GCNUpwardRPTracker::reset
void reset(const MachineInstr &MI, const LiveRegSet *LiveRegs=nullptr)
Definition: GCNRegPressure.cpp:294
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
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:506
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::GCNRegPressure
Definition: GCNRegPressure.h:30
llvm::GCNIterativeScheduler::tryMaximizeOccupancy
unsigned tryMaximizeOccupancy(unsigned TargetOcc=std::numeric_limits< unsigned >::max())
Definition: GCNIterativeScheduler.cpp:434
llvm::getLiveRegsBefore
GCNRPTracker::LiveRegSet getLiveRegsBefore(const MachineInstr &MI, const LiveIntervals &LIS)
Definition: GCNRegPressure.h:255
SIMachineFunctionInfo.h
llvm::getRegPressure
GCNRegPressure getRegPressure(const MachineRegisterInfo &MRI, Range &&LiveRegs)
Definition: GCNRegPressure.h:262
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:725
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:167
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::ScheduleDAGInstrs::NumRegionInstrs
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
Definition: ScheduleDAGInstrs.h:154
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:119
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:241
llvm::GCNIterativeScheduler::getRegionPressure
GCNRegPressure getRegionPressure(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End) const
Definition: GCNIterativeScheduler.cpp:232
llvm::GCNIterativeScheduler::BuildDAG::getTopRoots
ArrayRef< const SUnit * > getTopRoots() const
Definition: GCNIterativeScheduler.cpp:150
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::GCNIterativeScheduler::schedule
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
Definition: GCNIterativeScheduler.cpp:296
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:116
llvm::getLiveRegsAfter
GCNRPTracker::LiveRegSet getLiveRegsAfter(const MachineInstr &MI, const LiveIntervals &LIS)
Definition: GCNRegPressure.h:249
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:226
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:1512
llvm::GCNIterativeScheduler::printRegions
void printRegions(raw_ostream &OS) const
Definition: GCNIterativeScheduler.cpp:93
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:299
llvm::GCNRPTracker::moveMaxPressure
decltype(MaxPressure) moveMaxPressure()
Definition: GCNRegPressure.h:131
GCNIterativeScheduler.h
R2
#define R2(n)
llvm::MachineSchedStrategy
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
Definition: MachineScheduler.h:201
llvm::GCNIterativeScheduler::finalizeSchedule
void finalizeSchedule() override
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
Definition: GCNIterativeScheduler.cpp:307
llvm::MachineBasicBlock::remove
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
Definition: MachineBasicBlock.h:930
llvm::GCNRPTracker::getLastTrackedMI
const MachineInstr * getLastTrackedMI() const
Definition: GCNRegPressure.h:126
llvm::GCNMaxOccupancySchedStrategy
This is a minimal scheduler strategy.
Definition: GCNSchedStrategy.h:29
llvm::AArch64::RP
@ RP
Definition: AArch64ISelLowering.h:475
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:732
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::GCNIterativeScheduler::OverrideLegacyStrategy::~OverrideLegacyStrategy
~OverrideLegacyStrategy()
Definition: GCNIterativeScheduler.cpp:178
llvm::GCNIterativeScheduler::printSchedResult
void printSchedResult(raw_ostream &OS, const Region *R, const GCNRegPressure &RP) const
Definition: GCNIterativeScheduler.cpp:105
llvm::GCNIterativeScheduler::OverrideLegacyStrategy::restoreOrder
void restoreOrder()
Definition: GCNIterativeScheduler.cpp:198
llvm::ScheduleDAGMI::findRootsAndBiasEdges
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
Definition: MachineScheduler.cpp:846
llvm::GCNIterativeScheduler::getSchedulePressure
GCNRegPressure getSchedulePressure(const Region &R, Range &&Schedule) const
Definition: GCNIterativeScheduler.cpp:264
llvm::GCNIterativeScheduler::Context
MachineSchedContext * Context
Definition: GCNIterativeScheduler.h:76
llvm::GCNIterativeScheduler::OverrideLegacyStrategy
Definition: GCNIterativeScheduler.cpp:158
llvm::GCNIterativeScheduler::BuildDAG::~BuildDAG
~BuildDAG()
Definition: GCNIterativeScheduler.cpp:145
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:185
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:145
llvm::GCNIterativeScheduler::scheduleRegion
void scheduleRegion(Region &R, Range &&Schedule, const GCNRegPressure &MaxRP=GCNRegPressure())
Definition: GCNIterativeScheduler.cpp:356
llvm::ScheduleDAGInstrs::RegionEnd
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
Definition: ScheduleDAGInstrs.h:151
llvm::GCNMaxOccupancySchedStrategy::setTargetOccupancy
void setTargetOccupancy(unsigned Occ)
Definition: GCNSchedStrategy.h:70
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:408
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
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::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:634
llvm::ScheduleDAGMI::LIS
LiveIntervals * LIS
Definition: MachineScheduler.h:269
llvm::GCNIterativeScheduler::scheduleBest
void scheduleBest(Region &R)
Definition: GCNIterativeScheduler.cpp:347
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::GCNIterativeScheduler::BuildDAG::BuildDAG
BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
Definition: GCNIterativeScheduler.cpp:133
llvm::GCNIterativeScheduler::sortRegionsByPressure
void sortRegionsByPressure(unsigned TargetOcc)
Definition: GCNIterativeScheduler.cpp:418
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:120
llvm::GCNIterativeScheduler::SCHEDULE_MINREGFORCED
@ SCHEDULE_MINREGFORCED
Definition: GCNIterativeScheduler.h:35
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:122
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:1609
llvm::ScheduleDAGMI::SchedImpl
std::unique_ptr< MachineSchedStrategy > SchedImpl
Definition: MachineScheduler.h:270
llvm::GCNIterativeScheduler::Alloc
SpecificBumpPtrAllocator< Region > Alloc
Definition: GCNIterativeScheduler.h:73
llvm::ScheduleDAGInstrs::DbgValues
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
Definition: ScheduleDAGInstrs.h:248
llvm::ScheduleDAGMI
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
Definition: MachineScheduler.h:266
llvm::ScheduleDAGMI::placeDebugValues
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
Definition: MachineScheduler.cpp:906
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:254
llvm::GCNIterativeScheduler::Region
Definition: GCNIterativeScheduler.h:60
llvm::ScheduleDAG
Definition: ScheduleDAG.h:555
llvm::GCNIterativeScheduler::Strategy
const StrategyKind Strategy
Definition: GCNIterativeScheduler.h:77
llvm::ScheduleDAG::TRI
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:559
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:990
llvm::GCNIterativeScheduler::scheduleLegacyMaxOccupancy
void scheduleLegacyMaxOccupancy(bool TryMaximizeOccupancy=true)
Definition: GCNIterativeScheduler.cpp:471
llvm::ScheduleDAG::MF
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:560
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:340
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:1578
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:165
llvm::ScheduleDAG::SUnits
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
llvm::ScheduleDAGInstrs::RegionBegin
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
Definition: ScheduleDAGInstrs.h:148
std
Definition: BitVector.h:838
llvm::ScheduleDAGMI::AA
AAResults * AA
Definition: MachineScheduler.h:268
llvm::GCNIterativeScheduler::BuildDAG::getBottomRoots
ArrayRef< SUnit * > getBottomRoots() const
Definition: GCNIterativeScheduler.cpp:153
llvm::GCNIterativeScheduler::StrategyKind
StrategyKind
Definition: GCNIterativeScheduler.h:33
llvm::GCNUpwardRPTracker::isValid
bool isValid() const
Definition: GCNRegPressure.cpp:462
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
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:1317
llvm::GCNIterativeScheduler::BuildDAG
Definition: GCNIterativeScheduler.cpp:127
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
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:54
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:321
llvm::ScheduleDAGInstrs::BB
MachineBasicBlock * BB
The block in which to insert instructions.
Definition: ScheduleDAGInstrs.h:145
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:283
llvm::GCNRegPressure::clear
void clear()
Definition: GCNRegPressure.h:47
llvm::GCNIterativeScheduler::scheduleILP
void scheduleILP(bool TryMaximizeOccupancy=true)
Definition: GCNIterativeScheduler.cpp:559
llvm::SIMachineFunctionInfo
This class keeps track of the SPI_SP_INPUT_ADDR config register, which tells the hardware which inter...
Definition: SIMachineFunctionInfo.h:335
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::GCNIterativeScheduler::GCNIterativeScheduler
GCNIterativeScheduler(MachineSchedContext *C, StrategyKind S)
Definition: GCNIterativeScheduler.cpp:222
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:385
llvm::GCNRegPressure::print
void print(raw_ostream &OS, const GCNSubtarget *ST=nullptr) const
Definition: GCNRegPressure.cpp:172
llvm::GCNIterativeScheduler::scheduleMinReg
void scheduleMinReg(bool force=false)
Definition: GCNIterativeScheduler.cpp:526
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::GCNIterativeScheduler::printSchedRP
void printSchedRP(raw_ostream &OS, const GCNRegPressure &Before, const GCNRegPressure &After) const
Definition: GCNIterativeScheduler.cpp:115
llvm::RegPressureTracker::recede
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
Definition: RegisterPressure.cpp:874