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