LLVM  7.0.0svn
PostRASchedulerList.cpp
Go to the documentation of this file.
1 //===----- SchedulePostRAList.cpp - list scheduler ------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This implements a top-down list scheduler, using standard algorithms.
11 // The basic approach uses a priority queue of available nodes to schedule.
12 // One at a time, nodes are taken from the priority queue (thus in priority
13 // order), checked for legality to schedule, and emitted if legal.
14 //
15 // Nodes may not be legal to schedule either due to structural hazards (e.g.
16 // pipeline or resource constraints) or because an input to the instruction has
17 // not completed execution.
18 //
19 //===----------------------------------------------------------------------===//
20 
22 #include "AntiDepBreaker.h"
23 #include "CriticalAntiDepBreaker.h"
24 #include "llvm/ADT/Statistic.h"
31 #include "llvm/CodeGen/Passes.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  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  SU->dump(this);
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  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  DEBUG(dbgs() << "********** List Scheduling **********\n");
416  DEBUG(
417  for (const SUnit &SU : SUnits) {
418  SU.dumpAll(this);
419  dbgs() << '\n';
420  }
421  );
422 
423  AvailableQueue.initNodes(SUnits);
424  ListScheduleTopDown();
425  AvailableQueue.releaseState();
426 }
427 
428 /// Observe - Update liveness information to account for the current
429 /// instruction, which will not be scheduled.
430 ///
431 void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) {
432  if (AntiDepBreak)
433  AntiDepBreak->Observe(MI, Count, EndIndex);
434 }
435 
436 /// FinishBlock - Clean up register live-range state.
437 ///
438 void SchedulePostRATDList::finishBlock() {
439  if (AntiDepBreak)
440  AntiDepBreak->FinishBlock();
441 
442  // Call the superclass.
444 }
445 
446 /// Apply each ScheduleDAGMutation step in order.
447 void SchedulePostRATDList::postprocessDAG() {
448  for (auto &M : Mutations)
449  M->apply(this);
450 }
451 
452 //===----------------------------------------------------------------------===//
453 // Top-Down Scheduling
454 //===----------------------------------------------------------------------===//
455 
456 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
457 /// the PendingQueue if the count reaches zero.
458 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
459  SUnit *SuccSU = SuccEdge->getSUnit();
460 
461  if (SuccEdge->isWeak()) {
462  --SuccSU->WeakPredsLeft;
463  return;
464  }
465 #ifndef NDEBUG
466  if (SuccSU->NumPredsLeft == 0) {
467  dbgs() << "*** Scheduling failed! ***\n";
468  SuccSU->dump(this);
469  dbgs() << " has been released too many times!\n";
470  llvm_unreachable(nullptr);
471  }
472 #endif
473  --SuccSU->NumPredsLeft;
474 
475  // Standard scheduler algorithms will recompute the depth of the successor
476  // here as such:
477  // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency());
478  //
479  // However, we lazily compute node depth instead. Note that
480  // ScheduleNodeTopDown has already updated the depth of this node which causes
481  // all descendents to be marked dirty. Setting the successor depth explicitly
482  // here would cause depth to be recomputed for all its ancestors. If the
483  // successor is not yet ready (because of a transitively redundant edge) then
484  // this causes depth computation to be quadratic in the size of the DAG.
485 
486  // If all the node's predecessors are scheduled, this node is ready
487  // to be scheduled. Ignore the special ExitSU node.
488  if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
489  PendingQueue.push_back(SuccSU);
490 }
491 
492 /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
493 void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
494  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
495  I != E; ++I) {
496  ReleaseSucc(SU, &*I);
497  }
498 }
499 
500 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
501 /// count of its successors. If a successor pending count is zero, add it to
502 /// the Available queue.
503 void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
504  DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
505  DEBUG(SU->dump(this));
506 
507  Sequence.push_back(SU);
508  assert(CurCycle >= SU->getDepth() &&
509  "Node scheduled above its depth!");
510  SU->setDepthToAtLeast(CurCycle);
511 
512  ReleaseSuccessors(SU);
513  SU->isScheduled = true;
514  AvailableQueue.scheduledNode(SU);
515 }
516 
517 /// emitNoop - Add a noop to the current instruction sequence.
518 void SchedulePostRATDList::emitNoop(unsigned CurCycle) {
519  DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');
520  HazardRec->EmitNoop();
521  Sequence.push_back(nullptr); // NULL here means noop
522  ++NumNoops;
523 }
524 
525 /// ListScheduleTopDown - The main loop of list scheduling for top-down
526 /// schedulers.
527 void SchedulePostRATDList::ListScheduleTopDown() {
528  unsigned CurCycle = 0;
529 
530  // We're scheduling top-down but we're visiting the regions in
531  // bottom-up order, so we don't know the hazards at the start of a
532  // region. So assume no hazards (this should usually be ok as most
533  // blocks are a single region).
534  HazardRec->Reset();
535 
536  // Release any successors of the special Entry node.
537  ReleaseSuccessors(&EntrySU);
538 
539  // Add all leaves to Available queue.
540  for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
541  // It is available if it has no predecessors.
542  if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
543  AvailableQueue.push(&SUnits[i]);
544  SUnits[i].isAvailable = true;
545  }
546  }
547 
548  // In any cycle where we can't schedule any instructions, we must
549  // stall or emit a noop, depending on the target.
550  bool CycleHasInsts = false;
551 
552  // While Available queue is not empty, grab the node with the highest
553  // priority. If it is not ready put it back. Schedule the node.
554  std::vector<SUnit*> NotReady;
555  Sequence.reserve(SUnits.size());
556  while (!AvailableQueue.empty() || !PendingQueue.empty()) {
557  // Check to see if any of the pending instructions are ready to issue. If
558  // so, add them to the available queue.
559  unsigned MinDepth = ~0u;
560  for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
561  if (PendingQueue[i]->getDepth() <= CurCycle) {
562  AvailableQueue.push(PendingQueue[i]);
563  PendingQueue[i]->isAvailable = true;
564  PendingQueue[i] = PendingQueue.back();
565  PendingQueue.pop_back();
566  --i; --e;
567  } else if (PendingQueue[i]->getDepth() < MinDepth)
568  MinDepth = PendingQueue[i]->getDepth();
569  }
570 
571  DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this));
572 
573  SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
574  bool HasNoopHazards = false;
575  while (!AvailableQueue.empty()) {
576  SUnit *CurSUnit = AvailableQueue.pop();
577 
579  HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
581  if (HazardRec->ShouldPreferAnother(CurSUnit)) {
582  if (!NotPreferredSUnit) {
583  // If this is the first non-preferred node for this cycle, then
584  // record it and continue searching for a preferred node. If this
585  // is not the first non-preferred node, then treat it as though
586  // there had been a hazard.
587  NotPreferredSUnit = CurSUnit;
588  continue;
589  }
590  } else {
591  FoundSUnit = CurSUnit;
592  break;
593  }
594  }
595 
596  // Remember if this is a noop hazard.
597  HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
598 
599  NotReady.push_back(CurSUnit);
600  }
601 
602  // If we have a non-preferred node, push it back onto the available list.
603  // If we did not find a preferred node, then schedule this first
604  // non-preferred node.
605  if (NotPreferredSUnit) {
606  if (!FoundSUnit) {
607  DEBUG(dbgs() << "*** Will schedule a non-preferred instruction...\n");
608  FoundSUnit = NotPreferredSUnit;
609  } else {
610  AvailableQueue.push(NotPreferredSUnit);
611  }
612 
613  NotPreferredSUnit = nullptr;
614  }
615 
616  // Add the nodes that aren't ready back onto the available list.
617  if (!NotReady.empty()) {
618  AvailableQueue.push_all(NotReady);
619  NotReady.clear();
620  }
621 
622  // If we found a node to schedule...
623  if (FoundSUnit) {
624  // If we need to emit noops prior to this instruction, then do so.
625  unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit);
626  for (unsigned i = 0; i != NumPreNoops; ++i)
627  emitNoop(CurCycle);
628 
629  // ... schedule the node...
630  ScheduleNodeTopDown(FoundSUnit, CurCycle);
631  HazardRec->EmitInstruction(FoundSUnit);
632  CycleHasInsts = true;
633  if (HazardRec->atIssueLimit()) {
634  DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n');
635  HazardRec->AdvanceCycle();
636  ++CurCycle;
637  CycleHasInsts = false;
638  }
639  } else {
640  if (CycleHasInsts) {
641  DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n');
642  HazardRec->AdvanceCycle();
643  } else if (!HasNoopHazards) {
644  // Otherwise, we have a pipeline stall, but no other problem,
645  // just advance the current cycle and try again.
646  DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n');
647  HazardRec->AdvanceCycle();
648  ++NumStalls;
649  } else {
650  // Otherwise, we have no instructions to issue and we have instructions
651  // that will fault if we don't do this right. This is the case for
652  // processors without pipeline interlocks and other cases.
653  emitNoop(CurCycle);
654  }
655 
656  ++CurCycle;
657  CycleHasInsts = false;
658  }
659  }
660 
661 #ifndef NDEBUG
662  unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false);
663  unsigned Noops = 0;
664  for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
665  if (!Sequence[i])
666  ++Noops;
667  assert(Sequence.size() - Noops == ScheduledNodes &&
668  "The number of nodes scheduled doesn't match the expected number!");
669 #endif // NDEBUG
670 }
671 
672 // EmitSchedule - Emit the machine code in scheduled order.
673 void SchedulePostRATDList::EmitSchedule() {
674  RegionBegin = RegionEnd;
675 
676  // If first instruction was a DBG_VALUE then put it back.
677  if (FirstDbgValue)
678  BB->splice(RegionEnd, BB, FirstDbgValue);
679 
680  // Then re-insert them according to the given schedule.
681  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
682  if (SUnit *SU = Sequence[i])
683  BB->splice(RegionEnd, BB, SU->getInstr());
684  else
685  // Null SUnit* is a noop.
686  TII->insertNoop(*BB, RegionEnd);
687 
688  // Update the Begin iterator, as the first instruction in the block
689  // may have been scheduled later.
690  if (i == 0)
691  RegionBegin = std::prev(RegionEnd);
692  }
693 
694  // Reinsert any remaining debug_values.
695  for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
696  DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
697  std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
698  MachineInstr *DbgValue = P.first;
699  MachineBasicBlock::iterator OrigPrivMI = P.second;
700  BB->splice(++OrigPrivMI, BB, DbgValue);
701  }
702  DbgValues.clear();
703  FirstDbgValue = nullptr;
704 }
virtual void getCriticalPathRCs(RegClassVector &CriticalPathRCs) const
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:245
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:461
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:236
SI Whole Quad Mode
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
void dump(const ScheduleDAG *G) const
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:403
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:265
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:289
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:42
Target-Independent Code Generator Pass Configuration Options.
virtual AntiDepBreakMode getAntiDepBreakMode() const
bool isBundle() const
Definition: MachineInstr.h:856
Itinerary data supplied by a subtarget to be used by a target.
unsigned NumPredsLeft
of preds not scheduled.
Definition: ScheduleDAG.h:273
virtual const TargetInstrInfo * getInstrInfo() const
SUnit * getSUnit() const
Definition: ScheduleDAG.h:490
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:50
bool isAvailable()
Definition: Compression.cpp:58
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:378
unsigned const MachineRegisterInfo * MRI
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:59
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.
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:275
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:862
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
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:60
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:41
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:262
bool isWeak() const
Tests if this a weak dependence.
Definition: ScheduleDAG.h:195
#define DEBUG(X)
Definition: Debug.h:118
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...
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:247
This file describes how to lower LLVM code to machine code.