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