xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/PostRASchedulerList.cpp (revision 6966ac055c3b7a39266fb982493330df7a097997)
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 "AggressiveAntiDepBreaker.h"
21 #include "AntiDepBreaker.h"
22 #include "CriticalAntiDepBreaker.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/CodeGen/LatencyPriorityQueue.h"
26 #include "llvm/CodeGen/MachineDominators.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/CodeGen/MachineLoopInfo.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/CodeGen/Passes.h"
31 #include "llvm/CodeGen/RegisterClassInfo.h"
32 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
33 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
34 #include "llvm/CodeGen/SchedulerRegistry.h"
35 #include "llvm/CodeGen/TargetInstrInfo.h"
36 #include "llvm/CodeGen/TargetLowering.h"
37 #include "llvm/CodeGen/TargetPassConfig.h"
38 #include "llvm/CodeGen/TargetRegisterInfo.h"
39 #include "llvm/CodeGen/TargetSubtargetInfo.h"
40 #include "llvm/Config/llvm-config.h"
41 #include "llvm/Support/CommandLine.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/ErrorHandling.h"
44 #include "llvm/Support/raw_ostream.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);
60 static cl::opt<std::string>
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 
76 AntiDepBreaker::~AntiDepBreaker() { }
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();
89       AU.addRequired<AAResultsWrapperPass>();
90       AU.addRequired<TargetPassConfig>();
91       AU.addRequired<MachineDominatorTree>();
92       AU.addPreserved<MachineDominatorTree>();
93       AU.addRequired<MachineLoopInfo>();
94       AU.addPreserved<MachineLoopInfo>();
95       MachineFunctionPass::getAnalysisUsage(AU);
96     }
97 
98     MachineFunctionProperties getRequiredProperties() const override {
99       return MachineFunctionProperties().set(
100           MachineFunctionProperties::Property::NoVRegs);
101     }
102 
103     bool runOnMachineFunction(MachineFunction &Fn) override;
104 
105   private:
106     bool enablePostRAScheduler(
107         const TargetSubtargetInfo &ST, CodeGenOpt::Level OptLevel,
108         TargetSubtargetInfo::AntiDepBreakMode &Mode,
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(
147         MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
148         const RegisterClassInfo &,
149         TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
150         SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs);
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,
164                      MachineBasicBlock::iterator begin,
165                      MachineBasicBlock::iterator end,
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 
200 char &llvm::PostRASchedulerID = PostRAScheduler::ID;
201 
202 INITIALIZE_PASS(PostRAScheduler, DEBUG_TYPE,
203                 "Post RA top-down list latency scheduler", false, false)
204 
205 SchedulePostRATDList::SchedulePostRATDList(
206     MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
207     const RegisterClassInfo &RCI,
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,
236                  MachineBasicBlock::iterator begin,
237                  MachineBasicBlock::iterator end,
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   });
250   ScheduleDAGInstrs::exitRegion();
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,
268     TargetSubtargetInfo::AntiDepBreakMode &Mode,
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 
292   TargetSubtargetInfo::AntiDepBreakMode AntiDepMode =
293     TargetSubtargetInfo::ANTIDEP_NONE;
294   SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs;
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.
380   ScheduleDAGInstrs::startBlock(BB);
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.
406       ScheduleDAG::clearDAG();
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.
438   ScheduleDAGInstrs::finishBlock();
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 
574       ScheduleHazardRecognizer::HazardType HT =
575         HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
576       if (HT == ScheduleHazardRecognizer::NoHazard) {
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 }
703