LLVM 20.0.0git
PostRASchedulerList.cpp
Go to the documentation of this file.
1//===----- SchedulePostRAList.cpp - list scheduler ------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This implements a top-down list scheduler, using standard algorithms.
10// The basic approach uses a priority queue of available nodes to schedule.
11// One at a time, nodes are taken from the priority queue (thus in priority
12// order), checked for legality to schedule, and emitted if legal.
13//
14// Nodes may not be legal to schedule either due to structural hazards (e.g.
15// pipeline or resource constraints) or because an input to the instruction has
16// not completed execution.
17//
18//===----------------------------------------------------------------------===//
19
20#include "llvm/ADT/Statistic.h"
35#include "llvm/Config/llvm-config.h"
37#include "llvm/Pass.h"
39#include "llvm/Support/Debug.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(false), cl::Hidden);
58EnableAntiDepBreaking("break-anti-dependencies",
59 cl::desc("Break post-RA scheduling anti-dependencies: "
60 "\"critical\", \"all\", or \"none\""),
61 cl::init("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"),
68static cl::opt<int>
69DebugMod("postra-sched-debugmod",
70 cl::desc("Debug control MBBs that are scheduled"),
72
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();
93 }
94
97 MachineFunctionProperties::Property::NoVRegs);
98 }
99
100 bool runOnMachineFunction(MachineFunction &Fn) override;
101 };
102 char PostRAScheduler::ID = 0;
103
104 class SchedulePostRATDList : public ScheduleDAGInstrs {
105 /// AvailableQueue - The priority queue to use for the available SUnits.
106 ///
107 LatencyPriorityQueue AvailableQueue;
108
109 /// PendingQueue - This contains all of the instructions whose operands have
110 /// been issued, but their results are not ready yet (due to the latency of
111 /// the operation). Once the operands becomes available, the instruction is
112 /// added to the AvailableQueue.
113 std::vector<SUnit*> PendingQueue;
114
115 /// HazardRec - The hazard recognizer to use.
116 ScheduleHazardRecognizer *HazardRec;
117
118 /// AntiDepBreak - Anti-dependence breaking object, or NULL if none
119 AntiDepBreaker *AntiDepBreak;
120
121 /// AA - AliasAnalysis for making memory reference queries.
122 AliasAnalysis *AA;
123
124 /// The schedule. Null SUnit*'s represent noop instructions.
125 std::vector<SUnit*> Sequence;
126
127 /// Ordered list of DAG postprocessing steps.
128 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
129
130 /// The index in BB of RegionEnd.
131 ///
132 /// This is the instruction number from the top of the current block, not
133 /// the SlotIndex. It is only used by the AntiDepBreaker.
134 unsigned EndIndex = 0;
135
136 public:
137 SchedulePostRATDList(
139 const RegisterClassInfo &,
142
143 ~SchedulePostRATDList() override;
144
145 /// startBlock - Initialize register live-range state for scheduling in
146 /// this block.
147 ///
148 void startBlock(MachineBasicBlock *BB) override;
149
150 // Set the index of RegionEnd within the current BB.
151 void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; }
152
153 /// Initialize the scheduler state for the next scheduling region.
157 unsigned regioninstrs) override;
158
159 /// Notify that the scheduler has finished scheduling the current region.
160 void exitRegion() override;
161
162 /// Schedule - Schedule the instruction range using list scheduling.
163 ///
164 void schedule() override;
165
166 void EmitSchedule();
167
168 /// Observe - Update liveness information to account for the current
169 /// instruction, which will not be scheduled.
170 ///
171 void Observe(MachineInstr &MI, unsigned Count);
172
173 /// finishBlock - Clean up register live-range state.
174 ///
175 void finishBlock() override;
176
177 private:
178 /// Apply each ScheduleDAGMutation step in order.
179 void postProcessDAG();
180
181 void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
182 void ReleaseSuccessors(SUnit *SU);
183 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
184 void ListScheduleTopDown();
185
186 void dumpSchedule() const;
187 void emitNoop(unsigned CurCycle);
188 };
189}
190
191char &llvm::PostRASchedulerID = PostRAScheduler::ID;
192
194 "Post RA top-down list latency scheduler", false, false)
195
196SchedulePostRATDList::SchedulePostRATDList(
199 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
200 SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
201 : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
202
203 const InstrItineraryData *InstrItins =
204 MF.getSubtarget().getInstrItineraryData();
205 HazardRec =
206 MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
207 InstrItins, this);
208 MF.getSubtarget().getPostRAMutations(Mutations);
209
210 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||
211 MRI.tracksLiveness()) &&
212 "Live-ins must be accurate for anti-dependency breaking");
213 AntiDepBreak = ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL)
214 ? createAggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs)
215 : ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL)
217 : nullptr));
218}
219
220SchedulePostRATDList::~SchedulePostRATDList() {
221 delete HazardRec;
222 delete AntiDepBreak;
223}
224
225/// Initialize state associated with the next scheduling region.
226void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb,
229 unsigned regioninstrs) {
230 ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
231 Sequence.clear();
232}
233
234/// Print the schedule before exiting the region.
235void SchedulePostRATDList::exitRegion() {
236 LLVM_DEBUG({
237 dbgs() << "*** Final schedule ***\n";
238 dumpSchedule();
239 dbgs() << '\n';
240 });
242}
243
244#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
245/// dumpSchedule - dump the scheduled Sequence.
246LLVM_DUMP_METHOD void SchedulePostRATDList::dumpSchedule() const {
247 for (const SUnit *SU : Sequence) {
248 if (SU)
249 dumpNode(*SU);
250 else
251 dbgs() << "**** NOOP ****\n";
252 }
253}
254#endif
255
257 CodeGenOptLevel OptLevel) {
258 // Check for explicit enable/disable of post-ra scheduling.
259 if (EnablePostRAScheduler.getPosition() > 0)
261
262 return ST.enablePostRAScheduler() &&
263 OptLevel >= ST.getOptLevelToEnablePostRAScheduler();
264}
265
266bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
267 if (skipFunction(Fn.getFunction()))
268 return false;
269
270 const auto &Subtarget = Fn.getSubtarget();
271 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
272 // Check that post-RA scheduling is enabled for this target.
273 if (!enablePostRAScheduler(Subtarget, PassConfig->getOptLevel()))
274 return false;
275
276 TII = Subtarget.getInstrInfo();
277 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
278 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
280 Subtarget.getAntiDepBreakMode();
281 if (EnableAntiDepBreaking.getPosition() > 0) {
282 AntiDepMode = (EnableAntiDepBreaking == "all")
283 ? TargetSubtargetInfo::ANTIDEP_ALL
284 : ((EnableAntiDepBreaking == "critical")
285 ? TargetSubtargetInfo::ANTIDEP_CRITICAL
286 : TargetSubtargetInfo::ANTIDEP_NONE);
287 }
289 Subtarget.getCriticalPathRCs(CriticalPathRCs);
290 RegClassInfo.runOnMachineFunction(Fn);
291
292 LLVM_DEBUG(dbgs() << "PostRAScheduler\n");
293
294 SchedulePostRATDList Scheduler(Fn, MLI, AA, RegClassInfo, AntiDepMode,
295 CriticalPathRCs);
296
297 // Loop over all of the basic blocks
298 for (auto &MBB : Fn) {
299#ifndef NDEBUG
300 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
301 if (DebugDiv > 0) {
302 static int bbcnt = 0;
303 if (bbcnt++ % DebugDiv != DebugMod)
304 continue;
305 dbgs() << "*** DEBUG scheduling " << Fn.getName() << ":"
306 << printMBBReference(MBB) << " ***\n";
307 }
308#endif
309
310 // Initialize register live-range state for scheduling in this block.
311 Scheduler.startBlock(&MBB);
312
313 // Schedule each sequence of instructions not interrupted by a label
314 // or anything else that effectively needs to shut down scheduling.
316 unsigned Count = MBB.size(), CurrentCount = Count;
317 for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) {
318 MachineInstr &MI = *std::prev(I);
319 --Count;
320 // Calls are not scheduling boundaries before register allocation, but
321 // post-ra we don't gain anything by scheduling across calls since we
322 // don't need to worry about register pressure.
323 if (MI.isCall() || TII->isSchedulingBoundary(MI, &MBB, Fn)) {
324 Scheduler.enterRegion(&MBB, I, Current, CurrentCount - Count);
325 Scheduler.setEndIndex(CurrentCount);
326 Scheduler.schedule();
327 Scheduler.exitRegion();
328 Scheduler.EmitSchedule();
329 Current = &MI;
330 CurrentCount = Count;
331 Scheduler.Observe(MI, CurrentCount);
332 }
333 I = MI;
334 if (MI.isBundle())
335 Count -= MI.getBundleSize();
336 }
337 assert(Count == 0 && "Instruction count mismatch!");
338 assert((MBB.begin() == Current || CurrentCount != 0) &&
339 "Instruction count mismatch!");
340 Scheduler.enterRegion(&MBB, MBB.begin(), Current, CurrentCount);
341 Scheduler.setEndIndex(CurrentCount);
342 Scheduler.schedule();
343 Scheduler.exitRegion();
344 Scheduler.EmitSchedule();
345
346 // Clean up register live-range state.
347 Scheduler.finishBlock();
348
349 // Update register kills
350 Scheduler.fixupKills(MBB);
351 }
352
353 return true;
354}
355
356/// StartBlock - Initialize register live-range state for scheduling in
357/// this block.
358///
359void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) {
360 // Call the superclass.
362
363 // Reset the hazard recognizer and anti-dep breaker.
364 HazardRec->Reset();
365 if (AntiDepBreak)
366 AntiDepBreak->StartBlock(BB);
367}
368
369/// Schedule - Schedule the instruction range using list scheduling.
370///
371void SchedulePostRATDList::schedule() {
372 // Build the scheduling graph.
373 buildSchedGraph(AA);
374
375 if (AntiDepBreak) {
376 unsigned Broken =
377 AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd,
378 EndIndex, DbgValues);
379
380 if (Broken != 0) {
381 // We made changes. Update the dependency graph.
382 // Theoretically we could update the graph in place:
383 // When a live range is changed to use a different register, remove
384 // the def's anti-dependence *and* output-dependence edges due to
385 // that register, and add new anti-dependence and output-dependence
386 // edges based on the next live range of the register.
388 buildSchedGraph(AA);
389
390 NumFixedAnti += Broken;
391 }
392 }
393
394 postProcessDAG();
395
396 LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n");
397 LLVM_DEBUG(dump());
398
399 AvailableQueue.initNodes(SUnits);
400 ListScheduleTopDown();
401 AvailableQueue.releaseState();
402}
403
404/// Observe - Update liveness information to account for the current
405/// instruction, which will not be scheduled.
406///
407void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) {
408 if (AntiDepBreak)
409 AntiDepBreak->Observe(MI, Count, EndIndex);
410}
411
412/// FinishBlock - Clean up register live-range state.
413///
414void SchedulePostRATDList::finishBlock() {
415 if (AntiDepBreak)
416 AntiDepBreak->FinishBlock();
417
418 // Call the superclass.
420}
421
422/// Apply each ScheduleDAGMutation step in order.
423void SchedulePostRATDList::postProcessDAG() {
424 for (auto &M : Mutations)
425 M->apply(this);
426}
427
428//===----------------------------------------------------------------------===//
429// Top-Down Scheduling
430//===----------------------------------------------------------------------===//
431
432/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
433/// the PendingQueue if the count reaches zero.
434void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
435 SUnit *SuccSU = SuccEdge->getSUnit();
436
437 if (SuccEdge->isWeak()) {
438 --SuccSU->WeakPredsLeft;
439 return;
440 }
441#ifndef NDEBUG
442 if (SuccSU->NumPredsLeft == 0) {
443 dbgs() << "*** Scheduling failed! ***\n";
444 dumpNode(*SuccSU);
445 dbgs() << " has been released too many times!\n";
446 llvm_unreachable(nullptr);
447 }
448#endif
449 --SuccSU->NumPredsLeft;
450
451 // Standard scheduler algorithms will recompute the depth of the successor
452 // here as such:
453 // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency());
454 //
455 // However, we lazily compute node depth instead. Note that
456 // ScheduleNodeTopDown has already updated the depth of this node which causes
457 // all descendents to be marked dirty. Setting the successor depth explicitly
458 // here would cause depth to be recomputed for all its ancestors. If the
459 // successor is not yet ready (because of a transitively redundant edge) then
460 // this causes depth computation to be quadratic in the size of the DAG.
461
462 // If all the node's predecessors are scheduled, this node is ready
463 // to be scheduled. Ignore the special ExitSU node.
464 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
465 PendingQueue.push_back(SuccSU);
466}
467
468/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
469void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
470 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
471 I != E; ++I) {
472 ReleaseSucc(SU, &*I);
473 }
474}
475
476/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
477/// count of its successors. If a successor pending count is zero, add it to
478/// the Available queue.
479void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
480 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
481 LLVM_DEBUG(dumpNode(*SU));
482
483 Sequence.push_back(SU);
484 assert(CurCycle >= SU->getDepth() &&
485 "Node scheduled above its depth!");
486 SU->setDepthToAtLeast(CurCycle);
487
488 ReleaseSuccessors(SU);
489 SU->isScheduled = true;
490 AvailableQueue.scheduledNode(SU);
491}
492
493/// emitNoop - Add a noop to the current instruction sequence.
494void SchedulePostRATDList::emitNoop(unsigned CurCycle) {
495 LLVM_DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');
496 HazardRec->EmitNoop();
497 Sequence.push_back(nullptr); // NULL here means noop
498 ++NumNoops;
499}
500
501/// ListScheduleTopDown - The main loop of list scheduling for top-down
502/// schedulers.
503void SchedulePostRATDList::ListScheduleTopDown() {
504 unsigned CurCycle = 0;
505
506 // We're scheduling top-down but we're visiting the regions in
507 // bottom-up order, so we don't know the hazards at the start of a
508 // region. So assume no hazards (this should usually be ok as most
509 // blocks are a single region).
510 HazardRec->Reset();
511
512 // Release any successors of the special Entry node.
513 ReleaseSuccessors(&EntrySU);
514
515 // Add all leaves to Available queue.
516 for (SUnit &SUnit : SUnits) {
517 // It is available if it has no predecessors.
519 AvailableQueue.push(&SUnit);
520 SUnit.isAvailable = true;
521 }
522 }
523
524 // In any cycle where we can't schedule any instructions, we must
525 // stall or emit a noop, depending on the target.
526 bool CycleHasInsts = false;
527
528 // While Available queue is not empty, grab the node with the highest
529 // priority. If it is not ready put it back. Schedule the node.
530 std::vector<SUnit*> NotReady;
531 Sequence.reserve(SUnits.size());
532 while (!AvailableQueue.empty() || !PendingQueue.empty()) {
533 // Check to see if any of the pending instructions are ready to issue. If
534 // so, add them to the available queue.
535 unsigned MinDepth = ~0u;
536 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
537 if (PendingQueue[i]->getDepth() <= CurCycle) {
538 AvailableQueue.push(PendingQueue[i]);
539 PendingQueue[i]->isAvailable = true;
540 PendingQueue[i] = PendingQueue.back();
541 PendingQueue.pop_back();
542 --i; --e;
543 } else if (PendingQueue[i]->getDepth() < MinDepth)
544 MinDepth = PendingQueue[i]->getDepth();
545 }
546
547 LLVM_DEBUG(dbgs() << "\n*** Examining Available\n";
548 AvailableQueue.dump(this));
549
550 SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
551 bool HasNoopHazards = false;
552 while (!AvailableQueue.empty()) {
553 SUnit *CurSUnit = AvailableQueue.pop();
554
556 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
558 if (HazardRec->ShouldPreferAnother(CurSUnit)) {
559 if (!NotPreferredSUnit) {
560 // If this is the first non-preferred node for this cycle, then
561 // record it and continue searching for a preferred node. If this
562 // is not the first non-preferred node, then treat it as though
563 // there had been a hazard.
564 NotPreferredSUnit = CurSUnit;
565 continue;
566 }
567 } else {
568 FoundSUnit = CurSUnit;
569 break;
570 }
571 }
572
573 // Remember if this is a noop hazard.
574 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
575
576 NotReady.push_back(CurSUnit);
577 }
578
579 // If we have a non-preferred node, push it back onto the available list.
580 // If we did not find a preferred node, then schedule this first
581 // non-preferred node.
582 if (NotPreferredSUnit) {
583 if (!FoundSUnit) {
585 dbgs() << "*** Will schedule a non-preferred instruction...\n");
586 FoundSUnit = NotPreferredSUnit;
587 } else {
588 AvailableQueue.push(NotPreferredSUnit);
589 }
590
591 NotPreferredSUnit = nullptr;
592 }
593
594 // Add the nodes that aren't ready back onto the available list.
595 if (!NotReady.empty()) {
596 AvailableQueue.push_all(NotReady);
597 NotReady.clear();
598 }
599
600 // If we found a node to schedule...
601 if (FoundSUnit) {
602 // If we need to emit noops prior to this instruction, then do so.
603 unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit);
604 for (unsigned i = 0; i != NumPreNoops; ++i)
605 emitNoop(CurCycle);
606
607 // ... schedule the node...
608 ScheduleNodeTopDown(FoundSUnit, CurCycle);
609 HazardRec->EmitInstruction(FoundSUnit);
610 CycleHasInsts = true;
611 if (HazardRec->atIssueLimit()) {
612 LLVM_DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle
613 << '\n');
614 HazardRec->AdvanceCycle();
615 ++CurCycle;
616 CycleHasInsts = false;
617 }
618 } else {
619 if (CycleHasInsts) {
620 LLVM_DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n');
621 HazardRec->AdvanceCycle();
622 } else if (!HasNoopHazards) {
623 // Otherwise, we have a pipeline stall, but no other problem,
624 // just advance the current cycle and try again.
625 LLVM_DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n');
626 HazardRec->AdvanceCycle();
627 ++NumStalls;
628 } else {
629 // Otherwise, we have no instructions to issue and we have instructions
630 // that will fault if we don't do this right. This is the case for
631 // processors without pipeline interlocks and other cases.
632 emitNoop(CurCycle);
633 }
634
635 ++CurCycle;
636 CycleHasInsts = false;
637 }
638 }
639
640#ifndef NDEBUG
641 unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false);
642 unsigned Noops = llvm::count(Sequence, nullptr);
643 assert(Sequence.size() - Noops == ScheduledNodes &&
644 "The number of nodes scheduled doesn't match the expected number!");
645#endif // NDEBUG
646}
647
648// EmitSchedule - Emit the machine code in scheduled order.
649void SchedulePostRATDList::EmitSchedule() {
650 RegionBegin = RegionEnd;
651
652 // If first instruction was a DBG_VALUE then put it back.
653 if (FirstDbgValue)
654 BB->splice(RegionEnd, BB, FirstDbgValue);
655
656 // Then re-insert them according to the given schedule.
657 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
658 if (SUnit *SU = Sequence[i])
659 BB->splice(RegionEnd, BB, SU->getInstr());
660 else
661 // Null SUnit* is a noop.
662 TII->insertNoop(*BB, RegionEnd);
663
664 // Update the Begin iterator, as the first instruction in the block
665 // may have been scheduled later.
666 if (i == 0)
667 RegionBegin = std::prev(RegionEnd);
668 }
669
670 // Reinsert any remaining debug_values.
671 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
672 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
673 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
674 MachineInstr *DbgValue = P.first;
675 MachineBasicBlock::iterator OrigPrivMI = P.second;
676 BB->splice(++OrigPrivMI, BB, DbgValue);
677 }
678 DbgValues.clear();
679 FirstDbgValue = nullptr;
680}
unsigned const MachineRegisterInfo * MRI
aarch64 promote const
MachineBasicBlock & MBB
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:622
#define LLVM_DEBUG(...)
Definition: Debug.h:106
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
Machine Instruction Scheduler
#define P(N)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static cl::opt< int > DebugDiv("postra-sched-debugdiv", cl::desc("Debug control MBBs that are scheduled"), cl::init(0), cl::Hidden)
static cl::opt< bool > EnablePostRAScheduler("post-RA-scheduler", cl::desc("Enable scheduling after register allocation"), cl::init(false), cl::Hidden)
static cl::opt< std::string > EnableAntiDepBreaking("break-anti-dependencies", cl::desc("Break post-RA scheduling anti-dependencies: " "\"critical\", \"all\", or \"none\""), cl::init("none"), cl::Hidden)
static bool enablePostRAScheduler(const TargetSubtargetInfo &ST, CodeGenOptLevel OptLevel)
#define DEBUG_TYPE
static cl::opt< int > DebugMod("postra-sched-debugmod", cl::desc("Debug control MBBs that are scheduled"), cl::init(0), cl::Hidden)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:166
Target-Independent Code Generator Pass Configuration Options pass.
Class recording the (high level) value of a variable.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:256
This class works in conjunction with the post-RA scheduler to rename registers to break register anti...
virtual ~AntiDepBreaker()
void insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const override
Insert a noop into the instruction stream at the specified point.
bool isSchedulingBoundary(const MachineInstr &MI, const MachineBasicBlock *MBB, const MachineFunction &MF) const override
Test if the given instruction should be considered a scheduling boundary.
Itinerary data supplied by a subtarget to be used by a target.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Analysis pass which computes a MachineDominatorTree.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
Definition: MachineInstr.h:69
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Scheduling dependency.
Definition: ScheduleDAG.h:49
SUnit * getSUnit() const
Definition: ScheduleDAG.h:498
bool isWeak() const
Tests if this a weak dependence.
Definition: ScheduleDAG.h:194
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:416
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:296
bool isAvailable
True once available.
Definition: ScheduleDAG.h:295
unsigned NumPredsLeft
Definition: ScheduleDAG.h:274
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:263
unsigned WeakPredsLeft
Definition: ScheduleDAG.h:276
SmallVectorImpl< SDep >::iterator succ_iterator
Definition: ScheduleDAG.h:266
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node's depth value, sets it to be the new depth value.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:390
A ScheduleDAG for scheduling lists of MachineInstr.
virtual void finishBlock()
Cleans up after scheduling in the given block.
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
virtual void schedule()=0
Orders nodes according to selected style.
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:63
HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
TargetInstrInfo - Interface to description of machine instruction set.
Target-Independent Code Generator Pass Configuration Options.
CodeGenOptLevel getOptLevel() const
TargetSubtargetInfo - Generic base class for all target subtargets.
enum { ANTIDEP_NONE, ANTIDEP_CRITICAL, ANTIDEP_ALL } AntiDepBreakMode
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
constexpr double e
Definition: MathExtras.h:47
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
Definition: PtrState.h:41
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
AntiDepBreaker * createAggressiveAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI, TargetSubtargetInfo::RegClassVector &CriticalPathRCs)
char & PostRASchedulerID
PostRAScheduler - This pass performs post register allocation scheduling.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1938
AntiDepBreaker * createCriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.