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/CodeGen/PostRASchedulerList.h"
21#include "CodeGenOptions.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/CodeGen/AntiDepBreaker.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/RegisterClassInfo.h"
31#include "llvm/CodeGen/ScheduleDAGInstrs.h"
32#include "llvm/CodeGen/ScheduleDAGMutation.h"
33#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
34#include "llvm/CodeGen/TargetInstrInfo.h"
35#include "llvm/CodeGen/TargetPassConfig.h"
36#include "llvm/CodeGen/TargetSubtargetInfo.h"
37#include "llvm/Config/llvm-config.h"
38#include "llvm/InitializePasses.h"
39#include "llvm/Pass.h"
40#include "llvm/Support/Debug.h"
41#include "llvm/Support/ErrorHandling.h"
42#include "llvm/Support/raw_ostream.h"
43#include "llvm/Target/TargetMachine.h"
44using namespace llvm;
45
46#define DEBUG_TYPE "post-RA-sched"
47
48STATISTIC(NumNoops, "Number of noops inserted");
49STATISTIC(NumStalls, "Number of pipeline stalls");
50STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies");
51
52AntiDepBreaker::~AntiDepBreaker() = default;
53
54namespace {
55class PostRAScheduler {
56 const TargetInstrInfo *TII = nullptr;
57 MachineLoopInfo *MLI = nullptr;
58 AliasAnalysis *AA = nullptr;
59 const TargetMachine *TM = nullptr;
60 const RegisterClassInfo *RegClassInfo = nullptr;
61
62public:
63 PostRAScheduler(MachineFunction &MF, MachineLoopInfo *MLI, AliasAnalysis *AA,
64 const TargetMachine *TM,
65 const RegisterClassInfo *RegClassInfo)
66 : TII(MF.getSubtarget().getInstrInfo()), MLI(MLI), AA(AA), TM(TM),
67 RegClassInfo(RegClassInfo) {}
68 bool run(MachineFunction &MF);
69};
70
71class PostRASchedulerLegacy : public MachineFunctionPass {
72public:
73 static char ID;
74 PostRASchedulerLegacy() : MachineFunctionPass(ID) {}
75
76 void getAnalysisUsage(AnalysisUsage &AU) const override {
77 AU.setPreservesCFG();
78 AU.addRequired<AAResultsWrapperPass>();
79 AU.addRequired<TargetPassConfig>();
80 AU.addRequired<MachineLoopInfoWrapperPass>();
81 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
82 MachineFunctionPass::getAnalysisUsage(AU);
83 }
84
85 MachineFunctionProperties getRequiredProperties() const override {
86 return MachineFunctionProperties().setNoVRegs();
87 }
88
89 bool runOnMachineFunction(MachineFunction &Fn) override;
90};
91char PostRASchedulerLegacy::ID = 0;
92
93class SchedulePostRATDList : public ScheduleDAGInstrs {
94 /// AvailableQueue - The priority queue to use for the available SUnits.
95 ///
96 LatencyPriorityQueue AvailableQueue;
97
98 /// PendingQueue - This contains all of the instructions whose operands have
99 /// been issued, but their results are not ready yet (due to the latency of
100 /// the operation). Once the operands becomes available, the instruction is
101 /// added to the AvailableQueue.
102 std::vector<SUnit *> PendingQueue;
103
104 /// HazardRec - The hazard recognizer to use.
105 ScheduleHazardRecognizer *HazardRec;
106
107 /// AntiDepBreak - Anti-dependence breaking object, or NULL if none
108 AntiDepBreaker *AntiDepBreak;
109
110 /// AA - AliasAnalysis for making memory reference queries.
111 AliasAnalysis *AA;
112
113 /// The schedule. Null SUnit*'s represent noop instructions.
114 std::vector<SUnit *> Sequence;
115
116 /// Ordered list of DAG postprocessing steps.
117 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
118
119 /// The index in BB of RegionEnd.
120 ///
121 /// This is the instruction number from the top of the current block, not
122 /// the SlotIndex. It is only used by the AntiDepBreaker.
123 unsigned EndIndex = 0;
124
125public:
126 SchedulePostRATDList(
127 MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
128 const RegisterClassInfo &,
129 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
130 SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs);
131
132 ~SchedulePostRATDList() override;
133
134 /// startBlock - Initialize register live-range state for scheduling in
135 /// this block.
136 ///
137 void startBlock(MachineBasicBlock *BB) override;
138
139 // Set the index of RegionEnd within the current BB.
140 void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; }
141
142 /// Initialize the scheduler state for the next scheduling region.
143 void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin,
144 MachineBasicBlock::iterator end,
145 unsigned regioninstrs) override;
146
147 /// Notify that the scheduler has finished scheduling the current region.
148 void exitRegion() override;
149
150 /// Schedule - Schedule the instruction range using list scheduling.
151 ///
152 void schedule() override;
153
154 void EmitSchedule();
155
156 /// Observe - Update liveness information to account for the current
157 /// instruction, which will not be scheduled.
158 ///
159 void Observe(MachineInstr &MI, unsigned Count);
160
161 /// finishBlock - Clean up register live-range state.
162 ///
163 void finishBlock() override;
164
165private:
166 /// Apply each ScheduleDAGMutation step in order.
167 void postProcessDAG();
168
169 void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
170 void ReleaseSuccessors(SUnit *SU);
171 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
172 void ListScheduleTopDown();
173
174 void dumpSchedule() const;
175 void emitNoop(unsigned CurCycle);
176};
177} // namespace
178
179char &llvm::PostRASchedulerID = PostRASchedulerLegacy::ID;
180
181INITIALIZE_PASS_BEGIN(PostRASchedulerLegacy, DEBUG_TYPE,
182 "Post RA top-down list latency scheduler", false, false)
183INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
184INITIALIZE_PASS_END(PostRASchedulerLegacy, DEBUG_TYPE,
185 "Post RA top-down list latency scheduler", false, false)
186
187SchedulePostRATDList::SchedulePostRATDList(
188 MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
189 const RegisterClassInfo &RCI,
190 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
191 SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
192 : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
193
194 const InstrItineraryData *InstrItins =
195 MF.getSubtarget().getInstrItineraryData();
196 HazardRec =
197 MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
198 InstrItins, DAG: this);
199 MF.getSubtarget().getPostRAMutations(Mutations);
200
201 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||
202 MRI.tracksLiveness()) &&
203 "Live-ins must be accurate for anti-dependency breaking");
204 AntiDepBreak = ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL)
205 ? createAggressiveAntiDepBreaker(MFi&: MF, RCI, CriticalPathRCs)
206 : ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL)
207 ? createCriticalAntiDepBreaker(MFi&: MF, RCI)
208 : nullptr));
209}
210
211SchedulePostRATDList::~SchedulePostRATDList() {
212 delete HazardRec;
213 delete AntiDepBreak;
214}
215
216/// Initialize state associated with the next scheduling region.
217void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb,
218 MachineBasicBlock::iterator begin,
219 MachineBasicBlock::iterator end,
220 unsigned regioninstrs) {
221 ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
222 Sequence.clear();
223}
224
225/// Print the schedule before exiting the region.
226void SchedulePostRATDList::exitRegion() {
227 LLVM_DEBUG({
228 dbgs() << "*** Final schedule ***\n";
229 dumpSchedule();
230 dbgs() << '\n';
231 });
232 ScheduleDAGInstrs::exitRegion();
233}
234
235#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
236/// dumpSchedule - dump the scheduled Sequence.
237LLVM_DUMP_METHOD void SchedulePostRATDList::dumpSchedule() const {
238 for (const SUnit *SU : Sequence) {
239 if (SU)
240 dumpNode(*SU);
241 else
242 dbgs() << "**** NOOP ****\n";
243 }
244}
245#endif
246
247static bool enablePostRAScheduler(const CodeGenOptions &Opts,
248 const TargetSubtargetInfo &ST,
249 CodeGenOptLevel OptLevel) {
250 // Check for explicit enable/disable of post-ra scheduling.
251 return valueOr(X: Opts.post_RA_scheduler,
252 Default: ST.enablePostRAScheduler() &&
253 OptLevel >= ST.getOptLevelToEnablePostRAScheduler());
254}
255
256bool PostRAScheduler::run(MachineFunction &MF) {
257 const CodeGenOptions &Opts = getCodeGenOptions(MF);
258 const auto &Subtarget = MF.getSubtarget();
259 // Check that post-RA scheduling is enabled for this target.
260 if (!enablePostRAScheduler(Opts, ST: Subtarget, OptLevel: TM->getOptLevel()))
261 return false;
262
263 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode =
264 Subtarget.getAntiDepBreakMode();
265 if (auto Mode = Opts.break_anti_dependencies) {
266 AntiDepMode =
267 (*Mode == "all")
268 ? TargetSubtargetInfo::ANTIDEP_ALL
269 : ((*Mode == "critical") ? TargetSubtargetInfo::ANTIDEP_CRITICAL
270 : TargetSubtargetInfo::ANTIDEP_NONE);
271 }
272 SmallVector<const TargetRegisterClass *, 4> CriticalPathRCs;
273 Subtarget.getCriticalPathRCs(CriticalPathRCs);
274
275 LLVM_DEBUG(dbgs() << "PostRAScheduler\n");
276
277 SchedulePostRATDList Scheduler(MF, *MLI, AA, *RegClassInfo, AntiDepMode,
278 CriticalPathRCs);
279
280 // Loop over all of the basic blocks
281 for (auto &MBB : MF) {
282#ifndef NDEBUG
283 // If -postra-sched-debugdiv=D is positive, only schedule MBBs with
284 // ID % D == -postra-sched-debugmod.
285 if (Opts.postra_sched_debugdiv > 0) {
286 static int bbcnt = 0;
287 if (bbcnt++ % Opts.postra_sched_debugdiv != Opts.postra_sched_debugmod)
288 continue;
289 dbgs() << "*** DEBUG scheduling " << MF.getName() << ":"
290 << printMBBReference(MBB) << " ***\n";
291 }
292#endif
293
294 // Initialize register live-range state for scheduling in this block.
295 Scheduler.startBlock(BB: &MBB);
296
297 // Schedule each sequence of instructions not interrupted by a label
298 // or anything else that effectively needs to shut down scheduling.
299 MachineBasicBlock::iterator Current = MBB.end();
300 unsigned Count = MBB.size(), CurrentCount = Count;
301 for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) {
302 MachineInstr &MI = *std::prev(x: I);
303 --Count;
304 // Calls are not scheduling boundaries before register allocation, but
305 // post-ra we don't gain anything by scheduling across calls since we
306 // don't need to worry about register pressure.
307 if (MI.isCall() || TII->isSchedulingBoundary(MI, MBB: &MBB, MF)) {
308 Scheduler.enterRegion(bb: &MBB, begin: I, end: Current, regioninstrs: CurrentCount - Count);
309 Scheduler.setEndIndex(CurrentCount);
310 Scheduler.schedule();
311 Scheduler.exitRegion();
312 Scheduler.EmitSchedule();
313 Current = &MI;
314 CurrentCount = Count;
315 Scheduler.Observe(MI, Count: CurrentCount);
316 }
317 I = MI;
318 if (MI.isBundle())
319 Count -= MI.getBundleSize();
320 }
321 assert(Count == 0 && "Instruction count mismatch!");
322 assert((MBB.begin() == Current || CurrentCount != 0) &&
323 "Instruction count mismatch!");
324 Scheduler.enterRegion(bb: &MBB, begin: MBB.begin(), end: Current, regioninstrs: CurrentCount);
325 Scheduler.setEndIndex(CurrentCount);
326 Scheduler.schedule();
327 Scheduler.exitRegion();
328 Scheduler.EmitSchedule();
329
330 // Clean up register live-range state.
331 Scheduler.finishBlock();
332
333 // Update register kills
334 Scheduler.fixupKills(MBB);
335 }
336
337 return true;
338}
339
340bool PostRASchedulerLegacy::runOnMachineFunction(MachineFunction &MF) {
341 if (skipFunction(F: MF.getFunction()))
342 return false;
343
344 MachineLoopInfo *MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
345 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
346 const TargetMachine *TM =
347 &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
348 RegisterClassInfo *RegClassInfo =
349 &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
350 PostRAScheduler Impl(MF, MLI, AA, TM, RegClassInfo);
351 return Impl.run(MF);
352}
353
354PreservedAnalyses
355PostRASchedulerPass::run(MachineFunction &MF,
356 MachineFunctionAnalysisManager &MFAM) {
357 MFPropsModifier _(*this, MF);
358
359 MachineLoopInfo *MLI = &MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
360 auto &FAM = MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
361 .getManager();
362 AliasAnalysis *AA = &FAM.getResult<AAManager>(IR&: MF.getFunction());
363 const RegisterClassInfo &RegClassInfo =
364 MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
365 PostRAScheduler Impl(MF, MLI, AA, TM, &RegClassInfo);
366 bool Changed = Impl.run(MF);
367 if (!Changed)
368 return PreservedAnalyses::all();
369
370 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
371 PA.preserveSet<CFGAnalyses>();
372 return PA;
373}
374
375/// StartBlock - Initialize register live-range state for scheduling in
376/// this block.
377///
378void 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///
390void SchedulePostRATDList::schedule() {
391 // Build the scheduling graph.
392 buildSchedGraph(AA);
393
394 if (AntiDepBreak) {
395 unsigned Broken =
396 AntiDepBreak->BreakAntiDependencies(SUnits, Begin: RegionBegin, End: RegionEnd,
397 InsertPosIndex: 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&: 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///
426void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) {
427 if (AntiDepBreak)
428 AntiDepBreak->Observe(MI, Count, InsertPosIndex: EndIndex);
429}
430
431/// FinishBlock - Clean up register live-range state.
432///
433void 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.
442void SchedulePostRATDList::postProcessDAG() {
443 for (auto &M : Mutations)
444 M->apply(DAG: 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.
453void 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(x: SuccSU);
485}
486
487/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
488void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
489 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
490 I != E; ++I) {
491 ReleaseSucc(SU, SuccEdge: &*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.
498void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
499 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
500 LLVM_DEBUG(dumpNode(*SU));
501
502 Sequence.push_back(x: 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.
513void SchedulePostRATDList::emitNoop(unsigned CurCycle) {
514 LLVM_DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');
515 HazardRec->EmitNoop();
516 Sequence.push_back(x: nullptr); // NULL here means noop
517 ++NumNoops;
518}
519
520/// ListScheduleTopDown - The main loop of list scheduling for top-down
521/// schedulers.
522void 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(SU: &EntrySU);
533
534 // Add all leaves to Available queue.
535 for (SUnit &SUnit : SUnits) {
536 // It is available if it has no predecessors.
537 if (!SUnit.NumPredsLeft && !SUnit.isAvailable) {
538 AvailableQueue.push(U: &SUnit);
539 SUnit.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(n: 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(U: 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, Stalls: 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(x: 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(U: 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(Nodes: 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(SU: 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 = llvm::count(Sequence, nullptr);
662 assert(Sequence.size() - Noops == ScheduledNodes &&
663 "The number of nodes scheduled doesn't match the expected number!");
664#endif // NDEBUG
665}
666
667// EmitSchedule - Emit the machine code in scheduled order.
668void SchedulePostRATDList::EmitSchedule() {
669 RegionBegin = RegionEnd;
670
671 // If first instruction was a DBG_VALUE then put it back.
672 if (FirstDbgValue)
673 BB->splice(Where: RegionEnd, Other: BB, From: FirstDbgValue);
674
675 // Then re-insert them according to the given schedule.
676 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
677 if (SUnit *SU = Sequence[i])
678 BB->splice(Where: RegionEnd, Other: BB, From: SU->getInstr());
679 else
680 // Null SUnit* is a noop.
681 TII->insertNoop(MBB&: *BB, MI: RegionEnd);
682
683 // Update the Begin iterator, as the first instruction in the block
684 // may have been scheduled later.
685 if (i == 0)
686 RegionBegin = std::prev(x: RegionEnd);
687 }
688
689 // Reinsert any remaining debug_values.
690 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
691 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
692 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(x: DI);
693 MachineInstr *DbgValue = P.first;
694 MachineBasicBlock::iterator OrigPrivMI = P.second;
695 BB->splice(Where: ++OrigPrivMI, Other: BB, From: DbgValue);
696 }
697 DbgValues.clear();
698 FirstDbgValue = nullptr;
699}
700