1 //===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//
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
7 //===----------------------------------------------------------------------===//
9 // MachineScheduler schedules machine instructions after phi elimination. It
10 // preserves LiveIntervals so it can be invoked before register allocation.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/MachineScheduler.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/BitVector.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/PriorityQueue.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/iterator_range.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/CodeGen/LiveInterval.h"
24 #include "llvm/CodeGen/LiveIntervals.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/MachineDominators.h"
27 #include "llvm/CodeGen/MachineFunction.h"
28 #include "llvm/CodeGen/MachineFunctionPass.h"
29 #include "llvm/CodeGen/MachineInstr.h"
30 #include "llvm/CodeGen/MachineLoopInfo.h"
31 #include "llvm/CodeGen/MachineOperand.h"
32 #include "llvm/CodeGen/MachinePassRegistry.h"
33 #include "llvm/CodeGen/MachineRegisterInfo.h"
34 #include "llvm/CodeGen/Passes.h"
35 #include "llvm/CodeGen/RegisterClassInfo.h"
36 #include "llvm/CodeGen/RegisterPressure.h"
37 #include "llvm/CodeGen/ScheduleDAG.h"
38 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
39 #include "llvm/CodeGen/ScheduleDAGMutation.h"
40 #include "llvm/CodeGen/ScheduleDFS.h"
41 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
42 #include "llvm/CodeGen/SlotIndexes.h"
43 #include "llvm/CodeGen/TargetFrameLowering.h"
44 #include "llvm/CodeGen/TargetInstrInfo.h"
45 #include "llvm/CodeGen/TargetLowering.h"
46 #include "llvm/CodeGen/TargetPassConfig.h"
47 #include "llvm/CodeGen/TargetRegisterInfo.h"
48 #include "llvm/CodeGen/TargetSchedule.h"
49 #include "llvm/CodeGen/TargetSubtargetInfo.h"
50 #include "llvm/Config/llvm-config.h"
51 #include "llvm/MC/LaneBitmask.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/CommandLine.h"
54 #include "llvm/Support/Compiler.h"
55 #include "llvm/Support/Debug.h"
56 #include "llvm/Support/ErrorHandling.h"
57 #include "llvm/Support/GraphWriter.h"
58 #include "llvm/Support/MachineValueType.h"
59 #include "llvm/Support/raw_ostream.h"
73 #define DEBUG_TYPE "machine-scheduler"
77 cl::opt
<bool> ForceTopDown("misched-topdown", cl::Hidden
,
78 cl::desc("Force top-down list scheduling"));
79 cl::opt
<bool> ForceBottomUp("misched-bottomup", cl::Hidden
,
80 cl::desc("Force bottom-up list scheduling"));
82 DumpCriticalPathLength("misched-dcpl", cl::Hidden
,
83 cl::desc("Print critical path length to stdout"));
85 } // end namespace llvm
88 static cl::opt
<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden
,
89 cl::desc("Pop up a window to show MISched dags after they are processed"));
91 /// In some situations a few uninteresting nodes depend on nearly all other
92 /// nodes in the graph, provide a cutoff to hide them.
93 static cl::opt
<unsigned> ViewMISchedCutoff("view-misched-cutoff", cl::Hidden
,
94 cl::desc("Hide nodes with more predecessor/successor than cutoff"));
96 static cl::opt
<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden
,
97 cl::desc("Stop scheduling after N instructions"), cl::init(~0U));
99 static cl::opt
<std::string
> SchedOnlyFunc("misched-only-func", cl::Hidden
,
100 cl::desc("Only schedule this function"));
101 static cl::opt
<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden
,
102 cl::desc("Only schedule this MBB#"));
103 static cl::opt
<bool> PrintDAGs("misched-print-dags", cl::Hidden
,
104 cl::desc("Print schedule DAGs"));
106 static const bool ViewMISchedDAGs
= false;
107 static const bool PrintDAGs
= false;
110 /// Avoid quadratic complexity in unusually large basic blocks by limiting the
111 /// size of the ready lists.
112 static cl::opt
<unsigned> ReadyListLimit("misched-limit", cl::Hidden
,
113 cl::desc("Limit ready list to N instructions"), cl::init(256));
115 static cl::opt
<bool> EnableRegPressure("misched-regpressure", cl::Hidden
,
116 cl::desc("Enable register pressure scheduling."), cl::init(true));
118 static cl::opt
<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden
,
119 cl::desc("Enable cyclic critical path analysis."), cl::init(true));
121 static cl::opt
<bool> EnableMemOpCluster("misched-cluster", cl::Hidden
,
122 cl::desc("Enable memop clustering."),
125 static cl::opt
<bool> VerifyScheduling("verify-misched", cl::Hidden
,
126 cl::desc("Verify machine instrs before and after machine scheduling"));
128 // DAG subtrees must have at least this many nodes.
129 static const unsigned MinSubtreeSize
= 8;
131 // Pin the vtables to this file.
132 void MachineSchedStrategy::anchor() {}
134 void ScheduleDAGMutation::anchor() {}
136 //===----------------------------------------------------------------------===//
137 // Machine Instruction Scheduling Pass and Registry
138 //===----------------------------------------------------------------------===//
140 MachineSchedContext::MachineSchedContext() {
141 RegClassInfo
= new RegisterClassInfo();
144 MachineSchedContext::~MachineSchedContext() {
150 /// Base class for a machine scheduler class that can run at any point.
151 class MachineSchedulerBase
: public MachineSchedContext
,
152 public MachineFunctionPass
{
154 MachineSchedulerBase(char &ID
): MachineFunctionPass(ID
) {}
156 void print(raw_ostream
&O
, const Module
* = nullptr) const override
;
159 void scheduleRegions(ScheduleDAGInstrs
&Scheduler
, bool FixKillFlags
);
162 /// MachineScheduler runs after coalescing and before register allocation.
163 class MachineScheduler
: public MachineSchedulerBase
{
167 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
169 bool runOnMachineFunction(MachineFunction
&) override
;
171 static char ID
; // Class identification, replacement for typeinfo
174 ScheduleDAGInstrs
*createMachineScheduler();
177 /// PostMachineScheduler runs after shortly before code emission.
178 class PostMachineScheduler
: public MachineSchedulerBase
{
180 PostMachineScheduler();
182 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
184 bool runOnMachineFunction(MachineFunction
&) override
;
186 static char ID
; // Class identification, replacement for typeinfo
189 ScheduleDAGInstrs
*createPostMachineScheduler();
192 } // end anonymous namespace
194 char MachineScheduler::ID
= 0;
196 char &llvm::MachineSchedulerID
= MachineScheduler::ID
;
198 INITIALIZE_PASS_BEGIN(MachineScheduler
, DEBUG_TYPE
,
199 "Machine Instruction Scheduler", false, false)
200 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass
)
201 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo
)
202 INITIALIZE_PASS_DEPENDENCY(SlotIndexes
)
203 INITIALIZE_PASS_DEPENDENCY(LiveIntervals
)
204 INITIALIZE_PASS_END(MachineScheduler
, DEBUG_TYPE
,
205 "Machine Instruction Scheduler", false, false)
207 MachineScheduler::MachineScheduler() : MachineSchedulerBase(ID
) {
208 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
211 void MachineScheduler::getAnalysisUsage(AnalysisUsage
&AU
) const {
212 AU
.setPreservesCFG();
213 AU
.addRequiredID(MachineDominatorsID
);
214 AU
.addRequired
<MachineLoopInfo
>();
215 AU
.addRequired
<AAResultsWrapperPass
>();
216 AU
.addRequired
<TargetPassConfig
>();
217 AU
.addRequired
<SlotIndexes
>();
218 AU
.addPreserved
<SlotIndexes
>();
219 AU
.addRequired
<LiveIntervals
>();
220 AU
.addPreserved
<LiveIntervals
>();
221 MachineFunctionPass::getAnalysisUsage(AU
);
224 char PostMachineScheduler::ID
= 0;
226 char &llvm::PostMachineSchedulerID
= PostMachineScheduler::ID
;
228 INITIALIZE_PASS(PostMachineScheduler
, "postmisched",
229 "PostRA Machine Instruction Scheduler", false, false)
231 PostMachineScheduler::PostMachineScheduler() : MachineSchedulerBase(ID
) {
232 initializePostMachineSchedulerPass(*PassRegistry::getPassRegistry());
235 void PostMachineScheduler::getAnalysisUsage(AnalysisUsage
&AU
) const {
236 AU
.setPreservesCFG();
237 AU
.addRequiredID(MachineDominatorsID
);
238 AU
.addRequired
<MachineLoopInfo
>();
239 AU
.addRequired
<TargetPassConfig
>();
240 MachineFunctionPass::getAnalysisUsage(AU
);
243 MachinePassRegistry
<MachineSchedRegistry::ScheduleDAGCtor
>
244 MachineSchedRegistry::Registry
;
246 /// A dummy default scheduler factory indicates whether the scheduler
247 /// is overridden on the command line.
248 static ScheduleDAGInstrs
*useDefaultMachineSched(MachineSchedContext
*C
) {
252 /// MachineSchedOpt allows command line selection of the scheduler.
253 static cl::opt
<MachineSchedRegistry::ScheduleDAGCtor
, false,
254 RegisterPassParser
<MachineSchedRegistry
>>
255 MachineSchedOpt("misched",
256 cl::init(&useDefaultMachineSched
), cl::Hidden
,
257 cl::desc("Machine instruction scheduler to use"));
259 static MachineSchedRegistry
260 DefaultSchedRegistry("default", "Use the target's default scheduler choice.",
261 useDefaultMachineSched
);
263 static cl::opt
<bool> EnableMachineSched(
265 cl::desc("Enable the machine instruction scheduling pass."), cl::init(true),
268 static cl::opt
<bool> EnablePostRAMachineSched(
269 "enable-post-misched",
270 cl::desc("Enable the post-ra machine instruction scheduling pass."),
271 cl::init(true), cl::Hidden
);
273 /// Decrement this iterator until reaching the top or a non-debug instr.
274 static MachineBasicBlock::const_iterator
275 priorNonDebug(MachineBasicBlock::const_iterator I
,
276 MachineBasicBlock::const_iterator Beg
) {
277 assert(I
!= Beg
&& "reached the top of the region, cannot decrement");
279 if (!I
->isDebugInstr())
285 /// Non-const version.
286 static MachineBasicBlock::iterator
287 priorNonDebug(MachineBasicBlock::iterator I
,
288 MachineBasicBlock::const_iterator Beg
) {
289 return priorNonDebug(MachineBasicBlock::const_iterator(I
), Beg
)
290 .getNonConstIterator();
293 /// If this iterator is a debug value, increment until reaching the End or a
294 /// non-debug instruction.
295 static MachineBasicBlock::const_iterator
296 nextIfDebug(MachineBasicBlock::const_iterator I
,
297 MachineBasicBlock::const_iterator End
) {
298 for(; I
!= End
; ++I
) {
299 if (!I
->isDebugInstr())
305 /// Non-const version.
306 static MachineBasicBlock::iterator
307 nextIfDebug(MachineBasicBlock::iterator I
,
308 MachineBasicBlock::const_iterator End
) {
309 return nextIfDebug(MachineBasicBlock::const_iterator(I
), End
)
310 .getNonConstIterator();
313 /// Instantiate a ScheduleDAGInstrs that will be owned by the caller.
314 ScheduleDAGInstrs
*MachineScheduler::createMachineScheduler() {
315 // Select the scheduler, or set the default.
316 MachineSchedRegistry::ScheduleDAGCtor Ctor
= MachineSchedOpt
;
317 if (Ctor
!= useDefaultMachineSched
)
320 // Get the default scheduler set by the target for this function.
321 ScheduleDAGInstrs
*Scheduler
= PassConfig
->createMachineScheduler(this);
325 // Default to GenericScheduler.
326 return createGenericSchedLive(this);
329 /// Instantiate a ScheduleDAGInstrs for PostRA scheduling that will be owned by
330 /// the caller. We don't have a command line option to override the postRA
331 /// scheduler. The Target must configure it.
332 ScheduleDAGInstrs
*PostMachineScheduler::createPostMachineScheduler() {
333 // Get the postRA scheduler set by the target for this function.
334 ScheduleDAGInstrs
*Scheduler
= PassConfig
->createPostMachineScheduler(this);
338 // Default to GenericScheduler.
339 return createGenericSchedPostRA(this);
342 /// Top-level MachineScheduler pass driver.
344 /// Visit blocks in function order. Divide each block into scheduling regions
345 /// and visit them bottom-up. Visiting regions bottom-up is not required, but is
346 /// consistent with the DAG builder, which traverses the interior of the
347 /// scheduling regions bottom-up.
349 /// This design avoids exposing scheduling boundaries to the DAG builder,
350 /// simplifying the DAG builder's support for "special" target instructions.
351 /// At the same time the design allows target schedulers to operate across
352 /// scheduling boundaries, for example to bundle the boundary instructions
353 /// without reordering them. This creates complexity, because the target
354 /// scheduler must update the RegionBegin and RegionEnd positions cached by
355 /// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler
356 /// design would be to split blocks at scheduling boundaries, but LLVM has a
357 /// general bias against block splitting purely for implementation simplicity.
358 bool MachineScheduler::runOnMachineFunction(MachineFunction
&mf
) {
359 if (skipFunction(mf
.getFunction()))
362 if (EnableMachineSched
.getNumOccurrences()) {
363 if (!EnableMachineSched
)
365 } else if (!mf
.getSubtarget().enableMachineScheduler())
368 LLVM_DEBUG(dbgs() << "Before MISched:\n"; mf
.print(dbgs()));
370 // Initialize the context of the pass.
372 MLI
= &getAnalysis
<MachineLoopInfo
>();
373 MDT
= &getAnalysis
<MachineDominatorTree
>();
374 PassConfig
= &getAnalysis
<TargetPassConfig
>();
375 AA
= &getAnalysis
<AAResultsWrapperPass
>().getAAResults();
377 LIS
= &getAnalysis
<LiveIntervals
>();
379 if (VerifyScheduling
) {
380 LLVM_DEBUG(LIS
->dump());
381 MF
->verify(this, "Before machine scheduling.");
383 RegClassInfo
->runOnMachineFunction(*MF
);
385 // Instantiate the selected scheduler for this target, function, and
386 // optimization level.
387 std::unique_ptr
<ScheduleDAGInstrs
> Scheduler(createMachineScheduler());
388 scheduleRegions(*Scheduler
, false);
390 LLVM_DEBUG(LIS
->dump());
391 if (VerifyScheduling
)
392 MF
->verify(this, "After machine scheduling.");
396 bool PostMachineScheduler::runOnMachineFunction(MachineFunction
&mf
) {
397 if (skipFunction(mf
.getFunction()))
400 if (EnablePostRAMachineSched
.getNumOccurrences()) {
401 if (!EnablePostRAMachineSched
)
403 } else if (!mf
.getSubtarget().enablePostRAScheduler()) {
404 LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
407 LLVM_DEBUG(dbgs() << "Before post-MI-sched:\n"; mf
.print(dbgs()));
409 // Initialize the context of the pass.
411 MLI
= &getAnalysis
<MachineLoopInfo
>();
412 PassConfig
= &getAnalysis
<TargetPassConfig
>();
414 if (VerifyScheduling
)
415 MF
->verify(this, "Before post machine scheduling.");
417 // Instantiate the selected scheduler for this target, function, and
418 // optimization level.
419 std::unique_ptr
<ScheduleDAGInstrs
> Scheduler(createPostMachineScheduler());
420 scheduleRegions(*Scheduler
, true);
422 if (VerifyScheduling
)
423 MF
->verify(this, "After post machine scheduling.");
427 /// Return true of the given instruction should not be included in a scheduling
430 /// MachineScheduler does not currently support scheduling across calls. To
431 /// handle calls, the DAG builder needs to be modified to create register
432 /// anti/output dependencies on the registers clobbered by the call's regmask
433 /// operand. In PreRA scheduling, the stack pointer adjustment already prevents
434 /// scheduling across calls. In PostRA scheduling, we need the isCall to enforce
435 /// the boundary, but there would be no benefit to postRA scheduling across
436 /// calls this late anyway.
437 static bool isSchedBoundary(MachineBasicBlock::iterator MI
,
438 MachineBasicBlock
*MBB
,
440 const TargetInstrInfo
*TII
) {
441 return MI
->isCall() || TII
->isSchedulingBoundary(*MI
, MBB
, *MF
);
444 /// A region of an MBB for scheduling.
447 /// RegionBegin is the first instruction in the scheduling region, and
448 /// RegionEnd is either MBB->end() or the scheduling boundary after the
449 /// last instruction in the scheduling region. These iterators cannot refer
450 /// to instructions outside of the identified scheduling region because
451 /// those may be reordered before scheduling this region.
452 MachineBasicBlock::iterator RegionBegin
;
453 MachineBasicBlock::iterator RegionEnd
;
454 unsigned NumRegionInstrs
;
456 SchedRegion(MachineBasicBlock::iterator B
, MachineBasicBlock::iterator E
,
458 RegionBegin(B
), RegionEnd(E
), NumRegionInstrs(N
) {}
460 } // end anonymous namespace
462 using MBBRegionsVector
= SmallVector
<SchedRegion
, 16>;
465 getSchedRegions(MachineBasicBlock
*MBB
,
466 MBBRegionsVector
&Regions
,
467 bool RegionsTopDown
) {
468 MachineFunction
*MF
= MBB
->getParent();
469 const TargetInstrInfo
*TII
= MF
->getSubtarget().getInstrInfo();
471 MachineBasicBlock::iterator I
= nullptr;
472 for(MachineBasicBlock::iterator RegionEnd
= MBB
->end();
473 RegionEnd
!= MBB
->begin(); RegionEnd
= I
) {
475 // Avoid decrementing RegionEnd for blocks with no terminator.
476 if (RegionEnd
!= MBB
->end() ||
477 isSchedBoundary(&*std::prev(RegionEnd
), &*MBB
, MF
, TII
)) {
481 // The next region starts above the previous region. Look backward in the
482 // instruction stream until we find the nearest boundary.
483 unsigned NumRegionInstrs
= 0;
485 for (;I
!= MBB
->begin(); --I
) {
486 MachineInstr
&MI
= *std::prev(I
);
487 if (isSchedBoundary(&MI
, &*MBB
, MF
, TII
))
489 if (!MI
.isDebugInstr()) {
490 // MBB::size() uses instr_iterator to count. Here we need a bundle to
491 // count as a single instruction.
496 // It's possible we found a scheduling region that only has debug
497 // instructions. Don't bother scheduling these.
498 if (NumRegionInstrs
!= 0)
499 Regions
.push_back(SchedRegion(I
, RegionEnd
, NumRegionInstrs
));
503 std::reverse(Regions
.begin(), Regions
.end());
506 /// Main driver for both MachineScheduler and PostMachineScheduler.
507 void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs
&Scheduler
,
509 // Visit all machine basic blocks.
511 // TODO: Visit blocks in global postorder or postorder within the bottom-up
512 // loop tree. Then we can optionally compute global RegPressure.
513 for (MachineFunction::iterator MBB
= MF
->begin(), MBBEnd
= MF
->end();
514 MBB
!= MBBEnd
; ++MBB
) {
516 Scheduler
.startBlock(&*MBB
);
519 if (SchedOnlyFunc
.getNumOccurrences() && SchedOnlyFunc
!= MF
->getName())
521 if (SchedOnlyBlock
.getNumOccurrences()
522 && (int)SchedOnlyBlock
!= MBB
->getNumber())
526 // Break the block into scheduling regions [I, RegionEnd). RegionEnd
527 // points to the scheduling boundary at the bottom of the region. The DAG
528 // does not include RegionEnd, but the region does (i.e. the next
529 // RegionEnd is above the previous RegionBegin). If the current block has
530 // no terminator then RegionEnd == MBB->end() for the bottom region.
532 // All the regions of MBB are first found and stored in MBBRegions, which
533 // will be processed (MBB) top-down if initialized with true.
535 // The Scheduler may insert instructions during either schedule() or
536 // exitRegion(), even for empty regions. So the local iterators 'I' and
537 // 'RegionEnd' are invalid across these calls. Instructions must not be
538 // added to other regions than the current one without updating MBBRegions.
540 MBBRegionsVector MBBRegions
;
541 getSchedRegions(&*MBB
, MBBRegions
, Scheduler
.doMBBSchedRegionsTopDown());
542 for (MBBRegionsVector::iterator R
= MBBRegions
.begin();
543 R
!= MBBRegions
.end(); ++R
) {
544 MachineBasicBlock::iterator I
= R
->RegionBegin
;
545 MachineBasicBlock::iterator RegionEnd
= R
->RegionEnd
;
546 unsigned NumRegionInstrs
= R
->NumRegionInstrs
;
548 // Notify the scheduler of the region, even if we may skip scheduling
549 // it. Perhaps it still needs to be bundled.
550 Scheduler
.enterRegion(&*MBB
, I
, RegionEnd
, NumRegionInstrs
);
552 // Skip empty scheduling regions (0 or 1 schedulable instructions).
553 if (I
== RegionEnd
|| I
== std::prev(RegionEnd
)) {
554 // Close the current region. Bundle the terminator if needed.
555 // This invalidates 'RegionEnd' and 'I'.
556 Scheduler
.exitRegion();
559 LLVM_DEBUG(dbgs() << "********** MI Scheduling **********\n");
560 LLVM_DEBUG(dbgs() << MF
->getName() << ":" << printMBBReference(*MBB
)
561 << " " << MBB
->getName() << "\n From: " << *I
563 if (RegionEnd
!= MBB
->end()) dbgs() << *RegionEnd
;
564 else dbgs() << "End";
565 dbgs() << " RegionInstrs: " << NumRegionInstrs
<< '\n');
566 if (DumpCriticalPathLength
) {
567 errs() << MF
->getName();
568 errs() << ":%bb. " << MBB
->getNumber();
569 errs() << " " << MBB
->getName() << " \n";
572 // Schedule a region: possibly reorder instructions.
573 // This invalidates the original region iterators.
574 Scheduler
.schedule();
576 // Close the current region.
577 Scheduler
.exitRegion();
579 Scheduler
.finishBlock();
580 // FIXME: Ideally, no further passes should rely on kill flags. However,
581 // thumb2 size reduction is currently an exception, so the PostMIScheduler
584 Scheduler
.fixupKills(*MBB
);
586 Scheduler
.finalizeSchedule();
589 void MachineSchedulerBase::print(raw_ostream
&O
, const Module
* m
) const {
593 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
594 LLVM_DUMP_METHOD
void ReadyQueue::dump() const {
595 dbgs() << "Queue " << Name
<< ": ";
596 for (const SUnit
*SU
: Queue
)
597 dbgs() << SU
->NodeNum
<< " ";
602 //===----------------------------------------------------------------------===//
603 // ScheduleDAGMI - Basic machine instruction scheduling. This is
604 // independent of PreRA/PostRA scheduling and involves no extra book-keeping for
605 // virtual registers.
606 // ===----------------------------------------------------------------------===/
608 // Provide a vtable anchor.
609 ScheduleDAGMI::~ScheduleDAGMI() = default;
611 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When
612 /// NumPredsLeft reaches zero, release the successor node.
614 /// FIXME: Adjust SuccSU height based on MinLatency.
615 void ScheduleDAGMI::releaseSucc(SUnit
*SU
, SDep
*SuccEdge
) {
616 SUnit
*SuccSU
= SuccEdge
->getSUnit();
618 if (SuccEdge
->isWeak()) {
619 --SuccSU
->WeakPredsLeft
;
620 if (SuccEdge
->isCluster())
621 NextClusterSucc
= SuccSU
;
625 if (SuccSU
->NumPredsLeft
== 0) {
626 dbgs() << "*** Scheduling failed! ***\n";
628 dbgs() << " has been released too many times!\n";
629 llvm_unreachable(nullptr);
632 // SU->TopReadyCycle was set to CurrCycle when it was scheduled. However,
633 // CurrCycle may have advanced since then.
634 if (SuccSU
->TopReadyCycle
< SU
->TopReadyCycle
+ SuccEdge
->getLatency())
635 SuccSU
->TopReadyCycle
= SU
->TopReadyCycle
+ SuccEdge
->getLatency();
637 --SuccSU
->NumPredsLeft
;
638 if (SuccSU
->NumPredsLeft
== 0 && SuccSU
!= &ExitSU
)
639 SchedImpl
->releaseTopNode(SuccSU
);
642 /// releaseSuccessors - Call releaseSucc on each of SU's successors.
643 void ScheduleDAGMI::releaseSuccessors(SUnit
*SU
) {
644 for (SDep
&Succ
: SU
->Succs
)
645 releaseSucc(SU
, &Succ
);
648 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When
649 /// NumSuccsLeft reaches zero, release the predecessor node.
651 /// FIXME: Adjust PredSU height based on MinLatency.
652 void ScheduleDAGMI::releasePred(SUnit
*SU
, SDep
*PredEdge
) {
653 SUnit
*PredSU
= PredEdge
->getSUnit();
655 if (PredEdge
->isWeak()) {
656 --PredSU
->WeakSuccsLeft
;
657 if (PredEdge
->isCluster())
658 NextClusterPred
= PredSU
;
662 if (PredSU
->NumSuccsLeft
== 0) {
663 dbgs() << "*** Scheduling failed! ***\n";
665 dbgs() << " has been released too many times!\n";
666 llvm_unreachable(nullptr);
669 // SU->BotReadyCycle was set to CurrCycle when it was scheduled. However,
670 // CurrCycle may have advanced since then.
671 if (PredSU
->BotReadyCycle
< SU
->BotReadyCycle
+ PredEdge
->getLatency())
672 PredSU
->BotReadyCycle
= SU
->BotReadyCycle
+ PredEdge
->getLatency();
674 --PredSU
->NumSuccsLeft
;
675 if (PredSU
->NumSuccsLeft
== 0 && PredSU
!= &EntrySU
)
676 SchedImpl
->releaseBottomNode(PredSU
);
679 /// releasePredecessors - Call releasePred on each of SU's predecessors.
680 void ScheduleDAGMI::releasePredecessors(SUnit
*SU
) {
681 for (SDep
&Pred
: SU
->Preds
)
682 releasePred(SU
, &Pred
);
685 void ScheduleDAGMI::startBlock(MachineBasicBlock
*bb
) {
686 ScheduleDAGInstrs::startBlock(bb
);
687 SchedImpl
->enterMBB(bb
);
690 void ScheduleDAGMI::finishBlock() {
691 SchedImpl
->leaveMBB();
692 ScheduleDAGInstrs::finishBlock();
695 /// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
696 /// crossing a scheduling boundary. [begin, end) includes all instructions in
697 /// the region, including the boundary itself and single-instruction regions
698 /// that don't get scheduled.
699 void ScheduleDAGMI::enterRegion(MachineBasicBlock
*bb
,
700 MachineBasicBlock::iterator begin
,
701 MachineBasicBlock::iterator end
,
702 unsigned regioninstrs
)
704 ScheduleDAGInstrs::enterRegion(bb
, begin
, end
, regioninstrs
);
706 SchedImpl
->initPolicy(begin
, end
, regioninstrs
);
709 /// This is normally called from the main scheduler loop but may also be invoked
710 /// by the scheduling strategy to perform additional code motion.
711 void ScheduleDAGMI::moveInstruction(
712 MachineInstr
*MI
, MachineBasicBlock::iterator InsertPos
) {
713 // Advance RegionBegin if the first instruction moves down.
714 if (&*RegionBegin
== MI
)
717 // Update the instruction stream.
718 BB
->splice(InsertPos
, BB
, MI
);
720 // Update LiveIntervals
722 LIS
->handleMove(*MI
, /*UpdateFlags=*/true);
724 // Recede RegionBegin if an instruction moves above the first.
725 if (RegionBegin
== InsertPos
)
729 bool ScheduleDAGMI::checkSchedLimit() {
731 if (NumInstrsScheduled
== MISchedCutoff
&& MISchedCutoff
!= ~0U) {
732 CurrentTop
= CurrentBottom
;
735 ++NumInstrsScheduled
;
740 /// Per-region scheduling driver, called back from
741 /// MachineScheduler::runOnMachineFunction. This is a simplified driver that
742 /// does not consider liveness or register pressure. It is useful for PostRA
743 /// scheduling and potentially other custom schedulers.
744 void ScheduleDAGMI::schedule() {
745 LLVM_DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n");
746 LLVM_DEBUG(SchedImpl
->dumpPolicy());
753 SmallVector
<SUnit
*, 8> TopRoots
, BotRoots
;
754 findRootsAndBiasEdges(TopRoots
, BotRoots
);
757 if (PrintDAGs
) dump();
758 if (ViewMISchedDAGs
) viewGraph();
760 // Initialize the strategy before modifying the DAG.
761 // This may initialize a DFSResult to be used for queue priority.
762 SchedImpl
->initialize(this);
764 // Initialize ready queues now that the DAG and priority data are finalized.
765 initQueues(TopRoots
, BotRoots
);
767 bool IsTopNode
= false;
769 LLVM_DEBUG(dbgs() << "** ScheduleDAGMI::schedule picking next node\n");
770 SUnit
*SU
= SchedImpl
->pickNode(IsTopNode
);
773 assert(!SU
->isScheduled
&& "Node already scheduled");
774 if (!checkSchedLimit())
777 MachineInstr
*MI
= SU
->getInstr();
779 assert(SU
->isTopReady() && "node still has unscheduled dependencies");
780 if (&*CurrentTop
== MI
)
781 CurrentTop
= nextIfDebug(++CurrentTop
, CurrentBottom
);
783 moveInstruction(MI
, CurrentTop
);
785 assert(SU
->isBottomReady() && "node still has unscheduled dependencies");
786 MachineBasicBlock::iterator priorII
=
787 priorNonDebug(CurrentBottom
, CurrentTop
);
789 CurrentBottom
= priorII
;
791 if (&*CurrentTop
== MI
)
792 CurrentTop
= nextIfDebug(++CurrentTop
, priorII
);
793 moveInstruction(MI
, CurrentBottom
);
797 // Notify the scheduling strategy before updating the DAG.
798 // This sets the scheduled node's ReadyCycle to CurrCycle. When updateQueues
799 // runs, it can then use the accurate ReadyCycle time to determine whether
800 // newly released nodes can move to the readyQ.
801 SchedImpl
->schedNode(SU
, IsTopNode
);
803 updateQueues(SU
, IsTopNode
);
805 assert(CurrentTop
== CurrentBottom
&& "Nonempty unscheduled zone.");
810 dbgs() << "*** Final schedule for "
811 << printMBBReference(*begin()->getParent()) << " ***\n";
817 /// Apply each ScheduleDAGMutation step in order.
818 void ScheduleDAGMI::postprocessDAG() {
819 for (auto &m
: Mutations
)
824 findRootsAndBiasEdges(SmallVectorImpl
<SUnit
*> &TopRoots
,
825 SmallVectorImpl
<SUnit
*> &BotRoots
) {
826 for (SUnit
&SU
: SUnits
) {
827 assert(!SU
.isBoundaryNode() && "Boundary node should not be in SUnits");
829 // Order predecessors so DFSResult follows the critical path.
830 SU
.biasCriticalPath();
832 // A SUnit is ready to top schedule if it has no predecessors.
833 if (!SU
.NumPredsLeft
)
834 TopRoots
.push_back(&SU
);
835 // A SUnit is ready to bottom schedule if it has no successors.
836 if (!SU
.NumSuccsLeft
)
837 BotRoots
.push_back(&SU
);
839 ExitSU
.biasCriticalPath();
842 /// Identify DAG roots and setup scheduler queues.
843 void ScheduleDAGMI::initQueues(ArrayRef
<SUnit
*> TopRoots
,
844 ArrayRef
<SUnit
*> BotRoots
) {
845 NextClusterSucc
= nullptr;
846 NextClusterPred
= nullptr;
848 // Release all DAG roots for scheduling, not including EntrySU/ExitSU.
850 // Nodes with unreleased weak edges can still be roots.
851 // Release top roots in forward order.
852 for (SUnit
*SU
: TopRoots
)
853 SchedImpl
->releaseTopNode(SU
);
855 // Release bottom roots in reverse order so the higher priority nodes appear
856 // first. This is more natural and slightly more efficient.
857 for (SmallVectorImpl
<SUnit
*>::const_reverse_iterator
858 I
= BotRoots
.rbegin(), E
= BotRoots
.rend(); I
!= E
; ++I
) {
859 SchedImpl
->releaseBottomNode(*I
);
862 releaseSuccessors(&EntrySU
);
863 releasePredecessors(&ExitSU
);
865 SchedImpl
->registerRoots();
867 // Advance past initial DebugValues.
868 CurrentTop
= nextIfDebug(RegionBegin
, RegionEnd
);
869 CurrentBottom
= RegionEnd
;
872 /// Update scheduler queues after scheduling an instruction.
873 void ScheduleDAGMI::updateQueues(SUnit
*SU
, bool IsTopNode
) {
874 // Release dependent instructions for scheduling.
876 releaseSuccessors(SU
);
878 releasePredecessors(SU
);
880 SU
->isScheduled
= true;
883 /// Reinsert any remaining debug_values, just like the PostRA scheduler.
884 void ScheduleDAGMI::placeDebugValues() {
885 // If first instruction was a DBG_VALUE then put it back.
887 BB
->splice(RegionBegin
, BB
, FirstDbgValue
);
888 RegionBegin
= FirstDbgValue
;
891 for (std::vector
<std::pair
<MachineInstr
*, MachineInstr
*>>::iterator
892 DI
= DbgValues
.end(), DE
= DbgValues
.begin(); DI
!= DE
; --DI
) {
893 std::pair
<MachineInstr
*, MachineInstr
*> P
= *std::prev(DI
);
894 MachineInstr
*DbgValue
= P
.first
;
895 MachineBasicBlock::iterator OrigPrevMI
= P
.second
;
896 if (&*RegionBegin
== DbgValue
)
898 BB
->splice(++OrigPrevMI
, BB
, DbgValue
);
899 if (OrigPrevMI
== std::prev(RegionEnd
))
900 RegionEnd
= DbgValue
;
903 FirstDbgValue
= nullptr;
906 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
907 LLVM_DUMP_METHOD
void ScheduleDAGMI::dumpSchedule() const {
908 for (MachineBasicBlock::iterator MI
= begin(), ME
= end(); MI
!= ME
; ++MI
) {
909 if (SUnit
*SU
= getSUnit(&(*MI
)))
912 dbgs() << "Missing SUnit\n";
917 //===----------------------------------------------------------------------===//
918 // ScheduleDAGMILive - Base class for MachineInstr scheduling with LiveIntervals
920 //===----------------------------------------------------------------------===//
922 ScheduleDAGMILive::~ScheduleDAGMILive() {
926 void ScheduleDAGMILive::collectVRegUses(SUnit
&SU
) {
927 const MachineInstr
&MI
= *SU
.getInstr();
928 for (const MachineOperand
&MO
: MI
.operands()) {
933 if (TrackLaneMasks
&& !MO
.isUse())
936 Register Reg
= MO
.getReg();
937 if (!Register::isVirtualRegister(Reg
))
941 if (TrackLaneMasks
) {
942 bool FoundDef
= false;
943 for (const MachineOperand
&MO2
: MI
.operands()) {
944 if (MO2
.isReg() && MO2
.isDef() && MO2
.getReg() == Reg
&& !MO2
.isDead()) {
953 // Record this local VReg use.
954 VReg2SUnitMultiMap::iterator UI
= VRegUses
.find(Reg
);
955 for (; UI
!= VRegUses
.end(); ++UI
) {
959 if (UI
== VRegUses
.end())
960 VRegUses
.insert(VReg2SUnit(Reg
, LaneBitmask::getNone(), &SU
));
964 /// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
965 /// crossing a scheduling boundary. [begin, end) includes all instructions in
966 /// the region, including the boundary itself and single-instruction regions
967 /// that don't get scheduled.
968 void ScheduleDAGMILive::enterRegion(MachineBasicBlock
*bb
,
969 MachineBasicBlock::iterator begin
,
970 MachineBasicBlock::iterator end
,
971 unsigned regioninstrs
)
973 // ScheduleDAGMI initializes SchedImpl's per-region policy.
974 ScheduleDAGMI::enterRegion(bb
, begin
, end
, regioninstrs
);
976 // For convenience remember the end of the liveness region.
977 LiveRegionEnd
= (RegionEnd
== bb
->end()) ? RegionEnd
: std::next(RegionEnd
);
979 SUPressureDiffs
.clear();
981 ShouldTrackPressure
= SchedImpl
->shouldTrackPressure();
982 ShouldTrackLaneMasks
= SchedImpl
->shouldTrackLaneMasks();
984 assert((!ShouldTrackLaneMasks
|| ShouldTrackPressure
) &&
985 "ShouldTrackLaneMasks requires ShouldTrackPressure");
988 // Setup the register pressure trackers for the top scheduled and bottom
989 // scheduled regions.
990 void ScheduleDAGMILive::initRegPressure() {
992 VRegUses
.setUniverse(MRI
.getNumVirtRegs());
993 for (SUnit
&SU
: SUnits
)
996 TopRPTracker
.init(&MF
, RegClassInfo
, LIS
, BB
, RegionBegin
,
997 ShouldTrackLaneMasks
, false);
998 BotRPTracker
.init(&MF
, RegClassInfo
, LIS
, BB
, LiveRegionEnd
,
999 ShouldTrackLaneMasks
, false);
1001 // Close the RPTracker to finalize live ins.
1002 RPTracker
.closeRegion();
1004 LLVM_DEBUG(RPTracker
.dump());
1006 // Initialize the live ins and live outs.
1007 TopRPTracker
.addLiveRegs(RPTracker
.getPressure().LiveInRegs
);
1008 BotRPTracker
.addLiveRegs(RPTracker
.getPressure().LiveOutRegs
);
1010 // Close one end of the tracker so we can call
1011 // getMaxUpward/DownwardPressureDelta before advancing across any
1012 // instructions. This converts currently live regs into live ins/outs.
1013 TopRPTracker
.closeTop();
1014 BotRPTracker
.closeBottom();
1016 BotRPTracker
.initLiveThru(RPTracker
);
1017 if (!BotRPTracker
.getLiveThru().empty()) {
1018 TopRPTracker
.initLiveThru(BotRPTracker
.getLiveThru());
1019 LLVM_DEBUG(dbgs() << "Live Thru: ";
1020 dumpRegSetPressure(BotRPTracker
.getLiveThru(), TRI
));
1023 // For each live out vreg reduce the pressure change associated with other
1024 // uses of the same vreg below the live-out reaching def.
1025 updatePressureDiffs(RPTracker
.getPressure().LiveOutRegs
);
1027 // Account for liveness generated by the region boundary.
1028 if (LiveRegionEnd
!= RegionEnd
) {
1029 SmallVector
<RegisterMaskPair
, 8> LiveUses
;
1030 BotRPTracker
.recede(&LiveUses
);
1031 updatePressureDiffs(LiveUses
);
1034 LLVM_DEBUG(dbgs() << "Top Pressure:\n";
1035 dumpRegSetPressure(TopRPTracker
.getRegSetPressureAtPos(), TRI
);
1036 dbgs() << "Bottom Pressure:\n";
1037 dumpRegSetPressure(BotRPTracker
.getRegSetPressureAtPos(), TRI
););
1039 assert((BotRPTracker
.getPos() == RegionEnd
||
1040 (RegionEnd
->isDebugInstr() &&
1041 BotRPTracker
.getPos() == priorNonDebug(RegionEnd
, RegionBegin
))) &&
1042 "Can't find the region bottom");
1044 // Cache the list of excess pressure sets in this region. This will also track
1045 // the max pressure in the scheduled code for these sets.
1046 RegionCriticalPSets
.clear();
1047 const std::vector
<unsigned> &RegionPressure
=
1048 RPTracker
.getPressure().MaxSetPressure
;
1049 for (unsigned i
= 0, e
= RegionPressure
.size(); i
< e
; ++i
) {
1050 unsigned Limit
= RegClassInfo
->getRegPressureSetLimit(i
);
1051 if (RegionPressure
[i
] > Limit
) {
1052 LLVM_DEBUG(dbgs() << TRI
->getRegPressureSetName(i
) << " Limit " << Limit
1053 << " Actual " << RegionPressure
[i
] << "\n");
1054 RegionCriticalPSets
.push_back(PressureChange(i
));
1057 LLVM_DEBUG(dbgs() << "Excess PSets: ";
1058 for (const PressureChange
&RCPS
1059 : RegionCriticalPSets
) dbgs()
1060 << TRI
->getRegPressureSetName(RCPS
.getPSet()) << " ";
1064 void ScheduleDAGMILive::
1065 updateScheduledPressure(const SUnit
*SU
,
1066 const std::vector
<unsigned> &NewMaxPressure
) {
1067 const PressureDiff
&PDiff
= getPressureDiff(SU
);
1068 unsigned CritIdx
= 0, CritEnd
= RegionCriticalPSets
.size();
1069 for (const PressureChange
&PC
: PDiff
) {
1072 unsigned ID
= PC
.getPSet();
1073 while (CritIdx
!= CritEnd
&& RegionCriticalPSets
[CritIdx
].getPSet() < ID
)
1075 if (CritIdx
!= CritEnd
&& RegionCriticalPSets
[CritIdx
].getPSet() == ID
) {
1076 if ((int)NewMaxPressure
[ID
] > RegionCriticalPSets
[CritIdx
].getUnitInc()
1077 && NewMaxPressure
[ID
] <= (unsigned)std::numeric_limits
<int16_t>::max())
1078 RegionCriticalPSets
[CritIdx
].setUnitInc(NewMaxPressure
[ID
]);
1080 unsigned Limit
= RegClassInfo
->getRegPressureSetLimit(ID
);
1081 if (NewMaxPressure
[ID
] >= Limit
- 2) {
1082 LLVM_DEBUG(dbgs() << " " << TRI
->getRegPressureSetName(ID
) << ": "
1083 << NewMaxPressure
[ID
]
1084 << ((NewMaxPressure
[ID
] > Limit
) ? " > " : " <= ")
1085 << Limit
<< "(+ " << BotRPTracker
.getLiveThru()[ID
]
1091 /// Update the PressureDiff array for liveness after scheduling this
1093 void ScheduleDAGMILive::updatePressureDiffs(
1094 ArrayRef
<RegisterMaskPair
> LiveUses
) {
1095 for (const RegisterMaskPair
&P
: LiveUses
) {
1096 unsigned Reg
= P
.RegUnit
;
1097 /// FIXME: Currently assuming single-use physregs.
1098 if (!Register::isVirtualRegister(Reg
))
1101 if (ShouldTrackLaneMasks
) {
1102 // If the register has just become live then other uses won't change
1103 // this fact anymore => decrement pressure.
1104 // If the register has just become dead then other uses make it come
1105 // back to life => increment pressure.
1106 bool Decrement
= P
.LaneMask
.any();
1108 for (const VReg2SUnit
&V2SU
1109 : make_range(VRegUses
.find(Reg
), VRegUses
.end())) {
1110 SUnit
&SU
= *V2SU
.SU
;
1111 if (SU
.isScheduled
|| &SU
== &ExitSU
)
1114 PressureDiff
&PDiff
= getPressureDiff(&SU
);
1115 PDiff
.addPressureChange(Reg
, Decrement
, &MRI
);
1116 LLVM_DEBUG(dbgs() << " UpdateRegP: SU(" << SU
.NodeNum
<< ") "
1117 << printReg(Reg
, TRI
) << ':'
1118 << PrintLaneMask(P
.LaneMask
) << ' ' << *SU
.getInstr();
1119 dbgs() << " to "; PDiff
.dump(*TRI
););
1122 assert(P
.LaneMask
.any());
1123 LLVM_DEBUG(dbgs() << " LiveReg: " << printVRegOrUnit(Reg
, TRI
) << "\n");
1124 // This may be called before CurrentBottom has been initialized. However,
1125 // BotRPTracker must have a valid position. We want the value live into the
1126 // instruction or live out of the block, so ask for the previous
1127 // instruction's live-out.
1128 const LiveInterval
&LI
= LIS
->getInterval(Reg
);
1130 MachineBasicBlock::const_iterator I
=
1131 nextIfDebug(BotRPTracker
.getPos(), BB
->end());
1133 VNI
= LI
.getVNInfoBefore(LIS
->getMBBEndIdx(BB
));
1135 LiveQueryResult LRQ
= LI
.Query(LIS
->getInstructionIndex(*I
));
1136 VNI
= LRQ
.valueIn();
1138 // RegisterPressureTracker guarantees that readsReg is true for LiveUses.
1139 assert(VNI
&& "No live value at use.");
1140 for (const VReg2SUnit
&V2SU
1141 : make_range(VRegUses
.find(Reg
), VRegUses
.end())) {
1142 SUnit
*SU
= V2SU
.SU
;
1143 // If this use comes before the reaching def, it cannot be a last use,
1144 // so decrease its pressure change.
1145 if (!SU
->isScheduled
&& SU
!= &ExitSU
) {
1146 LiveQueryResult LRQ
=
1147 LI
.Query(LIS
->getInstructionIndex(*SU
->getInstr()));
1148 if (LRQ
.valueIn() == VNI
) {
1149 PressureDiff
&PDiff
= getPressureDiff(SU
);
1150 PDiff
.addPressureChange(Reg
, true, &MRI
);
1151 LLVM_DEBUG(dbgs() << " UpdateRegP: SU(" << SU
->NodeNum
<< ") "
1153 dbgs() << " to "; PDiff
.dump(*TRI
););
1161 void ScheduleDAGMILive::dump() const {
1162 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1163 if (EntrySU
.getInstr() != nullptr)
1164 dumpNodeAll(EntrySU
);
1165 for (const SUnit
&SU
: SUnits
) {
1167 if (ShouldTrackPressure
) {
1168 dbgs() << " Pressure Diff : ";
1169 getPressureDiff(&SU
).dump(*TRI
);
1171 dbgs() << " Single Issue : ";
1172 if (SchedModel
.mustBeginGroup(SU
.getInstr()) &&
1173 SchedModel
.mustEndGroup(SU
.getInstr()))
1179 if (ExitSU
.getInstr() != nullptr)
1180 dumpNodeAll(ExitSU
);
1184 /// schedule - Called back from MachineScheduler::runOnMachineFunction
1185 /// after setting up the current scheduling region. [RegionBegin, RegionEnd)
1186 /// only includes instructions that have DAG nodes, not scheduling boundaries.
1188 /// This is a skeletal driver, with all the functionality pushed into helpers,
1189 /// so that it can be easily extended by experimental schedulers. Generally,
1190 /// implementing MachineSchedStrategy should be sufficient to implement a new
1191 /// scheduling algorithm. However, if a scheduler further subclasses
1192 /// ScheduleDAGMILive then it will want to override this virtual method in order
1193 /// to update any specialized state.
1194 void ScheduleDAGMILive::schedule() {
1195 LLVM_DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n");
1196 LLVM_DEBUG(SchedImpl
->dumpPolicy());
1197 buildDAGWithRegPressure();
1201 SmallVector
<SUnit
*, 8> TopRoots
, BotRoots
;
1202 findRootsAndBiasEdges(TopRoots
, BotRoots
);
1204 // Initialize the strategy before modifying the DAG.
1205 // This may initialize a DFSResult to be used for queue priority.
1206 SchedImpl
->initialize(this);
1209 if (PrintDAGs
) dump();
1210 if (ViewMISchedDAGs
) viewGraph();
1212 // Initialize ready queues now that the DAG and priority data are finalized.
1213 initQueues(TopRoots
, BotRoots
);
1215 bool IsTopNode
= false;
1217 LLVM_DEBUG(dbgs() << "** ScheduleDAGMILive::schedule picking next node\n");
1218 SUnit
*SU
= SchedImpl
->pickNode(IsTopNode
);
1221 assert(!SU
->isScheduled
&& "Node already scheduled");
1222 if (!checkSchedLimit())
1225 scheduleMI(SU
, IsTopNode
);
1228 unsigned SubtreeID
= DFSResult
->getSubtreeID(SU
);
1229 if (!ScheduledTrees
.test(SubtreeID
)) {
1230 ScheduledTrees
.set(SubtreeID
);
1231 DFSResult
->scheduleTree(SubtreeID
);
1232 SchedImpl
->scheduleTree(SubtreeID
);
1236 // Notify the scheduling strategy after updating the DAG.
1237 SchedImpl
->schedNode(SU
, IsTopNode
);
1239 updateQueues(SU
, IsTopNode
);
1241 assert(CurrentTop
== CurrentBottom
&& "Nonempty unscheduled zone.");
1246 dbgs() << "*** Final schedule for "
1247 << printMBBReference(*begin()->getParent()) << " ***\n";
1253 /// Build the DAG and setup three register pressure trackers.
1254 void ScheduleDAGMILive::buildDAGWithRegPressure() {
1255 if (!ShouldTrackPressure
) {
1257 RegionCriticalPSets
.clear();
1258 buildSchedGraph(AA
);
1262 // Initialize the register pressure tracker used by buildSchedGraph.
1263 RPTracker
.init(&MF
, RegClassInfo
, LIS
, BB
, LiveRegionEnd
,
1264 ShouldTrackLaneMasks
, /*TrackUntiedDefs=*/true);
1266 // Account for liveness generate by the region boundary.
1267 if (LiveRegionEnd
!= RegionEnd
)
1270 // Build the DAG, and compute current register pressure.
1271 buildSchedGraph(AA
, &RPTracker
, &SUPressureDiffs
, LIS
, ShouldTrackLaneMasks
);
1273 // Initialize top/bottom trackers after computing region pressure.
1277 void ScheduleDAGMILive::computeDFSResult() {
1279 DFSResult
= new SchedDFSResult(/*BottomU*/true, MinSubtreeSize
);
1281 ScheduledTrees
.clear();
1282 DFSResult
->resize(SUnits
.size());
1283 DFSResult
->compute(SUnits
);
1284 ScheduledTrees
.resize(DFSResult
->getNumSubtrees());
1287 /// Compute the max cyclic critical path through the DAG. The scheduling DAG
1288 /// only provides the critical path for single block loops. To handle loops that
1289 /// span blocks, we could use the vreg path latencies provided by
1290 /// MachineTraceMetrics instead. However, MachineTraceMetrics is not currently
1291 /// available for use in the scheduler.
1293 /// The cyclic path estimation identifies a def-use pair that crosses the back
1294 /// edge and considers the depth and height of the nodes. For example, consider
1295 /// the following instruction sequence where each instruction has unit latency
1296 /// and defines an epomymous virtual register:
1298 /// a->b(a,c)->c(b)->d(c)->exit
1300 /// The cyclic critical path is a two cycles: b->c->b
1301 /// The acyclic critical path is four cycles: a->b->c->d->exit
1302 /// LiveOutHeight = height(c) = len(c->d->exit) = 2
1303 /// LiveOutDepth = depth(c) + 1 = len(a->b->c) + 1 = 3
1304 /// LiveInHeight = height(b) + 1 = len(b->c->d->exit) + 1 = 4
1305 /// LiveInDepth = depth(b) = len(a->b) = 1
1307 /// LiveOutDepth - LiveInDepth = 3 - 1 = 2
1308 /// LiveInHeight - LiveOutHeight = 4 - 2 = 2
1309 /// CyclicCriticalPath = min(2, 2) = 2
1311 /// This could be relevant to PostRA scheduling, but is currently implemented
1312 /// assuming LiveIntervals.
1313 unsigned ScheduleDAGMILive::computeCyclicCriticalPath() {
1314 // This only applies to single block loop.
1315 if (!BB
->isSuccessor(BB
))
1318 unsigned MaxCyclicLatency
= 0;
1319 // Visit each live out vreg def to find def/use pairs that cross iterations.
1320 for (const RegisterMaskPair
&P
: RPTracker
.getPressure().LiveOutRegs
) {
1321 unsigned Reg
= P
.RegUnit
;
1322 if (!Register::isVirtualRegister(Reg
))
1324 const LiveInterval
&LI
= LIS
->getInterval(Reg
);
1325 const VNInfo
*DefVNI
= LI
.getVNInfoBefore(LIS
->getMBBEndIdx(BB
));
1329 MachineInstr
*DefMI
= LIS
->getInstructionFromIndex(DefVNI
->def
);
1330 const SUnit
*DefSU
= getSUnit(DefMI
);
1334 unsigned LiveOutHeight
= DefSU
->getHeight();
1335 unsigned LiveOutDepth
= DefSU
->getDepth() + DefSU
->Latency
;
1336 // Visit all local users of the vreg def.
1337 for (const VReg2SUnit
&V2SU
1338 : make_range(VRegUses
.find(Reg
), VRegUses
.end())) {
1339 SUnit
*SU
= V2SU
.SU
;
1343 // Only consider uses of the phi.
1344 LiveQueryResult LRQ
= LI
.Query(LIS
->getInstructionIndex(*SU
->getInstr()));
1345 if (!LRQ
.valueIn()->isPHIDef())
1348 // Assume that a path spanning two iterations is a cycle, which could
1349 // overestimate in strange cases. This allows cyclic latency to be
1350 // estimated as the minimum slack of the vreg's depth or height.
1351 unsigned CyclicLatency
= 0;
1352 if (LiveOutDepth
> SU
->getDepth())
1353 CyclicLatency
= LiveOutDepth
- SU
->getDepth();
1355 unsigned LiveInHeight
= SU
->getHeight() + DefSU
->Latency
;
1356 if (LiveInHeight
> LiveOutHeight
) {
1357 if (LiveInHeight
- LiveOutHeight
< CyclicLatency
)
1358 CyclicLatency
= LiveInHeight
- LiveOutHeight
;
1362 LLVM_DEBUG(dbgs() << "Cyclic Path: SU(" << DefSU
->NodeNum
<< ") -> SU("
1363 << SU
->NodeNum
<< ") = " << CyclicLatency
<< "c\n");
1364 if (CyclicLatency
> MaxCyclicLatency
)
1365 MaxCyclicLatency
= CyclicLatency
;
1368 LLVM_DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency
<< "c\n");
1369 return MaxCyclicLatency
;
1372 /// Release ExitSU predecessors and setup scheduler queues. Re-position
1373 /// the Top RP tracker in case the region beginning has changed.
1374 void ScheduleDAGMILive::initQueues(ArrayRef
<SUnit
*> TopRoots
,
1375 ArrayRef
<SUnit
*> BotRoots
) {
1376 ScheduleDAGMI::initQueues(TopRoots
, BotRoots
);
1377 if (ShouldTrackPressure
) {
1378 assert(TopRPTracker
.getPos() == RegionBegin
&& "bad initial Top tracker");
1379 TopRPTracker
.setPos(CurrentTop
);
1383 /// Move an instruction and update register pressure.
1384 void ScheduleDAGMILive::scheduleMI(SUnit
*SU
, bool IsTopNode
) {
1385 // Move the instruction to its new location in the instruction stream.
1386 MachineInstr
*MI
= SU
->getInstr();
1389 assert(SU
->isTopReady() && "node still has unscheduled dependencies");
1390 if (&*CurrentTop
== MI
)
1391 CurrentTop
= nextIfDebug(++CurrentTop
, CurrentBottom
);
1393 moveInstruction(MI
, CurrentTop
);
1394 TopRPTracker
.setPos(MI
);
1397 if (ShouldTrackPressure
) {
1398 // Update top scheduled pressure.
1399 RegisterOperands RegOpers
;
1400 RegOpers
.collect(*MI
, *TRI
, MRI
, ShouldTrackLaneMasks
, false);
1401 if (ShouldTrackLaneMasks
) {
1402 // Adjust liveness and add missing dead+read-undef flags.
1403 SlotIndex SlotIdx
= LIS
->getInstructionIndex(*MI
).getRegSlot();
1404 RegOpers
.adjustLaneLiveness(*LIS
, MRI
, SlotIdx
, MI
);
1406 // Adjust for missing dead-def flags.
1407 RegOpers
.detectDeadDefs(*MI
, *LIS
);
1410 TopRPTracker
.advance(RegOpers
);
1411 assert(TopRPTracker
.getPos() == CurrentTop
&& "out of sync");
1412 LLVM_DEBUG(dbgs() << "Top Pressure:\n"; dumpRegSetPressure(
1413 TopRPTracker
.getRegSetPressureAtPos(), TRI
););
1415 updateScheduledPressure(SU
, TopRPTracker
.getPressure().MaxSetPressure
);
1418 assert(SU
->isBottomReady() && "node still has unscheduled dependencies");
1419 MachineBasicBlock::iterator priorII
=
1420 priorNonDebug(CurrentBottom
, CurrentTop
);
1421 if (&*priorII
== MI
)
1422 CurrentBottom
= priorII
;
1424 if (&*CurrentTop
== MI
) {
1425 CurrentTop
= nextIfDebug(++CurrentTop
, priorII
);
1426 TopRPTracker
.setPos(CurrentTop
);
1428 moveInstruction(MI
, CurrentBottom
);
1430 BotRPTracker
.setPos(CurrentBottom
);
1432 if (ShouldTrackPressure
) {
1433 RegisterOperands RegOpers
;
1434 RegOpers
.collect(*MI
, *TRI
, MRI
, ShouldTrackLaneMasks
, false);
1435 if (ShouldTrackLaneMasks
) {
1436 // Adjust liveness and add missing dead+read-undef flags.
1437 SlotIndex SlotIdx
= LIS
->getInstructionIndex(*MI
).getRegSlot();
1438 RegOpers
.adjustLaneLiveness(*LIS
, MRI
, SlotIdx
, MI
);
1440 // Adjust for missing dead-def flags.
1441 RegOpers
.detectDeadDefs(*MI
, *LIS
);
1444 if (BotRPTracker
.getPos() != CurrentBottom
)
1445 BotRPTracker
.recedeSkipDebugValues();
1446 SmallVector
<RegisterMaskPair
, 8> LiveUses
;
1447 BotRPTracker
.recede(RegOpers
, &LiveUses
);
1448 assert(BotRPTracker
.getPos() == CurrentBottom
&& "out of sync");
1449 LLVM_DEBUG(dbgs() << "Bottom Pressure:\n"; dumpRegSetPressure(
1450 BotRPTracker
.getRegSetPressureAtPos(), TRI
););
1452 updateScheduledPressure(SU
, BotRPTracker
.getPressure().MaxSetPressure
);
1453 updatePressureDiffs(LiveUses
);
1458 //===----------------------------------------------------------------------===//
1459 // BaseMemOpClusterMutation - DAG post-processing to cluster loads or stores.
1460 //===----------------------------------------------------------------------===//
1464 /// Post-process the DAG to create cluster edges between neighboring
1465 /// loads or between neighboring stores.
1466 class BaseMemOpClusterMutation
: public ScheduleDAGMutation
{
1469 const MachineOperand
*BaseOp
;
1472 MemOpInfo(SUnit
*su
, const MachineOperand
*Op
, int64_t ofs
)
1473 : SU(su
), BaseOp(Op
), Offset(ofs
) {}
1475 bool operator<(const MemOpInfo
&RHS
) const {
1476 if (BaseOp
->getType() != RHS
.BaseOp
->getType())
1477 return BaseOp
->getType() < RHS
.BaseOp
->getType();
1479 if (BaseOp
->isReg())
1480 return std::make_tuple(BaseOp
->getReg(), Offset
, SU
->NodeNum
) <
1481 std::make_tuple(RHS
.BaseOp
->getReg(), RHS
.Offset
,
1483 if (BaseOp
->isFI()) {
1484 const MachineFunction
&MF
=
1485 *BaseOp
->getParent()->getParent()->getParent();
1486 const TargetFrameLowering
&TFI
= *MF
.getSubtarget().getFrameLowering();
1487 bool StackGrowsDown
= TFI
.getStackGrowthDirection() ==
1488 TargetFrameLowering::StackGrowsDown
;
1489 // Can't use tuple comparison here since we might need to use a
1490 // different order when the stack grows down.
1491 if (BaseOp
->getIndex() != RHS
.BaseOp
->getIndex())
1492 return StackGrowsDown
? BaseOp
->getIndex() > RHS
.BaseOp
->getIndex()
1493 : BaseOp
->getIndex() < RHS
.BaseOp
->getIndex();
1495 if (Offset
!= RHS
.Offset
)
1496 return StackGrowsDown
? Offset
> RHS
.Offset
: Offset
< RHS
.Offset
;
1498 return SU
->NodeNum
< RHS
.SU
->NodeNum
;
1501 llvm_unreachable("MemOpClusterMutation only supports register or frame "
1506 const TargetInstrInfo
*TII
;
1507 const TargetRegisterInfo
*TRI
;
1511 BaseMemOpClusterMutation(const TargetInstrInfo
*tii
,
1512 const TargetRegisterInfo
*tri
, bool IsLoad
)
1513 : TII(tii
), TRI(tri
), IsLoad(IsLoad
) {}
1515 void apply(ScheduleDAGInstrs
*DAGInstrs
) override
;
1518 void clusterNeighboringMemOps(ArrayRef
<SUnit
*> MemOps
, ScheduleDAGInstrs
*DAG
);
1521 class StoreClusterMutation
: public BaseMemOpClusterMutation
{
1523 StoreClusterMutation(const TargetInstrInfo
*tii
,
1524 const TargetRegisterInfo
*tri
)
1525 : BaseMemOpClusterMutation(tii
, tri
, false) {}
1528 class LoadClusterMutation
: public BaseMemOpClusterMutation
{
1530 LoadClusterMutation(const TargetInstrInfo
*tii
, const TargetRegisterInfo
*tri
)
1531 : BaseMemOpClusterMutation(tii
, tri
, true) {}
1534 } // end anonymous namespace
1538 std::unique_ptr
<ScheduleDAGMutation
>
1539 createLoadClusterDAGMutation(const TargetInstrInfo
*TII
,
1540 const TargetRegisterInfo
*TRI
) {
1541 return EnableMemOpCluster
? std::make_unique
<LoadClusterMutation
>(TII
, TRI
)
1545 std::unique_ptr
<ScheduleDAGMutation
>
1546 createStoreClusterDAGMutation(const TargetInstrInfo
*TII
,
1547 const TargetRegisterInfo
*TRI
) {
1548 return EnableMemOpCluster
? std::make_unique
<StoreClusterMutation
>(TII
, TRI
)
1552 } // end namespace llvm
1554 void BaseMemOpClusterMutation::clusterNeighboringMemOps(
1555 ArrayRef
<SUnit
*> MemOps
, ScheduleDAGInstrs
*DAG
) {
1556 SmallVector
<MemOpInfo
, 32> MemOpRecords
;
1557 for (SUnit
*SU
: MemOps
) {
1558 const MachineOperand
*BaseOp
;
1560 if (TII
->getMemOperandWithOffset(*SU
->getInstr(), BaseOp
, Offset
, TRI
))
1561 MemOpRecords
.push_back(MemOpInfo(SU
, BaseOp
, Offset
));
1563 if (MemOpRecords
.size() < 2)
1566 llvm::sort(MemOpRecords
);
1567 unsigned ClusterLength
= 1;
1568 for (unsigned Idx
= 0, End
= MemOpRecords
.size(); Idx
< (End
- 1); ++Idx
) {
1569 SUnit
*SUa
= MemOpRecords
[Idx
].SU
;
1570 SUnit
*SUb
= MemOpRecords
[Idx
+1].SU
;
1571 if (TII
->shouldClusterMemOps(*MemOpRecords
[Idx
].BaseOp
,
1572 *MemOpRecords
[Idx
+ 1].BaseOp
,
1574 DAG
->addEdge(SUb
, SDep(SUa
, SDep::Cluster
))) {
1575 LLVM_DEBUG(dbgs() << "Cluster ld/st SU(" << SUa
->NodeNum
<< ") - SU("
1576 << SUb
->NodeNum
<< ")\n");
1577 // Copy successor edges from SUa to SUb. Interleaving computation
1578 // dependent on SUa can prevent load combining due to register reuse.
1579 // Predecessor edges do not need to be copied from SUb to SUa since nearby
1580 // loads should have effectively the same inputs.
1581 for (const SDep
&Succ
: SUa
->Succs
) {
1582 if (Succ
.getSUnit() == SUb
)
1584 LLVM_DEBUG(dbgs() << " Copy Succ SU(" << Succ
.getSUnit()->NodeNum
1586 DAG
->addEdge(Succ
.getSUnit(), SDep(SUb
, SDep::Artificial
));
1594 /// Callback from DAG postProcessing to create cluster edges for loads.
1595 void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs
*DAG
) {
1596 // Map DAG NodeNum to store chain ID.
1597 DenseMap
<unsigned, unsigned> StoreChainIDs
;
1598 // Map each store chain to a set of dependent MemOps.
1599 SmallVector
<SmallVector
<SUnit
*,4>, 32> StoreChainDependents
;
1600 for (SUnit
&SU
: DAG
->SUnits
) {
1601 if ((IsLoad
&& !SU
.getInstr()->mayLoad()) ||
1602 (!IsLoad
&& !SU
.getInstr()->mayStore()))
1605 unsigned ChainPredID
= DAG
->SUnits
.size();
1606 for (const SDep
&Pred
: SU
.Preds
) {
1607 if (Pred
.isCtrl()) {
1608 ChainPredID
= Pred
.getSUnit()->NodeNum
;
1612 // Check if this chain-like pred has been seen
1613 // before. ChainPredID==MaxNodeID at the top of the schedule.
1614 unsigned NumChains
= StoreChainDependents
.size();
1615 std::pair
<DenseMap
<unsigned, unsigned>::iterator
, bool> Result
=
1616 StoreChainIDs
.insert(std::make_pair(ChainPredID
, NumChains
));
1618 StoreChainDependents
.resize(NumChains
+ 1);
1619 StoreChainDependents
[Result
.first
->second
].push_back(&SU
);
1622 // Iterate over the store chains.
1623 for (auto &SCD
: StoreChainDependents
)
1624 clusterNeighboringMemOps(SCD
, DAG
);
1627 //===----------------------------------------------------------------------===//
1628 // CopyConstrain - DAG post-processing to encourage copy elimination.
1629 //===----------------------------------------------------------------------===//
1633 /// Post-process the DAG to create weak edges from all uses of a copy to
1634 /// the one use that defines the copy's source vreg, most likely an induction
1635 /// variable increment.
1636 class CopyConstrain
: public ScheduleDAGMutation
{
1638 SlotIndex RegionBeginIdx
;
1640 // RegionEndIdx is the slot index of the last non-debug instruction in the
1641 // scheduling region. So we may have RegionBeginIdx == RegionEndIdx.
1642 SlotIndex RegionEndIdx
;
1645 CopyConstrain(const TargetInstrInfo
*, const TargetRegisterInfo
*) {}
1647 void apply(ScheduleDAGInstrs
*DAGInstrs
) override
;
1650 void constrainLocalCopy(SUnit
*CopySU
, ScheduleDAGMILive
*DAG
);
1653 } // end anonymous namespace
1657 std::unique_ptr
<ScheduleDAGMutation
>
1658 createCopyConstrainDAGMutation(const TargetInstrInfo
*TII
,
1659 const TargetRegisterInfo
*TRI
) {
1660 return std::make_unique
<CopyConstrain
>(TII
, TRI
);
1663 } // end namespace llvm
1665 /// constrainLocalCopy handles two possibilities:
1670 /// I3: dst = src (copy)
1671 /// (create pred->succ edges I0->I1, I2->I1)
1674 /// I0: dst = src (copy)
1678 /// (create pred->succ edges I1->I2, I3->I2)
1680 /// Although the MachineScheduler is currently constrained to single blocks,
1681 /// this algorithm should handle extended blocks. An EBB is a set of
1682 /// contiguously numbered blocks such that the previous block in the EBB is
1683 /// always the single predecessor.
1684 void CopyConstrain::constrainLocalCopy(SUnit
*CopySU
, ScheduleDAGMILive
*DAG
) {
1685 LiveIntervals
*LIS
= DAG
->getLIS();
1686 MachineInstr
*Copy
= CopySU
->getInstr();
1688 // Check for pure vreg copies.
1689 const MachineOperand
&SrcOp
= Copy
->getOperand(1);
1690 Register SrcReg
= SrcOp
.getReg();
1691 if (!Register::isVirtualRegister(SrcReg
) || !SrcOp
.readsReg())
1694 const MachineOperand
&DstOp
= Copy
->getOperand(0);
1695 Register DstReg
= DstOp
.getReg();
1696 if (!Register::isVirtualRegister(DstReg
) || DstOp
.isDead())
1699 // Check if either the dest or source is local. If it's live across a back
1700 // edge, it's not local. Note that if both vregs are live across the back
1701 // edge, we cannot successfully contrain the copy without cyclic scheduling.
1702 // If both the copy's source and dest are local live intervals, then we
1703 // should treat the dest as the global for the purpose of adding
1704 // constraints. This adds edges from source's other uses to the copy.
1705 unsigned LocalReg
= SrcReg
;
1706 unsigned GlobalReg
= DstReg
;
1707 LiveInterval
*LocalLI
= &LIS
->getInterval(LocalReg
);
1708 if (!LocalLI
->isLocal(RegionBeginIdx
, RegionEndIdx
)) {
1711 LocalLI
= &LIS
->getInterval(LocalReg
);
1712 if (!LocalLI
->isLocal(RegionBeginIdx
, RegionEndIdx
))
1715 LiveInterval
*GlobalLI
= &LIS
->getInterval(GlobalReg
);
1717 // Find the global segment after the start of the local LI.
1718 LiveInterval::iterator GlobalSegment
= GlobalLI
->find(LocalLI
->beginIndex());
1719 // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a
1720 // local live range. We could create edges from other global uses to the local
1721 // start, but the coalescer should have already eliminated these cases, so
1722 // don't bother dealing with it.
1723 if (GlobalSegment
== GlobalLI
->end())
1726 // If GlobalSegment is killed at the LocalLI->start, the call to find()
1727 // returned the next global segment. But if GlobalSegment overlaps with
1728 // LocalLI->start, then advance to the next segment. If a hole in GlobalLI
1729 // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole.
1730 if (GlobalSegment
->contains(LocalLI
->beginIndex()))
1733 if (GlobalSegment
== GlobalLI
->end())
1736 // Check if GlobalLI contains a hole in the vicinity of LocalLI.
1737 if (GlobalSegment
!= GlobalLI
->begin()) {
1738 // Two address defs have no hole.
1739 if (SlotIndex::isSameInstr(std::prev(GlobalSegment
)->end
,
1740 GlobalSegment
->start
)) {
1743 // If the prior global segment may be defined by the same two-address
1744 // instruction that also defines LocalLI, then can't make a hole here.
1745 if (SlotIndex::isSameInstr(std::prev(GlobalSegment
)->start
,
1746 LocalLI
->beginIndex())) {
1749 // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise
1750 // it would be a disconnected component in the live range.
1751 assert(std::prev(GlobalSegment
)->start
< LocalLI
->beginIndex() &&
1752 "Disconnected LRG within the scheduling region.");
1754 MachineInstr
*GlobalDef
= LIS
->getInstructionFromIndex(GlobalSegment
->start
);
1758 SUnit
*GlobalSU
= DAG
->getSUnit(GlobalDef
);
1762 // GlobalDef is the bottom of the GlobalLI hole. Open the hole by
1763 // constraining the uses of the last local def to precede GlobalDef.
1764 SmallVector
<SUnit
*,8> LocalUses
;
1765 const VNInfo
*LastLocalVN
= LocalLI
->getVNInfoBefore(LocalLI
->endIndex());
1766 MachineInstr
*LastLocalDef
= LIS
->getInstructionFromIndex(LastLocalVN
->def
);
1767 SUnit
*LastLocalSU
= DAG
->getSUnit(LastLocalDef
);
1768 for (const SDep
&Succ
: LastLocalSU
->Succs
) {
1769 if (Succ
.getKind() != SDep::Data
|| Succ
.getReg() != LocalReg
)
1771 if (Succ
.getSUnit() == GlobalSU
)
1773 if (!DAG
->canAddEdge(GlobalSU
, Succ
.getSUnit()))
1775 LocalUses
.push_back(Succ
.getSUnit());
1777 // Open the top of the GlobalLI hole by constraining any earlier global uses
1778 // to precede the start of LocalLI.
1779 SmallVector
<SUnit
*,8> GlobalUses
;
1780 MachineInstr
*FirstLocalDef
=
1781 LIS
->getInstructionFromIndex(LocalLI
->beginIndex());
1782 SUnit
*FirstLocalSU
= DAG
->getSUnit(FirstLocalDef
);
1783 for (const SDep
&Pred
: GlobalSU
->Preds
) {
1784 if (Pred
.getKind() != SDep::Anti
|| Pred
.getReg() != GlobalReg
)
1786 if (Pred
.getSUnit() == FirstLocalSU
)
1788 if (!DAG
->canAddEdge(FirstLocalSU
, Pred
.getSUnit()))
1790 GlobalUses
.push_back(Pred
.getSUnit());
1792 LLVM_DEBUG(dbgs() << "Constraining copy SU(" << CopySU
->NodeNum
<< ")\n");
1793 // Add the weak edges.
1794 for (SmallVectorImpl
<SUnit
*>::const_iterator
1795 I
= LocalUses
.begin(), E
= LocalUses
.end(); I
!= E
; ++I
) {
1796 LLVM_DEBUG(dbgs() << " Local use SU(" << (*I
)->NodeNum
<< ") -> SU("
1797 << GlobalSU
->NodeNum
<< ")\n");
1798 DAG
->addEdge(GlobalSU
, SDep(*I
, SDep::Weak
));
1800 for (SmallVectorImpl
<SUnit
*>::const_iterator
1801 I
= GlobalUses
.begin(), E
= GlobalUses
.end(); I
!= E
; ++I
) {
1802 LLVM_DEBUG(dbgs() << " Global use SU(" << (*I
)->NodeNum
<< ") -> SU("
1803 << FirstLocalSU
->NodeNum
<< ")\n");
1804 DAG
->addEdge(FirstLocalSU
, SDep(*I
, SDep::Weak
));
1808 /// Callback from DAG postProcessing to create weak edges to encourage
1809 /// copy elimination.
1810 void CopyConstrain::apply(ScheduleDAGInstrs
*DAGInstrs
) {
1811 ScheduleDAGMI
*DAG
= static_cast<ScheduleDAGMI
*>(DAGInstrs
);
1812 assert(DAG
->hasVRegLiveness() && "Expect VRegs with LiveIntervals");
1814 MachineBasicBlock::iterator FirstPos
= nextIfDebug(DAG
->begin(), DAG
->end());
1815 if (FirstPos
== DAG
->end())
1817 RegionBeginIdx
= DAG
->getLIS()->getInstructionIndex(*FirstPos
);
1818 RegionEndIdx
= DAG
->getLIS()->getInstructionIndex(
1819 *priorNonDebug(DAG
->end(), DAG
->begin()));
1821 for (SUnit
&SU
: DAG
->SUnits
) {
1822 if (!SU
.getInstr()->isCopy())
1825 constrainLocalCopy(&SU
, static_cast<ScheduleDAGMILive
*>(DAG
));
1829 //===----------------------------------------------------------------------===//
1830 // MachineSchedStrategy helpers used by GenericScheduler, GenericPostScheduler
1831 // and possibly other custom schedulers.
1832 //===----------------------------------------------------------------------===//
1834 static const unsigned InvalidCycle
= ~0U;
1836 SchedBoundary::~SchedBoundary() { delete HazardRec
; }
1838 /// Given a Count of resource usage and a Latency value, return true if a
1839 /// SchedBoundary becomes resource limited.
1840 /// If we are checking after scheduling a node, we should return true when
1841 /// we just reach the resource limit.
1842 static bool checkResourceLimit(unsigned LFactor
, unsigned Count
,
1843 unsigned Latency
, bool AfterSchedNode
) {
1844 int ResCntFactor
= (int)(Count
- (Latency
* LFactor
));
1846 return ResCntFactor
>= (int)LFactor
;
1848 return ResCntFactor
> (int)LFactor
;
1851 void SchedBoundary::reset() {
1852 // A new HazardRec is created for each DAG and owned by SchedBoundary.
1853 // Destroying and reconstructing it is very expensive though. So keep
1854 // invalid, placeholder HazardRecs.
1855 if (HazardRec
&& HazardRec
->isEnabled()) {
1857 HazardRec
= nullptr;
1861 CheckPending
= false;
1864 MinReadyCycle
= std::numeric_limits
<unsigned>::max();
1865 ExpectedLatency
= 0;
1866 DependentLatency
= 0;
1868 MaxExecutedResCount
= 0;
1870 IsResourceLimited
= false;
1871 ReservedCycles
.clear();
1872 ReservedCyclesIndex
.clear();
1874 // Track the maximum number of stall cycles that could arise either from the
1875 // latency of a DAG edge or the number of cycles that a processor resource is
1876 // reserved (SchedBoundary::ReservedCycles).
1877 MaxObservedStall
= 0;
1879 // Reserve a zero-count for invalid CritResIdx.
1880 ExecutedResCounts
.resize(1);
1881 assert(!ExecutedResCounts
[0] && "nonzero count for bad resource");
1884 void SchedRemainder::
1885 init(ScheduleDAGMI
*DAG
, const TargetSchedModel
*SchedModel
) {
1887 if (!SchedModel
->hasInstrSchedModel())
1889 RemainingCounts
.resize(SchedModel
->getNumProcResourceKinds());
1890 for (SUnit
&SU
: DAG
->SUnits
) {
1891 const MCSchedClassDesc
*SC
= DAG
->getSchedClass(&SU
);
1892 RemIssueCount
+= SchedModel
->getNumMicroOps(SU
.getInstr(), SC
)
1893 * SchedModel
->getMicroOpFactor();
1894 for (TargetSchedModel::ProcResIter
1895 PI
= SchedModel
->getWriteProcResBegin(SC
),
1896 PE
= SchedModel
->getWriteProcResEnd(SC
); PI
!= PE
; ++PI
) {
1897 unsigned PIdx
= PI
->ProcResourceIdx
;
1898 unsigned Factor
= SchedModel
->getResourceFactor(PIdx
);
1899 RemainingCounts
[PIdx
] += (Factor
* PI
->Cycles
);
1904 void SchedBoundary::
1905 init(ScheduleDAGMI
*dag
, const TargetSchedModel
*smodel
, SchedRemainder
*rem
) {
1908 SchedModel
= smodel
;
1910 if (SchedModel
->hasInstrSchedModel()) {
1911 unsigned ResourceCount
= SchedModel
->getNumProcResourceKinds();
1912 ReservedCyclesIndex
.resize(ResourceCount
);
1913 ExecutedResCounts
.resize(ResourceCount
);
1914 unsigned NumUnits
= 0;
1916 for (unsigned i
= 0; i
< ResourceCount
; ++i
) {
1917 ReservedCyclesIndex
[i
] = NumUnits
;
1918 NumUnits
+= SchedModel
->getProcResource(i
)->NumUnits
;
1921 ReservedCycles
.resize(NumUnits
, InvalidCycle
);
1925 /// Compute the stall cycles based on this SUnit's ready time. Heuristics treat
1926 /// these "soft stalls" differently than the hard stall cycles based on CPU
1927 /// resources and computed by checkHazard(). A fully in-order model
1928 /// (MicroOpBufferSize==0) will not make use of this since instructions are not
1929 /// available for scheduling until they are ready. However, a weaker in-order
1930 /// model may use this for heuristics. For example, if a processor has in-order
1931 /// behavior when reading certain resources, this may come into play.
1932 unsigned SchedBoundary::getLatencyStallCycles(SUnit
*SU
) {
1933 if (!SU
->isUnbuffered
)
1936 unsigned ReadyCycle
= (isTop() ? SU
->TopReadyCycle
: SU
->BotReadyCycle
);
1937 if (ReadyCycle
> CurrCycle
)
1938 return ReadyCycle
- CurrCycle
;
1942 /// Compute the next cycle at which the given processor resource unit
1943 /// can be scheduled.
1944 unsigned SchedBoundary::getNextResourceCycleByInstance(unsigned InstanceIdx
,
1946 unsigned NextUnreserved
= ReservedCycles
[InstanceIdx
];
1947 // If this resource has never been used, always return cycle zero.
1948 if (NextUnreserved
== InvalidCycle
)
1950 // For bottom-up scheduling add the cycles needed for the current operation.
1952 NextUnreserved
+= Cycles
;
1953 return NextUnreserved
;
1956 /// Compute the next cycle at which the given processor resource can be
1957 /// scheduled. Returns the next cycle and the index of the processor resource
1958 /// instance in the reserved cycles vector.
1959 std::pair
<unsigned, unsigned>
1960 SchedBoundary::getNextResourceCycle(unsigned PIdx
, unsigned Cycles
) {
1961 unsigned MinNextUnreserved
= InvalidCycle
;
1962 unsigned InstanceIdx
= 0;
1963 unsigned StartIndex
= ReservedCyclesIndex
[PIdx
];
1964 unsigned NumberOfInstances
= SchedModel
->getProcResource(PIdx
)->NumUnits
;
1965 assert(NumberOfInstances
> 0 &&
1966 "Cannot have zero instances of a ProcResource");
1968 for (unsigned I
= StartIndex
, End
= StartIndex
+ NumberOfInstances
; I
< End
;
1970 unsigned NextUnreserved
= getNextResourceCycleByInstance(I
, Cycles
);
1971 if (MinNextUnreserved
> NextUnreserved
) {
1973 MinNextUnreserved
= NextUnreserved
;
1976 return std::make_pair(MinNextUnreserved
, InstanceIdx
);
1979 /// Does this SU have a hazard within the current instruction group.
1981 /// The scheduler supports two modes of hazard recognition. The first is the
1982 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
1983 /// supports highly complicated in-order reservation tables
1984 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
1986 /// The second is a streamlined mechanism that checks for hazards based on
1987 /// simple counters that the scheduler itself maintains. It explicitly checks
1988 /// for instruction dispatch limitations, including the number of micro-ops that
1989 /// can dispatch per cycle.
1991 /// TODO: Also check whether the SU must start a new group.
1992 bool SchedBoundary::checkHazard(SUnit
*SU
) {
1993 if (HazardRec
->isEnabled()
1994 && HazardRec
->getHazardType(SU
) != ScheduleHazardRecognizer::NoHazard
) {
1998 unsigned uops
= SchedModel
->getNumMicroOps(SU
->getInstr());
1999 if ((CurrMOps
> 0) && (CurrMOps
+ uops
> SchedModel
->getIssueWidth())) {
2000 LLVM_DEBUG(dbgs() << " SU(" << SU
->NodeNum
<< ") uops="
2001 << SchedModel
->getNumMicroOps(SU
->getInstr()) << '\n');
2006 ((isTop() && SchedModel
->mustBeginGroup(SU
->getInstr())) ||
2007 (!isTop() && SchedModel
->mustEndGroup(SU
->getInstr())))) {
2008 LLVM_DEBUG(dbgs() << " hazard: SU(" << SU
->NodeNum
<< ") must "
2009 << (isTop() ? "begin" : "end") << " group\n");
2013 if (SchedModel
->hasInstrSchedModel() && SU
->hasReservedResource
) {
2014 const MCSchedClassDesc
*SC
= DAG
->getSchedClass(SU
);
2015 for (const MCWriteProcResEntry
&PE
:
2016 make_range(SchedModel
->getWriteProcResBegin(SC
),
2017 SchedModel
->getWriteProcResEnd(SC
))) {
2018 unsigned ResIdx
= PE
.ProcResourceIdx
;
2019 unsigned Cycles
= PE
.Cycles
;
2020 unsigned NRCycle
, InstanceIdx
;
2021 std::tie(NRCycle
, InstanceIdx
) = getNextResourceCycle(ResIdx
, Cycles
);
2022 if (NRCycle
> CurrCycle
) {
2024 MaxObservedStall
= std::max(Cycles
, MaxObservedStall
);
2026 LLVM_DEBUG(dbgs() << " SU(" << SU
->NodeNum
<< ") "
2027 << SchedModel
->getResourceName(ResIdx
)
2028 << '[' << InstanceIdx
- ReservedCyclesIndex
[ResIdx
] << ']'
2029 << "=" << NRCycle
<< "c\n");
2037 // Find the unscheduled node in ReadySUs with the highest latency.
2038 unsigned SchedBoundary::
2039 findMaxLatency(ArrayRef
<SUnit
*> ReadySUs
) {
2040 SUnit
*LateSU
= nullptr;
2041 unsigned RemLatency
= 0;
2042 for (SUnit
*SU
: ReadySUs
) {
2043 unsigned L
= getUnscheduledLatency(SU
);
2044 if (L
> RemLatency
) {
2050 LLVM_DEBUG(dbgs() << Available
.getName() << " RemLatency SU("
2051 << LateSU
->NodeNum
<< ") " << RemLatency
<< "c\n");
2056 // Count resources in this zone and the remaining unscheduled
2057 // instruction. Return the max count, scaled. Set OtherCritIdx to the critical
2058 // resource index, or zero if the zone is issue limited.
2059 unsigned SchedBoundary::
2060 getOtherResourceCount(unsigned &OtherCritIdx
) {
2062 if (!SchedModel
->hasInstrSchedModel())
2065 unsigned OtherCritCount
= Rem
->RemIssueCount
2066 + (RetiredMOps
* SchedModel
->getMicroOpFactor());
2067 LLVM_DEBUG(dbgs() << " " << Available
.getName() << " + Remain MOps: "
2068 << OtherCritCount
/ SchedModel
->getMicroOpFactor() << '\n');
2069 for (unsigned PIdx
= 1, PEnd
= SchedModel
->getNumProcResourceKinds();
2070 PIdx
!= PEnd
; ++PIdx
) {
2071 unsigned OtherCount
= getResourceCount(PIdx
) + Rem
->RemainingCounts
[PIdx
];
2072 if (OtherCount
> OtherCritCount
) {
2073 OtherCritCount
= OtherCount
;
2074 OtherCritIdx
= PIdx
;
2079 dbgs() << " " << Available
.getName() << " + Remain CritRes: "
2080 << OtherCritCount
/ SchedModel
->getResourceFactor(OtherCritIdx
)
2081 << " " << SchedModel
->getResourceName(OtherCritIdx
) << "\n");
2083 return OtherCritCount
;
2086 void SchedBoundary::releaseNode(SUnit
*SU
, unsigned ReadyCycle
) {
2087 assert(SU
->getInstr() && "Scheduled SUnit must have instr");
2090 // ReadyCycle was been bumped up to the CurrCycle when this node was
2091 // scheduled, but CurrCycle may have been eagerly advanced immediately after
2092 // scheduling, so may now be greater than ReadyCycle.
2093 if (ReadyCycle
> CurrCycle
)
2094 MaxObservedStall
= std::max(ReadyCycle
- CurrCycle
, MaxObservedStall
);
2097 if (ReadyCycle
< MinReadyCycle
)
2098 MinReadyCycle
= ReadyCycle
;
2100 // Check for interlocks first. For the purpose of other heuristics, an
2101 // instruction that cannot issue appears as if it's not in the ReadyQueue.
2102 bool IsBuffered
= SchedModel
->getMicroOpBufferSize() != 0;
2103 if ((!IsBuffered
&& ReadyCycle
> CurrCycle
) || checkHazard(SU
) ||
2104 Available
.size() >= ReadyListLimit
)
2110 /// Move the boundary of scheduled code by one cycle.
2111 void SchedBoundary::bumpCycle(unsigned NextCycle
) {
2112 if (SchedModel
->getMicroOpBufferSize() == 0) {
2113 assert(MinReadyCycle
< std::numeric_limits
<unsigned>::max() &&
2114 "MinReadyCycle uninitialized");
2115 if (MinReadyCycle
> NextCycle
)
2116 NextCycle
= MinReadyCycle
;
2118 // Update the current micro-ops, which will issue in the next cycle.
2119 unsigned DecMOps
= SchedModel
->getIssueWidth() * (NextCycle
- CurrCycle
);
2120 CurrMOps
= (CurrMOps
<= DecMOps
) ? 0 : CurrMOps
- DecMOps
;
2122 // Decrement DependentLatency based on the next cycle.
2123 if ((NextCycle
- CurrCycle
) > DependentLatency
)
2124 DependentLatency
= 0;
2126 DependentLatency
-= (NextCycle
- CurrCycle
);
2128 if (!HazardRec
->isEnabled()) {
2129 // Bypass HazardRec virtual calls.
2130 CurrCycle
= NextCycle
;
2132 // Bypass getHazardType calls in case of long latency.
2133 for (; CurrCycle
!= NextCycle
; ++CurrCycle
) {
2135 HazardRec
->AdvanceCycle();
2137 HazardRec
->RecedeCycle();
2140 CheckPending
= true;
2142 checkResourceLimit(SchedModel
->getLatencyFactor(), getCriticalCount(),
2143 getScheduledLatency(), true);
2145 LLVM_DEBUG(dbgs() << "Cycle: " << CurrCycle
<< ' ' << Available
.getName()
2149 void SchedBoundary::incExecutedResources(unsigned PIdx
, unsigned Count
) {
2150 ExecutedResCounts
[PIdx
] += Count
;
2151 if (ExecutedResCounts
[PIdx
] > MaxExecutedResCount
)
2152 MaxExecutedResCount
= ExecutedResCounts
[PIdx
];
2155 /// Add the given processor resource to this scheduled zone.
2157 /// \param Cycles indicates the number of consecutive (non-pipelined) cycles
2158 /// during which this resource is consumed.
2160 /// \return the next cycle at which the instruction may execute without
2161 /// oversubscribing resources.
2162 unsigned SchedBoundary::
2163 countResource(unsigned PIdx
, unsigned Cycles
, unsigned NextCycle
) {
2164 unsigned Factor
= SchedModel
->getResourceFactor(PIdx
);
2165 unsigned Count
= Factor
* Cycles
;
2166 LLVM_DEBUG(dbgs() << " " << SchedModel
->getResourceName(PIdx
) << " +"
2167 << Cycles
<< "x" << Factor
<< "u\n");
2169 // Update Executed resources counts.
2170 incExecutedResources(PIdx
, Count
);
2171 assert(Rem
->RemainingCounts
[PIdx
] >= Count
&& "resource double counted");
2172 Rem
->RemainingCounts
[PIdx
] -= Count
;
2174 // Check if this resource exceeds the current critical resource. If so, it
2175 // becomes the critical resource.
2176 if (ZoneCritResIdx
!= PIdx
&& (getResourceCount(PIdx
) > getCriticalCount())) {
2177 ZoneCritResIdx
= PIdx
;
2178 LLVM_DEBUG(dbgs() << " *** Critical resource "
2179 << SchedModel
->getResourceName(PIdx
) << ": "
2180 << getResourceCount(PIdx
) / SchedModel
->getLatencyFactor()
2183 // For reserved resources, record the highest cycle using the resource.
2184 unsigned NextAvailable
, InstanceIdx
;
2185 std::tie(NextAvailable
, InstanceIdx
) = getNextResourceCycle(PIdx
, Cycles
);
2186 if (NextAvailable
> CurrCycle
) {
2187 LLVM_DEBUG(dbgs() << " Resource conflict: "
2188 << SchedModel
->getResourceName(PIdx
)
2189 << '[' << InstanceIdx
- ReservedCyclesIndex
[PIdx
] << ']'
2190 << " reserved until @" << NextAvailable
<< "\n");
2192 return NextAvailable
;
2195 /// Move the boundary of scheduled code by one SUnit.
2196 void SchedBoundary::bumpNode(SUnit
*SU
) {
2197 // Update the reservation table.
2198 if (HazardRec
->isEnabled()) {
2199 if (!isTop() && SU
->isCall
) {
2200 // Calls are scheduled with their preceding instructions. For bottom-up
2201 // scheduling, clear the pipeline state before emitting.
2204 HazardRec
->EmitInstruction(SU
);
2205 // Scheduling an instruction may have made pending instructions available.
2206 CheckPending
= true;
2208 // checkHazard should prevent scheduling multiple instructions per cycle that
2209 // exceed the issue width.
2210 const MCSchedClassDesc
*SC
= DAG
->getSchedClass(SU
);
2211 unsigned IncMOps
= SchedModel
->getNumMicroOps(SU
->getInstr());
2213 (CurrMOps
== 0 || (CurrMOps
+ IncMOps
) <= SchedModel
->getIssueWidth()) &&
2214 "Cannot schedule this instruction's MicroOps in the current cycle.");
2216 unsigned ReadyCycle
= (isTop() ? SU
->TopReadyCycle
: SU
->BotReadyCycle
);
2217 LLVM_DEBUG(dbgs() << " Ready @" << ReadyCycle
<< "c\n");
2219 unsigned NextCycle
= CurrCycle
;
2220 switch (SchedModel
->getMicroOpBufferSize()) {
2222 assert(ReadyCycle
<= CurrCycle
&& "Broken PendingQueue");
2225 if (ReadyCycle
> NextCycle
) {
2226 NextCycle
= ReadyCycle
;
2227 LLVM_DEBUG(dbgs() << " *** Stall until: " << ReadyCycle
<< "\n");
2231 // We don't currently model the OOO reorder buffer, so consider all
2232 // scheduled MOps to be "retired". We do loosely model in-order resource
2233 // latency. If this instruction uses an in-order resource, account for any
2234 // likely stall cycles.
2235 if (SU
->isUnbuffered
&& ReadyCycle
> NextCycle
)
2236 NextCycle
= ReadyCycle
;
2239 RetiredMOps
+= IncMOps
;
2241 // Update resource counts and critical resource.
2242 if (SchedModel
->hasInstrSchedModel()) {
2243 unsigned DecRemIssue
= IncMOps
* SchedModel
->getMicroOpFactor();
2244 assert(Rem
->RemIssueCount
>= DecRemIssue
&& "MOps double counted");
2245 Rem
->RemIssueCount
-= DecRemIssue
;
2246 if (ZoneCritResIdx
) {
2247 // Scale scheduled micro-ops for comparing with the critical resource.
2248 unsigned ScaledMOps
=
2249 RetiredMOps
* SchedModel
->getMicroOpFactor();
2251 // If scaled micro-ops are now more than the previous critical resource by
2252 // a full cycle, then micro-ops issue becomes critical.
2253 if ((int)(ScaledMOps
- getResourceCount(ZoneCritResIdx
))
2254 >= (int)SchedModel
->getLatencyFactor()) {
2256 LLVM_DEBUG(dbgs() << " *** Critical resource NumMicroOps: "
2257 << ScaledMOps
/ SchedModel
->getLatencyFactor()
2261 for (TargetSchedModel::ProcResIter
2262 PI
= SchedModel
->getWriteProcResBegin(SC
),
2263 PE
= SchedModel
->getWriteProcResEnd(SC
); PI
!= PE
; ++PI
) {
2265 countResource(PI
->ProcResourceIdx
, PI
->Cycles
, NextCycle
);
2266 if (RCycle
> NextCycle
)
2269 if (SU
->hasReservedResource
) {
2270 // For reserved resources, record the highest cycle using the resource.
2271 // For top-down scheduling, this is the cycle in which we schedule this
2272 // instruction plus the number of cycles the operations reserves the
2273 // resource. For bottom-up is it simply the instruction's cycle.
2274 for (TargetSchedModel::ProcResIter
2275 PI
= SchedModel
->getWriteProcResBegin(SC
),
2276 PE
= SchedModel
->getWriteProcResEnd(SC
); PI
!= PE
; ++PI
) {
2277 unsigned PIdx
= PI
->ProcResourceIdx
;
2278 if (SchedModel
->getProcResource(PIdx
)->BufferSize
== 0) {
2279 unsigned ReservedUntil
, InstanceIdx
;
2280 std::tie(ReservedUntil
, InstanceIdx
) = getNextResourceCycle(PIdx
, 0);
2282 ReservedCycles
[InstanceIdx
] =
2283 std::max(ReservedUntil
, NextCycle
+ PI
->Cycles
);
2285 ReservedCycles
[InstanceIdx
] = NextCycle
;
2290 // Update ExpectedLatency and DependentLatency.
2291 unsigned &TopLatency
= isTop() ? ExpectedLatency
: DependentLatency
;
2292 unsigned &BotLatency
= isTop() ? DependentLatency
: ExpectedLatency
;
2293 if (SU
->getDepth() > TopLatency
) {
2294 TopLatency
= SU
->getDepth();
2295 LLVM_DEBUG(dbgs() << " " << Available
.getName() << " TopLatency SU("
2296 << SU
->NodeNum
<< ") " << TopLatency
<< "c\n");
2298 if (SU
->getHeight() > BotLatency
) {
2299 BotLatency
= SU
->getHeight();
2300 LLVM_DEBUG(dbgs() << " " << Available
.getName() << " BotLatency SU("
2301 << SU
->NodeNum
<< ") " << BotLatency
<< "c\n");
2303 // If we stall for any reason, bump the cycle.
2304 if (NextCycle
> CurrCycle
)
2305 bumpCycle(NextCycle
);
2307 // After updating ZoneCritResIdx and ExpectedLatency, check if we're
2308 // resource limited. If a stall occurred, bumpCycle does this.
2310 checkResourceLimit(SchedModel
->getLatencyFactor(), getCriticalCount(),
2311 getScheduledLatency(), true);
2313 // Update CurrMOps after calling bumpCycle to handle stalls, since bumpCycle
2314 // resets CurrMOps. Loop to handle instructions with more MOps than issue in
2315 // one cycle. Since we commonly reach the max MOps here, opportunistically
2316 // bump the cycle to avoid uselessly checking everything in the readyQ.
2317 CurrMOps
+= IncMOps
;
2319 // Bump the cycle count for issue group constraints.
2320 // This must be done after NextCycle has been adjust for all other stalls.
2321 // Calling bumpCycle(X) will reduce CurrMOps by one issue group and set
2323 if ((isTop() && SchedModel
->mustEndGroup(SU
->getInstr())) ||
2324 (!isTop() && SchedModel
->mustBeginGroup(SU
->getInstr()))) {
2325 LLVM_DEBUG(dbgs() << " Bump cycle to " << (isTop() ? "end" : "begin")
2327 bumpCycle(++NextCycle
);
2330 while (CurrMOps
>= SchedModel
->getIssueWidth()) {
2331 LLVM_DEBUG(dbgs() << " *** Max MOps " << CurrMOps
<< " at cycle "
2332 << CurrCycle
<< '\n');
2333 bumpCycle(++NextCycle
);
2335 LLVM_DEBUG(dumpScheduledState());
2338 /// Release pending ready nodes in to the available queue. This makes them
2339 /// visible to heuristics.
2340 void SchedBoundary::releasePending() {
2341 // If the available queue is empty, it is safe to reset MinReadyCycle.
2342 if (Available
.empty())
2343 MinReadyCycle
= std::numeric_limits
<unsigned>::max();
2345 // Check to see if any of the pending instructions are ready to issue. If
2346 // so, add them to the available queue.
2347 bool IsBuffered
= SchedModel
->getMicroOpBufferSize() != 0;
2348 for (unsigned i
= 0, e
= Pending
.size(); i
!= e
; ++i
) {
2349 SUnit
*SU
= *(Pending
.begin()+i
);
2350 unsigned ReadyCycle
= isTop() ? SU
->TopReadyCycle
: SU
->BotReadyCycle
;
2352 if (ReadyCycle
< MinReadyCycle
)
2353 MinReadyCycle
= ReadyCycle
;
2355 if (!IsBuffered
&& ReadyCycle
> CurrCycle
)
2358 if (checkHazard(SU
))
2361 if (Available
.size() >= ReadyListLimit
)
2365 Pending
.remove(Pending
.begin()+i
);
2368 CheckPending
= false;
2371 /// Remove SU from the ready set for this boundary.
2372 void SchedBoundary::removeReady(SUnit
*SU
) {
2373 if (Available
.isInQueue(SU
))
2374 Available
.remove(Available
.find(SU
));
2376 assert(Pending
.isInQueue(SU
) && "bad ready count");
2377 Pending
.remove(Pending
.find(SU
));
2381 /// If this queue only has one ready candidate, return it. As a side effect,
2382 /// defer any nodes that now hit a hazard, and advance the cycle until at least
2383 /// one node is ready. If multiple instructions are ready, return NULL.
2384 SUnit
*SchedBoundary::pickOnlyChoice() {
2389 // Defer any ready instrs that now have a hazard.
2390 for (ReadyQueue::iterator I
= Available
.begin(); I
!= Available
.end();) {
2391 if (checkHazard(*I
)) {
2393 I
= Available
.remove(I
);
2399 for (unsigned i
= 0; Available
.empty(); ++i
) {
2400 // FIXME: Re-enable assert once PR20057 is resolved.
2401 // assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedStall) &&
2402 // "permanent hazard");
2404 bumpCycle(CurrCycle
+ 1);
2408 LLVM_DEBUG(Pending
.dump());
2409 LLVM_DEBUG(Available
.dump());
2411 if (Available
.size() == 1)
2412 return *Available
.begin();
2416 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2417 // This is useful information to dump after bumpNode.
2418 // Note that the Queue contents are more useful before pickNodeFromQueue.
2419 LLVM_DUMP_METHOD
void SchedBoundary::dumpScheduledState() const {
2422 if (ZoneCritResIdx
) {
2423 ResFactor
= SchedModel
->getResourceFactor(ZoneCritResIdx
);
2424 ResCount
= getResourceCount(ZoneCritResIdx
);
2426 ResFactor
= SchedModel
->getMicroOpFactor();
2427 ResCount
= RetiredMOps
* ResFactor
;
2429 unsigned LFactor
= SchedModel
->getLatencyFactor();
2430 dbgs() << Available
.getName() << " @" << CurrCycle
<< "c\n"
2431 << " Retired: " << RetiredMOps
;
2432 dbgs() << "\n Executed: " << getExecutedCount() / LFactor
<< "c";
2433 dbgs() << "\n Critical: " << ResCount
/ LFactor
<< "c, "
2434 << ResCount
/ ResFactor
<< " "
2435 << SchedModel
->getResourceName(ZoneCritResIdx
)
2436 << "\n ExpectedLatency: " << ExpectedLatency
<< "c\n"
2437 << (IsResourceLimited
? " - Resource" : " - Latency")
2442 //===----------------------------------------------------------------------===//
2443 // GenericScheduler - Generic implementation of MachineSchedStrategy.
2444 //===----------------------------------------------------------------------===//
2446 void GenericSchedulerBase::SchedCandidate::
2447 initResourceDelta(const ScheduleDAGMI
*DAG
,
2448 const TargetSchedModel
*SchedModel
) {
2449 if (!Policy
.ReduceResIdx
&& !Policy
.DemandResIdx
)
2452 const MCSchedClassDesc
*SC
= DAG
->getSchedClass(SU
);
2453 for (TargetSchedModel::ProcResIter
2454 PI
= SchedModel
->getWriteProcResBegin(SC
),
2455 PE
= SchedModel
->getWriteProcResEnd(SC
); PI
!= PE
; ++PI
) {
2456 if (PI
->ProcResourceIdx
== Policy
.ReduceResIdx
)
2457 ResDelta
.CritResources
+= PI
->Cycles
;
2458 if (PI
->ProcResourceIdx
== Policy
.DemandResIdx
)
2459 ResDelta
.DemandedResources
+= PI
->Cycles
;
2463 /// Compute remaining latency. We need this both to determine whether the
2464 /// overall schedule has become latency-limited and whether the instructions
2465 /// outside this zone are resource or latency limited.
2467 /// The "dependent" latency is updated incrementally during scheduling as the
2468 /// max height/depth of scheduled nodes minus the cycles since it was
2470 /// DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone
2472 /// The "independent" latency is the max ready queue depth:
2473 /// ILat = max N.depth for N in Available|Pending
2475 /// RemainingLatency is the greater of independent and dependent latency.
2477 /// These computations are expensive, especially in DAGs with many edges, so
2478 /// only do them if necessary.
2479 static unsigned computeRemLatency(SchedBoundary
&CurrZone
) {
2480 unsigned RemLatency
= CurrZone
.getDependentLatency();
2481 RemLatency
= std::max(RemLatency
,
2482 CurrZone
.findMaxLatency(CurrZone
.Available
.elements()));
2483 RemLatency
= std::max(RemLatency
,
2484 CurrZone
.findMaxLatency(CurrZone
.Pending
.elements()));
2488 /// Returns true if the current cycle plus remaning latency is greater than
2489 /// the critical path in the scheduling region.
2490 bool GenericSchedulerBase::shouldReduceLatency(const CandPolicy
&Policy
,
2491 SchedBoundary
&CurrZone
,
2492 bool ComputeRemLatency
,
2493 unsigned &RemLatency
) const {
2494 // The current cycle is already greater than the critical path, so we are
2495 // already latency limited and don't need to compute the remaining latency.
2496 if (CurrZone
.getCurrCycle() > Rem
.CriticalPath
)
2499 // If we haven't scheduled anything yet, then we aren't latency limited.
2500 if (CurrZone
.getCurrCycle() == 0)
2503 if (ComputeRemLatency
)
2504 RemLatency
= computeRemLatency(CurrZone
);
2506 return RemLatency
+ CurrZone
.getCurrCycle() > Rem
.CriticalPath
;
2509 /// Set the CandPolicy given a scheduling zone given the current resources and
2510 /// latencies inside and outside the zone.
2511 void GenericSchedulerBase::setPolicy(CandPolicy
&Policy
, bool IsPostRA
,
2512 SchedBoundary
&CurrZone
,
2513 SchedBoundary
*OtherZone
) {
2514 // Apply preemptive heuristics based on the total latency and resources
2515 // inside and outside this zone. Potential stalls should be considered before
2516 // following this policy.
2518 // Compute the critical resource outside the zone.
2519 unsigned OtherCritIdx
= 0;
2520 unsigned OtherCount
=
2521 OtherZone
? OtherZone
->getOtherResourceCount(OtherCritIdx
) : 0;
2523 bool OtherResLimited
= false;
2524 unsigned RemLatency
= 0;
2525 bool RemLatencyComputed
= false;
2526 if (SchedModel
->hasInstrSchedModel() && OtherCount
!= 0) {
2527 RemLatency
= computeRemLatency(CurrZone
);
2528 RemLatencyComputed
= true;
2529 OtherResLimited
= checkResourceLimit(SchedModel
->getLatencyFactor(),
2530 OtherCount
, RemLatency
, false);
2533 // Schedule aggressively for latency in PostRA mode. We don't check for
2534 // acyclic latency during PostRA, and highly out-of-order processors will
2535 // skip PostRA scheduling.
2536 if (!OtherResLimited
&&
2537 (IsPostRA
|| shouldReduceLatency(Policy
, CurrZone
, !RemLatencyComputed
,
2539 Policy
.ReduceLatency
|= true;
2540 LLVM_DEBUG(dbgs() << " " << CurrZone
.Available
.getName()
2541 << " RemainingLatency " << RemLatency
<< " + "
2542 << CurrZone
.getCurrCycle() << "c > CritPath "
2543 << Rem
.CriticalPath
<< "\n");
2545 // If the same resource is limiting inside and outside the zone, do nothing.
2546 if (CurrZone
.getZoneCritResIdx() == OtherCritIdx
)
2549 LLVM_DEBUG(if (CurrZone
.isResourceLimited()) {
2550 dbgs() << " " << CurrZone
.Available
.getName() << " ResourceLimited: "
2551 << SchedModel
->getResourceName(CurrZone
.getZoneCritResIdx()) << "\n";
2552 } if (OtherResLimited
) dbgs()
2553 << " RemainingLimit: "
2554 << SchedModel
->getResourceName(OtherCritIdx
) << "\n";
2555 if (!CurrZone
.isResourceLimited() && !OtherResLimited
) dbgs()
2556 << " Latency limited both directions.\n");
2558 if (CurrZone
.isResourceLimited() && !Policy
.ReduceResIdx
)
2559 Policy
.ReduceResIdx
= CurrZone
.getZoneCritResIdx();
2561 if (OtherResLimited
)
2562 Policy
.DemandResIdx
= OtherCritIdx
;
2566 const char *GenericSchedulerBase::getReasonStr(
2567 GenericSchedulerBase::CandReason Reason
) {
2569 case NoCand
: return "NOCAND ";
2570 case Only1
: return "ONLY1 ";
2571 case PhysReg
: return "PHYS-REG ";
2572 case RegExcess
: return "REG-EXCESS";
2573 case RegCritical
: return "REG-CRIT ";
2574 case Stall
: return "STALL ";
2575 case Cluster
: return "CLUSTER ";
2576 case Weak
: return "WEAK ";
2577 case RegMax
: return "REG-MAX ";
2578 case ResourceReduce
: return "RES-REDUCE";
2579 case ResourceDemand
: return "RES-DEMAND";
2580 case TopDepthReduce
: return "TOP-DEPTH ";
2581 case TopPathReduce
: return "TOP-PATH ";
2582 case BotHeightReduce
:return "BOT-HEIGHT";
2583 case BotPathReduce
: return "BOT-PATH ";
2584 case NextDefUse
: return "DEF-USE ";
2585 case NodeOrder
: return "ORDER ";
2587 llvm_unreachable("Unknown reason!");
2590 void GenericSchedulerBase::traceCandidate(const SchedCandidate
&Cand
) {
2592 unsigned ResIdx
= 0;
2593 unsigned Latency
= 0;
2594 switch (Cand
.Reason
) {
2598 P
= Cand
.RPDelta
.Excess
;
2601 P
= Cand
.RPDelta
.CriticalMax
;
2604 P
= Cand
.RPDelta
.CurrentMax
;
2606 case ResourceReduce
:
2607 ResIdx
= Cand
.Policy
.ReduceResIdx
;
2609 case ResourceDemand
:
2610 ResIdx
= Cand
.Policy
.DemandResIdx
;
2612 case TopDepthReduce
:
2613 Latency
= Cand
.SU
->getDepth();
2616 Latency
= Cand
.SU
->getHeight();
2618 case BotHeightReduce
:
2619 Latency
= Cand
.SU
->getHeight();
2622 Latency
= Cand
.SU
->getDepth();
2625 dbgs() << " Cand SU(" << Cand
.SU
->NodeNum
<< ") " << getReasonStr(Cand
.Reason
);
2627 dbgs() << " " << TRI
->getRegPressureSetName(P
.getPSet())
2628 << ":" << P
.getUnitInc() << " ";
2632 dbgs() << " " << SchedModel
->getProcResource(ResIdx
)->Name
<< " ";
2636 dbgs() << " " << Latency
<< " cycles ";
2644 /// Return true if this heuristic determines order.
2645 bool tryLess(int TryVal
, int CandVal
,
2646 GenericSchedulerBase::SchedCandidate
&TryCand
,
2647 GenericSchedulerBase::SchedCandidate
&Cand
,
2648 GenericSchedulerBase::CandReason Reason
) {
2649 if (TryVal
< CandVal
) {
2650 TryCand
.Reason
= Reason
;
2653 if (TryVal
> CandVal
) {
2654 if (Cand
.Reason
> Reason
)
2655 Cand
.Reason
= Reason
;
2661 bool tryGreater(int TryVal
, int CandVal
,
2662 GenericSchedulerBase::SchedCandidate
&TryCand
,
2663 GenericSchedulerBase::SchedCandidate
&Cand
,
2664 GenericSchedulerBase::CandReason Reason
) {
2665 if (TryVal
> CandVal
) {
2666 TryCand
.Reason
= Reason
;
2669 if (TryVal
< CandVal
) {
2670 if (Cand
.Reason
> Reason
)
2671 Cand
.Reason
= Reason
;
2677 bool tryLatency(GenericSchedulerBase::SchedCandidate
&TryCand
,
2678 GenericSchedulerBase::SchedCandidate
&Cand
,
2679 SchedBoundary
&Zone
) {
2681 if (Cand
.SU
->getDepth() > Zone
.getScheduledLatency()) {
2682 if (tryLess(TryCand
.SU
->getDepth(), Cand
.SU
->getDepth(),
2683 TryCand
, Cand
, GenericSchedulerBase::TopDepthReduce
))
2686 if (tryGreater(TryCand
.SU
->getHeight(), Cand
.SU
->getHeight(),
2687 TryCand
, Cand
, GenericSchedulerBase::TopPathReduce
))
2690 if (Cand
.SU
->getHeight() > Zone
.getScheduledLatency()) {
2691 if (tryLess(TryCand
.SU
->getHeight(), Cand
.SU
->getHeight(),
2692 TryCand
, Cand
, GenericSchedulerBase::BotHeightReduce
))
2695 if (tryGreater(TryCand
.SU
->getDepth(), Cand
.SU
->getDepth(),
2696 TryCand
, Cand
, GenericSchedulerBase::BotPathReduce
))
2701 } // end namespace llvm
2703 static void tracePick(GenericSchedulerBase::CandReason Reason
, bool IsTop
) {
2704 LLVM_DEBUG(dbgs() << "Pick " << (IsTop
? "Top " : "Bot ")
2705 << GenericSchedulerBase::getReasonStr(Reason
) << '\n');
2708 static void tracePick(const GenericSchedulerBase::SchedCandidate
&Cand
) {
2709 tracePick(Cand
.Reason
, Cand
.AtTop
);
2712 void GenericScheduler::initialize(ScheduleDAGMI
*dag
) {
2713 assert(dag
->hasVRegLiveness() &&
2714 "(PreRA)GenericScheduler needs vreg liveness");
2715 DAG
= static_cast<ScheduleDAGMILive
*>(dag
);
2716 SchedModel
= DAG
->getSchedModel();
2719 Rem
.init(DAG
, SchedModel
);
2720 Top
.init(DAG
, SchedModel
, &Rem
);
2721 Bot
.init(DAG
, SchedModel
, &Rem
);
2723 // Initialize resource counts.
2725 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
2726 // are disabled, then these HazardRecs will be disabled.
2727 const InstrItineraryData
*Itin
= SchedModel
->getInstrItineraries();
2728 if (!Top
.HazardRec
) {
2730 DAG
->MF
.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
2733 if (!Bot
.HazardRec
) {
2735 DAG
->MF
.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
2738 TopCand
.SU
= nullptr;
2739 BotCand
.SU
= nullptr;
2742 /// Initialize the per-region scheduling policy.
2743 void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin
,
2744 MachineBasicBlock::iterator End
,
2745 unsigned NumRegionInstrs
) {
2746 const MachineFunction
&MF
= *Begin
->getMF();
2747 const TargetLowering
*TLI
= MF
.getSubtarget().getTargetLowering();
2749 // Avoid setting up the register pressure tracker for small regions to save
2750 // compile time. As a rough heuristic, only track pressure when the number of
2751 // schedulable instructions exceeds half the integer register file.
2752 RegionPolicy
.ShouldTrackPressure
= true;
2753 for (unsigned VT
= MVT::i32
; VT
> (unsigned)MVT::i1
; --VT
) {
2754 MVT::SimpleValueType LegalIntVT
= (MVT::SimpleValueType
)VT
;
2755 if (TLI
->isTypeLegal(LegalIntVT
)) {
2756 unsigned NIntRegs
= Context
->RegClassInfo
->getNumAllocatableRegs(
2757 TLI
->getRegClassFor(LegalIntVT
));
2758 RegionPolicy
.ShouldTrackPressure
= NumRegionInstrs
> (NIntRegs
/ 2);
2762 // For generic targets, we default to bottom-up, because it's simpler and more
2763 // compile-time optimizations have been implemented in that direction.
2764 RegionPolicy
.OnlyBottomUp
= true;
2766 // Allow the subtarget to override default policy.
2767 MF
.getSubtarget().overrideSchedPolicy(RegionPolicy
, NumRegionInstrs
);
2769 // After subtarget overrides, apply command line options.
2770 if (!EnableRegPressure
) {
2771 RegionPolicy
.ShouldTrackPressure
= false;
2772 RegionPolicy
.ShouldTrackLaneMasks
= false;
2775 // Check -misched-topdown/bottomup can force or unforce scheduling direction.
2776 // e.g. -misched-bottomup=false allows scheduling in both directions.
2777 assert((!ForceTopDown
|| !ForceBottomUp
) &&
2778 "-misched-topdown incompatible with -misched-bottomup");
2779 if (ForceBottomUp
.getNumOccurrences() > 0) {
2780 RegionPolicy
.OnlyBottomUp
= ForceBottomUp
;
2781 if (RegionPolicy
.OnlyBottomUp
)
2782 RegionPolicy
.OnlyTopDown
= false;
2784 if (ForceTopDown
.getNumOccurrences() > 0) {
2785 RegionPolicy
.OnlyTopDown
= ForceTopDown
;
2786 if (RegionPolicy
.OnlyTopDown
)
2787 RegionPolicy
.OnlyBottomUp
= false;
2791 void GenericScheduler::dumpPolicy() const {
2792 // Cannot completely remove virtual function even in release mode.
2793 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2794 dbgs() << "GenericScheduler RegionPolicy: "
2795 << " ShouldTrackPressure=" << RegionPolicy
.ShouldTrackPressure
2796 << " OnlyTopDown=" << RegionPolicy
.OnlyTopDown
2797 << " OnlyBottomUp=" << RegionPolicy
.OnlyBottomUp
2802 /// Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic
2803 /// critical path by more cycles than it takes to drain the instruction buffer.
2804 /// We estimate an upper bounds on in-flight instructions as:
2806 /// CyclesPerIteration = max( CyclicPath, Loop-Resource-Height )
2807 /// InFlightIterations = AcyclicPath / CyclesPerIteration
2808 /// InFlightResources = InFlightIterations * LoopResources
2810 /// TODO: Check execution resources in addition to IssueCount.
2811 void GenericScheduler::checkAcyclicLatency() {
2812 if (Rem
.CyclicCritPath
== 0 || Rem
.CyclicCritPath
>= Rem
.CriticalPath
)
2815 // Scaled number of cycles per loop iteration.
2816 unsigned IterCount
=
2817 std::max(Rem
.CyclicCritPath
* SchedModel
->getLatencyFactor(),
2819 // Scaled acyclic critical path.
2820 unsigned AcyclicCount
= Rem
.CriticalPath
* SchedModel
->getLatencyFactor();
2821 // InFlightCount = (AcyclicPath / IterCycles) * InstrPerLoop
2822 unsigned InFlightCount
=
2823 (AcyclicCount
* Rem
.RemIssueCount
+ IterCount
-1) / IterCount
;
2824 unsigned BufferLimit
=
2825 SchedModel
->getMicroOpBufferSize() * SchedModel
->getMicroOpFactor();
2827 Rem
.IsAcyclicLatencyLimited
= InFlightCount
> BufferLimit
;
2830 dbgs() << "IssueCycles="
2831 << Rem
.RemIssueCount
/ SchedModel
->getLatencyFactor() << "c "
2832 << "IterCycles=" << IterCount
/ SchedModel
->getLatencyFactor()
2833 << "c NumIters=" << (AcyclicCount
+ IterCount
- 1) / IterCount
2834 << " InFlight=" << InFlightCount
/ SchedModel
->getMicroOpFactor()
2835 << "m BufferLim=" << SchedModel
->getMicroOpBufferSize() << "m\n";
2836 if (Rem
.IsAcyclicLatencyLimited
) dbgs() << " ACYCLIC LATENCY LIMIT\n");
2839 void GenericScheduler::registerRoots() {
2840 Rem
.CriticalPath
= DAG
->ExitSU
.getDepth();
2842 // Some roots may not feed into ExitSU. Check all of them in case.
2843 for (const SUnit
*SU
: Bot
.Available
) {
2844 if (SU
->getDepth() > Rem
.CriticalPath
)
2845 Rem
.CriticalPath
= SU
->getDepth();
2847 LLVM_DEBUG(dbgs() << "Critical Path(GS-RR ): " << Rem
.CriticalPath
<< '\n');
2848 if (DumpCriticalPathLength
) {
2849 errs() << "Critical Path(GS-RR ): " << Rem
.CriticalPath
<< " \n";
2852 if (EnableCyclicPath
&& SchedModel
->getMicroOpBufferSize() > 0) {
2853 Rem
.CyclicCritPath
= DAG
->computeCyclicCriticalPath();
2854 checkAcyclicLatency();
2859 bool tryPressure(const PressureChange
&TryP
,
2860 const PressureChange
&CandP
,
2861 GenericSchedulerBase::SchedCandidate
&TryCand
,
2862 GenericSchedulerBase::SchedCandidate
&Cand
,
2863 GenericSchedulerBase::CandReason Reason
,
2864 const TargetRegisterInfo
*TRI
,
2865 const MachineFunction
&MF
) {
2866 // If one candidate decreases and the other increases, go with it.
2867 // Invalid candidates have UnitInc==0.
2868 if (tryGreater(TryP
.getUnitInc() < 0, CandP
.getUnitInc() < 0, TryCand
, Cand
,
2872 // Do not compare the magnitude of pressure changes between top and bottom
2874 if (Cand
.AtTop
!= TryCand
.AtTop
)
2877 // If both candidates affect the same set in the same boundary, go with the
2878 // smallest increase.
2879 unsigned TryPSet
= TryP
.getPSetOrMax();
2880 unsigned CandPSet
= CandP
.getPSetOrMax();
2881 if (TryPSet
== CandPSet
) {
2882 return tryLess(TryP
.getUnitInc(), CandP
.getUnitInc(), TryCand
, Cand
,
2886 int TryRank
= TryP
.isValid() ? TRI
->getRegPressureSetScore(MF
, TryPSet
) :
2887 std::numeric_limits
<int>::max();
2889 int CandRank
= CandP
.isValid() ? TRI
->getRegPressureSetScore(MF
, CandPSet
) :
2890 std::numeric_limits
<int>::max();
2892 // If the candidates are decreasing pressure, reverse priority.
2893 if (TryP
.getUnitInc() < 0)
2894 std::swap(TryRank
, CandRank
);
2895 return tryGreater(TryRank
, CandRank
, TryCand
, Cand
, Reason
);
2898 unsigned getWeakLeft(const SUnit
*SU
, bool isTop
) {
2899 return (isTop
) ? SU
->WeakPredsLeft
: SU
->WeakSuccsLeft
;
2902 /// Minimize physical register live ranges. Regalloc wants them adjacent to
2903 /// their physreg def/use.
2905 /// FIXME: This is an unnecessary check on the critical path. Most are root/leaf
2906 /// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled
2907 /// with the operation that produces or consumes the physreg. We'll do this when
2908 /// regalloc has support for parallel copies.
2909 int biasPhysReg(const SUnit
*SU
, bool isTop
) {
2910 const MachineInstr
*MI
= SU
->getInstr();
2913 unsigned ScheduledOper
= isTop
? 1 : 0;
2914 unsigned UnscheduledOper
= isTop
? 0 : 1;
2915 // If we have already scheduled the physreg produce/consumer, immediately
2916 // schedule the copy.
2917 if (Register::isPhysicalRegister(MI
->getOperand(ScheduledOper
).getReg()))
2919 // If the physreg is at the boundary, defer it. Otherwise schedule it
2920 // immediately to free the dependent. We can hoist the copy later.
2921 bool AtBoundary
= isTop
? !SU
->NumSuccsLeft
: !SU
->NumPredsLeft
;
2922 if (Register::isPhysicalRegister(MI
->getOperand(UnscheduledOper
).getReg()))
2923 return AtBoundary
? -1 : 1;
2926 if (MI
->isMoveImmediate()) {
2927 // If we have a move immediate and all successors have been assigned, bias
2928 // towards scheduling this later. Make sure all register defs are to
2929 // physical registers.
2931 for (const MachineOperand
&Op
: MI
->defs()) {
2932 if (Op
.isReg() && !Register::isPhysicalRegister(Op
.getReg())) {
2939 return isTop
? -1 : 1;
2944 } // end namespace llvm
2946 void GenericScheduler::initCandidate(SchedCandidate
&Cand
, SUnit
*SU
,
2948 const RegPressureTracker
&RPTracker
,
2949 RegPressureTracker
&TempTracker
) {
2952 if (DAG
->isTrackingPressure()) {
2954 TempTracker
.getMaxDownwardPressureDelta(
2955 Cand
.SU
->getInstr(),
2957 DAG
->getRegionCriticalPSets(),
2958 DAG
->getRegPressure().MaxSetPressure
);
2960 if (VerifyScheduling
) {
2961 TempTracker
.getMaxUpwardPressureDelta(
2962 Cand
.SU
->getInstr(),
2963 &DAG
->getPressureDiff(Cand
.SU
),
2965 DAG
->getRegionCriticalPSets(),
2966 DAG
->getRegPressure().MaxSetPressure
);
2968 RPTracker
.getUpwardPressureDelta(
2969 Cand
.SU
->getInstr(),
2970 DAG
->getPressureDiff(Cand
.SU
),
2972 DAG
->getRegionCriticalPSets(),
2973 DAG
->getRegPressure().MaxSetPressure
);
2977 LLVM_DEBUG(if (Cand
.RPDelta
.Excess
.isValid()) dbgs()
2978 << " Try SU(" << Cand
.SU
->NodeNum
<< ") "
2979 << TRI
->getRegPressureSetName(Cand
.RPDelta
.Excess
.getPSet()) << ":"
2980 << Cand
.RPDelta
.Excess
.getUnitInc() << "\n");
2983 /// Apply a set of heuristics to a new candidate. Heuristics are currently
2984 /// hierarchical. This may be more efficient than a graduated cost model because
2985 /// we don't need to evaluate all aspects of the model for each node in the
2986 /// queue. But it's really done to make the heuristics easier to debug and
2987 /// statistically analyze.
2989 /// \param Cand provides the policy and current best candidate.
2990 /// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
2991 /// \param Zone describes the scheduled zone that we are extending, or nullptr
2992 // if Cand is from a different zone than TryCand.
2993 void GenericScheduler::tryCandidate(SchedCandidate
&Cand
,
2994 SchedCandidate
&TryCand
,
2995 SchedBoundary
*Zone
) const {
2996 // Initialize the candidate if needed.
2997 if (!Cand
.isValid()) {
2998 TryCand
.Reason
= NodeOrder
;
3002 // Bias PhysReg Defs and copies to their uses and defined respectively.
3003 if (tryGreater(biasPhysReg(TryCand
.SU
, TryCand
.AtTop
),
3004 biasPhysReg(Cand
.SU
, Cand
.AtTop
), TryCand
, Cand
, PhysReg
))
3007 // Avoid exceeding the target's limit.
3008 if (DAG
->isTrackingPressure() && tryPressure(TryCand
.RPDelta
.Excess
,
3009 Cand
.RPDelta
.Excess
,
3010 TryCand
, Cand
, RegExcess
, TRI
,
3014 // Avoid increasing the max critical pressure in the scheduled region.
3015 if (DAG
->isTrackingPressure() && tryPressure(TryCand
.RPDelta
.CriticalMax
,
3016 Cand
.RPDelta
.CriticalMax
,
3017 TryCand
, Cand
, RegCritical
, TRI
,
3021 // We only compare a subset of features when comparing nodes between
3022 // Top and Bottom boundary. Some properties are simply incomparable, in many
3023 // other instances we should only override the other boundary if something
3024 // is a clear good pick on one boundary. Skip heuristics that are more
3025 // "tie-breaking" in nature.
3026 bool SameBoundary
= Zone
!= nullptr;
3028 // For loops that are acyclic path limited, aggressively schedule for
3029 // latency. Within an single cycle, whenever CurrMOps > 0, allow normal
3030 // heuristics to take precedence.
3031 if (Rem
.IsAcyclicLatencyLimited
&& !Zone
->getCurrMOps() &&
3032 tryLatency(TryCand
, Cand
, *Zone
))
3035 // Prioritize instructions that read unbuffered resources by stall cycles.
3036 if (tryLess(Zone
->getLatencyStallCycles(TryCand
.SU
),
3037 Zone
->getLatencyStallCycles(Cand
.SU
), TryCand
, Cand
, Stall
))
3041 // Keep clustered nodes together to encourage downstream peephole
3042 // optimizations which may reduce resource requirements.
3044 // This is a best effort to set things up for a post-RA pass. Optimizations
3045 // like generating loads of multiple registers should ideally be done within
3046 // the scheduler pass by combining the loads during DAG postprocessing.
3047 const SUnit
*CandNextClusterSU
=
3048 Cand
.AtTop
? DAG
->getNextClusterSucc() : DAG
->getNextClusterPred();
3049 const SUnit
*TryCandNextClusterSU
=
3050 TryCand
.AtTop
? DAG
->getNextClusterSucc() : DAG
->getNextClusterPred();
3051 if (tryGreater(TryCand
.SU
== TryCandNextClusterSU
,
3052 Cand
.SU
== CandNextClusterSU
,
3053 TryCand
, Cand
, Cluster
))
3057 // Weak edges are for clustering and other constraints.
3058 if (tryLess(getWeakLeft(TryCand
.SU
, TryCand
.AtTop
),
3059 getWeakLeft(Cand
.SU
, Cand
.AtTop
),
3060 TryCand
, Cand
, Weak
))
3064 // Avoid increasing the max pressure of the entire region.
3065 if (DAG
->isTrackingPressure() && tryPressure(TryCand
.RPDelta
.CurrentMax
,
3066 Cand
.RPDelta
.CurrentMax
,
3067 TryCand
, Cand
, RegMax
, TRI
,
3072 // Avoid critical resource consumption and balance the schedule.
3073 TryCand
.initResourceDelta(DAG
, SchedModel
);
3074 if (tryLess(TryCand
.ResDelta
.CritResources
, Cand
.ResDelta
.CritResources
,
3075 TryCand
, Cand
, ResourceReduce
))
3077 if (tryGreater(TryCand
.ResDelta
.DemandedResources
,
3078 Cand
.ResDelta
.DemandedResources
,
3079 TryCand
, Cand
, ResourceDemand
))
3082 // Avoid serializing long latency dependence chains.
3083 // For acyclic path limited loops, latency was already checked above.
3084 if (!RegionPolicy
.DisableLatencyHeuristic
&& TryCand
.Policy
.ReduceLatency
&&
3085 !Rem
.IsAcyclicLatencyLimited
&& tryLatency(TryCand
, Cand
, *Zone
))
3088 // Fall through to original instruction order.
3089 if ((Zone
->isTop() && TryCand
.SU
->NodeNum
< Cand
.SU
->NodeNum
)
3090 || (!Zone
->isTop() && TryCand
.SU
->NodeNum
> Cand
.SU
->NodeNum
)) {
3091 TryCand
.Reason
= NodeOrder
;
3096 /// Pick the best candidate from the queue.
3098 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
3099 /// DAG building. To adjust for the current scheduling location we need to
3100 /// maintain the number of vreg uses remaining to be top-scheduled.
3101 void GenericScheduler::pickNodeFromQueue(SchedBoundary
&Zone
,
3102 const CandPolicy
&ZonePolicy
,
3103 const RegPressureTracker
&RPTracker
,
3104 SchedCandidate
&Cand
) {
3105 // getMaxPressureDelta temporarily modifies the tracker.
3106 RegPressureTracker
&TempTracker
= const_cast<RegPressureTracker
&>(RPTracker
);
3108 ReadyQueue
&Q
= Zone
.Available
;
3109 for (SUnit
*SU
: Q
) {
3111 SchedCandidate
TryCand(ZonePolicy
);
3112 initCandidate(TryCand
, SU
, Zone
.isTop(), RPTracker
, TempTracker
);
3113 // Pass SchedBoundary only when comparing nodes from the same boundary.
3114 SchedBoundary
*ZoneArg
= Cand
.AtTop
== TryCand
.AtTop
? &Zone
: nullptr;
3115 tryCandidate(Cand
, TryCand
, ZoneArg
);
3116 if (TryCand
.Reason
!= NoCand
) {
3117 // Initialize resource delta if needed in case future heuristics query it.
3118 if (TryCand
.ResDelta
== SchedResourceDelta())
3119 TryCand
.initResourceDelta(DAG
, SchedModel
);
3120 Cand
.setBest(TryCand
);
3121 LLVM_DEBUG(traceCandidate(Cand
));
3126 /// Pick the best candidate node from either the top or bottom queue.
3127 SUnit
*GenericScheduler::pickNodeBidirectional(bool &IsTopNode
) {
3128 // Schedule as far as possible in the direction of no choice. This is most
3129 // efficient, but also provides the best heuristics for CriticalPSets.
3130 if (SUnit
*SU
= Bot
.pickOnlyChoice()) {
3132 tracePick(Only1
, false);
3135 if (SUnit
*SU
= Top
.pickOnlyChoice()) {
3137 tracePick(Only1
, true);
3140 // Set the bottom-up policy based on the state of the current bottom zone and
3141 // the instructions outside the zone, including the top zone.
3142 CandPolicy BotPolicy
;
3143 setPolicy(BotPolicy
, /*IsPostRA=*/false, Bot
, &Top
);
3144 // Set the top-down policy based on the state of the current top zone and
3145 // the instructions outside the zone, including the bottom zone.
3146 CandPolicy TopPolicy
;
3147 setPolicy(TopPolicy
, /*IsPostRA=*/false, Top
, &Bot
);
3149 // See if BotCand is still valid (because we previously scheduled from Top).
3150 LLVM_DEBUG(dbgs() << "Picking from Bot:\n");
3151 if (!BotCand
.isValid() || BotCand
.SU
->isScheduled
||
3152 BotCand
.Policy
!= BotPolicy
) {
3153 BotCand
.reset(CandPolicy());
3154 pickNodeFromQueue(Bot
, BotPolicy
, DAG
->getBotRPTracker(), BotCand
);
3155 assert(BotCand
.Reason
!= NoCand
&& "failed to find the first candidate");
3157 LLVM_DEBUG(traceCandidate(BotCand
));
3159 if (VerifyScheduling
) {
3160 SchedCandidate TCand
;
3161 TCand
.reset(CandPolicy());
3162 pickNodeFromQueue(Bot
, BotPolicy
, DAG
->getBotRPTracker(), TCand
);
3163 assert(TCand
.SU
== BotCand
.SU
&&
3164 "Last pick result should correspond to re-picking right now");
3169 // Check if the top Q has a better candidate.
3170 LLVM_DEBUG(dbgs() << "Picking from Top:\n");
3171 if (!TopCand
.isValid() || TopCand
.SU
->isScheduled
||
3172 TopCand
.Policy
!= TopPolicy
) {
3173 TopCand
.reset(CandPolicy());
3174 pickNodeFromQueue(Top
, TopPolicy
, DAG
->getTopRPTracker(), TopCand
);
3175 assert(TopCand
.Reason
!= NoCand
&& "failed to find the first candidate");
3177 LLVM_DEBUG(traceCandidate(TopCand
));
3179 if (VerifyScheduling
) {
3180 SchedCandidate TCand
;
3181 TCand
.reset(CandPolicy());
3182 pickNodeFromQueue(Top
, TopPolicy
, DAG
->getTopRPTracker(), TCand
);
3183 assert(TCand
.SU
== TopCand
.SU
&&
3184 "Last pick result should correspond to re-picking right now");
3189 // Pick best from BotCand and TopCand.
3190 assert(BotCand
.isValid());
3191 assert(TopCand
.isValid());
3192 SchedCandidate Cand
= BotCand
;
3193 TopCand
.Reason
= NoCand
;
3194 tryCandidate(Cand
, TopCand
, nullptr);
3195 if (TopCand
.Reason
!= NoCand
) {
3196 Cand
.setBest(TopCand
);
3197 LLVM_DEBUG(traceCandidate(Cand
));
3200 IsTopNode
= Cand
.AtTop
;
3205 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
3206 SUnit
*GenericScheduler::pickNode(bool &IsTopNode
) {
3207 if (DAG
->top() == DAG
->bottom()) {
3208 assert(Top
.Available
.empty() && Top
.Pending
.empty() &&
3209 Bot
.Available
.empty() && Bot
.Pending
.empty() && "ReadyQ garbage");
3214 if (RegionPolicy
.OnlyTopDown
) {
3215 SU
= Top
.pickOnlyChoice();
3217 CandPolicy NoPolicy
;
3218 TopCand
.reset(NoPolicy
);
3219 pickNodeFromQueue(Top
, NoPolicy
, DAG
->getTopRPTracker(), TopCand
);
3220 assert(TopCand
.Reason
!= NoCand
&& "failed to find a candidate");
3225 } else if (RegionPolicy
.OnlyBottomUp
) {
3226 SU
= Bot
.pickOnlyChoice();
3228 CandPolicy NoPolicy
;
3229 BotCand
.reset(NoPolicy
);
3230 pickNodeFromQueue(Bot
, NoPolicy
, DAG
->getBotRPTracker(), BotCand
);
3231 assert(BotCand
.Reason
!= NoCand
&& "failed to find a candidate");
3237 SU
= pickNodeBidirectional(IsTopNode
);
3239 } while (SU
->isScheduled
);
3241 if (SU
->isTopReady())
3242 Top
.removeReady(SU
);
3243 if (SU
->isBottomReady())
3244 Bot
.removeReady(SU
);
3246 LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU
->NodeNum
<< ") "
3247 << *SU
->getInstr());
3251 void GenericScheduler::reschedulePhysReg(SUnit
*SU
, bool isTop
) {
3252 MachineBasicBlock::iterator InsertPos
= SU
->getInstr();
3255 SmallVectorImpl
<SDep
> &Deps
= isTop
? SU
->Preds
: SU
->Succs
;
3257 // Find already scheduled copies with a single physreg dependence and move
3258 // them just above the scheduled instruction.
3259 for (SDep
&Dep
: Deps
) {
3260 if (Dep
.getKind() != SDep::Data
||
3261 !Register::isPhysicalRegister(Dep
.getReg()))
3263 SUnit
*DepSU
= Dep
.getSUnit();
3264 if (isTop
? DepSU
->Succs
.size() > 1 : DepSU
->Preds
.size() > 1)
3266 MachineInstr
*Copy
= DepSU
->getInstr();
3267 if (!Copy
->isCopy() && !Copy
->isMoveImmediate())
3269 LLVM_DEBUG(dbgs() << " Rescheduling physreg copy ";
3270 DAG
->dumpNode(*Dep
.getSUnit()));
3271 DAG
->moveInstruction(Copy
, InsertPos
);
3275 /// Update the scheduler's state after scheduling a node. This is the same node
3276 /// that was just returned by pickNode(). However, ScheduleDAGMILive needs to
3277 /// update it's state based on the current cycle before MachineSchedStrategy
3280 /// FIXME: Eventually, we may bundle physreg copies rather than rescheduling
3281 /// them here. See comments in biasPhysReg.
3282 void GenericScheduler::schedNode(SUnit
*SU
, bool IsTopNode
) {
3284 SU
->TopReadyCycle
= std::max(SU
->TopReadyCycle
, Top
.getCurrCycle());
3286 if (SU
->hasPhysRegUses
)
3287 reschedulePhysReg(SU
, true);
3289 SU
->BotReadyCycle
= std::max(SU
->BotReadyCycle
, Bot
.getCurrCycle());
3291 if (SU
->hasPhysRegDefs
)
3292 reschedulePhysReg(SU
, false);
3296 /// Create the standard converging machine scheduler. This will be used as the
3297 /// default scheduler if the target does not set a default.
3298 ScheduleDAGMILive
*llvm::createGenericSchedLive(MachineSchedContext
*C
) {
3299 ScheduleDAGMILive
*DAG
=
3300 new ScheduleDAGMILive(C
, std::make_unique
<GenericScheduler
>(C
));
3301 // Register DAG post-processors.
3303 // FIXME: extend the mutation API to allow earlier mutations to instantiate
3304 // data and pass it to later mutations. Have a single mutation that gathers
3305 // the interesting nodes in one pass.
3306 DAG
->addMutation(createCopyConstrainDAGMutation(DAG
->TII
, DAG
->TRI
));
3310 static ScheduleDAGInstrs
*createConveringSched(MachineSchedContext
*C
) {
3311 return createGenericSchedLive(C
);
3314 static MachineSchedRegistry
3315 GenericSchedRegistry("converge", "Standard converging scheduler.",
3316 createConveringSched
);
3318 //===----------------------------------------------------------------------===//
3319 // PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy.
3320 //===----------------------------------------------------------------------===//
3322 void PostGenericScheduler::initialize(ScheduleDAGMI
*Dag
) {
3324 SchedModel
= DAG
->getSchedModel();
3327 Rem
.init(DAG
, SchedModel
);
3328 Top
.init(DAG
, SchedModel
, &Rem
);
3331 // Initialize the HazardRecognizers. If itineraries don't exist, are empty,
3332 // or are disabled, then these HazardRecs will be disabled.
3333 const InstrItineraryData
*Itin
= SchedModel
->getInstrItineraries();
3334 if (!Top
.HazardRec
) {
3336 DAG
->MF
.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
3341 void PostGenericScheduler::registerRoots() {
3342 Rem
.CriticalPath
= DAG
->ExitSU
.getDepth();
3344 // Some roots may not feed into ExitSU. Check all of them in case.
3345 for (const SUnit
*SU
: BotRoots
) {
3346 if (SU
->getDepth() > Rem
.CriticalPath
)
3347 Rem
.CriticalPath
= SU
->getDepth();
3349 LLVM_DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem
.CriticalPath
<< '\n');
3350 if (DumpCriticalPathLength
) {
3351 errs() << "Critical Path(PGS-RR ): " << Rem
.CriticalPath
<< " \n";
3355 /// Apply a set of heuristics to a new candidate for PostRA scheduling.
3357 /// \param Cand provides the policy and current best candidate.
3358 /// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
3359 void PostGenericScheduler::tryCandidate(SchedCandidate
&Cand
,
3360 SchedCandidate
&TryCand
) {
3361 // Initialize the candidate if needed.
3362 if (!Cand
.isValid()) {
3363 TryCand
.Reason
= NodeOrder
;
3367 // Prioritize instructions that read unbuffered resources by stall cycles.
3368 if (tryLess(Top
.getLatencyStallCycles(TryCand
.SU
),
3369 Top
.getLatencyStallCycles(Cand
.SU
), TryCand
, Cand
, Stall
))
3372 // Keep clustered nodes together.
3373 if (tryGreater(TryCand
.SU
== DAG
->getNextClusterSucc(),
3374 Cand
.SU
== DAG
->getNextClusterSucc(),
3375 TryCand
, Cand
, Cluster
))
3378 // Avoid critical resource consumption and balance the schedule.
3379 if (tryLess(TryCand
.ResDelta
.CritResources
, Cand
.ResDelta
.CritResources
,
3380 TryCand
, Cand
, ResourceReduce
))
3382 if (tryGreater(TryCand
.ResDelta
.DemandedResources
,
3383 Cand
.ResDelta
.DemandedResources
,
3384 TryCand
, Cand
, ResourceDemand
))
3387 // Avoid serializing long latency dependence chains.
3388 if (Cand
.Policy
.ReduceLatency
&& tryLatency(TryCand
, Cand
, Top
)) {
3392 // Fall through to original instruction order.
3393 if (TryCand
.SU
->NodeNum
< Cand
.SU
->NodeNum
)
3394 TryCand
.Reason
= NodeOrder
;
3397 void PostGenericScheduler::pickNodeFromQueue(SchedCandidate
&Cand
) {
3398 ReadyQueue
&Q
= Top
.Available
;
3399 for (SUnit
*SU
: Q
) {
3400 SchedCandidate
TryCand(Cand
.Policy
);
3402 TryCand
.AtTop
= true;
3403 TryCand
.initResourceDelta(DAG
, SchedModel
);
3404 tryCandidate(Cand
, TryCand
);
3405 if (TryCand
.Reason
!= NoCand
) {
3406 Cand
.setBest(TryCand
);
3407 LLVM_DEBUG(traceCandidate(Cand
));
3412 /// Pick the next node to schedule.
3413 SUnit
*PostGenericScheduler::pickNode(bool &IsTopNode
) {
3414 if (DAG
->top() == DAG
->bottom()) {
3415 assert(Top
.Available
.empty() && Top
.Pending
.empty() && "ReadyQ garbage");
3420 SU
= Top
.pickOnlyChoice();
3422 tracePick(Only1
, true);
3424 CandPolicy NoPolicy
;
3425 SchedCandidate
TopCand(NoPolicy
);
3426 // Set the top-down policy based on the state of the current top zone and
3427 // the instructions outside the zone, including the bottom zone.
3428 setPolicy(TopCand
.Policy
, /*IsPostRA=*/true, Top
, nullptr);
3429 pickNodeFromQueue(TopCand
);
3430 assert(TopCand
.Reason
!= NoCand
&& "failed to find a candidate");
3434 } while (SU
->isScheduled
);
3437 Top
.removeReady(SU
);
3439 LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU
->NodeNum
<< ") "
3440 << *SU
->getInstr());
3444 /// Called after ScheduleDAGMI has scheduled an instruction and updated
3445 /// scheduled/remaining flags in the DAG nodes.
3446 void PostGenericScheduler::schedNode(SUnit
*SU
, bool IsTopNode
) {
3447 SU
->TopReadyCycle
= std::max(SU
->TopReadyCycle
, Top
.getCurrCycle());
3451 ScheduleDAGMI
*llvm::createGenericSchedPostRA(MachineSchedContext
*C
) {
3452 return new ScheduleDAGMI(C
, std::make_unique
<PostGenericScheduler
>(C
),
3453 /*RemoveKillFlags=*/true);
3456 //===----------------------------------------------------------------------===//
3457 // ILP Scheduler. Currently for experimental analysis of heuristics.
3458 //===----------------------------------------------------------------------===//
3462 /// Order nodes by the ILP metric.
3464 const SchedDFSResult
*DFSResult
= nullptr;
3465 const BitVector
*ScheduledTrees
= nullptr;
3468 ILPOrder(bool MaxILP
) : MaximizeILP(MaxILP
) {}
3470 /// Apply a less-than relation on node priority.
3472 /// (Return true if A comes after B in the Q.)
3473 bool operator()(const SUnit
*A
, const SUnit
*B
) const {
3474 unsigned SchedTreeA
= DFSResult
->getSubtreeID(A
);
3475 unsigned SchedTreeB
= DFSResult
->getSubtreeID(B
);
3476 if (SchedTreeA
!= SchedTreeB
) {
3477 // Unscheduled trees have lower priority.
3478 if (ScheduledTrees
->test(SchedTreeA
) != ScheduledTrees
->test(SchedTreeB
))
3479 return ScheduledTrees
->test(SchedTreeB
);
3481 // Trees with shallower connections have have lower priority.
3482 if (DFSResult
->getSubtreeLevel(SchedTreeA
)
3483 != DFSResult
->getSubtreeLevel(SchedTreeB
)) {
3484 return DFSResult
->getSubtreeLevel(SchedTreeA
)
3485 < DFSResult
->getSubtreeLevel(SchedTreeB
);
3489 return DFSResult
->getILP(A
) < DFSResult
->getILP(B
);
3491 return DFSResult
->getILP(A
) > DFSResult
->getILP(B
);
3495 /// Schedule based on the ILP metric.
3496 class ILPScheduler
: public MachineSchedStrategy
{
3497 ScheduleDAGMILive
*DAG
= nullptr;
3500 std::vector
<SUnit
*> ReadyQ
;
3503 ILPScheduler(bool MaximizeILP
) : Cmp(MaximizeILP
) {}
3505 void initialize(ScheduleDAGMI
*dag
) override
{
3506 assert(dag
->hasVRegLiveness() && "ILPScheduler needs vreg liveness");
3507 DAG
= static_cast<ScheduleDAGMILive
*>(dag
);
3508 DAG
->computeDFSResult();
3509 Cmp
.DFSResult
= DAG
->getDFSResult();
3510 Cmp
.ScheduledTrees
= &DAG
->getScheduledTrees();
3514 void registerRoots() override
{
3515 // Restore the heap in ReadyQ with the updated DFS results.
3516 std::make_heap(ReadyQ
.begin(), ReadyQ
.end(), Cmp
);
3519 /// Implement MachineSchedStrategy interface.
3520 /// -----------------------------------------
3522 /// Callback to select the highest priority node from the ready Q.
3523 SUnit
*pickNode(bool &IsTopNode
) override
{
3524 if (ReadyQ
.empty()) return nullptr;
3525 std::pop_heap(ReadyQ
.begin(), ReadyQ
.end(), Cmp
);
3526 SUnit
*SU
= ReadyQ
.back();
3529 LLVM_DEBUG(dbgs() << "Pick node "
3530 << "SU(" << SU
->NodeNum
<< ") "
3531 << " ILP: " << DAG
->getDFSResult()->getILP(SU
)
3532 << " Tree: " << DAG
->getDFSResult()->getSubtreeID(SU
)
3534 << DAG
->getDFSResult()->getSubtreeLevel(
3535 DAG
->getDFSResult()->getSubtreeID(SU
))
3537 << "Scheduling " << *SU
->getInstr());
3541 /// Scheduler callback to notify that a new subtree is scheduled.
3542 void scheduleTree(unsigned SubtreeID
) override
{
3543 std::make_heap(ReadyQ
.begin(), ReadyQ
.end(), Cmp
);
3546 /// Callback after a node is scheduled. Mark a newly scheduled tree, notify
3547 /// DFSResults, and resort the priority Q.
3548 void schedNode(SUnit
*SU
, bool IsTopNode
) override
{
3549 assert(!IsTopNode
&& "SchedDFSResult needs bottom-up");
3552 void releaseTopNode(SUnit
*) override
{ /*only called for top roots*/ }
3554 void releaseBottomNode(SUnit
*SU
) override
{
3555 ReadyQ
.push_back(SU
);
3556 std::push_heap(ReadyQ
.begin(), ReadyQ
.end(), Cmp
);
3560 } // end anonymous namespace
3562 static ScheduleDAGInstrs
*createILPMaxScheduler(MachineSchedContext
*C
) {
3563 return new ScheduleDAGMILive(C
, std::make_unique
<ILPScheduler
>(true));
3565 static ScheduleDAGInstrs
*createILPMinScheduler(MachineSchedContext
*C
) {
3566 return new ScheduleDAGMILive(C
, std::make_unique
<ILPScheduler
>(false));
3569 static MachineSchedRegistry
ILPMaxRegistry(
3570 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler
);
3571 static MachineSchedRegistry
ILPMinRegistry(
3572 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler
);
3574 //===----------------------------------------------------------------------===//
3575 // Machine Instruction Shuffler for Correctness Testing
3576 //===----------------------------------------------------------------------===//
3581 /// Apply a less-than relation on the node order, which corresponds to the
3582 /// instruction order prior to scheduling. IsReverse implements greater-than.
3583 template<bool IsReverse
>
3585 bool operator()(SUnit
*A
, SUnit
*B
) const {
3587 return A
->NodeNum
> B
->NodeNum
;
3589 return A
->NodeNum
< B
->NodeNum
;
3593 /// Reorder instructions as much as possible.
3594 class InstructionShuffler
: public MachineSchedStrategy
{
3598 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority
3599 // gives nodes with a higher number higher priority causing the latest
3600 // instructions to be scheduled first.
3601 PriorityQueue
<SUnit
*, std::vector
<SUnit
*>, SUnitOrder
<false>>
3604 // When scheduling bottom-up, use greater-than as the queue priority.
3605 PriorityQueue
<SUnit
*, std::vector
<SUnit
*>, SUnitOrder
<true>>
3609 InstructionShuffler(bool alternate
, bool topdown
)
3610 : IsAlternating(alternate
), IsTopDown(topdown
) {}
3612 void initialize(ScheduleDAGMI
*) override
{
3617 /// Implement MachineSchedStrategy interface.
3618 /// -----------------------------------------
3620 SUnit
*pickNode(bool &IsTopNode
) override
{
3624 if (TopQ
.empty()) return nullptr;
3627 } while (SU
->isScheduled
);
3631 if (BottomQ
.empty()) return nullptr;
3634 } while (SU
->isScheduled
);
3638 IsTopDown
= !IsTopDown
;
3642 void schedNode(SUnit
*SU
, bool IsTopNode
) override
{}
3644 void releaseTopNode(SUnit
*SU
) override
{
3647 void releaseBottomNode(SUnit
*SU
) override
{
3652 } // end anonymous namespace
3654 static ScheduleDAGInstrs
*createInstructionShuffler(MachineSchedContext
*C
) {
3655 bool Alternate
= !ForceTopDown
&& !ForceBottomUp
;
3656 bool TopDown
= !ForceBottomUp
;
3657 assert((TopDown
|| !ForceTopDown
) &&
3658 "-misched-topdown incompatible with -misched-bottomup");
3659 return new ScheduleDAGMILive(
3660 C
, std::make_unique
<InstructionShuffler
>(Alternate
, TopDown
));
3663 static MachineSchedRegistry
ShufflerRegistry(
3664 "shuffle", "Shuffle machine instructions alternating directions",
3665 createInstructionShuffler
);
3668 //===----------------------------------------------------------------------===//
3669 // GraphWriter support for ScheduleDAGMILive.
3670 //===----------------------------------------------------------------------===//
3675 template<> struct GraphTraits
<
3676 ScheduleDAGMI
*> : public GraphTraits
<ScheduleDAG
*> {};
3679 struct DOTGraphTraits
<ScheduleDAGMI
*> : public DefaultDOTGraphTraits
{
3680 DOTGraphTraits(bool isSimple
= false) : DefaultDOTGraphTraits(isSimple
) {}
3682 static std::string
getGraphName(const ScheduleDAG
*G
) {
3683 return G
->MF
.getName();
3686 static bool renderGraphFromBottomUp() {
3690 static bool isNodeHidden(const SUnit
*Node
) {
3691 if (ViewMISchedCutoff
== 0)
3693 return (Node
->Preds
.size() > ViewMISchedCutoff
3694 || Node
->Succs
.size() > ViewMISchedCutoff
);
3697 /// If you want to override the dot attributes printed for a particular
3698 /// edge, override this method.
3699 static std::string
getEdgeAttributes(const SUnit
*Node
,
3701 const ScheduleDAG
*Graph
) {
3702 if (EI
.isArtificialDep())
3703 return "color=cyan,style=dashed";
3705 return "color=blue,style=dashed";
3709 static std::string
getNodeLabel(const SUnit
*SU
, const ScheduleDAG
*G
) {
3711 raw_string_ostream
SS(Str
);
3712 const ScheduleDAGMI
*DAG
= static_cast<const ScheduleDAGMI
*>(G
);
3713 const SchedDFSResult
*DFS
= DAG
->hasVRegLiveness() ?
3714 static_cast<const ScheduleDAGMILive
*>(G
)->getDFSResult() : nullptr;
3715 SS
<< "SU:" << SU
->NodeNum
;
3717 SS
<< " I:" << DFS
->getNumInstrs(SU
);
3721 static std::string
getNodeDescription(const SUnit
*SU
, const ScheduleDAG
*G
) {
3722 return G
->getGraphNodeLabel(SU
);
3725 static std::string
getNodeAttributes(const SUnit
*N
, const ScheduleDAG
*G
) {
3726 std::string
Str("shape=Mrecord");
3727 const ScheduleDAGMI
*DAG
= static_cast<const ScheduleDAGMI
*>(G
);
3728 const SchedDFSResult
*DFS
= DAG
->hasVRegLiveness() ?
3729 static_cast<const ScheduleDAGMILive
*>(G
)->getDFSResult() : nullptr;
3731 Str
+= ",style=filled,fillcolor=\"#";
3732 Str
+= DOT::getColorString(DFS
->getSubtreeID(N
));
3739 } // end namespace llvm
3742 /// viewGraph - Pop up a ghostview window with the reachable parts of the DAG
3743 /// rendered using 'dot'.
3744 void ScheduleDAGMI::viewGraph(const Twine
&Name
, const Twine
&Title
) {
3746 ViewGraph(this, Name
, false, Title
);
3748 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "
3749 << "systems with Graphviz or gv!\n";
3753 /// Out-of-line implementation with no arguments is handy for gdb.
3754 void ScheduleDAGMI::viewGraph() {
3755 viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName());