LLVM 19.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 private:
103 bool enablePostRAScheduler(
104 const TargetSubtargetInfo &ST, CodeGenOptLevel OptLevel,
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(
145 const RegisterClassInfo &,
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.
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
200 "Post RA top-down list latency scheduler", false, false)
201
202SchedulePostRATDList::SchedulePostRATDList(
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, 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(MF, RCI, CriticalPathRCs)
221 : ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL)
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,
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 });
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,
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)
272
273 return ST.enablePostRAScheduler() &&
274 OptLevel >= ST.getOptLevelToEnablePostRAScheduler();
275}
276
277bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
278 if (skipFunction(Fn.getFunction()))
279 return false;
280
282 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
283 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
284 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
285
286 RegClassInfo.runOnMachineFunction(Fn);
287
289 TargetSubtargetInfo::ANTIDEP_NONE;
291
292 // Check that post-RA scheduling is enabled for this target.
293 // This may upgrade the AntiDepMode.
294 if (!enablePostRAScheduler(Fn.getSubtarget(), PassConfig->getOptLevel(),
295 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(&MBB);
327
328 // Schedule each sequence of instructions not interrupted by a label
329 // or anything else that effectively needs to shut down scheduling.
331 unsigned Count = MBB.size(), CurrentCount = Count;
332 for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) {
333 MachineInstr &MI = *std::prev(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, Fn)) {
339 Scheduler.enterRegion(&MBB, I, Current, 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, 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(&MBB, MBB.begin(), Current, 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.
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, RegionBegin, RegionEnd,
393 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.
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);
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, 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.
435}
436
437/// Apply each ScheduleDAGMutation step in order.
438void SchedulePostRATDList::postProcessDAG() {
439 for (auto &M : Mutations)
440 M->apply(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(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, &*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(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(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(&EntrySU);
529
530 // Add all leaves to Available queue.
531 for (SUnit &SUnit : SUnits) {
532 // It is available if it has no predecessors.
534 AvailableQueue.push(&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(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(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
571 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
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(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) {
600 dbgs() << "*** Will schedule a non-preferred instruction...\n");
601 FoundSUnit = NotPreferredSUnit;
602 } else {
603 AvailableQueue.push(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(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(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(RegionEnd, BB, 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(RegionEnd, BB, SU->getInstr());
675 else
676 // Null SUnit* is a noop.
677 TII->insertNoop(*BB, 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(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(DI);
689 MachineInstr *DbgValue = P.first;
690 MachineBasicBlock::iterator OrigPrivMI = P.second;
691 BB->splice(++OrigPrivMI, BB, DbgValue);
692 }
693 DbgValues.clear();
694 FirstDbgValue = nullptr;
695}
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:537
#define LLVM_DEBUG(X)
Definition: Debug.h:101
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)
#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:167
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:269
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:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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
virtual const TargetInstrInfo * getInstrInfo() const
#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:450
constexpr double e
Definition: MathExtras.h:31
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:1914
AntiDepBreaker * createCriticalAntiDepBreaker(MachineFunction &MFi, const RegisterClassInfo &RCI)
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.