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