LLVM  10.0.0svn
PostRASchedulerList.cpp
Go to the documentation of this file.
1 //===----- SchedulePostRAList.cpp - list scheduler ------------------------===//
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 // This implements a top-down list scheduler, using standard algorithms.
10 // The basic approach uses a priority queue of available nodes to schedule.
11 // One at a time, nodes are taken from the priority queue (thus in priority
12 // order), checked for legality to schedule, and emitted if legal.
13 //
14 // Nodes may not be legal to schedule either due to structural hazards (e.g.
15 // pipeline or resource constraints) or because an input to the instruction has
16 // not completed execution.
17 //
18 //===----------------------------------------------------------------------===//
19 
21 #include "AntiDepBreaker.h"
22 #include "CriticalAntiDepBreaker.h"
23 #include "llvm/ADT/Statistic.h"
30 #include "llvm/CodeGen/Passes.h"
40 #include "llvm/Config/llvm-config.h"
42 #include "llvm/Support/Debug.h"
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "post-RA-sched"
48 
49 STATISTIC(NumNoops, "Number of noops inserted");
50 STATISTIC(NumStalls, "Number of pipeline stalls");
51 STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies");
52 
53 // Post-RA scheduling is enabled with
54 // TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to
55 // override the target.
56 static cl::opt<bool>
57 EnablePostRAScheduler("post-RA-scheduler",
58  cl::desc("Enable scheduling after register allocation"),
59  cl::init(false), cl::Hidden);
61 EnableAntiDepBreaking("break-anti-dependencies",
62  cl::desc("Break post-RA scheduling anti-dependencies: "
63  "\"critical\", \"all\", or \"none\""),
64  cl::init("none"), cl::Hidden);
65 
66 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
67 static cl::opt<int>
68 DebugDiv("postra-sched-debugdiv",
69  cl::desc("Debug control MBBs that are scheduled"),
70  cl::init(0), cl::Hidden);
71 static cl::opt<int>
72 DebugMod("postra-sched-debugmod",
73  cl::desc("Debug control MBBs that are scheduled"),
74  cl::init(0), cl::Hidden);
75 
77 
78 namespace {
79  class PostRAScheduler : public MachineFunctionPass {
80  const TargetInstrInfo *TII;
81  RegisterClassInfo RegClassInfo;
82 
83  public:
84  static char ID;
85  PostRAScheduler() : MachineFunctionPass(ID) {}
86 
87  void getAnalysisUsage(AnalysisUsage &AU) const override {
88  AU.setPreservesCFG();
96  }
97 
98  MachineFunctionProperties getRequiredProperties() const override {
101  }
102 
103  bool runOnMachineFunction(MachineFunction &Fn) override;
104 
105  private:
106  bool enablePostRAScheduler(
107  const TargetSubtargetInfo &ST, CodeGenOpt::Level OptLevel,
109  TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const;
110  };
111  char PostRAScheduler::ID = 0;
112 
113  class SchedulePostRATDList : public ScheduleDAGInstrs {
114  /// AvailableQueue - The priority queue to use for the available SUnits.
115  ///
116  LatencyPriorityQueue AvailableQueue;
117 
118  /// PendingQueue - This contains all of the instructions whose operands have
119  /// been issued, but their results are not ready yet (due to the latency of
120  /// the operation). Once the operands becomes available, the instruction is
121  /// added to the AvailableQueue.
122  std::vector<SUnit*> PendingQueue;
123 
124  /// HazardRec - The hazard recognizer to use.
125  ScheduleHazardRecognizer *HazardRec;
126 
127  /// AntiDepBreak - Anti-dependence breaking object, or NULL if none
128  AntiDepBreaker *AntiDepBreak;
129 
130  /// AA - AliasAnalysis for making memory reference queries.
131  AliasAnalysis *AA;
132 
133  /// The schedule. Null SUnit*'s represent noop instructions.
134  std::vector<SUnit*> Sequence;
135 
136  /// Ordered list of DAG postprocessing steps.
137  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
138 
139  /// The index in BB of RegionEnd.
140  ///
141  /// This is the instruction number from the top of the current block, not
142  /// the SlotIndex. It is only used by the AntiDepBreaker.
143  unsigned EndIndex;
144 
145  public:
146  SchedulePostRATDList(
148  const RegisterClassInfo &,
151 
152  ~SchedulePostRATDList() override;
153 
154  /// startBlock - Initialize register live-range state for scheduling in
155  /// this block.
156  ///
157  void startBlock(MachineBasicBlock *BB) override;
158 
159  // Set the index of RegionEnd within the current BB.
160  void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; }
161 
162  /// Initialize the scheduler state for the next scheduling region.
163  void enterRegion(MachineBasicBlock *bb,
166  unsigned regioninstrs) override;
167 
168  /// Notify that the scheduler has finished scheduling the current region.
169  void exitRegion() override;
170 
171  /// Schedule - Schedule the instruction range using list scheduling.
172  ///
173  void schedule() override;
174 
175  void EmitSchedule();
176 
177  /// Observe - Update liveness information to account for the current
178  /// instruction, which will not be scheduled.
179  ///
180  void Observe(MachineInstr &MI, unsigned Count);
181 
182  /// finishBlock - Clean up register live-range state.
183  ///
184  void finishBlock() override;
185 
186  private:
187  /// Apply each ScheduleDAGMutation step in order.
188  void postprocessDAG();
189 
190  void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
191  void ReleaseSuccessors(SUnit *SU);
192  void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
193  void ListScheduleTopDown();
194 
195  void dumpSchedule() const;
196  void emitNoop(unsigned CurCycle);
197  };
198 }
199 
201 
202 INITIALIZE_PASS(PostRAScheduler, DEBUG_TYPE,
203  "Post RA top-down list latency scheduler", false, false)
204 
205 SchedulePostRATDList::SchedulePostRATDList(
208  TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
209  SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
210  : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) {
211 
212  const InstrItineraryData *InstrItins =
213  MF.getSubtarget().getInstrItineraryData();
214  HazardRec =
215  MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
216  InstrItins, this);
217  MF.getSubtarget().getPostRAMutations(Mutations);
218 
219  assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||
220  MRI.tracksLiveness()) &&
221  "Live-ins must be accurate for anti-dependency breaking");
222  AntiDepBreak =
223  ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ?
224  (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) :
225  ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ?
226  (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : nullptr));
227 }
228 
229 SchedulePostRATDList::~SchedulePostRATDList() {
230  delete HazardRec;
231  delete AntiDepBreak;
232 }
233 
234 /// Initialize state associated with the next scheduling region.
235 void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb,
238  unsigned regioninstrs) {
239  ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
240  Sequence.clear();
241 }
242 
243 /// Print the schedule before exiting the region.
244 void SchedulePostRATDList::exitRegion() {
245  LLVM_DEBUG({
246  dbgs() << "*** Final schedule ***\n";
247  dumpSchedule();
248  dbgs() << '\n';
249  });
251 }
252 
253 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
254 /// dumpSchedule - dump the scheduled Sequence.
255 LLVM_DUMP_METHOD void SchedulePostRATDList::dumpSchedule() const {
256  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
257  if (SUnit *SU = Sequence[i])
258  dumpNode(*SU);
259  else
260  dbgs() << "**** NOOP ****\n";
261  }
262 }
263 #endif
264 
265 bool PostRAScheduler::enablePostRAScheduler(
266  const TargetSubtargetInfo &ST,
267  CodeGenOpt::Level OptLevel,
269  TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const {
270  Mode = ST.getAntiDepBreakMode();
271  ST.getCriticalPathRCs(CriticalPathRCs);
272 
273  // Check for explicit enable/disable of post-ra scheduling.
274  if (EnablePostRAScheduler.getPosition() > 0)
275  return EnablePostRAScheduler;
276 
277  return ST.enablePostRAScheduler() &&
278  OptLevel >= ST.getOptLevelToEnablePostRAScheduler();
279 }
280 
281 bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
282  if (skipFunction(Fn.getFunction()))
283  return false;
284 
285  TII = Fn.getSubtarget().getInstrInfo();
286  MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
287  AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
288  TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
289 
290  RegClassInfo.runOnMachineFunction(Fn);
291 
293  TargetSubtargetInfo::ANTIDEP_NONE;
295 
296  // Check that post-RA scheduling is enabled for this target.
297  // This may upgrade the AntiDepMode.
298  if (!enablePostRAScheduler(Fn.getSubtarget(), PassConfig->getOptLevel(),
299  AntiDepMode, CriticalPathRCs))
300  return false;
301 
302  // Check for antidep breaking override...
303  if (EnableAntiDepBreaking.getPosition() > 0) {
304  AntiDepMode = (EnableAntiDepBreaking == "all")
305  ? TargetSubtargetInfo::ANTIDEP_ALL
306  : ((EnableAntiDepBreaking == "critical")
307  ? TargetSubtargetInfo::ANTIDEP_CRITICAL
308  : TargetSubtargetInfo::ANTIDEP_NONE);
309  }
310 
311  LLVM_DEBUG(dbgs() << "PostRAScheduler\n");
312 
313  SchedulePostRATDList Scheduler(Fn, MLI, AA, RegClassInfo, AntiDepMode,
314  CriticalPathRCs);
315 
316  // Loop over all of the basic blocks
317  for (auto &MBB : Fn) {
318 #ifndef NDEBUG
319  // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
320  if (DebugDiv > 0) {
321  static int bbcnt = 0;
322  if (bbcnt++ % DebugDiv != DebugMod)
323  continue;
324  dbgs() << "*** DEBUG scheduling " << Fn.getName() << ":"
325  << printMBBReference(MBB) << " ***\n";
326  }
327 #endif
328 
329  // Initialize register live-range state for scheduling in this block.
330  Scheduler.startBlock(&MBB);
331 
332  // Schedule each sequence of instructions not interrupted by a label
333  // or anything else that effectively needs to shut down scheduling.
334  MachineBasicBlock::iterator Current = MBB.end();
335  unsigned Count = MBB.size(), CurrentCount = Count;
336  for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) {
337  MachineInstr &MI = *std::prev(I);
338  --Count;
339  // Calls are not scheduling boundaries before register allocation, but
340  // post-ra we don't gain anything by scheduling across calls since we
341  // don't need to worry about register pressure.
342  if (MI.isCall() || TII->isSchedulingBoundary(MI, &MBB, Fn)) {
343  Scheduler.enterRegion(&MBB, I, Current, CurrentCount - Count);
344  Scheduler.setEndIndex(CurrentCount);
345  Scheduler.schedule();
346  Scheduler.exitRegion();
347  Scheduler.EmitSchedule();
348  Current = &MI;
349  CurrentCount = Count;
350  Scheduler.Observe(MI, CurrentCount);
351  }
352  I = MI;
353  if (MI.isBundle())
354  Count -= MI.getBundleSize();
355  }
356  assert(Count == 0 && "Instruction count mismatch!");
357  assert((MBB.begin() == Current || CurrentCount != 0) &&
358  "Instruction count mismatch!");
359  Scheduler.enterRegion(&MBB, MBB.begin(), Current, CurrentCount);
360  Scheduler.setEndIndex(CurrentCount);
361  Scheduler.schedule();
362  Scheduler.exitRegion();
363  Scheduler.EmitSchedule();
364 
365  // Clean up register live-range state.
366  Scheduler.finishBlock();
367 
368  // Update register kills
369  Scheduler.fixupKills(MBB);
370  }
371 
372  return true;
373 }
374 
375 /// StartBlock - Initialize register live-range state for scheduling in
376 /// this block.
377 ///
378 void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) {
379  // Call the superclass.
381 
382  // Reset the hazard recognizer and anti-dep breaker.
383  HazardRec->Reset();
384  if (AntiDepBreak)
385  AntiDepBreak->StartBlock(BB);
386 }
387 
388 /// Schedule - Schedule the instruction range using list scheduling.
389 ///
390 void SchedulePostRATDList::schedule() {
391  // Build the scheduling graph.
392  buildSchedGraph(AA);
393 
394  if (AntiDepBreak) {
395  unsigned Broken =
396  AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd,
397  EndIndex, DbgValues);
398 
399  if (Broken != 0) {
400  // We made changes. Update the dependency graph.
401  // Theoretically we could update the graph in place:
402  // When a live range is changed to use a different register, remove
403  // the def's anti-dependence *and* output-dependence edges due to
404  // that register, and add new anti-dependence and output-dependence
405  // edges based on the next live range of the register.
407  buildSchedGraph(AA);
408 
409  NumFixedAnti += Broken;
410  }
411  }
412 
413  postprocessDAG();
414 
415  LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n");
416  LLVM_DEBUG(dump());
417 
418  AvailableQueue.initNodes(SUnits);
419  ListScheduleTopDown();
420  AvailableQueue.releaseState();
421 }
422 
423 /// Observe - Update liveness information to account for the current
424 /// instruction, which will not be scheduled.
425 ///
426 void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) {
427  if (AntiDepBreak)
428  AntiDepBreak->Observe(MI, Count, EndIndex);
429 }
430 
431 /// FinishBlock - Clean up register live-range state.
432 ///
433 void SchedulePostRATDList::finishBlock() {
434  if (AntiDepBreak)
435  AntiDepBreak->FinishBlock();
436 
437  // Call the superclass.
439 }
440 
441 /// Apply each ScheduleDAGMutation step in order.
442 void SchedulePostRATDList::postprocessDAG() {
443  for (auto &M : Mutations)
444  M->apply(this);
445 }
446 
447 //===----------------------------------------------------------------------===//
448 // Top-Down Scheduling
449 //===----------------------------------------------------------------------===//
450 
451 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
452 /// the PendingQueue if the count reaches zero.
453 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
454  SUnit *SuccSU = SuccEdge->getSUnit();
455 
456  if (SuccEdge->isWeak()) {
457  --SuccSU->WeakPredsLeft;
458  return;
459  }
460 #ifndef NDEBUG
461  if (SuccSU->NumPredsLeft == 0) {
462  dbgs() << "*** Scheduling failed! ***\n";
463  dumpNode(*SuccSU);
464  dbgs() << " has been released too many times!\n";
465  llvm_unreachable(nullptr);
466  }
467 #endif
468  --SuccSU->NumPredsLeft;
469 
470  // Standard scheduler algorithms will recompute the depth of the successor
471  // here as such:
472  // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency());
473  //
474  // However, we lazily compute node depth instead. Note that
475  // ScheduleNodeTopDown has already updated the depth of this node which causes
476  // all descendents to be marked dirty. Setting the successor depth explicitly
477  // here would cause depth to be recomputed for all its ancestors. If the
478  // successor is not yet ready (because of a transitively redundant edge) then
479  // this causes depth computation to be quadratic in the size of the DAG.
480 
481  // If all the node's predecessors are scheduled, this node is ready
482  // to be scheduled. Ignore the special ExitSU node.
483  if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
484  PendingQueue.push_back(SuccSU);
485 }
486 
487 /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
488 void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
489  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
490  I != E; ++I) {
491  ReleaseSucc(SU, &*I);
492  }
493 }
494 
495 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
496 /// count of its successors. If a successor pending count is zero, add it to
497 /// the Available queue.
498 void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
499  LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
500  LLVM_DEBUG(dumpNode(*SU));
501 
502  Sequence.push_back(SU);
503  assert(CurCycle >= SU->getDepth() &&
504  "Node scheduled above its depth!");
505  SU->setDepthToAtLeast(CurCycle);
506 
507  ReleaseSuccessors(SU);
508  SU->isScheduled = true;
509  AvailableQueue.scheduledNode(SU);
510 }
511 
512 /// emitNoop - Add a noop to the current instruction sequence.
513 void SchedulePostRATDList::emitNoop(unsigned CurCycle) {
514  LLVM_DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');
515  HazardRec->EmitNoop();
516  Sequence.push_back(nullptr); // NULL here means noop
517  ++NumNoops;
518 }
519 
520 /// ListScheduleTopDown - The main loop of list scheduling for top-down
521 /// schedulers.
522 void SchedulePostRATDList::ListScheduleTopDown() {
523  unsigned CurCycle = 0;
524 
525  // We're scheduling top-down but we're visiting the regions in
526  // bottom-up order, so we don't know the hazards at the start of a
527  // region. So assume no hazards (this should usually be ok as most
528  // blocks are a single region).
529  HazardRec->Reset();
530 
531  // Release any successors of the special Entry node.
532  ReleaseSuccessors(&EntrySU);
533 
534  // Add all leaves to Available queue.
535  for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
536  // It is available if it has no predecessors.
537  if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
538  AvailableQueue.push(&SUnits[i]);
539  SUnits[i].isAvailable = true;
540  }
541  }
542 
543  // In any cycle where we can't schedule any instructions, we must
544  // stall or emit a noop, depending on the target.
545  bool CycleHasInsts = false;
546 
547  // While Available queue is not empty, grab the node with the highest
548  // priority. If it is not ready put it back. Schedule the node.
549  std::vector<SUnit*> NotReady;
550  Sequence.reserve(SUnits.size());
551  while (!AvailableQueue.empty() || !PendingQueue.empty()) {
552  // Check to see if any of the pending instructions are ready to issue. If
553  // so, add them to the available queue.
554  unsigned MinDepth = ~0u;
555  for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
556  if (PendingQueue[i]->getDepth() <= CurCycle) {
557  AvailableQueue.push(PendingQueue[i]);
558  PendingQueue[i]->isAvailable = true;
559  PendingQueue[i] = PendingQueue.back();
560  PendingQueue.pop_back();
561  --i; --e;
562  } else if (PendingQueue[i]->getDepth() < MinDepth)
563  MinDepth = PendingQueue[i]->getDepth();
564  }
565 
566  LLVM_DEBUG(dbgs() << "\n*** Examining Available\n";
567  AvailableQueue.dump(this));
568 
569  SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
570  bool HasNoopHazards = false;
571  while (!AvailableQueue.empty()) {
572  SUnit *CurSUnit = AvailableQueue.pop();
573 
575  HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
577  if (HazardRec->ShouldPreferAnother(CurSUnit)) {
578  if (!NotPreferredSUnit) {
579  // If this is the first non-preferred node for this cycle, then
580  // record it and continue searching for a preferred node. If this
581  // is not the first non-preferred node, then treat it as though
582  // there had been a hazard.
583  NotPreferredSUnit = CurSUnit;
584  continue;
585  }
586  } else {
587  FoundSUnit = CurSUnit;
588  break;
589  }
590  }
591 
592  // Remember if this is a noop hazard.
593  HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
594 
595  NotReady.push_back(CurSUnit);
596  }
597 
598  // If we have a non-preferred node, push it back onto the available list.
599  // If we did not find a preferred node, then schedule this first
600  // non-preferred node.
601  if (NotPreferredSUnit) {
602  if (!FoundSUnit) {
603  LLVM_DEBUG(
604  dbgs() << "*** Will schedule a non-preferred instruction...\n");
605  FoundSUnit = NotPreferredSUnit;
606  } else {
607  AvailableQueue.push(NotPreferredSUnit);
608  }
609 
610  NotPreferredSUnit = nullptr;
611  }
612 
613  // Add the nodes that aren't ready back onto the available list.
614  if (!NotReady.empty()) {
615  AvailableQueue.push_all(NotReady);
616  NotReady.clear();
617  }
618 
619  // If we found a node to schedule...
620  if (FoundSUnit) {
621  // If we need to emit noops prior to this instruction, then do so.
622  unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit);
623  for (unsigned i = 0; i != NumPreNoops; ++i)
624  emitNoop(CurCycle);
625 
626  // ... schedule the node...
627  ScheduleNodeTopDown(FoundSUnit, CurCycle);
628  HazardRec->EmitInstruction(FoundSUnit);
629  CycleHasInsts = true;
630  if (HazardRec->atIssueLimit()) {
631  LLVM_DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle
632  << '\n');
633  HazardRec->AdvanceCycle();
634  ++CurCycle;
635  CycleHasInsts = false;
636  }
637  } else {
638  if (CycleHasInsts) {
639  LLVM_DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n');
640  HazardRec->AdvanceCycle();
641  } else if (!HasNoopHazards) {
642  // Otherwise, we have a pipeline stall, but no other problem,
643  // just advance the current cycle and try again.
644  LLVM_DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n');
645  HazardRec->AdvanceCycle();
646  ++NumStalls;
647  } else {
648  // Otherwise, we have no instructions to issue and we have instructions
649  // that will fault if we don't do this right. This is the case for
650  // processors without pipeline interlocks and other cases.
651  emitNoop(CurCycle);
652  }
653 
654  ++CurCycle;
655  CycleHasInsts = false;
656  }
657  }
658 
659 #ifndef NDEBUG
660  unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false);
661  unsigned Noops = 0;
662  for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
663  if (!Sequence[i])
664  ++Noops;
665  assert(Sequence.size() - Noops == ScheduledNodes &&
666  "The number of nodes scheduled doesn't match the expected number!");
667 #endif // NDEBUG
668 }
669 
670 // EmitSchedule - Emit the machine code in scheduled order.
671 void SchedulePostRATDList::EmitSchedule() {
672  RegionBegin = RegionEnd;
673 
674  // If first instruction was a DBG_VALUE then put it back.
675  if (FirstDbgValue)
676  BB->splice(RegionEnd, BB, FirstDbgValue);
677 
678  // Then re-insert them according to the given schedule.
679  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
680  if (SUnit *SU = Sequence[i])
681  BB->splice(RegionEnd, BB, SU->getInstr());
682  else
683  // Null SUnit* is a noop.
684  TII->insertNoop(*BB, RegionEnd);
685 
686  // Update the Begin iterator, as the first instruction in the block
687  // may have been scheduled later.
688  if (i == 0)
689  RegionBegin = std::prev(RegionEnd);
690  }
691 
692  // Reinsert any remaining debug_values.
693  for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
694  DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
695  std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
696  MachineInstr *DbgValue = P.first;
697  MachineBasicBlock::iterator OrigPrivMI = P.second;
698  BB->splice(++OrigPrivMI, BB, DbgValue);
699  }
700  DbgValues.clear();
701  FirstDbgValue = nullptr;
702 }
virtual void getCriticalPathRCs(RegClassVector &CriticalPathRCs) const
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
virtual void finishBlock()
Cleans up after scheduling in the given block.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:656
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
SI Whole Quad Mode
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:484
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:398
static cl::opt< int > DebugDiv("postra-sched-debugdiv", cl::desc("Debug control MBBs that are scheduled"), cl::init(0), cl::Hidden)
STATISTIC(NumFunctions, "Total number of functions")
SmallVectorImpl< SDep >::iterator succ_iterator
Definition: ScheduleDAG.h:260
CodeGenOpt::Level getOptLevel() const
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
void insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const override
Insert a noop into the instruction stream at the specified point.
AnalysisUsage & addRequired()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
static cl::opt< bool > EnablePostRAScheduler("post-RA-scheduler", cl::desc("Enable scheduling after register allocation"), cl::init(false), cl::Hidden)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
Target-Independent Code Generator Pass Configuration Options.
virtual AntiDepBreakMode getAntiDepBreakMode() const
bool isBundle() const
Itinerary data supplied by a subtarget to be used by a target.
unsigned NumPredsLeft
of preds not scheduled.
Definition: ScheduleDAG.h:268
virtual const TargetInstrInfo * getInstrInfo() const
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
TargetInstrInfo - Interface to description of machine instruction set.
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node&#39;s depth value, sets it to be the new depth value.
Scheduling dependency.
Definition: ScheduleDAG.h:49
bool isAvailable()
Definition: Compression.cpp:47
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
unsigned const MachineRegisterInfo * MRI
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:64
HazardRecognizer - This determines whether or not an instruction can be issued this cycle...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
INITIALIZE_PASS(PostRAScheduler, DEBUG_TYPE, "Post RA top-down list latency scheduler", false, false) SchedulePostRATDList
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
enum { ANTIDEP_NONE, ANTIDEP_CRITICAL, ANTIDEP_ALL } AntiDepBreakMode
Represent the analysis usage information of a pass.
constexpr double e
Definition: MathExtras.h:57
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
unsigned getBundleSize() const
Return the number of instructions inside the MI bundle, excluding the bundle header.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned WeakPredsLeft
of weak preds not scheduled.
Definition: ScheduleDAG.h:270
char & PostRASchedulerID
createPostRAScheduler - This pass performs post register allocation scheduling.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
static unsigned getDepth(const SmallVectorImpl< const MachineBasicBlock *> &Stack, const MachineBasicBlock *MBB)
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
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
bool isSchedulingBoundary(const MachineInstr &MI, const MachineBasicBlock *MBB, const MachineFunction &MF) const override
Test if the given instruction should be considered a scheduling boundary.
virtual void Observe(MachineInstr &MI, unsigned Count, unsigned InsertPosIndex)=0
Update liveness information to account for the current instruction, which will not be scheduled...
MachineFunctionProperties & set(Property P)
TargetSubtargetInfo - Generic base class for all target subtargets.
#define DEBUG_TYPE
static cl::opt< int > DebugMod("postra-sched-debugmod", cl::desc("Debug control MBBs that are scheduled"), cl::init(0), cl::Hidden)
A ScheduleDAG for scheduling lists of MachineInstr.
Representation of each machine instruction.
Definition: MachineInstr.h:63
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
#define I(x, y, z)
Definition: MD5.cpp:58
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
Definition: PtrState.h:40
static cl::opt< std::string > EnableAntiDepBreaking("break-anti-dependencies", cl::desc("Break post-RA scheduling anti-dependencies: " "\ritical\ \ll\ or \one\), cl::init("none"), cl::Hidden)
virtual bool enablePostRAScheduler() const
True if the subtarget should run a scheduler after register allocation.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
bool isWeak() const
Tests if this a weak dependence.
Definition: ScheduleDAG.h:194
Machine Instruction Scheduler
IRTranslator LLVM IR MI
virtual CodeGenOpt::Level getOptLevelToEnablePostRAScheduler() const
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Properties which a MachineFunction may have at a given point in time.
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
This file describes how to lower LLVM code to machine code.