1//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// MachineScheduler schedules machine instructions after phi elimination. It
10// preserves LiveIntervals so it can be invoked before register allocation.
11//
12//===----------------------------------------------------------------------===//
13
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/EquivalenceClasses.h"
19#include "llvm/ADT/PriorityQueue.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/ADT/iterator_range.h"
24#include "llvm/Analysis/AliasAnalysis.h"
25#include "llvm/CodeGen/LiveInterval.h"
26#include "llvm/CodeGen/LiveIntervals.h"
27#include "llvm/CodeGen/MachineBasicBlock.h"
28#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineFunctionPass.h"
30#include "llvm/CodeGen/MachineInstr.h"
31#include "llvm/CodeGen/MachineLoopInfo.h"
32#include "llvm/CodeGen/MachineOperand.h"
33#include "llvm/CodeGen/MachinePassRegistry.h"
34#include "llvm/CodeGen/MachineRegisterInfo.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/CodeGenTypes/MachineValueType.h"
51#include "llvm/Config/llvm-config.h"
52#include "llvm/InitializePasses.h"
53#include "llvm/MC/LaneBitmask.h"
54#include "llvm/Pass.h"
55#include "llvm/Support/CommandLine.h"
56#include "llvm/Support/Compiler.h"
57#include "llvm/Support/Debug.h"
58#include "llvm/Support/ErrorHandling.h"
59#include "llvm/Support/GraphWriter.h"
60#include "llvm/Support/raw_ostream.h"
61#include "llvm/Target/TargetMachine.h"
62#include <algorithm>
63#include <cassert>
64#include <cstdint>
65#include <iterator>
66#include <limits>
67#include <memory>
68#include <string>
69#include <tuple>
70#include <utility>
71#include <vector>
72
73using namespace llvm;
74
75#define DEBUG_TYPE "machine-scheduler"
76
77STATISTIC(NumInstrsInSourceOrderPreRA,
78 "Number of instructions in source order after pre-RA scheduling");
79STATISTIC(NumInstrsInSourceOrderPostRA,
80 "Number of instructions in source order after post-RA scheduling");
81STATISTIC(NumInstrsScheduledPreRA,
82 "Number of instructions scheduled by pre-RA scheduler");
83STATISTIC(NumInstrsScheduledPostRA,
84 "Number of instructions scheduled by post-RA scheduler");
85STATISTIC(NumClustered, "Number of load/store pairs clustered");
86
87STATISTIC(NumTopPreRA,
88 "Number of scheduling units chosen from top queue pre-RA");
89STATISTIC(NumBotPreRA,
90 "Number of scheduling units chosen from bottom queue pre-RA");
91STATISTIC(NumNoCandPreRA,
92 "Number of scheduling units chosen for NoCand heuristic pre-RA");
93STATISTIC(NumOnly1PreRA,
94 "Number of scheduling units chosen for Only1 heuristic pre-RA");
95STATISTIC(NumPhysRegPreRA,
96 "Number of scheduling units chosen for PhysReg heuristic pre-RA");
97STATISTIC(NumRegExcessPreRA,
98 "Number of scheduling units chosen for RegExcess heuristic pre-RA");
99STATISTIC(NumRegCriticalPreRA,
100 "Number of scheduling units chosen for RegCritical heuristic pre-RA");
101STATISTIC(NumStallPreRA,
102 "Number of scheduling units chosen for Stall heuristic pre-RA");
103STATISTIC(NumClusterPreRA,
104 "Number of scheduling units chosen for Cluster heuristic pre-RA");
105STATISTIC(NumWeakPreRA,
106 "Number of scheduling units chosen for Weak heuristic pre-RA");
107STATISTIC(NumRegMaxPreRA,
108 "Number of scheduling units chosen for RegMax heuristic pre-RA");
109STATISTIC(
110 NumResourceReducePreRA,
111 "Number of scheduling units chosen for ResourceReduce heuristic pre-RA");
112STATISTIC(
113 NumResourceDemandPreRA,
114 "Number of scheduling units chosen for ResourceDemand heuristic pre-RA");
115STATISTIC(
116 NumTopDepthReducePreRA,
117 "Number of scheduling units chosen for TopDepthReduce heuristic pre-RA");
118STATISTIC(
119 NumTopPathReducePreRA,
120 "Number of scheduling units chosen for TopPathReduce heuristic pre-RA");
121STATISTIC(
122 NumBotHeightReducePreRA,
123 "Number of scheduling units chosen for BotHeightReduce heuristic pre-RA");
124STATISTIC(
125 NumBotPathReducePreRA,
126 "Number of scheduling units chosen for BotPathReduce heuristic pre-RA");
127STATISTIC(NumNodeOrderPreRA,
128 "Number of scheduling units chosen for NodeOrder heuristic pre-RA");
129STATISTIC(NumFirstValidPreRA,
130 "Number of scheduling units chosen for FirstValid heuristic pre-RA");
131
132STATISTIC(NumTopPostRA,
133 "Number of scheduling units chosen from top queue post-RA");
134STATISTIC(NumBotPostRA,
135 "Number of scheduling units chosen from bottom queue post-RA");
136STATISTIC(NumNoCandPostRA,
137 "Number of scheduling units chosen for NoCand heuristic post-RA");
138STATISTIC(NumOnly1PostRA,
139 "Number of scheduling units chosen for Only1 heuristic post-RA");
140STATISTIC(NumPhysRegPostRA,
141 "Number of scheduling units chosen for PhysReg heuristic post-RA");
142STATISTIC(NumRegExcessPostRA,
143 "Number of scheduling units chosen for RegExcess heuristic post-RA");
144STATISTIC(
145 NumRegCriticalPostRA,
146 "Number of scheduling units chosen for RegCritical heuristic post-RA");
147STATISTIC(NumStallPostRA,
148 "Number of scheduling units chosen for Stall heuristic post-RA");
149STATISTIC(NumClusterPostRA,
150 "Number of scheduling units chosen for Cluster heuristic post-RA");
151STATISTIC(NumWeakPostRA,
152 "Number of scheduling units chosen for Weak heuristic post-RA");
153STATISTIC(NumRegMaxPostRA,
154 "Number of scheduling units chosen for RegMax heuristic post-RA");
155STATISTIC(
156 NumResourceReducePostRA,
157 "Number of scheduling units chosen for ResourceReduce heuristic post-RA");
158STATISTIC(
159 NumResourceDemandPostRA,
160 "Number of scheduling units chosen for ResourceDemand heuristic post-RA");
161STATISTIC(
162 NumTopDepthReducePostRA,
163 "Number of scheduling units chosen for TopDepthReduce heuristic post-RA");
164STATISTIC(
165 NumTopPathReducePostRA,
166 "Number of scheduling units chosen for TopPathReduce heuristic post-RA");
167STATISTIC(
168 NumBotHeightReducePostRA,
169 "Number of scheduling units chosen for BotHeightReduce heuristic post-RA");
170STATISTIC(
171 NumBotPathReducePostRA,
172 "Number of scheduling units chosen for BotPathReduce heuristic post-RA");
173STATISTIC(NumNodeOrderPostRA,
174 "Number of scheduling units chosen for NodeOrder heuristic post-RA");
175STATISTIC(NumFirstValidPostRA,
176 "Number of scheduling units chosen for FirstValid heuristic post-RA");
177
178cl::opt<MISched::Direction> llvm::PreRADirection(
179 "misched-prera-direction", cl::Hidden,
180 cl::desc("Pre reg-alloc list scheduling direction"),
181 cl::init(Val: MISched::Unspecified),
182 cl::values(
183 clEnumValN(MISched::TopDown, "topdown",
184 "Force top-down pre reg-alloc list scheduling"),
185 clEnumValN(MISched::BottomUp, "bottomup",
186 "Force bottom-up pre reg-alloc list scheduling"),
187 clEnumValN(MISched::Bidirectional, "bidirectional",
188 "Force bidirectional pre reg-alloc list scheduling")));
189
190static cl::opt<MISched::Direction> PostRADirection(
191 "misched-postra-direction", cl::Hidden,
192 cl::desc("Post reg-alloc list scheduling direction"),
193 cl::init(Val: MISched::Unspecified),
194 cl::values(
195 clEnumValN(MISched::TopDown, "topdown",
196 "Force top-down post reg-alloc list scheduling"),
197 clEnumValN(MISched::BottomUp, "bottomup",
198 "Force bottom-up post reg-alloc list scheduling"),
199 clEnumValN(MISched::Bidirectional, "bidirectional",
200 "Force bidirectional post reg-alloc list scheduling")));
201
202static cl::opt<bool>
203 DumpCriticalPathLength("misched-dcpl", cl::Hidden,
204 cl::desc("Print critical path length to stdout"));
205
206cl::opt<bool> llvm::VerifyScheduling(
207 "verify-misched", cl::Hidden,
208 cl::desc("Verify machine instrs before and after machine scheduling"));
209
210#ifndef NDEBUG
211cl::opt<bool> llvm::ViewMISchedDAGs(
212 "view-misched-dags", cl::Hidden,
213 cl::desc("Pop up a window to show MISched dags after they are processed"));
214cl::opt<bool> llvm::PrintDAGs("misched-print-dags", cl::Hidden,
215 cl::desc("Print schedule DAGs"));
216static cl::opt<bool> MISchedDumpReservedCycles(
217 "misched-dump-reserved-cycles", cl::Hidden, cl::init(false),
218 cl::desc("Dump resource usage at schedule boundary."));
219static cl::opt<bool> MischedDetailResourceBooking(
220 "misched-detail-resource-booking", cl::Hidden, cl::init(false),
221 cl::desc("Show details of invoking getNextResoufceCycle."));
222#else
223const bool llvm::ViewMISchedDAGs = false;
224const bool llvm::PrintDAGs = false;
225static const bool MischedDetailResourceBooking = false;
226#ifdef LLVM_ENABLE_DUMP
227static const bool MISchedDumpReservedCycles = false;
228#endif // LLVM_ENABLE_DUMP
229#endif // NDEBUG
230
231#ifndef NDEBUG
232/// In some situations a few uninteresting nodes depend on nearly all other
233/// nodes in the graph, provide a cutoff to hide them.
234static cl::opt<unsigned> ViewMISchedCutoff("view-misched-cutoff", cl::Hidden,
235 cl::desc("Hide nodes with more predecessor/successor than cutoff"));
236
237static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden,
238 cl::desc("Stop scheduling after N instructions"), cl::init(~0U));
239
240static cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden,
241 cl::desc("Only schedule this function"));
242static cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden,
243 cl::desc("Only schedule this MBB#"));
244#endif // NDEBUG
245
246/// Avoid quadratic complexity in unusually large basic blocks by limiting the
247/// size of the ready lists.
248static cl::opt<unsigned> ReadyListLimit("misched-limit", cl::Hidden,
249 cl::desc("Limit ready list to N instructions"), cl::init(Val: 256));
250
251static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden,
252 cl::desc("Enable register pressure scheduling."), cl::init(Val: true));
253
254static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden,
255 cl::desc("Enable cyclic critical path analysis."), cl::init(Val: true));
256
257static cl::opt<bool> EnableMemOpCluster("misched-cluster", cl::Hidden,
258 cl::desc("Enable memop clustering."),
259 cl::init(Val: true));
260static cl::opt<bool>
261 ForceFastCluster("force-fast-cluster", cl::Hidden,
262 cl::desc("Switch to fast cluster algorithm with the lost "
263 "of some fusion opportunities"),
264 cl::init(Val: false));
265static cl::opt<unsigned>
266 FastClusterThreshold("fast-cluster-threshold", cl::Hidden,
267 cl::desc("The threshold for fast cluster"),
268 cl::init(Val: 1000));
269
270#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
271static cl::opt<bool> MISchedDumpScheduleTrace(
272 "misched-dump-schedule-trace", cl::Hidden, cl::init(false),
273 cl::desc("Dump resource usage at schedule boundary."));
274static cl::opt<unsigned>
275 HeaderColWidth("misched-dump-schedule-trace-col-header-width", cl::Hidden,
276 cl::desc("Set width of the columns with "
277 "the resources and schedule units"),
278 cl::init(19));
279static cl::opt<unsigned>
280 ColWidth("misched-dump-schedule-trace-col-width", cl::Hidden,
281 cl::desc("Set width of the columns showing resource booking."),
282 cl::init(5));
283static cl::opt<bool> MISchedSortResourcesInTrace(
284 "misched-sort-resources-in-trace", cl::Hidden, cl::init(true),
285 cl::desc("Sort the resources printed in the dump trace"));
286#endif
287
288static cl::opt<unsigned>
289 MIResourceCutOff("misched-resource-cutoff", cl::Hidden,
290 cl::desc("Number of intervals to track"), cl::init(Val: 10));
291
292// DAG subtrees must have at least this many nodes.
293static const unsigned MinSubtreeSize = 8;
294
295// Pin the vtables to this file.
296void MachineSchedStrategy::anchor() {}
297
298void ScheduleDAGMutation::anchor() {}
299
300//===----------------------------------------------------------------------===//
301// Machine Instruction Scheduling Pass and Registry
302//===----------------------------------------------------------------------===//
303
304MachineSchedContext::MachineSchedContext() = default;
305MachineSchedContext::~MachineSchedContext() = default;
306
307namespace llvm {
308namespace impl_detail {
309
310/// Base class for the machine scheduler classes.
311class MachineSchedulerBase : public MachineSchedContext {
312protected:
313 void scheduleRegions(ScheduleDAGInstrs &Scheduler, bool FixKillFlags);
314};
315
316/// Impl class for MachineScheduler.
317class MachineSchedulerImpl : public MachineSchedulerBase {
318 // These are only for using MF.verify()
319 // remove when verify supports passing in all analyses
320 MachineFunctionPass *P = nullptr;
321 MachineFunctionAnalysisManager *MFAM = nullptr;
322
323public:
324 struct RequiredAnalyses {
325 MachineLoopInfo &MLI;
326 AAResults &AA;
327 LiveIntervals &LIS;
328 RegisterClassInfo &RegClassInfo;
329 MachineBlockFrequencyInfo &MBFI;
330 };
331
332 MachineSchedulerImpl() = default;
333 // Migration only
334 void setLegacyPass(MachineFunctionPass *P) { this->P = P; }
335 void setMFAM(MachineFunctionAnalysisManager *MFAM) { this->MFAM = MFAM; }
336
337 bool run(MachineFunction &MF, const TargetMachine &TM,
338 const RequiredAnalyses &Analyses);
339
340protected:
341 ScheduleDAGInstrs *createMachineScheduler();
342};
343
344/// Impl class for PostMachineScheduler.
345class PostMachineSchedulerImpl : public MachineSchedulerBase {
346 // These are only for using MF.verify()
347 // remove when verify supports passing in all analyses
348 MachineFunctionPass *P = nullptr;
349 MachineFunctionAnalysisManager *MFAM = nullptr;
350
351public:
352 struct RequiredAnalyses {
353 MachineLoopInfo &MLI;
354 AAResults &AA;
355 };
356 PostMachineSchedulerImpl() = default;
357 // Migration only
358 void setLegacyPass(MachineFunctionPass *P) { this->P = P; }
359 void setMFAM(MachineFunctionAnalysisManager *MFAM) { this->MFAM = MFAM; }
360
361 bool run(MachineFunction &Func, const TargetMachine &TM,
362 const RequiredAnalyses &Analyses);
363
364protected:
365 ScheduleDAGInstrs *createPostMachineScheduler();
366};
367
368} // namespace impl_detail
369} // namespace llvm
370
371using impl_detail::MachineSchedulerBase;
372using impl_detail::MachineSchedulerImpl;
373using impl_detail::PostMachineSchedulerImpl;
374
375namespace {
376/// MachineScheduler runs after coalescing and before register allocation.
377class MachineSchedulerLegacy : public MachineFunctionPass {
378 MachineSchedulerImpl Impl;
379
380public:
381 MachineSchedulerLegacy();
382 void getAnalysisUsage(AnalysisUsage &AU) const override;
383 bool runOnMachineFunction(MachineFunction&) override;
384
385 static char ID; // Class identification, replacement for typeinfo
386};
387
388/// PostMachineScheduler runs after shortly before code emission.
389class PostMachineSchedulerLegacy : public MachineFunctionPass {
390 PostMachineSchedulerImpl Impl;
391
392public:
393 PostMachineSchedulerLegacy();
394 void getAnalysisUsage(AnalysisUsage &AU) const override;
395 bool runOnMachineFunction(MachineFunction &) override;
396
397 static char ID; // Class identification, replacement for typeinfo
398};
399
400} // end anonymous namespace
401
402char MachineSchedulerLegacy::ID = 0;
403
404char &llvm::MachineSchedulerID = MachineSchedulerLegacy::ID;
405
406INITIALIZE_PASS_BEGIN(MachineSchedulerLegacy, DEBUG_TYPE,
407 "Machine Instruction Scheduler", false, false)
408INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
409INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
410INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
411INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
412INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass);
413INITIALIZE_PASS_END(MachineSchedulerLegacy, DEBUG_TYPE,
414 "Machine Instruction Scheduler", false, false)
415
416MachineSchedulerLegacy::MachineSchedulerLegacy() : MachineFunctionPass(ID) {}
417
418void MachineSchedulerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
419 AU.setPreservesCFG();
420 AU.addRequired<MachineLoopInfoWrapperPass>();
421 AU.addRequired<AAResultsWrapperPass>();
422 AU.addRequired<TargetPassConfig>();
423 AU.addPreserved<SlotIndexesWrapperPass>();
424 AU.addRequired<LiveIntervalsWrapperPass>();
425 AU.addPreserved<LiveIntervalsWrapperPass>();
426 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
427 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
428 MachineFunctionPass::getAnalysisUsage(AU);
429}
430
431char PostMachineSchedulerLegacy::ID = 0;
432
433char &llvm::PostMachineSchedulerID = PostMachineSchedulerLegacy::ID;
434
435INITIALIZE_PASS_BEGIN(PostMachineSchedulerLegacy, "postmisched",
436 "PostRA Machine Instruction Scheduler", false, false)
437INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
438INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
439INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
440INITIALIZE_PASS_END(PostMachineSchedulerLegacy, "postmisched",
441 "PostRA Machine Instruction Scheduler", false, false)
442
443PostMachineSchedulerLegacy::PostMachineSchedulerLegacy()
444 : MachineFunctionPass(ID) {}
445
446void PostMachineSchedulerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
447 AU.setPreservesCFG();
448 AU.addRequired<MachineLoopInfoWrapperPass>();
449 AU.addRequired<AAResultsWrapperPass>();
450 AU.addRequired<TargetPassConfig>();
451 MachineFunctionPass::getAnalysisUsage(AU);
452}
453
454MachinePassRegistry<MachineSchedRegistry::ScheduleDAGCtor>
455 MachineSchedRegistry::Registry;
456
457/// A dummy default scheduler factory indicates whether the scheduler
458/// is overridden on the command line.
459static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) {
460 return nullptr;
461}
462
463/// MachineSchedOpt allows command line selection of the scheduler.
464static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,
465 RegisterPassParser<MachineSchedRegistry>>
466MachineSchedOpt("misched",
467 cl::init(Val: &useDefaultMachineSched), cl::Hidden,
468 cl::desc("Machine instruction scheduler to use"));
469
470static MachineSchedRegistry
471DefaultSchedRegistry("default", "Use the target's default scheduler choice.",
472 useDefaultMachineSched);
473
474static cl::opt<bool> EnableMachineSched(
475 "enable-misched",
476 cl::desc("Enable the machine instruction scheduling pass."), cl::init(Val: true),
477 cl::Hidden);
478
479static cl::opt<bool> EnablePostRAMachineSched(
480 "enable-post-misched",
481 cl::desc("Enable the post-ra machine instruction scheduling pass."),
482 cl::init(Val: true), cl::Hidden);
483
484/// Decrement this iterator until reaching the top or a non-debug instr.
485static MachineBasicBlock::const_iterator
486priorNonDebug(MachineBasicBlock::const_iterator I,
487 MachineBasicBlock::const_iterator Beg) {
488 assert(I != Beg && "reached the top of the region, cannot decrement");
489 while (--I != Beg) {
490 if (!I->isDebugOrPseudoInstr())
491 break;
492 }
493 return I;
494}
495
496/// Non-const version.
497static MachineBasicBlock::iterator
498priorNonDebug(MachineBasicBlock::iterator I,
499 MachineBasicBlock::const_iterator Beg) {
500 return priorNonDebug(I: MachineBasicBlock::const_iterator(I), Beg)
501 .getNonConstIterator();
502}
503
504/// If this iterator is a debug value, increment until reaching the End or a
505/// non-debug instruction.
506static MachineBasicBlock::const_iterator
507nextIfDebug(MachineBasicBlock::const_iterator I,
508 MachineBasicBlock::const_iterator End) {
509 for(; I != End; ++I) {
510 if (!I->isDebugOrPseudoInstr())
511 break;
512 }
513 return I;
514}
515
516/// Non-const version.
517static MachineBasicBlock::iterator
518nextIfDebug(MachineBasicBlock::iterator I,
519 MachineBasicBlock::const_iterator End) {
520 return nextIfDebug(I: MachineBasicBlock::const_iterator(I), End)
521 .getNonConstIterator();
522}
523
524/// Instantiate a ScheduleDAGInstrs that will be owned by the caller.
525ScheduleDAGInstrs *MachineSchedulerImpl::createMachineScheduler() {
526 // Select the scheduler, or set the default.
527 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;
528 if (Ctor != useDefaultMachineSched)
529 return Ctor(this);
530
531 // Get the default scheduler set by the target for this function.
532 ScheduleDAGInstrs *Scheduler = TM->createMachineScheduler(C: this);
533 if (Scheduler)
534 return Scheduler;
535
536 // Default to GenericScheduler.
537 return createSchedLive(C: this);
538}
539
540bool MachineSchedulerImpl::run(MachineFunction &Func, const TargetMachine &TM,
541 const RequiredAnalyses &Analyses) {
542 MF = &Func;
543 MLI = &Analyses.MLI;
544 this->TM = &TM;
545 AA = &Analyses.AA;
546 LIS = &Analyses.LIS;
547 RegClassInfo = &Analyses.RegClassInfo;
548 MBFI = &Analyses.MBFI;
549
550 if (VerifyScheduling) {
551 LLVM_DEBUG(LIS->dump());
552 const char *MSchedBanner = "Before machine scheduling.";
553 if (P)
554 MF->verify(p: P, Banner: MSchedBanner, OS: &errs());
555 else
556 MF->verify(MFAM&: *MFAM, Banner: MSchedBanner, OS: &errs());
557 }
558
559 // Instantiate the selected scheduler for this target, function, and
560 // optimization level.
561 std::unique_ptr<ScheduleDAGInstrs> Scheduler(createMachineScheduler());
562 scheduleRegions(Scheduler&: *Scheduler, FixKillFlags: false);
563
564 LLVM_DEBUG(LIS->dump());
565 if (VerifyScheduling) {
566 const char *MSchedBanner = "After machine scheduling.";
567 if (P)
568 MF->verify(p: P, Banner: MSchedBanner, OS: &errs());
569 else
570 MF->verify(MFAM&: *MFAM, Banner: MSchedBanner, OS: &errs());
571 }
572 return true;
573}
574
575/// Instantiate a ScheduleDAGInstrs for PostRA scheduling that will be owned by
576/// the caller. We don't have a command line option to override the postRA
577/// scheduler. The Target must configure it.
578ScheduleDAGInstrs *PostMachineSchedulerImpl::createPostMachineScheduler() {
579 // Get the postRA scheduler set by the target for this function.
580 ScheduleDAGInstrs *Scheduler = TM->createPostMachineScheduler(C: this);
581 if (Scheduler)
582 return Scheduler;
583
584 // Default to GenericScheduler.
585 return createSchedPostRA(C: this);
586}
587
588bool PostMachineSchedulerImpl::run(MachineFunction &Func,
589 const TargetMachine &TM,
590 const RequiredAnalyses &Analyses) {
591 MF = &Func;
592 MLI = &Analyses.MLI;
593 this->TM = &TM;
594 AA = &Analyses.AA;
595
596 if (VerifyScheduling) {
597 const char *PostMSchedBanner = "Before post machine scheduling.";
598 if (P)
599 MF->verify(p: P, Banner: PostMSchedBanner, OS: &errs());
600 else
601 MF->verify(MFAM&: *MFAM, Banner: PostMSchedBanner, OS: &errs());
602 }
603
604 // Instantiate the selected scheduler for this target, function, and
605 // optimization level.
606 std::unique_ptr<ScheduleDAGInstrs> Scheduler(createPostMachineScheduler());
607 scheduleRegions(Scheduler&: *Scheduler, FixKillFlags: true);
608
609 if (VerifyScheduling) {
610 const char *PostMSchedBanner = "After post machine scheduling.";
611 if (P)
612 MF->verify(p: P, Banner: PostMSchedBanner, OS: &errs());
613 else
614 MF->verify(MFAM&: *MFAM, Banner: PostMSchedBanner, OS: &errs());
615 }
616 return true;
617}
618
619/// Top-level MachineScheduler pass driver.
620///
621/// Visit blocks in function order. Divide each block into scheduling regions
622/// and visit them bottom-up. Visiting regions bottom-up is not required, but is
623/// consistent with the DAG builder, which traverses the interior of the
624/// scheduling regions bottom-up.
625///
626/// This design avoids exposing scheduling boundaries to the DAG builder,
627/// simplifying the DAG builder's support for "special" target instructions.
628/// At the same time the design allows target schedulers to operate across
629/// scheduling boundaries, for example to bundle the boundary instructions
630/// without reordering them. This creates complexity, because the target
631/// scheduler must update the RegionBegin and RegionEnd positions cached by
632/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler
633/// design would be to split blocks at scheduling boundaries, but LLVM has a
634/// general bias against block splitting purely for implementation simplicity.
635bool MachineSchedulerLegacy::runOnMachineFunction(MachineFunction &MF) {
636 if (skipFunction(F: MF.getFunction()))
637 return false;
638
639 if (EnableMachineSched.getNumOccurrences()) {
640 if (!EnableMachineSched)
641 return false;
642 } else if (!MF.getSubtarget().enableMachineScheduler()) {
643 return false;
644 }
645
646 LLVM_DEBUG(dbgs() << "Before MISched:\n"; MF.print(dbgs()));
647
648 auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
649 auto &TM = getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
650 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
651 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
652 auto &RegClassInfo =
653 getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
654 auto &MBFI = getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
655
656 Impl.setLegacyPass(this);
657 return Impl.run(Func&: MF, TM, Analyses: {.MLI: MLI, .AA: AA, .LIS: LIS, .RegClassInfo: RegClassInfo, .MBFI: MBFI});
658}
659
660MachineSchedulerPass::MachineSchedulerPass(const TargetMachine *TM)
661 : Impl(std::make_unique<MachineSchedulerImpl>()), TM(TM) {}
662MachineSchedulerPass::~MachineSchedulerPass() = default;
663MachineSchedulerPass::MachineSchedulerPass(MachineSchedulerPass &&Other) =
664 default;
665
666PostMachineSchedulerPass::PostMachineSchedulerPass(const TargetMachine *TM)
667 : Impl(std::make_unique<PostMachineSchedulerImpl>()), TM(TM) {}
668PostMachineSchedulerPass::PostMachineSchedulerPass(
669 PostMachineSchedulerPass &&Other) = default;
670PostMachineSchedulerPass::~PostMachineSchedulerPass() = default;
671
672PreservedAnalyses
673MachineSchedulerPass::run(MachineFunction &MF,
674 MachineFunctionAnalysisManager &MFAM) {
675 if (EnableMachineSched.getNumOccurrences()) {
676 if (!EnableMachineSched)
677 return PreservedAnalyses::all();
678 } else if (!MF.getSubtarget().enableMachineScheduler()) {
679 return PreservedAnalyses::all();
680 }
681
682 LLVM_DEBUG(dbgs() << "Before MISched:\n"; MF.print(dbgs()));
683 auto &MLI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
684 auto &FAM = MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
685 .getManager();
686 auto &AA = FAM.getResult<AAManager>(IR&: MF.getFunction());
687 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
688 auto &RegClassInfo = MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
689 auto &MBFI = MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
690
691 Impl->setMFAM(&MFAM);
692 bool Changed = Impl->run(Func&: MF, TM: *TM, Analyses: {.MLI: MLI, .AA: AA, .LIS: LIS, .RegClassInfo: RegClassInfo, .MBFI: MBFI});
693 if (!Changed)
694 return PreservedAnalyses::all();
695
696 return getMachineFunctionPassPreservedAnalyses()
697 .preserveSet<CFGAnalyses>()
698 .preserve<SlotIndexesAnalysis>()
699 .preserve<LiveIntervalsAnalysis>();
700}
701
702bool PostMachineSchedulerLegacy::runOnMachineFunction(MachineFunction &MF) {
703 if (skipFunction(F: MF.getFunction()))
704 return false;
705
706 if (EnablePostRAMachineSched.getNumOccurrences()) {
707 if (!EnablePostRAMachineSched)
708 return false;
709 } else if (!MF.getSubtarget().enablePostRAMachineScheduler()) {
710 LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
711 return false;
712 }
713 LLVM_DEBUG(dbgs() << "Before post-MI-sched:\n"; MF.print(dbgs()));
714 auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
715 auto &TM = getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
716 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
717 Impl.setLegacyPass(this);
718 return Impl.run(Func&: MF, TM, Analyses: {.MLI: MLI, .AA: AA});
719}
720
721PreservedAnalyses
722PostMachineSchedulerPass::run(MachineFunction &MF,
723 MachineFunctionAnalysisManager &MFAM) {
724 if (EnablePostRAMachineSched.getNumOccurrences()) {
725 if (!EnablePostRAMachineSched)
726 return PreservedAnalyses::all();
727 } else if (!MF.getSubtarget().enablePostRAMachineScheduler()) {
728 LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
729 return PreservedAnalyses::all();
730 }
731 LLVM_DEBUG(dbgs() << "Before post-MI-sched:\n"; MF.print(dbgs()));
732 auto &MLI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
733 auto &FAM = MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
734 .getManager();
735 auto &AA = FAM.getResult<AAManager>(IR&: MF.getFunction());
736
737 Impl->setMFAM(&MFAM);
738 bool Changed = Impl->run(Func&: MF, TM: *TM, Analyses: {.MLI: MLI, .AA: AA});
739 if (!Changed)
740 return PreservedAnalyses::all();
741
742 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
743 PA.preserveSet<CFGAnalyses>();
744 return PA;
745}
746
747/// Return true of the given instruction should not be included in a scheduling
748/// region.
749///
750/// MachineScheduler does not currently support scheduling across calls. To
751/// handle calls, the DAG builder needs to be modified to create register
752/// anti/output dependencies on the registers clobbered by the call's regmask
753/// operand. In PreRA scheduling, the stack pointer adjustment already prevents
754/// scheduling across calls. In PostRA scheduling, we need the isCall to enforce
755/// the boundary, but there would be no benefit to postRA scheduling across
756/// calls this late anyway.
757static bool isSchedBoundary(MachineBasicBlock::iterator MI,
758 MachineBasicBlock *MBB,
759 MachineFunction *MF,
760 const TargetInstrInfo *TII) {
761 return MI->isCall() || TII->isSchedulingBoundary(MI: *MI, MBB, MF: *MF) ||
762 MI->isFakeUse();
763}
764
765using MBBRegionsVector = SmallVector<SchedRegion, 16>;
766
767static void
768getSchedRegions(MachineBasicBlock *MBB,
769 MBBRegionsVector &Regions,
770 bool RegionsTopDown) {
771 MachineFunction *MF = MBB->getParent();
772 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
773
774 MachineBasicBlock::iterator I = nullptr;
775 for(MachineBasicBlock::iterator RegionEnd = MBB->end();
776 RegionEnd != MBB->begin(); RegionEnd = I) {
777
778 // Avoid decrementing RegionEnd for blocks with no terminator.
779 if (RegionEnd != MBB->end() ||
780 isSchedBoundary(MI: &*std::prev(x: RegionEnd), MBB: &*MBB, MF, TII)) {
781 --RegionEnd;
782 }
783
784 // The next region starts above the previous region. Look backward in the
785 // instruction stream until we find the nearest boundary.
786 unsigned NumRegionInstrs = 0;
787 I = RegionEnd;
788 for (;I != MBB->begin(); --I) {
789 MachineInstr &MI = *std::prev(x: I);
790 if (isSchedBoundary(MI: &MI, MBB: &*MBB, MF, TII))
791 break;
792 if (!MI.isDebugOrPseudoInstr()) {
793 // MBB::size() uses instr_iterator to count. Here we need a bundle to
794 // count as a single instruction.
795 ++NumRegionInstrs;
796 }
797 }
798
799 // It's possible we found a scheduling region that only has debug
800 // instructions. Don't bother scheduling these.
801 if (NumRegionInstrs != 0)
802 Regions.push_back(Elt: SchedRegion(I, RegionEnd, NumRegionInstrs));
803 }
804
805 if (RegionsTopDown)
806 std::reverse(first: Regions.begin(), last: Regions.end());
807}
808
809/// Main driver for both MachineScheduler and PostMachineScheduler.
810void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler,
811 bool FixKillFlags) {
812 // Visit all machine basic blocks.
813 //
814 // TODO: Visit blocks in global postorder or postorder within the bottom-up
815 // loop tree. Then we can optionally compute global RegPressure.
816 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
817 MBB != MBBEnd; ++MBB) {
818
819 Scheduler.startBlock(BB: &*MBB);
820
821#ifndef NDEBUG
822 if (SchedOnlyFunc.getNumOccurrences() && SchedOnlyFunc != MF->getName())
823 continue;
824 if (SchedOnlyBlock.getNumOccurrences()
825 && (int)SchedOnlyBlock != MBB->getNumber())
826 continue;
827#endif
828
829 // Break the block into scheduling regions [I, RegionEnd). RegionEnd
830 // points to the scheduling boundary at the bottom of the region. The DAG
831 // does not include RegionEnd, but the region does (i.e. the next
832 // RegionEnd is above the previous RegionBegin). If the current block has
833 // no terminator then RegionEnd == MBB->end() for the bottom region.
834 //
835 // All the regions of MBB are first found and stored in MBBRegions, which
836 // will be processed (MBB) top-down if initialized with true.
837 //
838 // The Scheduler may insert instructions during either schedule() or
839 // exitRegion(), even for empty regions. So the local iterators 'I' and
840 // 'RegionEnd' are invalid across these calls. Instructions must not be
841 // added to other regions than the current one without updating MBBRegions.
842
843 MBBRegionsVector MBBRegions;
844 getSchedRegions(MBB: &*MBB, Regions&: MBBRegions, RegionsTopDown: Scheduler.doMBBSchedRegionsTopDown());
845 bool ScheduleSingleMI = Scheduler.shouldScheduleSingleMIRegions();
846 for (const SchedRegion &R : MBBRegions) {
847 MachineBasicBlock::iterator I = R.RegionBegin;
848 MachineBasicBlock::iterator RegionEnd = R.RegionEnd;
849 unsigned NumRegionInstrs = R.NumRegionInstrs;
850
851 // Notify the scheduler of the region, even if we may skip scheduling
852 // it. Perhaps it still needs to be bundled.
853 Scheduler.enterRegion(bb: &*MBB, begin: I, end: RegionEnd, regioninstrs: NumRegionInstrs);
854
855 // Skip empty scheduling regions and, conditionally, regions with a single
856 // MI.
857 if (I == RegionEnd || (!ScheduleSingleMI && I == std::prev(x: RegionEnd))) {
858 // Close the current region. Bundle the terminator if needed.
859 // This invalidates 'RegionEnd' and 'I'.
860 Scheduler.exitRegion();
861 continue;
862 }
863 auto DumpRegionHeader = [&] {
864 dbgs() << "Current Schedule Region\n";
865 dbgs() << MF->getName() << ":" << printMBBReference(MBB: *MBB) << " "
866 << MBB->getName() << "\n From: " << *I << " To: ";
867 if (RegionEnd != MBB->end())
868 dbgs() << *RegionEnd;
869 else
870 dbgs() << "End\n";
871 dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n';
872 };
873 if (PrintDAGs)
874 DumpRegionHeader();
875 else
876 LLVM_DEBUG(DumpRegionHeader());
877 if (DumpCriticalPathLength) {
878 errs() << MF->getName();
879 errs() << ":%bb. " << MBB->getNumber();
880 errs() << " " << MBB->getName() << " \n";
881 }
882
883 // Schedule a region: possibly reorder instructions.
884 // This invalidates the original region iterators.
885 Scheduler.schedule();
886
887 // Close the current region.
888 Scheduler.exitRegion();
889 }
890 Scheduler.finishBlock();
891 // FIXME: Ideally, no further passes should rely on kill flags. However,
892 // thumb2 size reduction is currently an exception, so the PostMIScheduler
893 // needs to do this.
894 if (FixKillFlags)
895 Scheduler.fixupKills(MBB&: *MBB);
896 }
897 Scheduler.finalizeSchedule();
898}
899
900#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
901LLVM_DUMP_METHOD void ReadyQueue::dump() const {
902 dbgs() << "Queue " << Name << ": ";
903 for (const SUnit *SU : Queue)
904 dbgs() << SU->NodeNum << " ";
905 dbgs() << "\n";
906}
907#endif
908
909//===----------------------------------------------------------------------===//
910// ScheduleDAGMI - Basic machine instruction scheduling. This is
911// independent of PreRA/PostRA scheduling and involves no extra book-keeping for
912// virtual registers.
913// ===----------------------------------------------------------------------===/
914
915// Provide a vtable anchor.
916ScheduleDAGMI::~ScheduleDAGMI() = default;
917
918/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When
919/// NumPredsLeft reaches zero, release the successor node.
920///
921/// FIXME: Adjust SuccSU height based on MinLatency.
922void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
923 SUnit *SuccSU = SuccEdge->getSUnit();
924
925 if (SuccEdge->isWeak()) {
926 --SuccSU->WeakPredsLeft;
927 return;
928 }
929#ifndef NDEBUG
930 if (SuccSU->NumPredsLeft == 0) {
931 dbgs() << "*** Scheduling failed! ***\n";
932 dumpNode(*SuccSU);
933 dbgs() << " has been released too many times!\n";
934 llvm_unreachable(nullptr);
935 }
936#endif
937 // SU->TopReadyCycle was set to CurrCycle when it was scheduled. However,
938 // CurrCycle may have advanced since then.
939 if (SuccSU->TopReadyCycle < SU->TopReadyCycle + SuccEdge->getLatency())
940 SuccSU->TopReadyCycle = SU->TopReadyCycle + SuccEdge->getLatency();
941
942 --SuccSU->NumPredsLeft;
943 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
944 SchedImpl->releaseTopNode(SU: SuccSU);
945}
946
947/// releaseSuccessors - Call releaseSucc on each of SU's successors.
948void ScheduleDAGMI::releaseSuccessors(SUnit *SU) {
949 for (SDep &Succ : SU->Succs)
950 releaseSucc(SU, SuccEdge: &Succ);
951}
952
953/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When
954/// NumSuccsLeft reaches zero, release the predecessor node.
955///
956/// FIXME: Adjust PredSU height based on MinLatency.
957void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {
958 SUnit *PredSU = PredEdge->getSUnit();
959
960 if (PredEdge->isWeak()) {
961 --PredSU->WeakSuccsLeft;
962 return;
963 }
964#ifndef NDEBUG
965 if (PredSU->NumSuccsLeft == 0) {
966 dbgs() << "*** Scheduling failed! ***\n";
967 dumpNode(*PredSU);
968 dbgs() << " has been released too many times!\n";
969 llvm_unreachable(nullptr);
970 }
971#endif
972 // SU->BotReadyCycle was set to CurrCycle when it was scheduled. However,
973 // CurrCycle may have advanced since then.
974 if (PredSU->BotReadyCycle < SU->BotReadyCycle + PredEdge->getLatency())
975 PredSU->BotReadyCycle = SU->BotReadyCycle + PredEdge->getLatency();
976
977 --PredSU->NumSuccsLeft;
978 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
979 SchedImpl->releaseBottomNode(SU: PredSU);
980}
981
982/// releasePredecessors - Call releasePred on each of SU's predecessors.
983void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
984 for (SDep &Pred : SU->Preds)
985 releasePred(SU, PredEdge: &Pred);
986}
987
988void ScheduleDAGMI::startBlock(MachineBasicBlock *bb) {
989 ScheduleDAGInstrs::startBlock(BB: bb);
990 SchedImpl->enterMBB(MBB: bb);
991}
992
993void ScheduleDAGMI::finishBlock() {
994 SchedImpl->leaveMBB();
995 ScheduleDAGInstrs::finishBlock();
996}
997
998/// enterRegion - Called back from PostMachineScheduler::runOnMachineFunction
999/// after crossing a scheduling boundary. [begin, end) includes all instructions
1000/// in the region, including the boundary itself and single-instruction regions
1001/// that don't get scheduled.
1002void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,
1003 MachineBasicBlock::iterator begin,
1004 MachineBasicBlock::iterator end,
1005 unsigned regioninstrs)
1006{
1007 ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
1008
1009 SchedImpl->initPolicy(Begin: begin, End: end, NumRegionInstrs: regioninstrs);
1010
1011 // Set dump direction after initializing sched policy.
1012 ScheduleDAGMI::DumpDirection D;
1013 if (SchedImpl->getPolicy().OnlyTopDown)
1014 D = ScheduleDAGMI::DumpDirection::TopDown;
1015 else if (SchedImpl->getPolicy().OnlyBottomUp)
1016 D = ScheduleDAGMI::DumpDirection::BottomUp;
1017 else
1018 D = ScheduleDAGMI::DumpDirection::Bidirectional;
1019 setDumpDirection(D);
1020}
1021
1022/// This is normally called from the main scheduler loop but may also be invoked
1023/// by the scheduling strategy to perform additional code motion.
1024void ScheduleDAGMI::moveInstruction(
1025 MachineInstr *MI, MachineBasicBlock::iterator InsertPos) {
1026 // Advance RegionBegin if the first instruction moves down.
1027 if (&*RegionBegin == MI)
1028 ++RegionBegin;
1029
1030 // Update the instruction stream.
1031 BB->splice(Where: InsertPos, Other: BB, From: MI);
1032
1033 // Update LiveIntervals
1034 if (LIS)
1035 LIS->handleMove(MI&: *MI, /*UpdateFlags=*/true);
1036
1037 // Recede RegionBegin if an instruction moves above the first.
1038 if (RegionBegin == InsertPos)
1039 RegionBegin = MI;
1040}
1041
1042bool ScheduleDAGMI::checkSchedLimit() {
1043#if LLVM_ENABLE_ABI_BREAKING_CHECKS && !defined(NDEBUG)
1044 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
1045 CurrentTop = CurrentBottom;
1046 return false;
1047 }
1048 ++NumInstrsScheduled;
1049#endif
1050 return true;
1051}
1052
1053/// Per-region scheduling driver, called back from
1054/// PostMachineScheduler::runOnMachineFunction. This is a simplified driver
1055/// that does not consider liveness or register pressure. It is useful for
1056/// PostRA scheduling and potentially other custom schedulers.
1057void ScheduleDAGMI::schedule() {
1058 LLVM_DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n");
1059 LLVM_DEBUG(SchedImpl->dumpPolicy());
1060
1061 // Build the DAG.
1062 buildSchedGraph(AA);
1063
1064 postProcessDAG();
1065
1066 SmallVector<SUnit*, 8> TopRoots, BotRoots;
1067 findRootsAndBiasEdges(TopRoots, BotRoots);
1068
1069 LLVM_DEBUG(dump());
1070 if (PrintDAGs) dump();
1071 if (ViewMISchedDAGs) viewGraph();
1072
1073 // Initialize the strategy before modifying the DAG.
1074 // This may initialize a DFSResult to be used for queue priority.
1075 SchedImpl->initialize(DAG: this);
1076
1077 // Initialize ready queues now that the DAG and priority data are finalized.
1078 initQueues(TopRoots, BotRoots);
1079
1080 bool IsTopNode = false;
1081 while (true) {
1082 if (!checkSchedLimit())
1083 break;
1084
1085 LLVM_DEBUG(dbgs() << "** ScheduleDAGMI::schedule picking next node\n");
1086 SUnit *SU = SchedImpl->pickNode(IsTopNode);
1087 if (!SU) break;
1088
1089 assert(!SU->isScheduled && "Node already scheduled");
1090
1091 MachineInstr *MI = SU->getInstr();
1092 if (IsTopNode) {
1093 assert(SU->isTopReady() && "node still has unscheduled dependencies");
1094 if (&*CurrentTop == MI)
1095 CurrentTop = nextIfDebug(I: ++CurrentTop, End: CurrentBottom);
1096 else
1097 moveInstruction(MI, InsertPos: CurrentTop);
1098 } else {
1099 assert(SU->isBottomReady() && "node still has unscheduled dependencies");
1100 MachineBasicBlock::iterator priorII =
1101 priorNonDebug(I: CurrentBottom, Beg: CurrentTop);
1102 if (&*priorII == MI)
1103 CurrentBottom = priorII;
1104 else {
1105 if (&*CurrentTop == MI)
1106 CurrentTop = nextIfDebug(I: ++CurrentTop, End: priorII);
1107 moveInstruction(MI, InsertPos: CurrentBottom);
1108 CurrentBottom = MI;
1109 }
1110 }
1111 // Notify the scheduling strategy before updating the DAG.
1112 // This sets the scheduled node's ReadyCycle to CurrCycle. When updateQueues
1113 // runs, it can then use the accurate ReadyCycle time to determine whether
1114 // newly released nodes can move to the readyQ.
1115 SchedImpl->schedNode(SU, IsTopNode);
1116
1117 updateQueues(SU, IsTopNode);
1118 }
1119 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
1120
1121 placeDebugValues();
1122
1123 LLVM_DEBUG({
1124 dbgs() << "*** Final schedule for "
1125 << printMBBReference(*begin()->getParent()) << " ***\n";
1126 dumpSchedule();
1127 dbgs() << '\n';
1128 });
1129}
1130
1131/// Apply each ScheduleDAGMutation step in order.
1132void ScheduleDAGMI::postProcessDAG() {
1133 for (auto &m : Mutations)
1134 m->apply(DAG: this);
1135}
1136
1137void ScheduleDAGMI::
1138findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
1139 SmallVectorImpl<SUnit*> &BotRoots) {
1140 for (SUnit &SU : SUnits) {
1141 assert(!SU.isBoundaryNode() && "Boundary node should not be in SUnits");
1142
1143 // Order predecessors so DFSResult follows the critical path.
1144 SU.biasCriticalPath();
1145
1146 // A SUnit is ready to top schedule if it has no predecessors.
1147 if (!SU.NumPredsLeft)
1148 TopRoots.push_back(Elt: &SU);
1149 // A SUnit is ready to bottom schedule if it has no successors.
1150 if (!SU.NumSuccsLeft)
1151 BotRoots.push_back(Elt: &SU);
1152 }
1153 ExitSU.biasCriticalPath();
1154}
1155
1156/// Identify DAG roots and setup scheduler queues.
1157void ScheduleDAGMI::initQueues(ArrayRef<SUnit *> TopRoots,
1158 ArrayRef<SUnit *> BotRoots) {
1159 // Release all DAG roots for scheduling, not including EntrySU/ExitSU.
1160 //
1161 // Nodes with unreleased weak edges can still be roots.
1162 // Release top roots in forward order.
1163 for (SUnit *SU : TopRoots)
1164 SchedImpl->releaseTopNode(SU);
1165
1166 // Release bottom roots in reverse order so the higher priority nodes appear
1167 // first. This is more natural and slightly more efficient.
1168 for (SmallVectorImpl<SUnit*>::const_reverse_iterator
1169 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) {
1170 SchedImpl->releaseBottomNode(SU: *I);
1171 }
1172
1173 releaseSuccessors(SU: &EntrySU);
1174 releasePredecessors(SU: &ExitSU);
1175
1176 SchedImpl->registerRoots();
1177
1178 // Advance past initial DebugValues.
1179 CurrentTop = nextIfDebug(I: RegionBegin, End: RegionEnd);
1180 CurrentBottom = RegionEnd;
1181}
1182
1183/// Update scheduler queues after scheduling an instruction.
1184void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) {
1185 // Release dependent instructions for scheduling.
1186 if (IsTopNode)
1187 releaseSuccessors(SU);
1188 else
1189 releasePredecessors(SU);
1190
1191 SU->isScheduled = true;
1192}
1193
1194/// Reinsert any remaining debug_values, just like the PostRA scheduler.
1195void ScheduleDAGMI::placeDebugValues() {
1196 // If first instruction was a DBG_VALUE then put it back.
1197 if (FirstDbgValue) {
1198 BB->splice(Where: RegionBegin, Other: BB, From: FirstDbgValue);
1199 RegionBegin = FirstDbgValue;
1200 }
1201
1202 for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator
1203 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
1204 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(x: DI);
1205 MachineInstr *DbgValue = P.first;
1206 MachineBasicBlock::iterator OrigPrevMI = P.second;
1207 if (&*RegionBegin == DbgValue)
1208 ++RegionBegin;
1209 BB->splice(Where: std::next(x: OrigPrevMI), Other: BB, From: DbgValue);
1210 if (RegionEnd != BB->end() && OrigPrevMI == &*RegionEnd)
1211 RegionEnd = DbgValue;
1212 }
1213}
1214
1215#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1216static const char *scheduleTableLegend = " i: issue\n x: resource booked";
1217
1218LLVM_DUMP_METHOD void ScheduleDAGMI::dumpScheduleTraceTopDown() const {
1219 // Bail off when there is no schedule model to query.
1220 if (!SchedModel.hasInstrSchedModel())
1221 return;
1222
1223 // Nothing to show if there is no or just one instruction.
1224 if (BB->size() < 2)
1225 return;
1226
1227 dbgs() << " * Schedule table (TopDown):\n";
1228 dbgs() << scheduleTableLegend << "\n";
1229 const unsigned FirstCycle = getSUnit(&*(std::begin(*this)))->TopReadyCycle;
1230 unsigned LastCycle = getSUnit(&*(std::prev(std::end(*this))))->TopReadyCycle;
1231 for (MachineInstr &MI : *this) {
1232 SUnit *SU = getSUnit(&MI);
1233 if (!SU)
1234 continue;
1235 const MCSchedClassDesc *SC = getSchedClass(SU);
1236 for (TargetSchedModel::ProcResIter PI = SchedModel.getWriteProcResBegin(SC),
1237 PE = SchedModel.getWriteProcResEnd(SC);
1238 PI != PE; ++PI) {
1239 if (SU->TopReadyCycle + PI->ReleaseAtCycle - 1 > LastCycle)
1240 LastCycle = SU->TopReadyCycle + PI->ReleaseAtCycle - 1;
1241 }
1242 }
1243 // Print the header with the cycles
1244 dbgs() << llvm::left_justify("Cycle", HeaderColWidth);
1245 for (unsigned C = FirstCycle; C <= LastCycle; ++C)
1246 dbgs() << llvm::left_justify("| " + std::to_string(C), ColWidth);
1247 dbgs() << "|\n";
1248
1249 for (MachineInstr &MI : *this) {
1250 SUnit *SU = getSUnit(&MI);
1251 if (!SU) {
1252 dbgs() << "Missing SUnit\n";
1253 continue;
1254 }
1255 std::string NodeName("SU(");
1256 NodeName += std::to_string(SU->NodeNum) + ")";
1257 dbgs() << llvm::left_justify(NodeName, HeaderColWidth);
1258 unsigned C = FirstCycle;
1259 for (; C <= LastCycle; ++C) {
1260 if (C == SU->TopReadyCycle)
1261 dbgs() << llvm::left_justify("| i", ColWidth);
1262 else
1263 dbgs() << llvm::left_justify("|", ColWidth);
1264 }
1265 dbgs() << "|\n";
1266 const MCSchedClassDesc *SC = getSchedClass(SU);
1267
1268 SmallVector<MCWriteProcResEntry, 4> ResourcesIt(
1269 make_range(SchedModel.getWriteProcResBegin(SC),
1270 SchedModel.getWriteProcResEnd(SC)));
1271
1272 if (MISchedSortResourcesInTrace)
1273 llvm::stable_sort(
1274 ResourcesIt,
1275 [](const MCWriteProcResEntry &LHS,
1276 const MCWriteProcResEntry &RHS) -> bool {
1277 return std::tie(LHS.AcquireAtCycle, LHS.ReleaseAtCycle) <
1278 std::tie(RHS.AcquireAtCycle, RHS.ReleaseAtCycle);
1279 });
1280 for (const MCWriteProcResEntry &PI : ResourcesIt) {
1281 C = FirstCycle;
1282 const std::string ResName =
1283 SchedModel.getResourceName(PI.ProcResourceIdx);
1284 dbgs() << llvm::right_justify(ResName + " ", HeaderColWidth);
1285 for (; C < SU->TopReadyCycle + PI.AcquireAtCycle; ++C) {
1286 dbgs() << llvm::left_justify("|", ColWidth);
1287 }
1288 for (unsigned I = 0, E = PI.ReleaseAtCycle - PI.AcquireAtCycle; I != E;
1289 ++I, ++C)
1290 dbgs() << llvm::left_justify("| x", ColWidth);
1291 while (C++ <= LastCycle)
1292 dbgs() << llvm::left_justify("|", ColWidth);
1293 // Place end char
1294 dbgs() << "| \n";
1295 }
1296 }
1297}
1298
1299LLVM_DUMP_METHOD void ScheduleDAGMI::dumpScheduleTraceBottomUp() const {
1300 // Bail off when there is no schedule model to query.
1301 if (!SchedModel.hasInstrSchedModel())
1302 return;
1303
1304 // Nothing to show if there is no or just one instruction.
1305 if (BB->size() < 2)
1306 return;
1307
1308 dbgs() << " * Schedule table (BottomUp):\n";
1309 dbgs() << scheduleTableLegend << "\n";
1310
1311 const int FirstCycle = getSUnit(&*(std::begin(*this)))->BotReadyCycle;
1312 int LastCycle = getSUnit(&*(std::prev(std::end(*this))))->BotReadyCycle;
1313 for (MachineInstr &MI : *this) {
1314 SUnit *SU = getSUnit(&MI);
1315 if (!SU)
1316 continue;
1317 const MCSchedClassDesc *SC = getSchedClass(SU);
1318 for (TargetSchedModel::ProcResIter PI = SchedModel.getWriteProcResBegin(SC),
1319 PE = SchedModel.getWriteProcResEnd(SC);
1320 PI != PE; ++PI) {
1321 if ((int)SU->BotReadyCycle - PI->ReleaseAtCycle + 1 < LastCycle)
1322 LastCycle = (int)SU->BotReadyCycle - PI->ReleaseAtCycle + 1;
1323 }
1324 }
1325 // Print the header with the cycles
1326 dbgs() << llvm::left_justify("Cycle", HeaderColWidth);
1327 for (int C = FirstCycle; C >= LastCycle; --C)
1328 dbgs() << llvm::left_justify("| " + std::to_string(C), ColWidth);
1329 dbgs() << "|\n";
1330
1331 for (MachineInstr &MI : *this) {
1332 SUnit *SU = getSUnit(&MI);
1333 if (!SU) {
1334 dbgs() << "Missing SUnit\n";
1335 continue;
1336 }
1337 std::string NodeName("SU(");
1338 NodeName += std::to_string(SU->NodeNum) + ")";
1339 dbgs() << llvm::left_justify(NodeName, HeaderColWidth);
1340 int C = FirstCycle;
1341 for (; C >= LastCycle; --C) {
1342 if (C == (int)SU->BotReadyCycle)
1343 dbgs() << llvm::left_justify("| i", ColWidth);
1344 else
1345 dbgs() << llvm::left_justify("|", ColWidth);
1346 }
1347 dbgs() << "|\n";
1348 const MCSchedClassDesc *SC = getSchedClass(SU);
1349 SmallVector<MCWriteProcResEntry, 4> ResourcesIt(
1350 make_range(SchedModel.getWriteProcResBegin(SC),
1351 SchedModel.getWriteProcResEnd(SC)));
1352
1353 if (MISchedSortResourcesInTrace)
1354 llvm::stable_sort(
1355 ResourcesIt,
1356 [](const MCWriteProcResEntry &LHS,
1357 const MCWriteProcResEntry &RHS) -> bool {
1358 return std::tie(LHS.AcquireAtCycle, LHS.ReleaseAtCycle) <
1359 std::tie(RHS.AcquireAtCycle, RHS.ReleaseAtCycle);
1360 });
1361 for (const MCWriteProcResEntry &PI : ResourcesIt) {
1362 C = FirstCycle;
1363 const std::string ResName =
1364 SchedModel.getResourceName(PI.ProcResourceIdx);
1365 dbgs() << llvm::right_justify(ResName + " ", HeaderColWidth);
1366 for (; C > ((int)SU->BotReadyCycle - (int)PI.AcquireAtCycle); --C) {
1367 dbgs() << llvm::left_justify("|", ColWidth);
1368 }
1369 for (unsigned I = 0, E = PI.ReleaseAtCycle - PI.AcquireAtCycle; I != E;
1370 ++I, --C)
1371 dbgs() << llvm::left_justify("| x", ColWidth);
1372 while (C-- >= LastCycle)
1373 dbgs() << llvm::left_justify("|", ColWidth);
1374 // Place end char
1375 dbgs() << "| \n";
1376 }
1377 }
1378}
1379#endif
1380
1381#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1382LLVM_DUMP_METHOD void ScheduleDAGMI::dumpSchedule() const {
1383 if (MISchedDumpScheduleTrace) {
1384 if (DumpDir == DumpDirection::TopDown)
1385 dumpScheduleTraceTopDown();
1386 else if (DumpDir == DumpDirection::BottomUp)
1387 dumpScheduleTraceBottomUp();
1388 else if (DumpDir == DumpDirection::Bidirectional) {
1389 dbgs() << "* Schedule table (Bidirectional): not implemented\n";
1390 } else {
1391 dbgs() << "* Schedule table: DumpDirection not set.\n";
1392 }
1393 }
1394
1395 for (MachineInstr &MI : *this) {
1396 if (SUnit *SU = getSUnit(&MI))
1397 dumpNode(*SU);
1398 else
1399 dbgs() << "Missing SUnit\n";
1400 }
1401}
1402#endif
1403
1404//===----------------------------------------------------------------------===//
1405// ScheduleDAGMILive - Base class for MachineInstr scheduling with LiveIntervals
1406// preservation.
1407//===----------------------------------------------------------------------===//
1408
1409ScheduleDAGMILive::~ScheduleDAGMILive() {
1410 delete DFSResult;
1411}
1412
1413void ScheduleDAGMILive::collectVRegUses(SUnit &SU) {
1414 const MachineInstr &MI = *SU.getInstr();
1415 for (const MachineOperand &MO : MI.operands()) {
1416 if (!MO.isReg())
1417 continue;
1418 if (!MO.readsReg())
1419 continue;
1420 if (TrackLaneMasks && !MO.isUse())
1421 continue;
1422
1423 Register Reg = MO.getReg();
1424 if (!Reg.isVirtual())
1425 continue;
1426
1427 // Ignore re-defs.
1428 if (TrackLaneMasks) {
1429 bool FoundDef = false;
1430 for (const MachineOperand &MO2 : MI.all_defs()) {
1431 if (MO2.getReg() == Reg && !MO2.isDead()) {
1432 FoundDef = true;
1433 break;
1434 }
1435 }
1436 if (FoundDef)
1437 continue;
1438 }
1439
1440 // Record this local VReg use.
1441 VReg2SUnitMultiMap::iterator UI = VRegUses.find(Key: Reg);
1442 for (; UI != VRegUses.end(); ++UI) {
1443 if (UI->SU == &SU)
1444 break;
1445 }
1446 if (UI == VRegUses.end())
1447 VRegUses.insert(Val: VReg2SUnit(Reg, LaneBitmask::getNone(), &SU));
1448 }
1449}
1450
1451/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
1452/// crossing a scheduling boundary. [begin, end) includes all instructions in
1453/// the region, including the boundary itself and single-instruction regions
1454/// that don't get scheduled.
1455void ScheduleDAGMILive::enterRegion(MachineBasicBlock *bb,
1456 MachineBasicBlock::iterator begin,
1457 MachineBasicBlock::iterator end,
1458 unsigned regioninstrs)
1459{
1460 // ScheduleDAGMI initializes SchedImpl's per-region policy.
1461 ScheduleDAGMI::enterRegion(bb, begin, end, regioninstrs);
1462
1463 // For convenience remember the end of the liveness region.
1464 LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(x: RegionEnd);
1465
1466 SUPressureDiffs.clear();
1467
1468 ShouldTrackPressure = SchedImpl->shouldTrackPressure();
1469 ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks();
1470
1471 assert((!ShouldTrackLaneMasks || ShouldTrackPressure) &&
1472 "ShouldTrackLaneMasks requires ShouldTrackPressure");
1473}
1474
1475// Setup the register pressure trackers for the top scheduled and bottom
1476// scheduled regions.
1477void ScheduleDAGMILive::initRegPressure() {
1478 VRegUses.clear();
1479 VRegUses.setUniverse(MRI.getNumVirtRegs());
1480 for (SUnit &SU : SUnits)
1481 collectVRegUses(SU);
1482
1483 TopRPTracker.init(mf: &MF, rci: RegClassInfo, lis: LIS, mbb: BB, pos: RegionBegin,
1484 TrackLaneMasks: ShouldTrackLaneMasks, TrackUntiedDefs: false);
1485 BotRPTracker.init(mf: &MF, rci: RegClassInfo, lis: LIS, mbb: BB, pos: LiveRegionEnd,
1486 TrackLaneMasks: ShouldTrackLaneMasks, TrackUntiedDefs: false);
1487
1488 // Close the RPTracker to finalize live ins.
1489 RPTracker.closeRegion();
1490
1491 LLVM_DEBUG(RPTracker.dump());
1492
1493 // Initialize the live ins and live outs.
1494 TopRPTracker.addLiveRegs(Regs: RPTracker.getPressure().LiveInRegs);
1495 BotRPTracker.addLiveRegs(Regs: RPTracker.getPressure().LiveOutRegs);
1496
1497 // Close one end of the tracker so we can call
1498 // getMaxUpward/DownwardPressureDelta before advancing across any
1499 // instructions. This converts currently live regs into live ins/outs.
1500 TopRPTracker.closeTop();
1501 BotRPTracker.closeBottom();
1502
1503 BotRPTracker.initLiveThru(RPTracker);
1504 if (!BotRPTracker.getLiveThru().empty()) {
1505 TopRPTracker.initLiveThru(PressureSet: BotRPTracker.getLiveThru());
1506 LLVM_DEBUG(dbgs() << "Live Thru: ";
1507 dumpRegSetPressure(BotRPTracker.getLiveThru(), TRI));
1508 };
1509
1510 // For each live out vreg reduce the pressure change associated with other
1511 // uses of the same vreg below the live-out reaching def.
1512 updatePressureDiffs(LiveUses: RPTracker.getPressure().LiveOutRegs);
1513
1514 // Account for liveness generated by the region boundary.
1515 if (LiveRegionEnd != RegionEnd) {
1516 SmallVector<VRegMaskOrUnit, 8> LiveUses;
1517 BotRPTracker.recede(LiveUses: &LiveUses);
1518 updatePressureDiffs(LiveUses);
1519 }
1520
1521 LLVM_DEBUG(dbgs() << "Top Pressure: ";
1522 dumpRegSetPressure(TopRPTracker.getRegSetPressureAtPos(), TRI);
1523 dbgs() << "Bottom Pressure: ";
1524 dumpRegSetPressure(BotRPTracker.getRegSetPressureAtPos(), TRI););
1525
1526 assert((BotRPTracker.getPos() == RegionEnd ||
1527 (RegionEnd->isDebugInstr() &&
1528 BotRPTracker.getPos() == priorNonDebug(RegionEnd, RegionBegin))) &&
1529 "Can't find the region bottom");
1530
1531 // Cache the list of excess pressure sets in this region. This will also track
1532 // the max pressure in the scheduled code for these sets.
1533 RegionCriticalPSets.clear();
1534 const std::vector<unsigned> &RegionPressure =
1535 RPTracker.getPressure().MaxSetPressure;
1536 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
1537 unsigned Limit = RegClassInfo->getRegPressureSetLimit(Idx: i);
1538 if (RegionPressure[i] > Limit) {
1539 LLVM_DEBUG(dbgs() << TRI->getRegPressureSetName(i) << " Limit " << Limit
1540 << " Actual " << RegionPressure[i] << "\n");
1541 RegionCriticalPSets.push_back(x: PressureChange(i));
1542 }
1543 }
1544 LLVM_DEBUG({
1545 if (RegionCriticalPSets.size() > 0) {
1546 dbgs() << "Excess PSets: ";
1547 for (const PressureChange &RCPS : RegionCriticalPSets)
1548 dbgs() << TRI->getRegPressureSetName(RCPS.getPSet()) << " ";
1549 dbgs() << "\n";
1550 }
1551 });
1552}
1553
1554void ScheduleDAGMILive::
1555updateScheduledPressure(const SUnit *SU,
1556 const std::vector<unsigned> &NewMaxPressure) {
1557 const PressureDiff &PDiff = getPressureDiff(SU);
1558 unsigned CritIdx = 0, CritEnd = RegionCriticalPSets.size();
1559 for (const PressureChange &PC : PDiff) {
1560 if (!PC.isValid())
1561 break;
1562 unsigned ID = PC.getPSet();
1563 while (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() < ID)
1564 ++CritIdx;
1565 if (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() == ID) {
1566 if ((int)NewMaxPressure[ID] > RegionCriticalPSets[CritIdx].getUnitInc()
1567 && NewMaxPressure[ID] <= (unsigned)std::numeric_limits<int16_t>::max())
1568 RegionCriticalPSets[CritIdx].setUnitInc(NewMaxPressure[ID]);
1569 }
1570 unsigned Limit = RegClassInfo->getRegPressureSetLimit(Idx: ID);
1571 if (NewMaxPressure[ID] >= Limit - 2) {
1572 LLVM_DEBUG(dbgs() << " " << TRI->getRegPressureSetName(ID) << ": "
1573 << NewMaxPressure[ID]
1574 << ((NewMaxPressure[ID] > Limit) ? " > " : " <= ")
1575 << Limit << "(+ " << BotRPTracker.getLiveThru()[ID]
1576 << " livethru)\n");
1577 }
1578 }
1579}
1580
1581/// Update the PressureDiff array for liveness after scheduling this
1582/// instruction.
1583void ScheduleDAGMILive::updatePressureDiffs(ArrayRef<VRegMaskOrUnit> LiveUses) {
1584 for (const VRegMaskOrUnit &P : LiveUses) {
1585 /// FIXME: Currently assuming single-use physregs.
1586 if (!P.VRegOrUnit.isVirtualReg())
1587 continue;
1588 Register Reg = P.VRegOrUnit.asVirtualReg();
1589
1590 if (ShouldTrackLaneMasks) {
1591 // If the register has just become live then other uses won't change
1592 // this fact anymore => decrement pressure.
1593 // If the register has just become dead then other uses make it come
1594 // back to life => increment pressure.
1595 bool Decrement = P.LaneMask.any();
1596
1597 for (const VReg2SUnit &V2SU
1598 : make_range(x: VRegUses.find(Key: Reg), y: VRegUses.end())) {
1599 SUnit &SU = *V2SU.SU;
1600 if (SU.isScheduled || &SU == &ExitSU)
1601 continue;
1602
1603 PressureDiff &PDiff = getPressureDiff(SU: &SU);
1604 PDiff.addPressureChange(VRegOrUnit: VirtRegOrUnit(Reg), IsDec: Decrement, MRI: &MRI);
1605 if (llvm::any_of(Range&: PDiff, P: [](const PressureChange &Change) {
1606 return Change.isValid();
1607 }))
1608 LLVM_DEBUG(dbgs()
1609 << " UpdateRegPressure: SU(" << SU.NodeNum << ") "
1610 << printReg(Reg, TRI) << ':'
1611 << PrintLaneMask(P.LaneMask) << ' ' << *SU.getInstr();
1612 dbgs() << " to "; PDiff.dump(*TRI););
1613 }
1614 } else {
1615 assert(P.LaneMask.any());
1616 LLVM_DEBUG(dbgs() << " LiveReg: " << printReg(Reg, TRI) << "\n");
1617 // This may be called before CurrentBottom has been initialized. However,
1618 // BotRPTracker must have a valid position. We want the value live into the
1619 // instruction or live out of the block, so ask for the previous
1620 // instruction's live-out.
1621 const LiveInterval &LI = LIS->getInterval(Reg);
1622 VNInfo *VNI;
1623 MachineBasicBlock::const_iterator I =
1624 nextIfDebug(I: BotRPTracker.getPos(), End: BB->end());
1625 if (I == BB->end())
1626 VNI = LI.getVNInfoBefore(Idx: LIS->getMBBEndIdx(mbb: BB));
1627 else {
1628 LiveQueryResult LRQ = LI.Query(Idx: LIS->getInstructionIndex(Instr: *I));
1629 VNI = LRQ.valueIn();
1630 }
1631 // RegisterPressureTracker guarantees that readsReg is true for LiveUses.
1632 assert(VNI && "No live value at use.");
1633 for (const VReg2SUnit &V2SU
1634 : make_range(x: VRegUses.find(Key: Reg), y: VRegUses.end())) {
1635 SUnit *SU = V2SU.SU;
1636 // If this use comes before the reaching def, it cannot be a last use,
1637 // so decrease its pressure change.
1638 if (!SU->isScheduled && SU != &ExitSU) {
1639 LiveQueryResult LRQ =
1640 LI.Query(Idx: LIS->getInstructionIndex(Instr: *SU->getInstr()));
1641 if (LRQ.valueIn() == VNI) {
1642 PressureDiff &PDiff = getPressureDiff(SU);
1643 PDiff.addPressureChange(VRegOrUnit: VirtRegOrUnit(Reg), IsDec: true, MRI: &MRI);
1644 if (llvm::any_of(Range&: PDiff, P: [](const PressureChange &Change) {
1645 return Change.isValid();
1646 }))
1647 LLVM_DEBUG(dbgs() << " UpdateRegPressure: SU(" << SU->NodeNum
1648 << ") " << *SU->getInstr();
1649 dbgs() << " to ";
1650 PDiff.dump(*TRI););
1651 }
1652 }
1653 }
1654 }
1655 }
1656}
1657
1658void ScheduleDAGMILive::dump() const {
1659#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1660 if (EntrySU.getInstr() != nullptr)
1661 dumpNodeAll(EntrySU);
1662 for (const SUnit &SU : SUnits) {
1663 dumpNodeAll(SU);
1664 if (ShouldTrackPressure) {
1665 dbgs() << " Pressure Diff : ";
1666 getPressureDiff(&SU).dump(*TRI);
1667 }
1668 dbgs() << " Single Issue : ";
1669 if (SchedModel.mustBeginGroup(SU.getInstr()) &&
1670 SchedModel.mustEndGroup(SU.getInstr()))
1671 dbgs() << "true;";
1672 else
1673 dbgs() << "false;";
1674 dbgs() << '\n';
1675 }
1676 if (ExitSU.getInstr() != nullptr)
1677 dumpNodeAll(ExitSU);
1678#endif
1679}
1680
1681/// schedule - Called back from MachineScheduler::runOnMachineFunction
1682/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
1683/// only includes instructions that have DAG nodes, not scheduling boundaries.
1684///
1685/// This is a skeletal driver, with all the functionality pushed into helpers,
1686/// so that it can be easily extended by experimental schedulers. Generally,
1687/// implementing MachineSchedStrategy should be sufficient to implement a new
1688/// scheduling algorithm. However, if a scheduler further subclasses
1689/// ScheduleDAGMILive then it will want to override this virtual method in order
1690/// to update any specialized state.
1691void ScheduleDAGMILive::schedule() {
1692 LLVM_DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n");
1693 LLVM_DEBUG(SchedImpl->dumpPolicy());
1694 buildDAGWithRegPressure();
1695
1696 postProcessDAG();
1697
1698 SmallVector<SUnit*, 8> TopRoots, BotRoots;
1699 findRootsAndBiasEdges(TopRoots, BotRoots);
1700
1701 // Initialize the strategy before modifying the DAG.
1702 // This may initialize a DFSResult to be used for queue priority.
1703 SchedImpl->initialize(DAG: this);
1704
1705 LLVM_DEBUG(dump());
1706 if (PrintDAGs) dump();
1707 if (ViewMISchedDAGs) viewGraph();
1708
1709 // Initialize ready queues now that the DAG and priority data are finalized.
1710 initQueues(TopRoots, BotRoots);
1711
1712 bool IsTopNode = false;
1713 while (true) {
1714 if (!checkSchedLimit())
1715 break;
1716
1717 LLVM_DEBUG(dbgs() << "** ScheduleDAGMILive::schedule picking next node\n");
1718 SUnit *SU = SchedImpl->pickNode(IsTopNode);
1719 if (!SU) break;
1720
1721 assert(!SU->isScheduled && "Node already scheduled");
1722
1723 scheduleMI(SU, IsTopNode);
1724
1725 if (DFSResult) {
1726 unsigned SubtreeID = DFSResult->getSubtreeID(SU);
1727 if (!ScheduledTrees.test(Idx: SubtreeID)) {
1728 ScheduledTrees.set(SubtreeID);
1729 DFSResult->scheduleTree(SubtreeID);
1730 SchedImpl->scheduleTree(SubtreeID);
1731 }
1732 }
1733
1734 // Notify the scheduling strategy after updating the DAG.
1735 SchedImpl->schedNode(SU, IsTopNode);
1736
1737 updateQueues(SU, IsTopNode);
1738 }
1739 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
1740
1741 placeDebugValues();
1742
1743 LLVM_DEBUG({
1744 dbgs() << "*** Final schedule for "
1745 << printMBBReference(*begin()->getParent()) << " ***\n";
1746 dumpSchedule();
1747 dbgs() << '\n';
1748 });
1749}
1750
1751/// Build the DAG and setup three register pressure trackers.
1752void ScheduleDAGMILive::buildDAGWithRegPressure() {
1753 if (!ShouldTrackPressure) {
1754 RPTracker.reset();
1755 RegionCriticalPSets.clear();
1756 buildSchedGraph(AA);
1757 return;
1758 }
1759
1760 // Initialize the register pressure tracker used by buildSchedGraph.
1761 RPTracker.init(mf: &MF, rci: RegClassInfo, lis: LIS, mbb: BB, pos: LiveRegionEnd,
1762 TrackLaneMasks: ShouldTrackLaneMasks, /*TrackUntiedDefs=*/true);
1763
1764 // Account for liveness generate by the region boundary.
1765 if (LiveRegionEnd != RegionEnd)
1766 RPTracker.recede();
1767
1768 // Build the DAG, and compute current register pressure.
1769 buildSchedGraph(AA, RPTracker: &RPTracker, PDiffs: &SUPressureDiffs, LIS, TrackLaneMasks: ShouldTrackLaneMasks);
1770
1771 // Initialize top/bottom trackers after computing region pressure.
1772 initRegPressure();
1773}
1774
1775void ScheduleDAGMILive::computeDFSResult() {
1776 if (!DFSResult)
1777 DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize);
1778 DFSResult->clear();
1779 ScheduledTrees.clear();
1780 DFSResult->resize(NumSUnits: SUnits.size());
1781 DFSResult->compute(SUnits);
1782 ScheduledTrees.resize(N: DFSResult->getNumSubtrees());
1783}
1784
1785/// Compute the max cyclic critical path through the DAG. The scheduling DAG
1786/// only provides the critical path for single block loops. To handle loops that
1787/// span blocks, we could use the vreg path latencies provided by
1788/// MachineTraceMetrics instead. However, MachineTraceMetrics is not currently
1789/// available for use in the scheduler.
1790///
1791/// The cyclic path estimation identifies a def-use pair that crosses the back
1792/// edge and considers the depth and height of the nodes. For example, consider
1793/// the following instruction sequence where each instruction has unit latency
1794/// and defines an eponymous virtual register:
1795///
1796/// a->b(a,c)->c(b)->d(c)->exit
1797///
1798/// The cyclic critical path is a two cycles: b->c->b
1799/// The acyclic critical path is four cycles: a->b->c->d->exit
1800/// LiveOutHeight = height(c) = len(c->d->exit) = 2
1801/// LiveOutDepth = depth(c) + 1 = len(a->b->c) + 1 = 3
1802/// LiveInHeight = height(b) + 1 = len(b->c->d->exit) + 1 = 4
1803/// LiveInDepth = depth(b) = len(a->b) = 1
1804///
1805/// LiveOutDepth - LiveInDepth = 3 - 1 = 2
1806/// LiveInHeight - LiveOutHeight = 4 - 2 = 2
1807/// CyclicCriticalPath = min(2, 2) = 2
1808///
1809/// This could be relevant to PostRA scheduling, but is currently implemented
1810/// assuming LiveIntervals.
1811unsigned ScheduleDAGMILive::computeCyclicCriticalPath() {
1812 // This only applies to single block loop.
1813 if (!BB->isSuccessor(MBB: BB))
1814 return 0;
1815
1816 unsigned MaxCyclicLatency = 0;
1817 // Visit each live out vreg def to find def/use pairs that cross iterations.
1818 for (const VRegMaskOrUnit &P : RPTracker.getPressure().LiveOutRegs) {
1819 if (!P.VRegOrUnit.isVirtualReg())
1820 continue;
1821 Register Reg = P.VRegOrUnit.asVirtualReg();
1822 const LiveInterval &LI = LIS->getInterval(Reg);
1823 const VNInfo *DefVNI = LI.getVNInfoBefore(Idx: LIS->getMBBEndIdx(mbb: BB));
1824 if (!DefVNI)
1825 continue;
1826
1827 MachineInstr *DefMI = LIS->getInstructionFromIndex(index: DefVNI->def);
1828 const SUnit *DefSU = getSUnit(MI: DefMI);
1829 if (!DefSU)
1830 continue;
1831
1832 unsigned LiveOutHeight = DefSU->getHeight();
1833 unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency;
1834 // Visit all local users of the vreg def.
1835 for (const VReg2SUnit &V2SU
1836 : make_range(x: VRegUses.find(Key: Reg), y: VRegUses.end())) {
1837 SUnit *SU = V2SU.SU;
1838 if (SU == &ExitSU)
1839 continue;
1840
1841 // Only consider uses of the phi.
1842 LiveQueryResult LRQ = LI.Query(Idx: LIS->getInstructionIndex(Instr: *SU->getInstr()));
1843 if (!LRQ.valueIn()->isPHIDef())
1844 continue;
1845
1846 // Assume that a path spanning two iterations is a cycle, which could
1847 // overestimate in strange cases. This allows cyclic latency to be
1848 // estimated as the minimum slack of the vreg's depth or height.
1849 unsigned CyclicLatency = 0;
1850 if (LiveOutDepth > SU->getDepth())
1851 CyclicLatency = LiveOutDepth - SU->getDepth();
1852
1853 unsigned LiveInHeight = SU->getHeight() + DefSU->Latency;
1854 if (LiveInHeight > LiveOutHeight) {
1855 if (LiveInHeight - LiveOutHeight < CyclicLatency)
1856 CyclicLatency = LiveInHeight - LiveOutHeight;
1857 } else
1858 CyclicLatency = 0;
1859
1860 LLVM_DEBUG(dbgs() << "Cyclic Path: SU(" << DefSU->NodeNum << ") -> SU("
1861 << SU->NodeNum << ") = " << CyclicLatency << "c\n");
1862 if (CyclicLatency > MaxCyclicLatency)
1863 MaxCyclicLatency = CyclicLatency;
1864 }
1865 }
1866 LLVM_DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency << "c\n");
1867 return MaxCyclicLatency;
1868}
1869
1870/// Release ExitSU predecessors and setup scheduler queues. Re-position
1871/// the Top RP tracker in case the region beginning has changed.
1872void ScheduleDAGMILive::initQueues(ArrayRef<SUnit*> TopRoots,
1873 ArrayRef<SUnit*> BotRoots) {
1874 ScheduleDAGMI::initQueues(TopRoots, BotRoots);
1875 if (ShouldTrackPressure) {
1876 assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker");
1877 TopRPTracker.setPos(CurrentTop);
1878 }
1879}
1880
1881/// Move an instruction and update register pressure.
1882void ScheduleDAGMILive::scheduleMI(SUnit *SU, bool IsTopNode) {
1883 // Move the instruction to its new location in the instruction stream.
1884 MachineInstr *MI = SU->getInstr();
1885
1886 if (IsTopNode) {
1887 assert(SU->isTopReady() && "node still has unscheduled dependencies");
1888 if (&*CurrentTop == MI)
1889 CurrentTop = nextIfDebug(I: ++CurrentTop, End: CurrentBottom);
1890 else {
1891 moveInstruction(MI, InsertPos: CurrentTop);
1892 TopRPTracker.setPos(MI);
1893 }
1894
1895 if (ShouldTrackPressure) {
1896 // Update top scheduled pressure.
1897 RegisterOperands RegOpers;
1898 RegOpers.collect(MI: *MI, TRI: *TRI, MRI, TrackLaneMasks: ShouldTrackLaneMasks,
1899 /*IgnoreDead=*/false);
1900 if (ShouldTrackLaneMasks) {
1901 // Adjust liveness and add missing dead+read-undef flags.
1902 RegOpers.adjustLaneLiveness(LIS: *LIS, MRI, MI&: *MI);
1903 } else {
1904 // Adjust for missing dead-def flags.
1905 RegOpers.detectDeadDefs(MI: *MI, LIS: *LIS);
1906 }
1907
1908 TopRPTracker.advance(RegOpers);
1909 assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
1910 LLVM_DEBUG(dbgs() << "Top Pressure: "; dumpRegSetPressure(
1911 TopRPTracker.getRegSetPressureAtPos(), TRI););
1912
1913 updateScheduledPressure(SU, NewMaxPressure: TopRPTracker.getPressure().MaxSetPressure);
1914 }
1915 } else {
1916 assert(SU->isBottomReady() && "node still has unscheduled dependencies");
1917 MachineBasicBlock::iterator priorII =
1918 priorNonDebug(I: CurrentBottom, Beg: CurrentTop);
1919 if (&*priorII == MI)
1920 CurrentBottom = priorII;
1921 else {
1922 if (&*CurrentTop == MI) {
1923 CurrentTop = nextIfDebug(I: ++CurrentTop, End: priorII);
1924 TopRPTracker.setPos(CurrentTop);
1925 }
1926 moveInstruction(MI, InsertPos: CurrentBottom);
1927 CurrentBottom = MI;
1928 BotRPTracker.setPos(CurrentBottom);
1929 }
1930 if (ShouldTrackPressure) {
1931 RegisterOperands RegOpers;
1932 RegOpers.collect(MI: *MI, TRI: *TRI, MRI, TrackLaneMasks: ShouldTrackLaneMasks,
1933 /*IgnoreDead=*/false);
1934 if (ShouldTrackLaneMasks) {
1935 // Adjust liveness and add missing dead+read-undef flags.
1936 RegOpers.adjustLaneLiveness(LIS: *LIS, MRI, MI&: *MI);
1937 } else {
1938 // Adjust for missing dead-def flags.
1939 RegOpers.detectDeadDefs(MI: *MI, LIS: *LIS);
1940 }
1941
1942 if (BotRPTracker.getPos() != CurrentBottom)
1943 BotRPTracker.recedeSkipDebugValues();
1944 SmallVector<VRegMaskOrUnit, 8> LiveUses;
1945 BotRPTracker.recede(RegOpers, LiveUses: &LiveUses);
1946 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
1947 LLVM_DEBUG(dbgs() << "Bottom Pressure: "; dumpRegSetPressure(
1948 BotRPTracker.getRegSetPressureAtPos(), TRI););
1949
1950 updateScheduledPressure(SU, NewMaxPressure: BotRPTracker.getPressure().MaxSetPressure);
1951 updatePressureDiffs(LiveUses);
1952 }
1953 }
1954}
1955
1956//===----------------------------------------------------------------------===//
1957// BaseMemOpClusterMutation - DAG post-processing to cluster loads or stores.
1958//===----------------------------------------------------------------------===//
1959
1960namespace {
1961
1962/// Post-process the DAG to create cluster edges between neighboring
1963/// loads or between neighboring stores.
1964class BaseMemOpClusterMutation : public ScheduleDAGMutation {
1965 struct MemOpInfo {
1966 SUnit *SU;
1967 SmallVector<const MachineOperand *, 4> BaseOps;
1968 int64_t Offset;
1969 LocationSize Width;
1970 bool OffsetIsScalable;
1971
1972 MemOpInfo(SUnit *SU, ArrayRef<const MachineOperand *> BaseOps,
1973 int64_t Offset, bool OffsetIsScalable, LocationSize Width)
1974 : SU(SU), BaseOps(BaseOps), Offset(Offset), Width(Width),
1975 OffsetIsScalable(OffsetIsScalable) {}
1976
1977 static bool Compare(const MachineOperand *const &A,
1978 const MachineOperand *const &B) {
1979 if (A->getType() != B->getType())
1980 return A->getType() < B->getType();
1981 if (A->isReg())
1982 return A->getReg() < B->getReg();
1983 if (A->isFI()) {
1984 const MachineFunction &MF = *A->getParent()->getParent()->getParent();
1985 const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
1986 bool StackGrowsDown = TFI.getStackGrowthDirection() ==
1987 TargetFrameLowering::StackGrowsDown;
1988 return StackGrowsDown ? A->getIndex() > B->getIndex()
1989 : A->getIndex() < B->getIndex();
1990 }
1991
1992 llvm_unreachable("MemOpClusterMutation only supports register or frame "
1993 "index bases.");
1994 }
1995
1996 bool operator<(const MemOpInfo &RHS) const {
1997 // FIXME: Don't compare everything twice. Maybe use C++20 three way
1998 // comparison instead when it's available.
1999 if (std::lexicographical_compare(first1: BaseOps.begin(), last1: BaseOps.end(),
2000 first2: RHS.BaseOps.begin(), last2: RHS.BaseOps.end(),
2001 comp: Compare))
2002 return true;
2003 if (std::lexicographical_compare(first1: RHS.BaseOps.begin(), last1: RHS.BaseOps.end(),
2004 first2: BaseOps.begin(), last2: BaseOps.end(), comp: Compare))
2005 return false;
2006 if (Offset != RHS.Offset)
2007 return Offset < RHS.Offset;
2008 return SU->NodeNum < RHS.SU->NodeNum;
2009 }
2010 };
2011
2012 const TargetInstrInfo *TII;
2013 const TargetRegisterInfo *TRI;
2014 bool IsLoad;
2015 bool ReorderWhileClustering;
2016
2017public:
2018 BaseMemOpClusterMutation(const TargetInstrInfo *tii,
2019 const TargetRegisterInfo *tri, bool IsLoad,
2020 bool ReorderWhileClustering)
2021 : TII(tii), TRI(tri), IsLoad(IsLoad),
2022 ReorderWhileClustering(ReorderWhileClustering) {}
2023
2024 void apply(ScheduleDAGInstrs *DAGInstrs) override;
2025
2026protected:
2027 void clusterNeighboringMemOps(ArrayRef<MemOpInfo> MemOps, bool FastCluster,
2028 ScheduleDAGInstrs *DAG);
2029 void collectMemOpRecords(std::vector<SUnit> &SUnits,
2030 SmallVectorImpl<MemOpInfo> &MemOpRecords);
2031 bool groupMemOps(ArrayRef<MemOpInfo> MemOps, ScheduleDAGInstrs *DAG,
2032 DenseMap<unsigned, SmallVector<MemOpInfo, 32>> &Groups);
2033};
2034
2035class StoreClusterMutation : public BaseMemOpClusterMutation {
2036public:
2037 StoreClusterMutation(const TargetInstrInfo *tii,
2038 const TargetRegisterInfo *tri,
2039 bool ReorderWhileClustering)
2040 : BaseMemOpClusterMutation(tii, tri, false, ReorderWhileClustering) {}
2041};
2042
2043class LoadClusterMutation : public BaseMemOpClusterMutation {
2044public:
2045 LoadClusterMutation(const TargetInstrInfo *tii, const TargetRegisterInfo *tri,
2046 bool ReorderWhileClustering)
2047 : BaseMemOpClusterMutation(tii, tri, true, ReorderWhileClustering) {}
2048};
2049
2050} // end anonymous namespace
2051
2052std::unique_ptr<ScheduleDAGMutation>
2053llvm::createLoadClusterDAGMutation(const TargetInstrInfo *TII,
2054 const TargetRegisterInfo *TRI,
2055 bool ReorderWhileClustering) {
2056 return EnableMemOpCluster ? std::make_unique<LoadClusterMutation>(
2057 args&: TII, args&: TRI, args&: ReorderWhileClustering)
2058 : nullptr;
2059}
2060
2061std::unique_ptr<ScheduleDAGMutation>
2062llvm::createStoreClusterDAGMutation(const TargetInstrInfo *TII,
2063 const TargetRegisterInfo *TRI,
2064 bool ReorderWhileClustering) {
2065 return EnableMemOpCluster ? std::make_unique<StoreClusterMutation>(
2066 args&: TII, args&: TRI, args&: ReorderWhileClustering)
2067 : nullptr;
2068}
2069
2070// Sorting all the loads/stores first, then for each load/store, checking the
2071// following load/store one by one, until reach the first non-dependent one and
2072// call target hook to see if they can cluster.
2073// If FastCluster is enabled, we assume that, all the loads/stores have been
2074// preprocessed and now, they didn't have dependencies on each other.
2075void BaseMemOpClusterMutation::clusterNeighboringMemOps(
2076 ArrayRef<MemOpInfo> MemOpRecords, bool FastCluster,
2077 ScheduleDAGInstrs *DAG) {
2078 // Keep track of the current cluster length and bytes for each SUnit.
2079 DenseMap<unsigned, std::pair<unsigned, unsigned>> SUnit2ClusterInfo;
2080 EquivalenceClasses<SUnit *> Clusters;
2081
2082 // At this point, `MemOpRecords` array must hold atleast two mem ops. Try to
2083 // cluster mem ops collected within `MemOpRecords` array.
2084 for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {
2085 // Decision to cluster mem ops is taken based on target dependent logic
2086 auto MemOpa = MemOpRecords[Idx];
2087
2088 // Seek for the next load/store to do the cluster.
2089 unsigned NextIdx = Idx + 1;
2090 for (; NextIdx < End; ++NextIdx)
2091 // Skip if MemOpb has been clustered already or has dependency with
2092 // MemOpa.
2093 if (!SUnit2ClusterInfo.count(Val: MemOpRecords[NextIdx].SU->NodeNum) &&
2094 (FastCluster ||
2095 (!DAG->IsReachable(SU: MemOpRecords[NextIdx].SU, TargetSU: MemOpa.SU) &&
2096 !DAG->IsReachable(SU: MemOpa.SU, TargetSU: MemOpRecords[NextIdx].SU))))
2097 break;
2098 if (NextIdx == End)
2099 continue;
2100
2101 auto MemOpb = MemOpRecords[NextIdx];
2102 unsigned ClusterLength = 2;
2103 unsigned CurrentClusterBytes = MemOpa.Width.getValue().getKnownMinValue() +
2104 MemOpb.Width.getValue().getKnownMinValue();
2105 auto It = SUnit2ClusterInfo.find(Val: MemOpa.SU->NodeNum);
2106 if (It != SUnit2ClusterInfo.end()) {
2107 const auto &[Len, Bytes] = It->second;
2108 ClusterLength = Len + 1;
2109 CurrentClusterBytes = Bytes + MemOpb.Width.getValue().getKnownMinValue();
2110 }
2111
2112 if (!TII->shouldClusterMemOps(BaseOps1: MemOpa.BaseOps, Offset1: MemOpa.Offset,
2113 OffsetIsScalable1: MemOpa.OffsetIsScalable, BaseOps2: MemOpb.BaseOps,
2114 Offset2: MemOpb.Offset, OffsetIsScalable2: MemOpb.OffsetIsScalable,
2115 ClusterSize: ClusterLength, NumBytes: CurrentClusterBytes))
2116 continue;
2117
2118 SUnit *SUa = MemOpa.SU;
2119 SUnit *SUb = MemOpb.SU;
2120
2121 if (!ReorderWhileClustering && SUa->NodeNum > SUb->NodeNum)
2122 std::swap(a&: SUa, b&: SUb);
2123
2124 // FIXME: Is this check really required?
2125 if (!DAG->addEdge(SuccSU: SUb, PredDep: SDep(SUa, SDep::Cluster)))
2126 continue;
2127
2128 Clusters.unionSets(V1: SUa, V2: SUb);
2129 LLVM_DEBUG(dbgs() << "Cluster ld/st SU(" << SUa->NodeNum << ") - SU("
2130 << SUb->NodeNum << ")\n");
2131 ++NumClustered;
2132
2133 if (IsLoad) {
2134 // Copy successor edges from SUa to SUb. Interleaving computation
2135 // dependent on SUa can prevent load combining due to register reuse.
2136 // Predecessor edges do not need to be copied from SUb to SUa since
2137 // nearby loads should have effectively the same inputs.
2138 for (const SDep &Succ : SUa->Succs) {
2139 if (Succ.getSUnit() == SUb)
2140 continue;
2141 LLVM_DEBUG(dbgs() << " Copy Succ SU(" << Succ.getSUnit()->NodeNum
2142 << ")\n");
2143 DAG->addEdge(SuccSU: Succ.getSUnit(), PredDep: SDep(SUb, SDep::Artificial));
2144 }
2145 } else {
2146 // Copy predecessor edges from SUb to SUa to avoid the SUnits that
2147 // SUb dependent on scheduled in-between SUb and SUa. Successor edges
2148 // do not need to be copied from SUa to SUb since no one will depend
2149 // on stores.
2150 // Notice that, we don't need to care about the memory dependency as
2151 // we won't try to cluster them if they have any memory dependency.
2152 for (const SDep &Pred : SUb->Preds) {
2153 if (Pred.getSUnit() == SUa)
2154 continue;
2155 LLVM_DEBUG(dbgs() << " Copy Pred SU(" << Pred.getSUnit()->NodeNum
2156 << ")\n");
2157 DAG->addEdge(SuccSU: SUa, PredDep: SDep(Pred.getSUnit(), SDep::Artificial));
2158 }
2159 }
2160
2161 SUnit2ClusterInfo[MemOpb.SU->NodeNum] = {ClusterLength,
2162 CurrentClusterBytes};
2163
2164 LLVM_DEBUG(dbgs() << " Curr cluster length: " << ClusterLength
2165 << ", Curr cluster bytes: " << CurrentClusterBytes
2166 << "\n");
2167 }
2168
2169 // Add cluster group information.
2170 // Iterate over all of the equivalence sets.
2171 auto &AllClusters = DAG->getClusters();
2172 for (const EquivalenceClasses<SUnit *>::ECValue *I : Clusters) {
2173 if (!I->isLeader())
2174 continue;
2175 ClusterInfo Group;
2176 unsigned ClusterIdx = AllClusters.size();
2177 for (SUnit *MemberI : Clusters.members(ECV: *I)) {
2178 MemberI->ParentClusterIdx = ClusterIdx;
2179 Group.insert(Ptr: MemberI);
2180 }
2181 AllClusters.push_back(Elt: Group);
2182 }
2183}
2184
2185void BaseMemOpClusterMutation::collectMemOpRecords(
2186 std::vector<SUnit> &SUnits, SmallVectorImpl<MemOpInfo> &MemOpRecords) {
2187 for (auto &SU : SUnits) {
2188 if ((IsLoad && !SU.getInstr()->mayLoad()) ||
2189 (!IsLoad && !SU.getInstr()->mayStore()))
2190 continue;
2191
2192 const MachineInstr &MI = *SU.getInstr();
2193 SmallVector<const MachineOperand *, 4> BaseOps;
2194 int64_t Offset;
2195 bool OffsetIsScalable;
2196 LocationSize Width = LocationSize::precise(Value: 0);
2197 if (TII->getMemOperandsWithOffsetWidth(MI, BaseOps, Offset,
2198 OffsetIsScalable, Width, TRI)) {
2199 if (!Width.hasValue())
2200 continue;
2201
2202 MemOpRecords.push_back(
2203 Elt: MemOpInfo(&SU, BaseOps, Offset, OffsetIsScalable, Width));
2204
2205 LLVM_DEBUG(dbgs() << "Num BaseOps: " << BaseOps.size() << ", Offset: "
2206 << Offset << ", OffsetIsScalable: " << OffsetIsScalable
2207 << ", Width: " << Width << "\n");
2208 }
2209#ifndef NDEBUG
2210 for (const auto *Op : BaseOps)
2211 assert(Op);
2212#endif
2213 }
2214}
2215
2216bool BaseMemOpClusterMutation::groupMemOps(
2217 ArrayRef<MemOpInfo> MemOps, ScheduleDAGInstrs *DAG,
2218 DenseMap<unsigned, SmallVector<MemOpInfo, 32>> &Groups) {
2219 bool FastCluster =
2220 ForceFastCluster ||
2221 MemOps.size() * DAG->SUnits.size() / 1000 > FastClusterThreshold;
2222
2223 for (const auto &MemOp : MemOps) {
2224 unsigned ChainPredID = DAG->SUnits.size();
2225 if (FastCluster) {
2226 for (const SDep &Pred : MemOp.SU->Preds) {
2227 // We only want to cluster the mem ops that have the same ctrl(non-data)
2228 // pred so that they didn't have ctrl dependency for each other. But for
2229 // store instrs, we can still cluster them if the pred is load instr.
2230 if ((Pred.isCtrl() &&
2231 (IsLoad ||
2232 (Pred.getSUnit() && Pred.getSUnit()->getInstr()->mayStore()))) &&
2233 !Pred.isArtificial()) {
2234 ChainPredID = Pred.getSUnit()->NodeNum;
2235 break;
2236 }
2237 }
2238 } else
2239 ChainPredID = 0;
2240
2241 Groups[ChainPredID].push_back(Elt: MemOp);
2242 }
2243 return FastCluster;
2244}
2245
2246/// Callback from DAG postProcessing to create cluster edges for loads/stores.
2247void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAG) {
2248 // Collect all the clusterable loads/stores
2249 SmallVector<MemOpInfo, 32> MemOpRecords;
2250 collectMemOpRecords(SUnits&: DAG->SUnits, MemOpRecords);
2251
2252 if (MemOpRecords.size() < 2)
2253 return;
2254
2255 // Put the loads/stores without dependency into the same group with some
2256 // heuristic if the DAG is too complex to avoid compiling time blow up.
2257 // Notice that, some fusion pair could be lost with this.
2258 DenseMap<unsigned, SmallVector<MemOpInfo, 32>> Groups;
2259 bool FastCluster = groupMemOps(MemOps: MemOpRecords, DAG, Groups);
2260
2261 for (auto &Group : Groups) {
2262 // Sorting the loads/stores, so that, we can stop the cluster as early as
2263 // possible.
2264 llvm::sort(C&: Group.second);
2265
2266 // Trying to cluster all the neighboring loads/stores.
2267 clusterNeighboringMemOps(MemOpRecords: Group.second, FastCluster, DAG);
2268 }
2269}
2270
2271//===----------------------------------------------------------------------===//
2272// CopyConstrain - DAG post-processing to encourage copy elimination.
2273//===----------------------------------------------------------------------===//
2274
2275namespace {
2276
2277/// Post-process the DAG to create weak edges from all uses of a copy to
2278/// the one use that defines the copy's source vreg, most likely an induction
2279/// variable increment.
2280class CopyConstrain : public ScheduleDAGMutation {
2281 // Transient state.
2282 SlotIndex RegionBeginIdx;
2283
2284 // RegionEndIdx is the slot index of the last non-debug instruction in the
2285 // scheduling region. So we may have RegionBeginIdx == RegionEndIdx.
2286 SlotIndex RegionEndIdx;
2287
2288public:
2289 CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}
2290
2291 void apply(ScheduleDAGInstrs *DAGInstrs) override;
2292
2293protected:
2294 void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG);
2295};
2296
2297} // end anonymous namespace
2298
2299std::unique_ptr<ScheduleDAGMutation>
2300llvm::createCopyConstrainDAGMutation(const TargetInstrInfo *TII,
2301 const TargetRegisterInfo *TRI) {
2302 return std::make_unique<CopyConstrain>(args&: TII, args&: TRI);
2303}
2304
2305/// constrainLocalCopy handles two possibilities:
2306/// 1) Local src:
2307/// I0: = dst
2308/// I1: src = ...
2309/// I2: = dst
2310/// I3: dst = src (copy)
2311/// (create pred->succ edges I0->I1, I2->I1)
2312///
2313/// 2) Local copy:
2314/// I0: dst = src (copy)
2315/// I1: = dst
2316/// I2: src = ...
2317/// I3: = dst
2318/// (create pred->succ edges I1->I2, I3->I2)
2319///
2320/// Although the MachineScheduler is currently constrained to single blocks,
2321/// this algorithm should handle extended blocks. An EBB is a set of
2322/// contiguously numbered blocks such that the previous block in the EBB is
2323/// always the single predecessor.
2324void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG) {
2325 LiveIntervals *LIS = DAG->getLIS();
2326 MachineInstr *Copy = CopySU->getInstr();
2327
2328 // Check for pure vreg copies.
2329 const MachineOperand &SrcOp = Copy->getOperand(i: 1);
2330 Register SrcReg = SrcOp.getReg();
2331 if (!SrcReg.isVirtual() || !SrcOp.readsReg())
2332 return;
2333
2334 const MachineOperand &DstOp = Copy->getOperand(i: 0);
2335 Register DstReg = DstOp.getReg();
2336 if (!DstReg.isVirtual() || DstOp.isDead())
2337 return;
2338
2339 // Check if either the dest or source is local. If it's live across a back
2340 // edge, it's not local. Note that if both vregs are live across the back
2341 // edge, we cannot successfully contrain the copy without cyclic scheduling.
2342 // If both the copy's source and dest are local live intervals, then we
2343 // should treat the dest as the global for the purpose of adding
2344 // constraints. This adds edges from source's other uses to the copy.
2345 unsigned LocalReg = SrcReg;
2346 unsigned GlobalReg = DstReg;
2347 LiveInterval *LocalLI = &LIS->getInterval(Reg: LocalReg);
2348 if (!LocalLI->isLocal(Start: RegionBeginIdx, End: RegionEndIdx)) {
2349 LocalReg = DstReg;
2350 GlobalReg = SrcReg;
2351 LocalLI = &LIS->getInterval(Reg: LocalReg);
2352 if (!LocalLI->isLocal(Start: RegionBeginIdx, End: RegionEndIdx))
2353 return;
2354 }
2355 LiveInterval *GlobalLI = &LIS->getInterval(Reg: GlobalReg);
2356
2357 // Find the global segment after the start of the local LI.
2358 LiveInterval::iterator GlobalSegment = GlobalLI->find(Pos: LocalLI->beginIndex());
2359 // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a
2360 // local live range. We could create edges from other global uses to the local
2361 // start, but the coalescer should have already eliminated these cases, so
2362 // don't bother dealing with it.
2363 if (GlobalSegment == GlobalLI->end())
2364 return;
2365
2366 // If GlobalSegment is killed at the LocalLI->start, the call to find()
2367 // returned the next global segment. But if GlobalSegment overlaps with
2368 // LocalLI->start, then advance to the next segment. If a hole in GlobalLI
2369 // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole.
2370 if (GlobalSegment->contains(I: LocalLI->beginIndex()))
2371 ++GlobalSegment;
2372
2373 if (GlobalSegment == GlobalLI->end())
2374 return;
2375
2376 // Check if GlobalLI contains a hole in the vicinity of LocalLI.
2377 if (GlobalSegment != GlobalLI->begin()) {
2378 // Two address defs have no hole.
2379 if (SlotIndex::isSameInstr(A: std::prev(x: GlobalSegment)->end,
2380 B: GlobalSegment->start)) {
2381 return;
2382 }
2383 // If the prior global segment may be defined by the same two-address
2384 // instruction that also defines LocalLI, then can't make a hole here.
2385 if (SlotIndex::isSameInstr(A: std::prev(x: GlobalSegment)->start,
2386 B: LocalLI->beginIndex())) {
2387 return;
2388 }
2389 // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise
2390 // it would be a disconnected component in the live range.
2391 assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&
2392 "Disconnected LRG within the scheduling region.");
2393 }
2394 MachineInstr *GlobalDef = LIS->getInstructionFromIndex(index: GlobalSegment->start);
2395 if (!GlobalDef)
2396 return;
2397
2398 SUnit *GlobalSU = DAG->getSUnit(MI: GlobalDef);
2399 if (!GlobalSU)
2400 return;
2401
2402 // GlobalDef is the bottom of the GlobalLI hole. Open the hole by
2403 // constraining the uses of the last local def to precede GlobalDef.
2404 SmallVector<SUnit*,8> LocalUses;
2405 const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(Idx: LocalLI->endIndex());
2406 MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(index: LastLocalVN->def);
2407 SUnit *LastLocalSU = DAG->getSUnit(MI: LastLocalDef);
2408 for (const SDep &Succ : LastLocalSU->Succs) {
2409 if (Succ.getKind() != SDep::Data || Succ.getReg() != LocalReg)
2410 continue;
2411 if (Succ.getSUnit() == GlobalSU)
2412 continue;
2413 if (!DAG->canAddEdge(SuccSU: GlobalSU, PredSU: Succ.getSUnit()))
2414 return;
2415 LocalUses.push_back(Elt: Succ.getSUnit());
2416 }
2417 // Open the top of the GlobalLI hole by constraining any earlier global uses
2418 // to precede the start of LocalLI.
2419 SmallVector<SUnit*,8> GlobalUses;
2420 MachineInstr *FirstLocalDef =
2421 LIS->getInstructionFromIndex(index: LocalLI->beginIndex());
2422 SUnit *FirstLocalSU = DAG->getSUnit(MI: FirstLocalDef);
2423 for (const SDep &Pred : GlobalSU->Preds) {
2424 if (Pred.getKind() != SDep::Anti || Pred.getReg() != GlobalReg)
2425 continue;
2426 if (Pred.getSUnit() == FirstLocalSU)
2427 continue;
2428 if (!DAG->canAddEdge(SuccSU: FirstLocalSU, PredSU: Pred.getSUnit()))
2429 return;
2430 GlobalUses.push_back(Elt: Pred.getSUnit());
2431 }
2432 LLVM_DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n");
2433 // Add the weak edges.
2434 for (SUnit *LU : LocalUses) {
2435 LLVM_DEBUG(dbgs() << " Local use SU(" << LU->NodeNum << ") -> SU("
2436 << GlobalSU->NodeNum << ")\n");
2437 DAG->addEdge(SuccSU: GlobalSU, PredDep: SDep(LU, SDep::Weak));
2438 }
2439 for (SUnit *GU : GlobalUses) {
2440 LLVM_DEBUG(dbgs() << " Global use SU(" << GU->NodeNum << ") -> SU("
2441 << FirstLocalSU->NodeNum << ")\n");
2442 DAG->addEdge(SuccSU: FirstLocalSU, PredDep: SDep(GU, SDep::Weak));
2443 }
2444}
2445
2446/// Callback from DAG postProcessing to create weak edges to encourage
2447/// copy elimination.
2448void CopyConstrain::apply(ScheduleDAGInstrs *DAGInstrs) {
2449 ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
2450 assert(DAG->hasVRegLiveness() && "Expect VRegs with LiveIntervals");
2451
2452 MachineBasicBlock::iterator FirstPos = nextIfDebug(I: DAG->begin(), End: DAG->end());
2453 if (FirstPos == DAG->end())
2454 return;
2455 RegionBeginIdx = DAG->getLIS()->getInstructionIndex(Instr: *FirstPos);
2456 RegionEndIdx = DAG->getLIS()->getInstructionIndex(
2457 Instr: *priorNonDebug(I: DAG->end(), Beg: DAG->begin()));
2458
2459 for (SUnit &SU : DAG->SUnits) {
2460 if (!SU.getInstr()->isCopy())
2461 continue;
2462
2463 constrainLocalCopy(CopySU: &SU, DAG: static_cast<ScheduleDAGMILive*>(DAG));
2464 }
2465}
2466
2467//===----------------------------------------------------------------------===//
2468// MachineSchedStrategy helpers used by GenericScheduler, GenericPostScheduler
2469// and possibly other custom schedulers.
2470//===----------------------------------------------------------------------===//
2471
2472static const unsigned InvalidCycle = ~0U;
2473
2474SchedBoundary::~SchedBoundary() = default;
2475
2476/// Given a Count of resource usage and a Latency value, return true if a
2477/// SchedBoundary becomes resource limited.
2478/// If we are checking after scheduling a node, we should return true when
2479/// we just reach the resource limit.
2480static bool checkResourceLimit(unsigned LFactor, unsigned Count,
2481 unsigned Latency, bool AfterSchedNode) {
2482 int ResCntFactor = (int)(Count - (Latency * LFactor));
2483 if (AfterSchedNode)
2484 return ResCntFactor >= (int)LFactor;
2485 else
2486 return ResCntFactor > (int)LFactor;
2487}
2488
2489void SchedBoundary::reset() {
2490 // A new HazardRec is created for each DAG and owned by SchedBoundary.
2491 // Destroying and reconstructing it is very expensive though. So keep
2492 // invalid, placeholder HazardRecs.
2493 if (HazardRec && HazardRec->isEnabled())
2494 HazardRec.reset();
2495 Available.clear();
2496 Pending.clear();
2497 CheckPending = false;
2498 CurrCycle = 0;
2499 CurrMOps = 0;
2500 MinReadyCycle = std::numeric_limits<unsigned>::max();
2501 ExpectedLatency = 0;
2502 DependentLatency = 0;
2503 RetiredMOps = 0;
2504 MaxExecutedResCount = 0;
2505 ZoneCritResIdx = 0;
2506 IsResourceLimited = false;
2507 ReservedCycles.clear();
2508 ReservedResourceSegments.clear();
2509 ReservedCyclesIndex.clear();
2510 ResourceGroupSubUnitMasks.clear();
2511#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2512 // Track the maximum number of stall cycles that could arise either from the
2513 // latency of a DAG edge or the number of cycles that a processor resource is
2514 // reserved (SchedBoundary::ReservedCycles).
2515 MaxObservedStall = 0;
2516#endif
2517 // Reserve a zero-count for invalid CritResIdx.
2518 ExecutedResCounts.resize(N: 1);
2519 assert(!ExecutedResCounts[0] && "nonzero count for bad resource");
2520}
2521
2522void SchedRemainder::
2523init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
2524 reset();
2525 if (!SchedModel->hasInstrSchedModel())
2526 return;
2527 RemainingCounts.resize(N: SchedModel->getNumProcResourceKinds());
2528 for (SUnit &SU : DAG->SUnits) {
2529 const MCSchedClassDesc *SC = DAG->getSchedClass(SU: &SU);
2530 RemIssueCount += SchedModel->getNumMicroOps(MI: SU.getInstr(), SC)
2531 * SchedModel->getMicroOpFactor();
2532 for (TargetSchedModel::ProcResIter
2533 PI = SchedModel->getWriteProcResBegin(SC),
2534 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2535 unsigned PIdx = PI->ProcResourceIdx;
2536 unsigned Factor = SchedModel->getResourceFactor(ResIdx: PIdx);
2537 assert(PI->ReleaseAtCycle >= PI->AcquireAtCycle);
2538 RemainingCounts[PIdx] +=
2539 (Factor * (PI->ReleaseAtCycle - PI->AcquireAtCycle));
2540 }
2541 }
2542}
2543
2544void SchedBoundary::
2545init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
2546 reset();
2547 DAG = dag;
2548 SchedModel = smodel;
2549 Rem = rem;
2550 if (SchedModel->hasInstrSchedModel()) {
2551 unsigned ResourceCount = SchedModel->getNumProcResourceKinds();
2552 ReservedCyclesIndex.resize(N: ResourceCount);
2553 ExecutedResCounts.resize(N: ResourceCount);
2554 ResourceGroupSubUnitMasks.resize(N: ResourceCount, NV: APInt(ResourceCount, 0));
2555 unsigned NumUnits = 0;
2556
2557 for (unsigned i = 0; i < ResourceCount; ++i) {
2558 ReservedCyclesIndex[i] = NumUnits;
2559 NumUnits += SchedModel->getProcResource(PIdx: i)->NumUnits;
2560 if (isReservedGroup(PIdx: i)) {
2561 auto SubUnits = SchedModel->getProcResource(PIdx: i)->SubUnitsIdxBegin;
2562 for (unsigned U = 0, UE = SchedModel->getProcResource(PIdx: i)->NumUnits;
2563 U != UE; ++U)
2564 ResourceGroupSubUnitMasks[i].setBit(SubUnits[U]);
2565 }
2566 }
2567
2568 ReservedCycles.resize(new_size: NumUnits, x: InvalidCycle);
2569 }
2570}
2571
2572/// Compute the stall cycles based on this SUnit's ready time. Heuristics treat
2573/// these "soft stalls" differently than the hard stall cycles based on CPU
2574/// resources and computed by checkHazard(). A fully in-order model
2575/// (MicroOpBufferSize==0) will not make use of this since instructions are not
2576/// available for scheduling until they are ready. However, a weaker in-order
2577/// model may use this for heuristics. For example, if a processor has in-order
2578/// behavior when reading certain resources, this may come into play.
2579unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {
2580 if (!SU->isUnbuffered)
2581 return 0;
2582
2583 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
2584 if (ReadyCycle > CurrCycle)
2585 return ReadyCycle - CurrCycle;
2586 return 0;
2587}
2588
2589/// Compute the next cycle at which the given processor resource unit
2590/// can be scheduled.
2591unsigned SchedBoundary::getNextResourceCycleByInstance(unsigned InstanceIdx,
2592 unsigned ReleaseAtCycle,
2593 unsigned AcquireAtCycle) {
2594 if (SchedModel && SchedModel->enableIntervals()) {
2595 if (isTop())
2596 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromTop(
2597 CurrCycle, AcquireAtCycle, ReleaseAtCycle);
2598
2599 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromBottom(
2600 CurrCycle, AcquireAtCycle, ReleaseAtCycle);
2601 }
2602
2603 unsigned NextUnreserved = ReservedCycles[InstanceIdx];
2604 // If this resource has never been used, always return cycle zero.
2605 if (NextUnreserved == InvalidCycle)
2606 return CurrCycle;
2607 // For bottom-up scheduling add the cycles needed for the current operation.
2608 if (!isTop())
2609 NextUnreserved = std::max(a: CurrCycle, b: NextUnreserved + ReleaseAtCycle);
2610 return NextUnreserved;
2611}
2612
2613/// Compute the next cycle at which the given processor resource can be
2614/// scheduled. Returns the next cycle and the index of the processor resource
2615/// instance in the reserved cycles vector.
2616std::pair<unsigned, unsigned>
2617SchedBoundary::getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx,
2618 unsigned ReleaseAtCycle,
2619 unsigned AcquireAtCycle) {
2620 if (MischedDetailResourceBooking) {
2621 LLVM_DEBUG(dbgs() << " Resource booking (@" << CurrCycle << "c): \n");
2622 LLVM_DEBUG(dumpReservedCycles());
2623 LLVM_DEBUG(dbgs() << " getNextResourceCycle (@" << CurrCycle << "c): \n");
2624 }
2625 unsigned MinNextUnreserved = InvalidCycle;
2626 unsigned InstanceIdx = 0;
2627 unsigned StartIndex = ReservedCyclesIndex[PIdx];
2628 unsigned NumberOfInstances = SchedModel->getProcResource(PIdx)->NumUnits;
2629 assert(NumberOfInstances > 0 &&
2630 "Cannot have zero instances of a ProcResource");
2631
2632 if (isReservedGroup(PIdx)) {
2633 // If any subunits are used by the instruction, report that the
2634 // subunits of the resource group are available at the first cycle
2635 // in which the unit is available, effectively removing the group
2636 // record from hazarding and basing the hazarding decisions on the
2637 // subunit records. Otherwise, choose the first available instance
2638 // from among the subunits. Specifications which assign cycles to
2639 // both the subunits and the group or which use an unbuffered
2640 // group with buffered subunits will appear to schedule
2641 // strangely. In the first case, the additional cycles for the
2642 // group will be ignored. In the second, the group will be
2643 // ignored entirely.
2644 for (const MCWriteProcResEntry &PE :
2645 make_range(x: SchedModel->getWriteProcResBegin(SC),
2646 y: SchedModel->getWriteProcResEnd(SC)))
2647 if (ResourceGroupSubUnitMasks[PIdx][PE.ProcResourceIdx])
2648 return std::make_pair(x: getNextResourceCycleByInstance(
2649 InstanceIdx: StartIndex, ReleaseAtCycle, AcquireAtCycle),
2650 y&: StartIndex);
2651
2652 auto SubUnits = SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin;
2653 for (unsigned I = 0, End = NumberOfInstances; I < End; ++I) {
2654 unsigned NextUnreserved, NextInstanceIdx;
2655 std::tie(args&: NextUnreserved, args&: NextInstanceIdx) =
2656 getNextResourceCycle(SC, PIdx: SubUnits[I], ReleaseAtCycle, AcquireAtCycle);
2657 if (MinNextUnreserved > NextUnreserved) {
2658 InstanceIdx = NextInstanceIdx;
2659 MinNextUnreserved = NextUnreserved;
2660 }
2661 }
2662 return std::make_pair(x&: MinNextUnreserved, y&: InstanceIdx);
2663 }
2664
2665 for (unsigned I = StartIndex, End = StartIndex + NumberOfInstances; I < End;
2666 ++I) {
2667 unsigned NextUnreserved =
2668 getNextResourceCycleByInstance(InstanceIdx: I, ReleaseAtCycle, AcquireAtCycle);
2669 if (MischedDetailResourceBooking)
2670 LLVM_DEBUG(dbgs() << " Instance " << I - StartIndex << " available @"
2671 << NextUnreserved << "c\n");
2672 if (MinNextUnreserved > NextUnreserved) {
2673 InstanceIdx = I;
2674 MinNextUnreserved = NextUnreserved;
2675 }
2676 }
2677 if (MischedDetailResourceBooking)
2678 LLVM_DEBUG(dbgs() << " selecting " << SchedModel->getResourceName(PIdx)
2679 << "[" << InstanceIdx - StartIndex << "]"
2680 << " available @" << MinNextUnreserved << "c"
2681 << "\n");
2682 return std::make_pair(x&: MinNextUnreserved, y&: InstanceIdx);
2683}
2684
2685/// Does this SU have a hazard within the current instruction group.
2686///
2687/// The scheduler supports two modes of hazard recognition. The first is the
2688/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
2689/// supports highly complicated in-order reservation tables
2690/// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
2691///
2692/// The second is a streamlined mechanism that checks for hazards based on
2693/// simple counters that the scheduler itself maintains. It explicitly checks
2694/// for instruction dispatch limitations, including the number of micro-ops that
2695/// can dispatch per cycle.
2696///
2697/// TODO: Also check whether the SU must start a new group.
2698bool SchedBoundary::checkHazard(SUnit *SU) {
2699 if (HazardRec->isEnabled()
2700 && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard) {
2701 LLVM_DEBUG(dbgs().indent(2)
2702 << "hazard: SU(" << SU->NodeNum << ") reported by HazardRec\n");
2703 return true;
2704 }
2705
2706 unsigned uops = SchedModel->getNumMicroOps(MI: SU->getInstr());
2707 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {
2708 LLVM_DEBUG(dbgs().indent(2) << "hazard: SU(" << SU->NodeNum << ") uops="
2709 << uops << ", CurrMOps = " << CurrMOps << ", "
2710 << "CurrMOps + uops > issue width of "
2711 << SchedModel->getIssueWidth() << "\n");
2712 return true;
2713 }
2714
2715 if (CurrMOps > 0 &&
2716 ((isTop() && SchedModel->mustBeginGroup(MI: SU->getInstr())) ||
2717 (!isTop() && SchedModel->mustEndGroup(MI: SU->getInstr())))) {
2718 LLVM_DEBUG(dbgs().indent(2) << "hazard: SU(" << SU->NodeNum << ") must "
2719 << (isTop() ? "begin" : "end") << " group\n");
2720 return true;
2721 }
2722
2723 if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
2724 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
2725 for (const MCWriteProcResEntry &PE :
2726 make_range(x: SchedModel->getWriteProcResBegin(SC),
2727 y: SchedModel->getWriteProcResEnd(SC))) {
2728 unsigned ResIdx = PE.ProcResourceIdx;
2729 unsigned ReleaseAtCycle = PE.ReleaseAtCycle;
2730 unsigned AcquireAtCycle = PE.AcquireAtCycle;
2731 unsigned NRCycle, InstanceIdx;
2732 std::tie(args&: NRCycle, args&: InstanceIdx) =
2733 getNextResourceCycle(SC, PIdx: ResIdx, ReleaseAtCycle, AcquireAtCycle);
2734 if (NRCycle > CurrCycle) {
2735#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2736 MaxObservedStall = std::max(ReleaseAtCycle, MaxObservedStall);
2737#endif
2738 LLVM_DEBUG(dbgs().indent(2)
2739 << "hazard: SU(" << SU->NodeNum << ") "
2740 << SchedModel->getResourceName(ResIdx) << '['
2741 << InstanceIdx - ReservedCyclesIndex[ResIdx] << ']' << "="
2742 << NRCycle << "c, is later than "
2743 << "CurrCycle = " << CurrCycle << "c\n");
2744 return true;
2745 }
2746 }
2747 }
2748 return false;
2749}
2750
2751// Find the unscheduled node in ReadySUs with the highest latency.
2752unsigned SchedBoundary::
2753findMaxLatency(ArrayRef<SUnit*> ReadySUs) {
2754 SUnit *LateSU = nullptr;
2755 unsigned RemLatency = 0;
2756 for (SUnit *SU : ReadySUs) {
2757 unsigned L = getUnscheduledLatency(SU);
2758 if (L > RemLatency) {
2759 RemLatency = L;
2760 LateSU = SU;
2761 }
2762 }
2763 if (LateSU) {
2764 LLVM_DEBUG(dbgs() << Available.getName() << " RemLatency SU("
2765 << LateSU->NodeNum << ") " << RemLatency << "c\n");
2766 }
2767 return RemLatency;
2768}
2769
2770// Count resources in this zone and the remaining unscheduled
2771// instruction. Return the max count, scaled. Set OtherCritIdx to the critical
2772// resource index, or zero if the zone is issue limited.
2773unsigned SchedBoundary::
2774getOtherResourceCount(unsigned &OtherCritIdx) {
2775 OtherCritIdx = 0;
2776 if (!SchedModel->hasInstrSchedModel())
2777 return 0;
2778
2779 unsigned OtherCritCount = Rem->RemIssueCount
2780 + (RetiredMOps * SchedModel->getMicroOpFactor());
2781 LLVM_DEBUG(dbgs() << " " << Available.getName() << " + Remain MOps: "
2782 << OtherCritCount / SchedModel->getMicroOpFactor() << '\n');
2783 for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds();
2784 PIdx != PEnd; ++PIdx) {
2785 unsigned OtherCount = getResourceCount(ResIdx: PIdx) + Rem->RemainingCounts[PIdx];
2786 if (OtherCount > OtherCritCount) {
2787 OtherCritCount = OtherCount;
2788 OtherCritIdx = PIdx;
2789 }
2790 }
2791 if (OtherCritIdx) {
2792 LLVM_DEBUG(
2793 dbgs() << " " << Available.getName() << " + Remain CritRes: "
2794 << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)
2795 << " " << SchedModel->getResourceName(OtherCritIdx) << "\n");
2796 }
2797 return OtherCritCount;
2798}
2799
2800void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue,
2801 unsigned Idx) {
2802 assert(SU->getInstr() && "Scheduled SUnit must have instr");
2803
2804#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2805 // ReadyCycle was been bumped up to the CurrCycle when this node was
2806 // scheduled, but CurrCycle may have been eagerly advanced immediately after
2807 // scheduling, so may now be greater than ReadyCycle.
2808 if (ReadyCycle > CurrCycle)
2809 MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);
2810#endif
2811
2812 if (ReadyCycle < MinReadyCycle)
2813 MinReadyCycle = ReadyCycle;
2814
2815 // Check for interlocks first. For the purpose of other heuristics, an
2816 // instruction that cannot issue appears as if it's not in the ReadyQueue.
2817 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
2818 bool HazardDetected = !IsBuffered && ReadyCycle > CurrCycle;
2819 if (HazardDetected)
2820 LLVM_DEBUG(dbgs().indent(2) << "hazard: SU(" << SU->NodeNum
2821 << ") ReadyCycle = " << ReadyCycle
2822 << " is later than CurrCycle = " << CurrCycle
2823 << " on an unbuffered resource" << "\n");
2824 else
2825 HazardDetected = checkHazard(SU);
2826
2827 if (!HazardDetected && Available.size() >= ReadyListLimit) {
2828 HazardDetected = true;
2829 LLVM_DEBUG(dbgs().indent(2) << "hazard: Available Q is full (size: "
2830 << Available.size() << ")\n");
2831 }
2832
2833 if (!HazardDetected) {
2834 Available.push(SU);
2835 LLVM_DEBUG(dbgs().indent(2)
2836 << "Move SU(" << SU->NodeNum << ") into Available Q\n");
2837
2838 if (InPQueue)
2839 Pending.remove(I: Pending.begin() + Idx);
2840 return;
2841 }
2842
2843 if (!InPQueue)
2844 Pending.push(SU);
2845}
2846
2847/// Move the boundary of scheduled code by one cycle.
2848void SchedBoundary::bumpCycle(unsigned NextCycle) {
2849 if (SchedModel->getMicroOpBufferSize() == 0) {
2850 assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
2851 "MinReadyCycle uninitialized");
2852 if (MinReadyCycle > NextCycle)
2853 NextCycle = MinReadyCycle;
2854 }
2855 // Update the current micro-ops, which will issue in the next cycle.
2856 unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle);
2857 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
2858
2859 // Decrement DependentLatency based on the next cycle.
2860 if ((NextCycle - CurrCycle) > DependentLatency)
2861 DependentLatency = 0;
2862 else
2863 DependentLatency -= (NextCycle - CurrCycle);
2864
2865 if (!HazardRec->isEnabled()) {
2866 // Bypass HazardRec virtual calls.
2867 CurrCycle = NextCycle;
2868 } else {
2869 // Bypass getHazardType calls in case of long latency.
2870 for (; CurrCycle != NextCycle; ++CurrCycle) {
2871 if (isTop())
2872 HazardRec->AdvanceCycle();
2873 else
2874 HazardRec->RecedeCycle();
2875 }
2876 }
2877 CheckPending = true;
2878 IsResourceLimited =
2879 checkResourceLimit(LFactor: SchedModel->getLatencyFactor(), Count: getCriticalCount(),
2880 Latency: getScheduledLatency(), AfterSchedNode: true);
2881
2882 LLVM_DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName()
2883 << '\n');
2884}
2885
2886void SchedBoundary::incExecutedResources(unsigned PIdx, unsigned Count) {
2887 ExecutedResCounts[PIdx] += Count;
2888 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
2889 MaxExecutedResCount = ExecutedResCounts[PIdx];
2890}
2891
2892/// Add the given processor resource to this scheduled zone.
2893///
2894/// \param ReleaseAtCycle indicates the number of consecutive (non-pipelined)
2895/// cycles during which this resource is released.
2896///
2897/// \param AcquireAtCycle indicates the number of consecutive (non-pipelined)
2898/// cycles at which the resource is aquired after issue (assuming no stalls).
2899///
2900/// \return the next cycle at which the instruction may execute without
2901/// oversubscribing resources.
2902unsigned SchedBoundary::countResource(const MCSchedClassDesc *SC, unsigned PIdx,
2903 unsigned ReleaseAtCycle,
2904 unsigned NextCycle,
2905 unsigned AcquireAtCycle) {
2906 unsigned Factor = SchedModel->getResourceFactor(ResIdx: PIdx);
2907 unsigned Count = Factor * (ReleaseAtCycle- AcquireAtCycle);
2908 LLVM_DEBUG(dbgs() << " " << SchedModel->getResourceName(PIdx) << " +"
2909 << ReleaseAtCycle << "x" << Factor << "u\n");
2910
2911 // Update Executed resources counts.
2912 incExecutedResources(PIdx, Count);
2913 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");
2914 Rem->RemainingCounts[PIdx] -= Count;
2915
2916 // Check if this resource exceeds the current critical resource. If so, it
2917 // becomes the critical resource.
2918 if (ZoneCritResIdx != PIdx && (getResourceCount(ResIdx: PIdx) > getCriticalCount())) {
2919 ZoneCritResIdx = PIdx;
2920 LLVM_DEBUG(dbgs() << " *** Critical resource "
2921 << SchedModel->getResourceName(PIdx) << ": "
2922 << getResourceCount(PIdx) / SchedModel->getLatencyFactor()
2923 << "c\n");
2924 }
2925 // For reserved resources, record the highest cycle using the resource.
2926 unsigned NextAvailable, InstanceIdx;
2927 std::tie(args&: NextAvailable, args&: InstanceIdx) =
2928 getNextResourceCycle(SC, PIdx, ReleaseAtCycle, AcquireAtCycle);
2929 if (NextAvailable > CurrCycle) {
2930 LLVM_DEBUG(dbgs() << " Resource conflict: "
2931 << SchedModel->getResourceName(PIdx)
2932 << '[' << InstanceIdx - ReservedCyclesIndex[PIdx] << ']'
2933 << " reserved until @" << NextAvailable << "\n");
2934 }
2935 return NextAvailable;
2936}
2937
2938/// Move the boundary of scheduled code by one SUnit.
2939void SchedBoundary::bumpNode(SUnit *SU) {
2940 // checkHazard should prevent scheduling multiple instructions per cycle that
2941 // exceed the issue width.
2942 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
2943 unsigned IncMOps = SchedModel->getNumMicroOps(MI: SU->getInstr());
2944 assert(
2945 (CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) &&
2946 "Cannot schedule this instruction's MicroOps in the current cycle.");
2947
2948 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
2949 LLVM_DEBUG(dbgs() << " Ready @" << ReadyCycle << "c\n");
2950
2951 unsigned NextCycle = CurrCycle;
2952 switch (SchedModel->getMicroOpBufferSize()) {
2953 case 0:
2954 assert(ReadyCycle <= CurrCycle && "Broken PendingQueue");
2955 break;
2956 case 1:
2957 if (ReadyCycle > NextCycle) {
2958 NextCycle = ReadyCycle;
2959 LLVM_DEBUG(dbgs() << " *** Stall until: " << ReadyCycle << "\n");
2960 }
2961 break;
2962 default:
2963 // We don't currently model the OOO reorder buffer, so consider all
2964 // scheduled MOps to be "retired". We do loosely model in-order resource
2965 // latency. If this instruction uses an in-order resource, account for any
2966 // likely stall cycles.
2967 if (SU->isUnbuffered && ReadyCycle > NextCycle)
2968 NextCycle = ReadyCycle;
2969 break;
2970 }
2971 RetiredMOps += IncMOps;
2972
2973 // Update resource counts and critical resource.
2974 if (SchedModel->hasInstrSchedModel()) {
2975 unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor();
2976 assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted");
2977 Rem->RemIssueCount -= DecRemIssue;
2978 if (ZoneCritResIdx) {
2979 // Scale scheduled micro-ops for comparing with the critical resource.
2980 unsigned ScaledMOps =
2981 RetiredMOps * SchedModel->getMicroOpFactor();
2982
2983 // If scaled micro-ops are now more than the previous critical resource by
2984 // a full cycle, then micro-ops issue becomes critical.
2985 if ((int)(ScaledMOps - getResourceCount(ResIdx: ZoneCritResIdx))
2986 >= (int)SchedModel->getLatencyFactor()) {
2987 ZoneCritResIdx = 0;
2988 LLVM_DEBUG(dbgs() << " *** Critical resource NumMicroOps: "
2989 << ScaledMOps / SchedModel->getLatencyFactor()
2990 << "c\n");
2991 }
2992 }
2993 for (TargetSchedModel::ProcResIter
2994 PI = SchedModel->getWriteProcResBegin(SC),
2995 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2996 unsigned RCycle =
2997 countResource(SC, PIdx: PI->ProcResourceIdx, ReleaseAtCycle: PI->ReleaseAtCycle, NextCycle,
2998 AcquireAtCycle: PI->AcquireAtCycle);
2999 if (RCycle > NextCycle)
3000 NextCycle = RCycle;
3001 }
3002 if (SU->hasReservedResource) {
3003 // For reserved resources, record the highest cycle using the resource.
3004 // For top-down scheduling, this is the cycle in which we schedule this
3005 // instruction plus the number of cycles the operations reserves the
3006 // resource. For bottom-up is it simply the instruction's cycle.
3007 for (TargetSchedModel::ProcResIter
3008 PI = SchedModel->getWriteProcResBegin(SC),
3009 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
3010 unsigned PIdx = PI->ProcResourceIdx;
3011 if (SchedModel->getResourceBufferSize(PIdx) == 0) {
3012
3013 if (SchedModel && SchedModel->enableIntervals()) {
3014 unsigned ReservedUntil, InstanceIdx;
3015 std::tie(args&: ReservedUntil, args&: InstanceIdx) = getNextResourceCycle(
3016 SC, PIdx, ReleaseAtCycle: PI->ReleaseAtCycle, AcquireAtCycle: PI->AcquireAtCycle);
3017 if (isTop()) {
3018 ReservedResourceSegments[InstanceIdx].add(
3019 A: ResourceSegments::getResourceIntervalTop(
3020 C: NextCycle, AcquireAtCycle: PI->AcquireAtCycle, ReleaseAtCycle: PI->ReleaseAtCycle),
3021 CutOff: MIResourceCutOff);
3022 } else {
3023 ReservedResourceSegments[InstanceIdx].add(
3024 A: ResourceSegments::getResourceIntervalBottom(
3025 C: NextCycle, AcquireAtCycle: PI->AcquireAtCycle, ReleaseAtCycle: PI->ReleaseAtCycle),
3026 CutOff: MIResourceCutOff);
3027 }
3028 } else {
3029
3030 unsigned ReservedUntil, InstanceIdx;
3031 std::tie(args&: ReservedUntil, args&: InstanceIdx) = getNextResourceCycle(
3032 SC, PIdx, ReleaseAtCycle: PI->ReleaseAtCycle, AcquireAtCycle: PI->AcquireAtCycle);
3033 if (isTop()) {
3034 ReservedCycles[InstanceIdx] =
3035 std::max(a: ReservedUntil, b: NextCycle + PI->ReleaseAtCycle);
3036 } else
3037 ReservedCycles[InstanceIdx] = NextCycle;
3038 }
3039 }
3040 }
3041 }
3042 }
3043 // Update ExpectedLatency and DependentLatency.
3044 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
3045 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
3046 if (SU->getDepth() > TopLatency) {
3047 TopLatency = SU->getDepth();
3048 LLVM_DEBUG(dbgs() << " " << Available.getName() << " TopLatency SU("
3049 << SU->NodeNum << ") " << TopLatency << "c\n");
3050 }
3051 if (SU->getHeight() > BotLatency) {
3052 BotLatency = SU->getHeight();
3053 LLVM_DEBUG(dbgs() << " " << Available.getName() << " BotLatency SU("
3054 << SU->NodeNum << ") " << BotLatency << "c\n");
3055 }
3056 // If we stall for any reason, bump the cycle.
3057 if (NextCycle > CurrCycle)
3058 bumpCycle(NextCycle);
3059 else
3060 // After updating ZoneCritResIdx and ExpectedLatency, check if we're
3061 // resource limited. If a stall occurred, bumpCycle does this.
3062 IsResourceLimited =
3063 checkResourceLimit(LFactor: SchedModel->getLatencyFactor(), Count: getCriticalCount(),
3064 Latency: getScheduledLatency(), AfterSchedNode: true);
3065
3066 // Update the reservation table.
3067 if (HazardRec->isEnabled()) {
3068 if (!isTop() && SU->isCall) {
3069 // Calls are scheduled with their preceding instructions. For bottom-up
3070 // scheduling, clear the pipeline state before emitting.
3071 HazardRec->Reset();
3072 }
3073 HazardRec->EmitInstruction(SU);
3074 // Scheduling an instruction may have made pending instructions available.
3075 CheckPending = true;
3076 }
3077
3078 // Update CurrMOps after calling bumpCycle to handle stalls, since bumpCycle
3079 // resets CurrMOps. Loop to handle instructions with more MOps than issue in
3080 // one cycle. Since we commonly reach the max MOps here, opportunistically
3081 // bump the cycle to avoid uselessly checking everything in the readyQ.
3082 CurrMOps += IncMOps;
3083
3084 // Bump the cycle count for issue group constraints.
3085 // This must be done after NextCycle has been adjust for all other stalls.
3086 // Calling bumpCycle(X) will reduce CurrMOps by one issue group and set
3087 // currCycle to X.
3088 if ((isTop() && SchedModel->mustEndGroup(MI: SU->getInstr())) ||
3089 (!isTop() && SchedModel->mustBeginGroup(MI: SU->getInstr()))) {
3090 LLVM_DEBUG(dbgs() << " Bump cycle to " << (isTop() ? "end" : "begin")
3091 << " group\n");
3092 bumpCycle(NextCycle: ++NextCycle);
3093 }
3094
3095 while (CurrMOps >= SchedModel->getIssueWidth()) {
3096 LLVM_DEBUG(dbgs() << " *** Max MOps " << CurrMOps << " at cycle "
3097 << CurrCycle << '\n');
3098 bumpCycle(NextCycle: ++NextCycle);
3099 }
3100 LLVM_DEBUG(dumpScheduledState());
3101}
3102
3103/// Release pending ready nodes in to the available queue. This makes them
3104/// visible to heuristics.
3105void SchedBoundary::releasePending() {
3106 // If the available queue is empty, it is safe to reset MinReadyCycle.
3107 if (Available.empty())
3108 MinReadyCycle = std::numeric_limits<unsigned>::max();
3109
3110 // Check to see if any of the pending instructions are ready to issue. If
3111 // so, add them to the available queue.
3112 for (unsigned I = 0, E = Pending.size(); I < E; ++I) {
3113 SUnit *SU = *(Pending.begin() + I);
3114 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
3115
3116 LLVM_DEBUG(dbgs() << "Checking pending node SU(" << SU->NodeNum << ")\n");
3117
3118 if (ReadyCycle < MinReadyCycle)
3119 MinReadyCycle = ReadyCycle;
3120
3121 if (Available.size() >= ReadyListLimit)
3122 break;
3123
3124 releaseNode(SU, ReadyCycle, InPQueue: true, Idx: I);
3125 if (E != Pending.size()) {
3126 --I;
3127 --E;
3128 }
3129 }
3130 CheckPending = false;
3131}
3132
3133/// Remove SU from the ready set for this boundary.
3134void SchedBoundary::removeReady(SUnit *SU) {
3135 if (Available.isInQueue(SU))
3136 Available.remove(I: Available.find(SU));
3137 else {
3138 assert(Pending.isInQueue(SU) && "bad ready count");
3139 Pending.remove(I: Pending.find(SU));
3140 }
3141}
3142
3143/// If this queue only has one ready candidate, return it. As a side effect,
3144/// defer any nodes that now hit a hazard, and advance the cycle until at least
3145/// one node is ready. If multiple instructions are ready, return NULL.
3146SUnit *SchedBoundary::pickOnlyChoice() {
3147 if (CheckPending)
3148 releasePending();
3149
3150 // Defer any ready instrs that now have a hazard.
3151 for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) {
3152 if (checkHazard(SU: *I)) {
3153 Pending.push(SU: *I);
3154 I = Available.remove(I);
3155 continue;
3156 }
3157 ++I;
3158 }
3159 for (unsigned i = 0; Available.empty(); ++i) {
3160// FIXME: Re-enable assert once PR20057 is resolved.
3161// assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedStall) &&
3162// "permanent hazard");
3163 (void)i;
3164 bumpCycle(NextCycle: CurrCycle + 1);
3165 releasePending();
3166 }
3167
3168 LLVM_DEBUG(Pending.dump());
3169 LLVM_DEBUG(Available.dump());
3170
3171 if (Available.size() == 1)
3172 return *Available.begin();
3173 return nullptr;
3174}
3175
3176#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3177
3178/// Dump the content of the \ref ReservedCycles vector for the
3179/// resources that are used in the basic block.
3180///
3181LLVM_DUMP_METHOD void SchedBoundary::dumpReservedCycles() const {
3182 if (!SchedModel->hasInstrSchedModel())
3183 return;
3184
3185 unsigned ResourceCount = SchedModel->getNumProcResourceKinds();
3186 unsigned StartIdx = 0;
3187
3188 for (unsigned ResIdx = 0; ResIdx < ResourceCount; ++ResIdx) {
3189 const unsigned NumUnits = SchedModel->getProcResource(ResIdx)->NumUnits;
3190 std::string ResName = SchedModel->getResourceName(ResIdx);
3191 for (unsigned UnitIdx = 0; UnitIdx < NumUnits; ++UnitIdx) {
3192 dbgs() << ResName << "(" << UnitIdx << ") = ";
3193 if (SchedModel && SchedModel->enableIntervals()) {
3194 if (ReservedResourceSegments.count(StartIdx + UnitIdx))
3195 dbgs() << ReservedResourceSegments.at(StartIdx + UnitIdx);
3196 else
3197 dbgs() << "{ }\n";
3198 } else
3199 dbgs() << ReservedCycles[StartIdx + UnitIdx] << "\n";
3200 }
3201 StartIdx += NumUnits;
3202 }
3203}
3204
3205// This is useful information to dump after bumpNode.
3206// Note that the Queue contents are more useful before pickNodeFromQueue.
3207LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState() const {
3208 unsigned ResFactor;
3209 unsigned ResCount;
3210 if (ZoneCritResIdx) {
3211 ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx);
3212 ResCount = getResourceCount(ZoneCritResIdx);
3213 } else {
3214 ResFactor = SchedModel->getMicroOpFactor();
3215 ResCount = RetiredMOps * ResFactor;
3216 }
3217 unsigned LFactor = SchedModel->getLatencyFactor();
3218 dbgs() << Available.getName() << " @" << CurrCycle << "c\n"
3219 << " Retired: " << RetiredMOps;
3220 dbgs() << "\n Executed: " << getExecutedCount() / LFactor << "c";
3221 dbgs() << "\n Critical: " << ResCount / LFactor << "c, "
3222 << ResCount / ResFactor << " "
3223 << SchedModel->getResourceName(ZoneCritResIdx)
3224 << "\n ExpectedLatency: " << ExpectedLatency << "c\n"
3225 << (IsResourceLimited ? " - Resource" : " - Latency")
3226 << " limited.\n";
3227 if (MISchedDumpReservedCycles)
3228 dumpReservedCycles();
3229}
3230#endif
3231
3232//===----------------------------------------------------------------------===//
3233// GenericScheduler - Generic implementation of MachineSchedStrategy.
3234//===----------------------------------------------------------------------===//
3235
3236void GenericSchedulerBase::SchedCandidate::
3237initResourceDelta(const ScheduleDAGMI *DAG,
3238 const TargetSchedModel *SchedModel) {
3239 if (!Policy.ReduceResIdx && !Policy.DemandResIdx)
3240 return;
3241
3242 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
3243 for (TargetSchedModel::ProcResIter
3244 PI = SchedModel->getWriteProcResBegin(SC),
3245 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
3246 if (PI->ProcResourceIdx == Policy.ReduceResIdx)
3247 ResDelta.CritResources += PI->ReleaseAtCycle;
3248 if (PI->ProcResourceIdx == Policy.DemandResIdx)
3249 ResDelta.DemandedResources += PI->ReleaseAtCycle;
3250 }
3251}
3252
3253/// Returns true if the current cycle plus remaning latency is greater than
3254/// the critical path in the scheduling region.
3255bool GenericSchedulerBase::shouldReduceLatency(const CandPolicy &Policy,
3256 SchedBoundary &CurrZone,
3257 bool ComputeRemLatency,
3258 unsigned &RemLatency) const {
3259 // The current cycle is already greater than the critical path, so we are
3260 // already latency limited and don't need to compute the remaining latency.
3261 if (CurrZone.getCurrCycle() > Rem.CriticalPath)
3262 return true;
3263
3264 // If we haven't scheduled anything yet, then we aren't latency limited.
3265 if (CurrZone.getCurrCycle() == 0)
3266 return false;
3267
3268 if (ComputeRemLatency)
3269 RemLatency = computeRemLatency(CurrZone);
3270
3271 return RemLatency + CurrZone.getCurrCycle() > Rem.CriticalPath;
3272}
3273
3274/// Set the CandPolicy given a scheduling zone given the current resources and
3275/// latencies inside and outside the zone.
3276void GenericSchedulerBase::setPolicy(CandPolicy &Policy, bool IsPostRA,
3277 SchedBoundary &CurrZone,
3278 SchedBoundary *OtherZone) {
3279 // Apply preemptive heuristics based on the total latency and resources
3280 // inside and outside this zone. Potential stalls should be considered before
3281 // following this policy.
3282
3283 // Compute the critical resource outside the zone.
3284 unsigned OtherCritIdx = 0;
3285 unsigned OtherCount =
3286 OtherZone ? OtherZone->getOtherResourceCount(OtherCritIdx) : 0;
3287
3288 bool OtherResLimited = false;
3289 unsigned RemLatency = 0;
3290 bool RemLatencyComputed = false;
3291 if (SchedModel->hasInstrSchedModel() && OtherCount != 0) {
3292 RemLatency = computeRemLatency(CurrZone);
3293 RemLatencyComputed = true;
3294 OtherResLimited = checkResourceLimit(LFactor: SchedModel->getLatencyFactor(),
3295 Count: OtherCount, Latency: RemLatency, AfterSchedNode: false);
3296 }
3297
3298 // Schedule aggressively for latency in PostRA mode. We don't check for
3299 // acyclic latency during PostRA, and highly out-of-order processors will
3300 // skip PostRA scheduling.
3301 if (!OtherResLimited &&
3302 (IsPostRA || shouldReduceLatency(Policy, CurrZone, ComputeRemLatency: !RemLatencyComputed,
3303 RemLatency))) {
3304 Policy.ReduceLatency |= true;
3305 LLVM_DEBUG(dbgs() << " " << CurrZone.Available.getName()
3306 << " RemainingLatency " << RemLatency << " + "
3307 << CurrZone.getCurrCycle() << "c > CritPath "
3308 << Rem.CriticalPath << "\n");
3309 }
3310 // If the same resource is limiting inside and outside the zone, do nothing.
3311 if (CurrZone.getZoneCritResIdx() == OtherCritIdx)
3312 return;
3313
3314 LLVM_DEBUG(if (CurrZone.isResourceLimited()) {
3315 dbgs() << " " << CurrZone.Available.getName() << " ResourceLimited: "
3316 << SchedModel->getResourceName(CurrZone.getZoneCritResIdx()) << "\n";
3317 } if (OtherResLimited) dbgs()
3318 << " RemainingLimit: "
3319 << SchedModel->getResourceName(OtherCritIdx) << "\n";
3320 if (!CurrZone.isResourceLimited() && !OtherResLimited) dbgs()
3321 << " Latency limited both directions.\n");
3322
3323 if (CurrZone.isResourceLimited() && !Policy.ReduceResIdx)
3324 Policy.ReduceResIdx = CurrZone.getZoneCritResIdx();
3325
3326 if (OtherResLimited)
3327 Policy.DemandResIdx = OtherCritIdx;
3328}
3329
3330#ifndef NDEBUG
3331const char *GenericSchedulerBase::getReasonStr(
3332 GenericSchedulerBase::CandReason Reason) {
3333 // clang-format off
3334 switch (Reason) {
3335 case NoCand: return "NOCAND ";
3336 case Only1: return "ONLY1 ";
3337 case PhysReg: return "PHYS-REG ";
3338 case RegExcess: return "REG-EXCESS";
3339 case RegCritical: return "REG-CRIT ";
3340 case Stall: return "STALL ";
3341 case Cluster: return "CLUSTER ";
3342 case Weak: return "WEAK ";
3343 case RegMax: return "REG-MAX ";
3344 case ResourceReduce: return "RES-REDUCE";
3345 case ResourceDemand: return "RES-DEMAND";
3346 case TopDepthReduce: return "TOP-DEPTH ";
3347 case TopPathReduce: return "TOP-PATH ";
3348 case BotHeightReduce:return "BOT-HEIGHT";
3349 case BotPathReduce: return "BOT-PATH ";
3350 case NodeOrder: return "ORDER ";
3351 case FirstValid: return "FIRST ";
3352 };
3353 // clang-format on
3354 llvm_unreachable("Unknown reason!");
3355}
3356
3357void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) {
3358 PressureChange P;
3359 unsigned ResIdx = 0;
3360 unsigned Latency = 0;
3361 switch (Cand.Reason) {
3362 default:
3363 break;
3364 case RegExcess:
3365 P = Cand.RPDelta.Excess;
3366 break;
3367 case RegCritical:
3368 P = Cand.RPDelta.CriticalMax;
3369 break;
3370 case RegMax:
3371 P = Cand.RPDelta.CurrentMax;
3372 break;
3373 case ResourceReduce:
3374 ResIdx = Cand.Policy.ReduceResIdx;
3375 break;
3376 case ResourceDemand:
3377 ResIdx = Cand.Policy.DemandResIdx;
3378 break;
3379 case TopDepthReduce:
3380 Latency = Cand.SU->getDepth();
3381 break;
3382 case TopPathReduce:
3383 Latency = Cand.SU->getHeight();
3384 break;
3385 case BotHeightReduce:
3386 Latency = Cand.SU->getHeight();
3387 break;
3388 case BotPathReduce:
3389 Latency = Cand.SU->getDepth();
3390 break;
3391 }
3392 dbgs() << " Cand SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);
3393 if (P.isValid())
3394 dbgs() << " " << TRI->getRegPressureSetName(P.getPSet())
3395 << ":" << P.getUnitInc() << " ";
3396 else
3397 dbgs() << " ";
3398 if (ResIdx)
3399 dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";
3400 else
3401 dbgs() << " ";
3402 if (Latency)
3403 dbgs() << " " << Latency << " cycles ";
3404 else
3405 dbgs() << " ";
3406 dbgs() << '\n';
3407}
3408#endif
3409
3410/// Compute remaining latency. We need this both to determine whether the
3411/// overall schedule has become latency-limited and whether the instructions
3412/// outside this zone are resource or latency limited.
3413///
3414/// The "dependent" latency is updated incrementally during scheduling as the
3415/// max height/depth of scheduled nodes minus the cycles since it was
3416/// scheduled:
3417/// DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone
3418///
3419/// The "independent" latency is the max ready queue depth:
3420/// ILat = max N.depth for N in Available|Pending
3421///
3422/// RemainingLatency is the greater of independent and dependent latency.
3423///
3424/// These computations are expensive, especially in DAGs with many edges, so
3425/// only do them if necessary.
3426unsigned llvm::computeRemLatency(SchedBoundary &CurrZone) {
3427 unsigned RemLatency = CurrZone.getDependentLatency();
3428 RemLatency = std::max(a: RemLatency,
3429 b: CurrZone.findMaxLatency(ReadySUs: CurrZone.Available.elements()));
3430 RemLatency = std::max(a: RemLatency,
3431 b: CurrZone.findMaxLatency(ReadySUs: CurrZone.Pending.elements()));
3432 return RemLatency;
3433}
3434
3435/// Return true if this heuristic determines order.
3436/// TODO: Consider refactor return type of these functions as integer or enum,
3437/// as we may need to differentiate whether TryCand is better than Cand.
3438bool llvm::tryLess(int TryVal, int CandVal,
3439 GenericSchedulerBase::SchedCandidate &TryCand,
3440 GenericSchedulerBase::SchedCandidate &Cand,
3441 GenericSchedulerBase::CandReason Reason) {
3442 if (TryVal < CandVal) {
3443 TryCand.Reason = Reason;
3444 return true;
3445 }
3446 if (TryVal > CandVal) {
3447 if (Cand.Reason > Reason)
3448 Cand.Reason = Reason;
3449 return true;
3450 }
3451 return false;
3452}
3453
3454bool llvm::tryGreater(int TryVal, int CandVal,
3455 GenericSchedulerBase::SchedCandidate &TryCand,
3456 GenericSchedulerBase::SchedCandidate &Cand,
3457 GenericSchedulerBase::CandReason Reason) {
3458 if (TryVal > CandVal) {
3459 TryCand.Reason = Reason;
3460 return true;
3461 }
3462 if (TryVal < CandVal) {
3463 if (Cand.Reason > Reason)
3464 Cand.Reason = Reason;
3465 return true;
3466 }
3467 return false;
3468}
3469
3470bool llvm::tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
3471 GenericSchedulerBase::SchedCandidate &Cand,
3472 SchedBoundary &Zone) {
3473 if (Zone.isTop()) {
3474 // Prefer the candidate with the lesser depth, but only if one of them has
3475 // depth greater than the total latency scheduled so far, otherwise either
3476 // of them could be scheduled now with no stall.
3477 if (std::max(a: TryCand.SU->getDepth(), b: Cand.SU->getDepth()) >
3478 Zone.getScheduledLatency()) {
3479 if (tryLess(TryVal: TryCand.SU->getDepth(), CandVal: Cand.SU->getDepth(),
3480 TryCand, Cand, Reason: GenericSchedulerBase::TopDepthReduce))
3481 return true;
3482 }
3483 if (tryGreater(TryVal: TryCand.SU->getHeight(), CandVal: Cand.SU->getHeight(),
3484 TryCand, Cand, Reason: GenericSchedulerBase::TopPathReduce))
3485 return true;
3486 } else {
3487 // Prefer the candidate with the lesser height, but only if one of them has
3488 // height greater than the total latency scheduled so far, otherwise either
3489 // of them could be scheduled now with no stall.
3490 if (std::max(a: TryCand.SU->getHeight(), b: Cand.SU->getHeight()) >
3491 Zone.getScheduledLatency()) {
3492 if (tryLess(TryVal: TryCand.SU->getHeight(), CandVal: Cand.SU->getHeight(),
3493 TryCand, Cand, Reason: GenericSchedulerBase::BotHeightReduce))
3494 return true;
3495 }
3496 if (tryGreater(TryVal: TryCand.SU->getDepth(), CandVal: Cand.SU->getDepth(),
3497 TryCand, Cand, Reason: GenericSchedulerBase::BotPathReduce))
3498 return true;
3499 }
3500 return false;
3501}
3502
3503static void tracePick(GenericSchedulerBase::CandReason Reason, bool IsTop,
3504 bool IsPostRA = false) {
3505 LLVM_DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")
3506 << GenericSchedulerBase::getReasonStr(Reason) << " ["
3507 << (IsPostRA ? "post-RA" : "pre-RA") << "]\n");
3508
3509 if (IsPostRA) {
3510 if (IsTop)
3511 NumTopPostRA++;
3512 else
3513 NumBotPostRA++;
3514
3515 switch (Reason) {
3516 case GenericScheduler::NoCand:
3517 NumNoCandPostRA++;
3518 return;
3519 case GenericScheduler::Only1:
3520 NumOnly1PostRA++;
3521 return;
3522 case GenericScheduler::PhysReg:
3523 NumPhysRegPostRA++;
3524 return;
3525 case GenericScheduler::RegExcess:
3526 NumRegExcessPostRA++;
3527 return;
3528 case GenericScheduler::RegCritical:
3529 NumRegCriticalPostRA++;
3530 return;
3531 case GenericScheduler::Stall:
3532 NumStallPostRA++;
3533 return;
3534 case GenericScheduler::Cluster:
3535 NumClusterPostRA++;
3536 return;
3537 case GenericScheduler::Weak:
3538 NumWeakPostRA++;
3539 return;
3540 case GenericScheduler::RegMax:
3541 NumRegMaxPostRA++;
3542 return;
3543 case GenericScheduler::ResourceReduce:
3544 NumResourceReducePostRA++;
3545 return;
3546 case GenericScheduler::ResourceDemand:
3547 NumResourceDemandPostRA++;
3548 return;
3549 case GenericScheduler::TopDepthReduce:
3550 NumTopDepthReducePostRA++;
3551 return;
3552 case GenericScheduler::TopPathReduce:
3553 NumTopPathReducePostRA++;
3554 return;
3555 case GenericScheduler::BotHeightReduce:
3556 NumBotHeightReducePostRA++;
3557 return;
3558 case GenericScheduler::BotPathReduce:
3559 NumBotPathReducePostRA++;
3560 return;
3561 case GenericScheduler::NodeOrder:
3562 NumNodeOrderPostRA++;
3563 return;
3564 case GenericScheduler::FirstValid:
3565 NumFirstValidPostRA++;
3566 return;
3567 };
3568 } else {
3569 if (IsTop)
3570 NumTopPreRA++;
3571 else
3572 NumBotPreRA++;
3573
3574 switch (Reason) {
3575 case GenericScheduler::NoCand:
3576 NumNoCandPreRA++;
3577 return;
3578 case GenericScheduler::Only1:
3579 NumOnly1PreRA++;
3580 return;
3581 case GenericScheduler::PhysReg:
3582 NumPhysRegPreRA++;
3583 return;
3584 case GenericScheduler::RegExcess:
3585 NumRegExcessPreRA++;
3586 return;
3587 case GenericScheduler::RegCritical:
3588 NumRegCriticalPreRA++;
3589 return;
3590 case GenericScheduler::Stall:
3591 NumStallPreRA++;
3592 return;
3593 case GenericScheduler::Cluster:
3594 NumClusterPreRA++;
3595 return;
3596 case GenericScheduler::Weak:
3597 NumWeakPreRA++;
3598 return;
3599 case GenericScheduler::RegMax:
3600 NumRegMaxPreRA++;
3601 return;
3602 case GenericScheduler::ResourceReduce:
3603 NumResourceReducePreRA++;
3604 return;
3605 case GenericScheduler::ResourceDemand:
3606 NumResourceDemandPreRA++;
3607 return;
3608 case GenericScheduler::TopDepthReduce:
3609 NumTopDepthReducePreRA++;
3610 return;
3611 case GenericScheduler::TopPathReduce:
3612 NumTopPathReducePreRA++;
3613 return;
3614 case GenericScheduler::BotHeightReduce:
3615 NumBotHeightReducePreRA++;
3616 return;
3617 case GenericScheduler::BotPathReduce:
3618 NumBotPathReducePreRA++;
3619 return;
3620 case GenericScheduler::NodeOrder:
3621 NumNodeOrderPreRA++;
3622 return;
3623 case GenericScheduler::FirstValid:
3624 NumFirstValidPreRA++;
3625 return;
3626 };
3627 }
3628 llvm_unreachable("Unknown reason!");
3629}
3630
3631static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand,
3632 bool IsPostRA = false) {
3633 tracePick(Reason: Cand.Reason, IsTop: Cand.AtTop, IsPostRA);
3634}
3635
3636void GenericScheduler::initialize(ScheduleDAGMI *dag) {
3637 assert(dag->hasVRegLiveness() &&
3638 "(PreRA)GenericScheduler needs vreg liveness");
3639 DAG = static_cast<ScheduleDAGMILive*>(dag);
3640 SchedModel = DAG->getSchedModel();
3641 TRI = DAG->TRI;
3642
3643 if (RegionPolicy.ComputeDFSResult)
3644 DAG->computeDFSResult();
3645
3646 Rem.init(DAG, SchedModel);
3647 Top.init(dag: DAG, smodel: SchedModel, rem: &Rem);
3648 Bot.init(dag: DAG, smodel: SchedModel, rem: &Rem);
3649
3650 // Initialize resource counts.
3651
3652 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
3653 // are disabled, then these HazardRecs will be disabled.
3654 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
3655 if (!Top.HazardRec)
3656 Top.HazardRec.reset(p: DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG));
3657 if (!Bot.HazardRec)
3658 Bot.HazardRec.reset(p: DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG));
3659 TopCand.SU = nullptr;
3660 BotCand.SU = nullptr;
3661
3662 TopClusterID = InvalidClusterId;
3663 BotClusterID = InvalidClusterId;
3664}
3665
3666/// Initialize the per-region scheduling policy.
3667void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,
3668 MachineBasicBlock::iterator End,
3669 unsigned NumRegionInstrs) {
3670 const MachineFunction &MF = *Begin->getMF();
3671 const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
3672
3673 // Avoid setting up the register pressure tracker for small regions to save
3674 // compile time. As a rough heuristic, only track pressure when the number of
3675 // schedulable instructions exceeds half the allocatable integer register file
3676 // that is the largest legal integer regiser type.
3677 RegionPolicy.ShouldTrackPressure = true;
3678 for (unsigned VT = MVT::i64; VT > (unsigned)MVT::i1; --VT) {
3679 MVT::SimpleValueType LegalIntVT = (MVT::SimpleValueType)VT;
3680 if (TLI->isTypeLegal(VT: LegalIntVT)) {
3681 unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs(
3682 RC: TLI->getRegClassFor(VT: LegalIntVT));
3683 RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
3684 break;
3685 }
3686 }
3687
3688 // For generic targets, we default to bottom-up, because it's simpler and more
3689 // compile-time optimizations have been implemented in that direction.
3690 RegionPolicy.OnlyBottomUp = true;
3691
3692 // Allow the subtarget to override default policy.
3693 SchedRegion Region(Begin, End, NumRegionInstrs);
3694 MF.getSubtarget().overrideSchedPolicy(Policy&: RegionPolicy, Region);
3695
3696 // After subtarget overrides, apply command line options.
3697 if (!EnableRegPressure) {
3698 RegionPolicy.ShouldTrackPressure = false;
3699 RegionPolicy.ShouldTrackLaneMasks = false;
3700 }
3701
3702 if (PreRADirection == MISched::TopDown) {
3703 RegionPolicy.OnlyTopDown = true;
3704 RegionPolicy.OnlyBottomUp = false;
3705 } else if (PreRADirection == MISched::BottomUp) {
3706 RegionPolicy.OnlyTopDown = false;
3707 RegionPolicy.OnlyBottomUp = true;
3708 } else if (PreRADirection == MISched::Bidirectional) {
3709 RegionPolicy.OnlyBottomUp = false;
3710 RegionPolicy.OnlyTopDown = false;
3711 }
3712
3713 BotIdx = NumRegionInstrs - 1;
3714 this->NumRegionInstrs = NumRegionInstrs;
3715}
3716
3717void GenericScheduler::dumpPolicy() const {
3718 // Cannot completely remove virtual function even in release mode.
3719#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3720 dbgs() << "GenericScheduler RegionPolicy: "
3721 << " ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure
3722 << " OnlyTopDown=" << RegionPolicy.OnlyTopDown
3723 << " OnlyBottomUp=" << RegionPolicy.OnlyBottomUp
3724 << "\n";
3725#endif
3726}
3727
3728/// Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic
3729/// critical path by more cycles than it takes to drain the instruction buffer.
3730/// We estimate an upper bounds on in-flight instructions as:
3731///
3732/// CyclesPerIteration = max( CyclicPath, Loop-Resource-Height )
3733/// InFlightIterations = AcyclicPath / CyclesPerIteration
3734/// InFlightResources = InFlightIterations * LoopResources
3735///
3736/// TODO: Check execution resources in addition to IssueCount.
3737void GenericScheduler::checkAcyclicLatency() {
3738 if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)
3739 return;
3740
3741 // Scaled number of cycles per loop iteration.
3742 unsigned IterCount =
3743 std::max(a: Rem.CyclicCritPath * SchedModel->getLatencyFactor(),
3744 b: Rem.RemIssueCount);
3745 // Scaled acyclic critical path.
3746 unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor();
3747 // InFlightCount = (AcyclicPath / IterCycles) * InstrPerLoop
3748 unsigned InFlightCount =
3749 (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;
3750 unsigned BufferLimit =
3751 SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor();
3752
3753 Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;
3754
3755 LLVM_DEBUG(
3756 dbgs() << "IssueCycles="
3757 << Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c "
3758 << "IterCycles=" << IterCount / SchedModel->getLatencyFactor()
3759 << "c NumIters=" << (AcyclicCount + IterCount - 1) / IterCount
3760 << " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor()
3761 << "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n";
3762 if (Rem.IsAcyclicLatencyLimited) dbgs() << " ACYCLIC LATENCY LIMIT\n");
3763}
3764
3765void GenericScheduler::registerRoots() {
3766 Rem.CriticalPath = DAG->ExitSU.getDepth();
3767
3768 // Some roots may not feed into ExitSU. Check all of them in case.
3769 for (const SUnit *SU : Bot.Available) {
3770 if (SU->getDepth() > Rem.CriticalPath)
3771 Rem.CriticalPath = SU->getDepth();
3772 }
3773 LLVM_DEBUG(dbgs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << '\n');
3774 if (DumpCriticalPathLength) {
3775 errs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << " \n";
3776 }
3777
3778 if (EnableCyclicPath && SchedModel->getMicroOpBufferSize() > 0) {
3779 Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();
3780 checkAcyclicLatency();
3781 }
3782}
3783
3784bool llvm::tryPressure(const PressureChange &TryP, const PressureChange &CandP,
3785 GenericSchedulerBase::SchedCandidate &TryCand,
3786 GenericSchedulerBase::SchedCandidate &Cand,
3787 GenericSchedulerBase::CandReason Reason,
3788 const TargetRegisterInfo *TRI,
3789 const MachineFunction &MF) {
3790 // If one candidate decreases and the other increases, go with it.
3791 // Invalid candidates have UnitInc==0.
3792 if (tryGreater(TryVal: TryP.getUnitInc() < 0, CandVal: CandP.getUnitInc() < 0, TryCand, Cand,
3793 Reason)) {
3794 return true;
3795 }
3796 // Do not compare the magnitude of pressure changes between top and bottom
3797 // boundary.
3798 if (Cand.AtTop != TryCand.AtTop)
3799 return false;
3800
3801 // If both candidates affect the same set in the same boundary, go with the
3802 // smallest increase.
3803 unsigned TryPSet = TryP.getPSetOrMax();
3804 unsigned CandPSet = CandP.getPSetOrMax();
3805 if (TryPSet == CandPSet) {
3806 return tryLess(TryVal: TryP.getUnitInc(), CandVal: CandP.getUnitInc(), TryCand, Cand,
3807 Reason);
3808 }
3809
3810 int TryRank = TryP.isValid() ? TRI->getRegPressureSetScore(MF, PSetID: TryPSet) :
3811 std::numeric_limits<int>::max();
3812
3813 int CandRank = CandP.isValid() ? TRI->getRegPressureSetScore(MF, PSetID: CandPSet) :
3814 std::numeric_limits<int>::max();
3815
3816 // If the candidates are decreasing pressure, reverse priority.
3817 if (TryP.getUnitInc() < 0)
3818 std::swap(a&: TryRank, b&: CandRank);
3819 return tryGreater(TryVal: TryRank, CandVal: CandRank, TryCand, Cand, Reason);
3820}
3821
3822unsigned llvm::getWeakLeft(const SUnit *SU, bool isTop) {
3823 return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft;
3824}
3825
3826/// Minimize physical register live ranges. Regalloc wants them adjacent to
3827/// their physreg def/use.
3828///
3829/// FIXME: This is an unnecessary check on the critical path. Most are root/leaf
3830/// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled
3831/// with the operation that produces or consumes the physreg. We'll do this when
3832/// regalloc has support for parallel copies.
3833int llvm::biasPhysReg(const SUnit *SU, bool isTop, bool BiasPRegsExtra) {
3834 const MachineInstr *MI = SU->getInstr();
3835
3836 if (MI->isCopy()) {
3837 unsigned ScheduledOper = isTop ? 1 : 0;
3838 unsigned UnscheduledOper = isTop ? 0 : 1;
3839 // If we have already scheduled the physreg produce/consumer, immediately
3840 // schedule the copy.
3841 if (MI->getOperand(i: ScheduledOper).getReg().isPhysical())
3842 return 1;
3843 // If the physreg is at the boundary, defer it. Otherwise schedule it
3844 // immediately to free the dependent. We can hoist the copy later.
3845 bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft;
3846 if (MI->getOperand(i: UnscheduledOper).getReg().isPhysical())
3847 return AtBoundary ? -1 : 1;
3848 }
3849
3850 if (MI->isMoveImmediate()) {
3851 // If we have a move immediate and all successors have been assigned, bias
3852 // towards scheduling this later. Make sure all register defs are to
3853 // physical registers.
3854 bool DoBias = true;
3855 for (const MachineOperand &Op : MI->defs()) {
3856 if (Op.isReg() && !Op.getReg().isPhysical()) {
3857 DoBias = false;
3858 break;
3859 }
3860 }
3861
3862 if (DoBias)
3863 return isTop ? -1 : 1;
3864 }
3865
3866 if (BiasPRegsExtra && !isTop && MI->getNumExplicitDefs() == 1)
3867 // Register coalescer will create cases of e.g. Load Address of a frame
3868 // index directly into a physreg.
3869 return MI->getOperand(i: 0).getReg().isPhysical();
3870
3871 return 0;
3872}
3873
3874bool llvm::tryBiasPhysRegs(GenericSchedulerBase::SchedCandidate &TryCand,
3875 GenericSchedulerBase::SchedCandidate &Cand,
3876 SchedBoundary *Zone, bool BiasPRegsExtra) {
3877 int TryCandPRegBias = biasPhysReg(SU: TryCand.SU, isTop: TryCand.AtTop, BiasPRegsExtra);
3878 int CandPRegBias = biasPhysReg(SU: Cand.SU, isTop: Cand.AtTop, BiasPRegsExtra);
3879 if (tryGreater(TryVal: TryCandPRegBias, CandVal: CandPRegBias, TryCand, Cand,
3880 Reason: GenericSchedulerBase::PhysReg))
3881 return true;
3882 if (BiasPRegsExtra && Zone != nullptr && TryCandPRegBias &&
3883 TryCandPRegBias == CandPRegBias) {
3884 // Both biased same way - maintain their input order.
3885 if (Zone->isTop())
3886 tryLess(TryVal: TryCand.SU->NodeNum, CandVal: Cand.SU->NodeNum, TryCand, Cand,
3887 Reason: GenericSchedulerBase::NodeOrder);
3888 else
3889 tryGreater(TryVal: TryCand.SU->NodeNum, CandVal: Cand.SU->NodeNum, TryCand, Cand,
3890 Reason: GenericSchedulerBase::NodeOrder);
3891 return true;
3892 }
3893 return false;
3894}
3895
3896void GenericScheduler::initCandidate(SchedCandidate &Cand, SUnit *SU,
3897 bool AtTop,
3898 const RegPressureTracker &RPTracker,
3899 RegPressureTracker &TempTracker) {
3900 Cand.SU = SU;
3901 Cand.AtTop = AtTop;
3902 if (DAG->isTrackingPressure()) {
3903 if (AtTop) {
3904 TempTracker.getMaxDownwardPressureDelta(
3905 MI: Cand.SU->getInstr(),
3906 Delta&: Cand.RPDelta,
3907 CriticalPSets: DAG->getRegionCriticalPSets(),
3908 MaxPressureLimit: DAG->getRegPressure().MaxSetPressure);
3909 } else {
3910 if (VerifyScheduling) {
3911 TempTracker.getMaxUpwardPressureDelta(
3912 MI: Cand.SU->getInstr(),
3913 PDiff: &DAG->getPressureDiff(SU: Cand.SU),
3914 Delta&: Cand.RPDelta,
3915 CriticalPSets: DAG->getRegionCriticalPSets(),
3916 MaxPressureLimit: DAG->getRegPressure().MaxSetPressure);
3917 } else {
3918 RPTracker.getUpwardPressureDelta(
3919 MI: Cand.SU->getInstr(),
3920 PDiff&: DAG->getPressureDiff(SU: Cand.SU),
3921 Delta&: Cand.RPDelta,
3922 CriticalPSets: DAG->getRegionCriticalPSets(),
3923 MaxPressureLimit: DAG->getRegPressure().MaxSetPressure);
3924 }
3925 }
3926 }
3927 LLVM_DEBUG(if (Cand.RPDelta.Excess.isValid()) dbgs()
3928 << " Try SU(" << Cand.SU->NodeNum << ") "
3929 << TRI->getRegPressureSetName(Cand.RPDelta.Excess.getPSet()) << ":"
3930 << Cand.RPDelta.Excess.getUnitInc() << "\n");
3931}
3932
3933/// Apply a set of heuristics to a new candidate. Heuristics are currently
3934/// hierarchical. This may be more efficient than a graduated cost model because
3935/// we don't need to evaluate all aspects of the model for each node in the
3936/// queue. But it's really done to make the heuristics easier to debug and
3937/// statistically analyze.
3938///
3939/// \param Cand provides the policy and current best candidate.
3940/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
3941/// \param Zone describes the scheduled zone that we are extending, or nullptr
3942/// if Cand is from a different zone than TryCand.
3943/// \return \c true if TryCand is better than Cand (Reason is NOT NoCand)
3944bool GenericScheduler::tryCandidate(SchedCandidate &Cand,
3945 SchedCandidate &TryCand,
3946 SchedBoundary *Zone) const {
3947 // Initialize the candidate if needed.
3948 if (!Cand.isValid()) {
3949 TryCand.Reason = FirstValid;
3950 return true;
3951 }
3952
3953 // Bias PhysReg Defs and copies to their uses and defined respectively.
3954 if (tryBiasPhysRegs(TryCand, Cand, Zone, BiasPRegsExtra: RegionPolicy.BiasPRegsExtra))
3955 return TryCand.Reason != NoCand;
3956
3957 // Avoid exceeding the target's limit.
3958 if (DAG->isTrackingPressure() && tryPressure(TryP: TryCand.RPDelta.Excess,
3959 CandP: Cand.RPDelta.Excess,
3960 TryCand, Cand, Reason: RegExcess, TRI,
3961 MF: DAG->MF))
3962 return TryCand.Reason != NoCand;
3963
3964 // Avoid increasing the max critical pressure in the scheduled region.
3965 if (DAG->isTrackingPressure() && tryPressure(TryP: TryCand.RPDelta.CriticalMax,
3966 CandP: Cand.RPDelta.CriticalMax,
3967 TryCand, Cand, Reason: RegCritical, TRI,
3968 MF: DAG->MF))
3969 return TryCand.Reason != NoCand;
3970
3971 // We only compare a subset of features when comparing nodes between
3972 // Top and Bottom boundary. Some properties are simply incomparable, in many
3973 // other instances we should only override the other boundary if something
3974 // is a clear good pick on one boundary. Skip heuristics that are more
3975 // "tie-breaking" in nature.
3976 bool SameBoundary = Zone != nullptr;
3977 if (SameBoundary) {
3978 // For loops that are acyclic path limited, aggressively schedule for
3979 // latency. Within an single cycle, whenever CurrMOps > 0, allow normal
3980 // heuristics to take precedence.
3981 if (Rem.IsAcyclicLatencyLimited && !Zone->getCurrMOps() &&
3982 tryLatency(TryCand, Cand, Zone&: *Zone))
3983 return TryCand.Reason != NoCand;
3984
3985 // Prioritize instructions that read unbuffered resources by stall cycles.
3986 if (tryLess(TryVal: Zone->getLatencyStallCycles(SU: TryCand.SU),
3987 CandVal: Zone->getLatencyStallCycles(SU: Cand.SU), TryCand, Cand, Reason: Stall))
3988 return TryCand.Reason != NoCand;
3989 }
3990
3991 // Keep clustered nodes together to encourage downstream peephole
3992 // optimizations which may reduce resource requirements.
3993 //
3994 // This is a best effort to set things up for a post-RA pass. Optimizations
3995 // like generating loads of multiple registers should ideally be done within
3996 // the scheduler pass by combining the loads during DAG postprocessing.
3997 unsigned CandZoneCluster = Cand.AtTop ? TopClusterID : BotClusterID;
3998 unsigned TryCandZoneCluster = TryCand.AtTop ? TopClusterID : BotClusterID;
3999 bool CandIsClusterSucc =
4000 isTheSameCluster(A: CandZoneCluster, B: Cand.SU->ParentClusterIdx);
4001 bool TryCandIsClusterSucc =
4002 isTheSameCluster(A: TryCandZoneCluster, B: TryCand.SU->ParentClusterIdx);
4003
4004 if (tryGreater(TryVal: TryCandIsClusterSucc, CandVal: CandIsClusterSucc, TryCand, Cand,
4005 Reason: Cluster))
4006 return TryCand.Reason != NoCand;
4007
4008 if (SameBoundary) {
4009 // Weak edges are for clustering and other constraints.
4010 if (tryLess(TryVal: getWeakLeft(SU: TryCand.SU, isTop: TryCand.AtTop),
4011 CandVal: getWeakLeft(SU: Cand.SU, isTop: Cand.AtTop),
4012 TryCand, Cand, Reason: Weak))
4013 return TryCand.Reason != NoCand;
4014 }
4015
4016 // Avoid increasing the max pressure of the entire region.
4017 if (DAG->isTrackingPressure() && tryPressure(TryP: TryCand.RPDelta.CurrentMax,
4018 CandP: Cand.RPDelta.CurrentMax,
4019 TryCand, Cand, Reason: RegMax, TRI,
4020 MF: DAG->MF))
4021 return TryCand.Reason != NoCand;
4022
4023 if (SameBoundary) {
4024 // Avoid critical resource consumption and balance the schedule.
4025 TryCand.initResourceDelta(DAG, SchedModel);
4026 if (tryLess(TryVal: TryCand.ResDelta.CritResources, CandVal: Cand.ResDelta.CritResources,
4027 TryCand, Cand, Reason: ResourceReduce))
4028 return TryCand.Reason != NoCand;
4029 if (tryGreater(TryVal: TryCand.ResDelta.DemandedResources,
4030 CandVal: Cand.ResDelta.DemandedResources,
4031 TryCand, Cand, Reason: ResourceDemand))
4032 return TryCand.Reason != NoCand;
4033
4034 // Avoid serializing long latency dependence chains.
4035 // For acyclic path limited loops, latency was already checked above.
4036 if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency &&
4037 !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, Zone&: *Zone))
4038 return TryCand.Reason != NoCand;
4039
4040 // Fall through to original instruction order.
4041 if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)
4042 || (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
4043 TryCand.Reason = NodeOrder;
4044 return true;
4045 }
4046 }
4047
4048 return false;
4049}
4050
4051/// Pick the best candidate from the queue.
4052///
4053/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
4054/// DAG building. To adjust for the current scheduling location we need to
4055/// maintain the number of vreg uses remaining to be top-scheduled.
4056void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
4057 const CandPolicy &ZonePolicy,
4058 const RegPressureTracker &RPTracker,
4059 SchedCandidate &Cand) {
4060 // getMaxPressureDelta temporarily modifies the tracker.
4061 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
4062
4063 ReadyQueue &Q = Zone.Available;
4064 for (SUnit *SU : Q) {
4065
4066 SchedCandidate TryCand(ZonePolicy);
4067 initCandidate(Cand&: TryCand, SU, AtTop: Zone.isTop(), RPTracker, TempTracker);
4068 // Pass SchedBoundary only when comparing nodes from the same boundary.
4069 SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
4070 if (tryCandidate(Cand, TryCand, Zone: ZoneArg)) {
4071 // Initialize resource delta if needed in case future heuristics query it.
4072 if (TryCand.ResDelta == SchedResourceDelta())
4073 TryCand.initResourceDelta(DAG, SchedModel);
4074 Cand.setBest(TryCand);
4075 LLVM_DEBUG(traceCandidate(Cand));
4076 }
4077 }
4078}
4079
4080/// Pick the best candidate node from either the top or bottom queue.
4081SUnit *GenericScheduler::pickNodeBidirectional(bool &IsTopNode) {
4082 // Schedule as far as possible in the direction of no choice. This is most
4083 // efficient, but also provides the best heuristics for CriticalPSets.
4084 if (SUnit *SU = Bot.pickOnlyChoice()) {
4085 IsTopNode = false;
4086 tracePick(Reason: Only1, /*IsTopNode=*/IsTop: false);
4087 return SU;
4088 }
4089 if (SUnit *SU = Top.pickOnlyChoice()) {
4090 IsTopNode = true;
4091 tracePick(Reason: Only1, /*IsTopNode=*/IsTop: true);
4092 return SU;
4093 }
4094 // Set the bottom-up policy based on the state of the current bottom zone and
4095 // the instructions outside the zone, including the top zone.
4096 CandPolicy BotPolicy;
4097 setPolicy(Policy&: BotPolicy, /*IsPostRA=*/false, CurrZone&: Bot, OtherZone: &Top);
4098 // Set the top-down policy based on the state of the current top zone and
4099 // the instructions outside the zone, including the bottom zone.
4100 CandPolicy TopPolicy;
4101 setPolicy(Policy&: TopPolicy, /*IsPostRA=*/false, CurrZone&: Top, OtherZone: &Bot);
4102
4103 // See if BotCand is still valid (because we previously scheduled from Top).
4104 LLVM_DEBUG(dbgs() << "Picking from Bot:\n");
4105 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
4106 BotCand.Policy != BotPolicy) {
4107 BotCand.reset(NewPolicy: CandPolicy());
4108 pickNodeFromQueue(Zone&: Bot, ZonePolicy: BotPolicy, RPTracker: DAG->getBotRPTracker(), Cand&: BotCand);
4109 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
4110 } else {
4111 LLVM_DEBUG(traceCandidate(BotCand));
4112#ifndef NDEBUG
4113 if (VerifyScheduling) {
4114 SchedCandidate TCand;
4115 TCand.reset(CandPolicy());
4116 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);
4117 assert(TCand.SU == BotCand.SU &&
4118 "Last pick result should correspond to re-picking right now");
4119 }
4120#endif
4121 }
4122
4123 // Check if the top Q has a better candidate.
4124 LLVM_DEBUG(dbgs() << "Picking from Top:\n");
4125 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
4126 TopCand.Policy != TopPolicy) {
4127 TopCand.reset(NewPolicy: CandPolicy());
4128 pickNodeFromQueue(Zone&: Top, ZonePolicy: TopPolicy, RPTracker: DAG->getTopRPTracker(), Cand&: TopCand);
4129 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
4130 } else {
4131 LLVM_DEBUG(traceCandidate(TopCand));
4132#ifndef NDEBUG
4133 if (VerifyScheduling) {
4134 SchedCandidate TCand;
4135 TCand.reset(CandPolicy());
4136 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);
4137 assert(TCand.SU == TopCand.SU &&
4138 "Last pick result should correspond to re-picking right now");
4139 }
4140#endif
4141 }
4142
4143 // Pick best from BotCand and TopCand.
4144 assert(BotCand.isValid());
4145 assert(TopCand.isValid());
4146 SchedCandidate Cand = BotCand;
4147 TopCand.Reason = NoCand;
4148 if (tryCandidate(Cand, TryCand&: TopCand, Zone: nullptr)) {
4149 Cand.setBest(TopCand);
4150 LLVM_DEBUG(traceCandidate(Cand));
4151 }
4152
4153 IsTopNode = Cand.AtTop;
4154 tracePick(Cand);
4155 return Cand.SU;
4156}
4157
4158/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
4159SUnit *GenericScheduler::pickNode(bool &IsTopNode) {
4160 if (DAG->top() == DAG->bottom()) {
4161 assert(Top.Available.empty() && Top.Pending.empty() &&
4162 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
4163 return nullptr;
4164 }
4165 SUnit *SU;
4166 if (RegionPolicy.OnlyTopDown) {
4167 SU = Top.pickOnlyChoice();
4168 if (!SU) {
4169 CandPolicy NoPolicy;
4170 TopCand.reset(NewPolicy: NoPolicy);
4171 pickNodeFromQueue(Zone&: Top, ZonePolicy: NoPolicy, RPTracker: DAG->getTopRPTracker(), Cand&: TopCand);
4172 assert(TopCand.Reason != NoCand && "failed to find a candidate");
4173 tracePick(Cand: TopCand);
4174 SU = TopCand.SU;
4175 }
4176 IsTopNode = true;
4177 } else if (RegionPolicy.OnlyBottomUp) {
4178 SU = Bot.pickOnlyChoice();
4179 if (!SU) {
4180 CandPolicy NoPolicy;
4181 BotCand.reset(NewPolicy: NoPolicy);
4182 pickNodeFromQueue(Zone&: Bot, ZonePolicy: NoPolicy, RPTracker: DAG->getBotRPTracker(), Cand&: BotCand);
4183 assert(BotCand.Reason != NoCand && "failed to find a candidate");
4184 tracePick(Cand: BotCand);
4185 SU = BotCand.SU;
4186 }
4187 IsTopNode = false;
4188 } else {
4189 SU = pickNodeBidirectional(IsTopNode);
4190 }
4191 assert(!SU->isScheduled && "SUnit scheduled twice.");
4192
4193 // If IsTopNode, then SU is in Top.Available and must be removed. Otherwise,
4194 // if isTopReady(), then SU is in either Top.Available or Top.Pending.
4195 // If !IsTopNode, then SU is in Bot.Available and must be removed. Otherwise,
4196 // if isBottomReady(), then SU is in either Bot.Available or Bot.Pending.
4197 //
4198 // It is coincidental when !IsTopNode && isTopReady or when IsTopNode &&
4199 // isBottomReady. That is, it didn't factor into the decision to choose SU
4200 // because it isTopReady or isBottomReady, respectively. In fact, if the
4201 // RegionPolicy is OnlyTopDown or OnlyBottomUp, then the Bot queues and Top
4202 // queues respectivley contain the original roots and don't get updated when
4203 // picking a node. So if SU isTopReady on a OnlyBottomUp pick, then it was
4204 // because we schduled everything but the top roots. Conversley, if SU
4205 // isBottomReady on OnlyTopDown, then it was because we scheduled everything
4206 // but the bottom roots. If its in a queue even coincidentally, it should be
4207 // removed so it does not get re-picked in a subsequent pickNode call.
4208 if (SU->isTopReady())
4209 Top.removeReady(SU);
4210 if (SU->isBottomReady())
4211 Bot.removeReady(SU);
4212
4213 LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
4214 << *SU->getInstr());
4215
4216 if (IsTopNode) {
4217 if (SU->NodeNum == TopIdx++)
4218 ++NumInstrsInSourceOrderPreRA;
4219 } else {
4220 assert(BotIdx < NumRegionInstrs && "out of bounds");
4221 if (SU->NodeNum == BotIdx--)
4222 ++NumInstrsInSourceOrderPreRA;
4223 }
4224
4225 NumInstrsScheduledPreRA += 1;
4226
4227 return SU;
4228}
4229
4230void GenericScheduler::reschedulePhysReg(SUnit *SU, bool isTop) {
4231 MachineBasicBlock::iterator InsertPos = SU->getInstr();
4232 if (!isTop)
4233 ++InsertPos;
4234 SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs;
4235
4236 // Find already scheduled copies with a single physreg dependence and move
4237 // them just above the scheduled instruction.
4238 for (SDep &Dep : Deps) {
4239 if (Dep.getKind() != SDep::Data || !Dep.getReg().isPhysical())
4240 continue;
4241 SUnit *DepSU = Dep.getSUnit();
4242 if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1)
4243 continue;
4244 MachineInstr *Copy = DepSU->getInstr();
4245 if (!Copy->isCopy() && !Copy->isMoveImmediate())
4246 continue;
4247 LLVM_DEBUG(dbgs() << " Rescheduling physreg copy ";
4248 DAG->dumpNode(*Dep.getSUnit()));
4249 DAG->moveInstruction(MI: Copy, InsertPos);
4250 }
4251}
4252
4253/// Update the scheduler's state after scheduling a node. This is the same node
4254/// that was just returned by pickNode(). However, ScheduleDAGMILive needs to
4255/// update it's state based on the current cycle before MachineSchedStrategy
4256/// does.
4257///
4258/// FIXME: Eventually, we may bundle physreg copies rather than rescheduling
4259/// them here. See comments in biasPhysReg.
4260void GenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
4261 if (IsTopNode) {
4262 SU->TopReadyCycle = std::max(a: SU->TopReadyCycle, b: Top.getCurrCycle());
4263 TopClusterID = SU->ParentClusterIdx;
4264 LLVM_DEBUG({
4265 if (TopClusterID != InvalidClusterId) {
4266 ClusterInfo *TopCluster = DAG->getCluster(TopClusterID);
4267 dbgs() << " Top Cluster: ";
4268 for (auto *N : *TopCluster)
4269 dbgs() << N->NodeNum << '\t';
4270 dbgs() << '\n';
4271 }
4272 });
4273 Top.bumpNode(SU);
4274 if (SU->hasPhysRegUses)
4275 reschedulePhysReg(SU, isTop: true);
4276 } else {
4277 SU->BotReadyCycle = std::max(a: SU->BotReadyCycle, b: Bot.getCurrCycle());
4278 BotClusterID = SU->ParentClusterIdx;
4279 LLVM_DEBUG({
4280 if (BotClusterID != InvalidClusterId) {
4281 ClusterInfo *BotCluster = DAG->getCluster(BotClusterID);
4282 dbgs() << " Bot Cluster: ";
4283 for (auto *N : *BotCluster)
4284 dbgs() << N->NodeNum << '\t';
4285 dbgs() << '\n';
4286 }
4287 });
4288 Bot.bumpNode(SU);
4289 if (SU->hasPhysRegDefs)
4290 reschedulePhysReg(SU, isTop: false);
4291 }
4292}
4293
4294static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) {
4295 return createSchedLive(C);
4296}
4297
4298static MachineSchedRegistry
4299GenericSchedRegistry("converge", "Standard converging scheduler.",
4300 createConvergingSched);
4301
4302//===----------------------------------------------------------------------===//
4303// PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy.
4304//===----------------------------------------------------------------------===//
4305
4306void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) {
4307 DAG = Dag;
4308 SchedModel = DAG->getSchedModel();
4309 TRI = DAG->TRI;
4310
4311 Rem.init(DAG, SchedModel);
4312 Top.init(dag: DAG, smodel: SchedModel, rem: &Rem);
4313 Bot.init(dag: DAG, smodel: SchedModel, rem: &Rem);
4314
4315 // Initialize the HazardRecognizers. If itineraries don't exist, are empty,
4316 // or are disabled, then these HazardRecs will be disabled.
4317 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
4318 if (!Top.HazardRec)
4319 Top.HazardRec.reset(p: DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG));
4320 if (!Bot.HazardRec)
4321 Bot.HazardRec.reset(p: DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG));
4322 TopClusterID = InvalidClusterId;
4323 BotClusterID = InvalidClusterId;
4324}
4325
4326void PostGenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,
4327 MachineBasicBlock::iterator End,
4328 unsigned NumRegionInstrs) {
4329 const MachineFunction &MF = *Begin->getMF();
4330
4331 // Default to top-down because it was implemented first and existing targets
4332 // expect that behavior by default.
4333 RegionPolicy.OnlyTopDown = true;
4334 RegionPolicy.OnlyBottomUp = false;
4335
4336 // Allow the subtarget to override default policy.
4337 SchedRegion Region(Begin, End, NumRegionInstrs);
4338 MF.getSubtarget().overridePostRASchedPolicy(Policy&: RegionPolicy, Region);
4339
4340 // After subtarget overrides, apply command line options.
4341 if (PostRADirection == MISched::TopDown) {
4342 RegionPolicy.OnlyTopDown = true;
4343 RegionPolicy.OnlyBottomUp = false;
4344 } else if (PostRADirection == MISched::BottomUp) {
4345 RegionPolicy.OnlyTopDown = false;
4346 RegionPolicy.OnlyBottomUp = true;
4347 } else if (PostRADirection == MISched::Bidirectional) {
4348 RegionPolicy.OnlyBottomUp = false;
4349 RegionPolicy.OnlyTopDown = false;
4350 }
4351
4352 BotIdx = NumRegionInstrs - 1;
4353 this->NumRegionInstrs = NumRegionInstrs;
4354}
4355
4356void PostGenericScheduler::registerRoots() {
4357 Rem.CriticalPath = DAG->ExitSU.getDepth();
4358
4359 // Some roots may not feed into ExitSU. Check all of them in case.
4360 for (const SUnit *SU : Bot.Available) {
4361 if (SU->getDepth() > Rem.CriticalPath)
4362 Rem.CriticalPath = SU->getDepth();
4363 }
4364 LLVM_DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem.CriticalPath << '\n');
4365 if (DumpCriticalPathLength) {
4366 errs() << "Critical Path(PGS-RR ): " << Rem.CriticalPath << " \n";
4367 }
4368}
4369
4370/// Apply a set of heuristics to a new candidate for PostRA scheduling.
4371///
4372/// \param Cand provides the policy and current best candidate.
4373/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
4374/// \return \c true if TryCand is better than Cand (Reason is NOT NoCand)
4375bool PostGenericScheduler::tryCandidate(SchedCandidate &Cand,
4376 SchedCandidate &TryCand) {
4377 // Initialize the candidate if needed.
4378 if (!Cand.isValid()) {
4379 TryCand.Reason = FirstValid;
4380 return true;
4381 }
4382
4383 // Prioritize instructions that read unbuffered resources by stall cycles.
4384 if (tryLess(TryVal: Top.getLatencyStallCycles(SU: TryCand.SU),
4385 CandVal: Top.getLatencyStallCycles(SU: Cand.SU), TryCand, Cand, Reason: Stall))
4386 return TryCand.Reason != NoCand;
4387
4388 // Keep clustered nodes together.
4389 unsigned CandZoneCluster = Cand.AtTop ? TopClusterID : BotClusterID;
4390 unsigned TryCandZoneCluster = TryCand.AtTop ? TopClusterID : BotClusterID;
4391 bool CandIsClusterSucc =
4392 isTheSameCluster(A: CandZoneCluster, B: Cand.SU->ParentClusterIdx);
4393 bool TryCandIsClusterSucc =
4394 isTheSameCluster(A: TryCandZoneCluster, B: TryCand.SU->ParentClusterIdx);
4395
4396 if (tryGreater(TryVal: TryCandIsClusterSucc, CandVal: CandIsClusterSucc, TryCand, Cand,
4397 Reason: Cluster))
4398 return TryCand.Reason != NoCand;
4399 // Avoid critical resource consumption and balance the schedule.
4400 if (tryLess(TryVal: TryCand.ResDelta.CritResources, CandVal: Cand.ResDelta.CritResources,
4401 TryCand, Cand, Reason: ResourceReduce))
4402 return TryCand.Reason != NoCand;
4403 if (tryGreater(TryVal: TryCand.ResDelta.DemandedResources,
4404 CandVal: Cand.ResDelta.DemandedResources,
4405 TryCand, Cand, Reason: ResourceDemand))
4406 return TryCand.Reason != NoCand;
4407
4408 // We only compare a subset of features when comparing nodes between
4409 // Top and Bottom boundary.
4410 if (Cand.AtTop == TryCand.AtTop) {
4411 // Avoid serializing long latency dependence chains.
4412 if (Cand.Policy.ReduceLatency &&
4413 tryLatency(TryCand, Cand, Zone&: Cand.AtTop ? Top : Bot))
4414 return TryCand.Reason != NoCand;
4415 }
4416
4417 // Fall through to original instruction order.
4418 if (TryCand.SU->NodeNum < Cand.SU->NodeNum) {
4419 TryCand.Reason = NodeOrder;
4420 return true;
4421 }
4422
4423 return false;
4424}
4425
4426void PostGenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
4427 SchedCandidate &Cand) {
4428 ReadyQueue &Q = Zone.Available;
4429 for (SUnit *SU : Q) {
4430 SchedCandidate TryCand(Cand.Policy);
4431 TryCand.SU = SU;
4432 TryCand.AtTop = Zone.isTop();
4433 TryCand.initResourceDelta(DAG, SchedModel);
4434 if (tryCandidate(Cand, TryCand)) {
4435 Cand.setBest(TryCand);
4436 LLVM_DEBUG(traceCandidate(Cand));
4437 }
4438 }
4439}
4440
4441/// Pick the best candidate node from either the top or bottom queue.
4442SUnit *PostGenericScheduler::pickNodeBidirectional(bool &IsTopNode) {
4443 // FIXME: This is similiar to GenericScheduler::pickNodeBidirectional. Factor
4444 // out common parts.
4445
4446 // Schedule as far as possible in the direction of no choice. This is most
4447 // efficient, but also provides the best heuristics for CriticalPSets.
4448 if (SUnit *SU = Bot.pickOnlyChoice()) {
4449 IsTopNode = false;
4450 tracePick(Reason: Only1, /*IsTopNode=*/IsTop: false, /*IsPostRA=*/true);
4451 return SU;
4452 }
4453 if (SUnit *SU = Top.pickOnlyChoice()) {
4454 IsTopNode = true;
4455 tracePick(Reason: Only1, /*IsTopNode=*/IsTop: true, /*IsPostRA=*/true);
4456 return SU;
4457 }
4458 // Set the bottom-up policy based on the state of the current bottom zone and
4459 // the instructions outside the zone, including the top zone.
4460 CandPolicy BotPolicy;
4461 setPolicy(Policy&: BotPolicy, /*IsPostRA=*/true, CurrZone&: Bot, OtherZone: &Top);
4462 // Set the top-down policy based on the state of the current top zone and
4463 // the instructions outside the zone, including the bottom zone.
4464 CandPolicy TopPolicy;
4465 setPolicy(Policy&: TopPolicy, /*IsPostRA=*/true, CurrZone&: Top, OtherZone: &Bot);
4466
4467 // See if BotCand is still valid (because we previously scheduled from Top).
4468 LLVM_DEBUG(dbgs() << "Picking from Bot:\n");
4469 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
4470 BotCand.Policy != BotPolicy) {
4471 BotCand.reset(NewPolicy: CandPolicy());
4472 pickNodeFromQueue(Zone&: Bot, Cand&: BotCand);
4473 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
4474 } else {
4475 LLVM_DEBUG(traceCandidate(BotCand));
4476#ifndef NDEBUG
4477 if (VerifyScheduling) {
4478 SchedCandidate TCand;
4479 TCand.reset(CandPolicy());
4480 pickNodeFromQueue(Bot, BotCand);
4481 assert(TCand.SU == BotCand.SU &&
4482 "Last pick result should correspond to re-picking right now");
4483 }
4484#endif
4485 }
4486
4487 // Check if the top Q has a better candidate.
4488 LLVM_DEBUG(dbgs() << "Picking from Top:\n");
4489 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
4490 TopCand.Policy != TopPolicy) {
4491 TopCand.reset(NewPolicy: CandPolicy());
4492 pickNodeFromQueue(Zone&: Top, Cand&: TopCand);
4493 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
4494 } else {
4495 LLVM_DEBUG(traceCandidate(TopCand));
4496#ifndef NDEBUG
4497 if (VerifyScheduling) {
4498 SchedCandidate TCand;
4499 TCand.reset(CandPolicy());
4500 pickNodeFromQueue(Top, TopCand);
4501 assert(TCand.SU == TopCand.SU &&
4502 "Last pick result should correspond to re-picking right now");
4503 }
4504#endif
4505 }
4506
4507 // Pick best from BotCand and TopCand.
4508 assert(BotCand.isValid());
4509 assert(TopCand.isValid());
4510 SchedCandidate Cand = BotCand;
4511 TopCand.Reason = NoCand;
4512 if (tryCandidate(Cand, TryCand&: TopCand)) {
4513 Cand.setBest(TopCand);
4514 LLVM_DEBUG(traceCandidate(Cand));
4515 }
4516
4517 IsTopNode = Cand.AtTop;
4518 tracePick(Cand, /*IsPostRA=*/true);
4519 return Cand.SU;
4520}
4521
4522/// Pick the next node to schedule.
4523SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) {
4524 if (DAG->top() == DAG->bottom()) {
4525 assert(Top.Available.empty() && Top.Pending.empty() &&
4526 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
4527 return nullptr;
4528 }
4529 SUnit *SU;
4530 if (RegionPolicy.OnlyBottomUp) {
4531 SU = Bot.pickOnlyChoice();
4532 if (SU) {
4533 tracePick(Reason: Only1, /*IsTopNode=*/IsTop: true, /*IsPostRA=*/true);
4534 } else {
4535 CandPolicy NoPolicy;
4536 BotCand.reset(NewPolicy: NoPolicy);
4537 // Set the bottom-up policy based on the state of the current bottom
4538 // zone and the instructions outside the zone, including the top zone.
4539 setPolicy(Policy&: BotCand.Policy, /*IsPostRA=*/true, CurrZone&: Bot, OtherZone: nullptr);
4540 pickNodeFromQueue(Zone&: Bot, Cand&: BotCand);
4541 assert(BotCand.Reason != NoCand && "failed to find a candidate");
4542 tracePick(Cand: BotCand, /*IsPostRA=*/true);
4543 SU = BotCand.SU;
4544 }
4545 IsTopNode = false;
4546 } else if (RegionPolicy.OnlyTopDown) {
4547 SU = Top.pickOnlyChoice();
4548 if (SU) {
4549 tracePick(Reason: Only1, /*IsTopNode=*/IsTop: true, /*IsPostRA=*/true);
4550 } else {
4551 CandPolicy NoPolicy;
4552 TopCand.reset(NewPolicy: NoPolicy);
4553 // Set the top-down policy based on the state of the current top zone
4554 // and the instructions outside the zone, including the bottom zone.
4555 setPolicy(Policy&: TopCand.Policy, /*IsPostRA=*/true, CurrZone&: Top, OtherZone: nullptr);
4556 pickNodeFromQueue(Zone&: Top, Cand&: TopCand);
4557 assert(TopCand.Reason != NoCand && "failed to find a candidate");
4558 tracePick(Cand: TopCand, /*IsPostRA=*/true);
4559 SU = TopCand.SU;
4560 }
4561 IsTopNode = true;
4562 } else {
4563 SU = pickNodeBidirectional(IsTopNode);
4564 }
4565 assert(!SU->isScheduled && "SUnit scheduled twice.");
4566
4567 if (SU->isTopReady())
4568 Top.removeReady(SU);
4569 if (SU->isBottomReady())
4570 Bot.removeReady(SU);
4571
4572 LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
4573 << *SU->getInstr());
4574
4575 if (IsTopNode) {
4576 if (SU->NodeNum == TopIdx++)
4577 ++NumInstrsInSourceOrderPostRA;
4578 } else {
4579 assert(BotIdx < NumRegionInstrs && "out of bounds");
4580 if (SU->NodeNum == BotIdx--)
4581 ++NumInstrsInSourceOrderPostRA;
4582 }
4583
4584 NumInstrsScheduledPostRA += 1;
4585
4586 return SU;
4587}
4588
4589/// Called after ScheduleDAGMI has scheduled an instruction and updated
4590/// scheduled/remaining flags in the DAG nodes.
4591void PostGenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
4592 if (IsTopNode) {
4593 SU->TopReadyCycle = std::max(a: SU->TopReadyCycle, b: Top.getCurrCycle());
4594 TopClusterID = SU->ParentClusterIdx;
4595 Top.bumpNode(SU);
4596 } else {
4597 SU->BotReadyCycle = std::max(a: SU->BotReadyCycle, b: Bot.getCurrCycle());
4598 BotClusterID = SU->ParentClusterIdx;
4599 Bot.bumpNode(SU);
4600 }
4601}
4602
4603//===----------------------------------------------------------------------===//
4604// ILP Scheduler. Currently for experimental analysis of heuristics.
4605//===----------------------------------------------------------------------===//
4606
4607namespace {
4608
4609/// Order nodes by the ILP metric.
4610struct ILPOrder {
4611 const SchedDFSResult *DFSResult = nullptr;
4612 const BitVector *ScheduledTrees = nullptr;
4613 bool MaximizeILP;
4614
4615 ILPOrder(bool MaxILP) : MaximizeILP(MaxILP) {}
4616
4617 /// Apply a less-than relation on node priority.
4618 ///
4619 /// (Return true if A comes after B in the Q.)
4620 bool operator()(const SUnit *A, const SUnit *B) const {
4621 unsigned SchedTreeA = DFSResult->getSubtreeID(SU: A);
4622 unsigned SchedTreeB = DFSResult->getSubtreeID(SU: B);
4623 if (SchedTreeA != SchedTreeB) {
4624 // Unscheduled trees have lower priority.
4625 if (ScheduledTrees->test(Idx: SchedTreeA) != ScheduledTrees->test(Idx: SchedTreeB))
4626 return ScheduledTrees->test(Idx: SchedTreeB);
4627
4628 // Trees with shallower connections have lower priority.
4629 if (DFSResult->getSubtreeLevel(SubtreeID: SchedTreeA)
4630 != DFSResult->getSubtreeLevel(SubtreeID: SchedTreeB)) {
4631 return DFSResult->getSubtreeLevel(SubtreeID: SchedTreeA)
4632 < DFSResult->getSubtreeLevel(SubtreeID: SchedTreeB);
4633 }
4634 }
4635 if (MaximizeILP)
4636 return DFSResult->getILP(SU: A) < DFSResult->getILP(SU: B);
4637 else
4638 return DFSResult->getILP(SU: A) > DFSResult->getILP(SU: B);
4639 }
4640};
4641
4642/// Schedule based on the ILP metric.
4643class ILPScheduler : public MachineSchedStrategy {
4644 ScheduleDAGMILive *DAG = nullptr;
4645 ILPOrder Cmp;
4646
4647 std::vector<SUnit*> ReadyQ;
4648
4649public:
4650 ILPScheduler(bool MaximizeILP) : Cmp(MaximizeILP) {}
4651
4652 void initialize(ScheduleDAGMI *dag) override {
4653 assert(dag->hasVRegLiveness() && "ILPScheduler needs vreg liveness");
4654 DAG = static_cast<ScheduleDAGMILive*>(dag);
4655 DAG->computeDFSResult();
4656 Cmp.DFSResult = DAG->getDFSResult();
4657 Cmp.ScheduledTrees = &DAG->getScheduledTrees();
4658 ReadyQ.clear();
4659 }
4660
4661 void registerRoots() override {
4662 // Restore the heap in ReadyQ with the updated DFS results.
4663 std::make_heap(first: ReadyQ.begin(), last: ReadyQ.end(), comp: Cmp);
4664 }
4665
4666 /// Implement MachineSchedStrategy interface.
4667 /// -----------------------------------------
4668
4669 /// Callback to select the highest priority node from the ready Q.
4670 SUnit *pickNode(bool &IsTopNode) override {
4671 if (ReadyQ.empty()) return nullptr;
4672 std::pop_heap(first: ReadyQ.begin(), last: ReadyQ.end(), comp: Cmp);
4673 SUnit *SU = ReadyQ.back();
4674 ReadyQ.pop_back();
4675 IsTopNode = false;
4676 LLVM_DEBUG(dbgs() << "Pick node "
4677 << "SU(" << SU->NodeNum << ") "
4678 << " ILP: " << DAG->getDFSResult()->getILP(SU)
4679 << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU)
4680 << " @"
4681 << DAG->getDFSResult()->getSubtreeLevel(
4682 DAG->getDFSResult()->getSubtreeID(SU))
4683 << '\n'
4684 << "Scheduling " << *SU->getInstr());
4685 return SU;
4686 }
4687
4688 /// Scheduler callback to notify that a new subtree is scheduled.
4689 void scheduleTree(unsigned SubtreeID) override {
4690 std::make_heap(first: ReadyQ.begin(), last: ReadyQ.end(), comp: Cmp);
4691 }
4692
4693 /// Callback after a node is scheduled. Mark a newly scheduled tree, notify
4694 /// DFSResults, and resort the priority Q.
4695 void schedNode(SUnit *SU, bool IsTopNode) override {
4696 assert(!IsTopNode && "SchedDFSResult needs bottom-up");
4697 }
4698
4699 void releaseTopNode(SUnit *) override { /*only called for top roots*/ }
4700
4701 void releaseBottomNode(SUnit *SU) override {
4702 ReadyQ.push_back(x: SU);
4703 std::push_heap(first: ReadyQ.begin(), last: ReadyQ.end(), comp: Cmp);
4704 }
4705};
4706
4707} // end anonymous namespace
4708
4709static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) {
4710 return new ScheduleDAGMILive(C, std::make_unique<ILPScheduler>(args: true));
4711}
4712static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) {
4713 return new ScheduleDAGMILive(C, std::make_unique<ILPScheduler>(args: false));
4714}
4715
4716static MachineSchedRegistry ILPMaxRegistry(
4717 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler);
4718static MachineSchedRegistry ILPMinRegistry(
4719 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler);
4720
4721//===----------------------------------------------------------------------===//
4722// Machine Instruction Shuffler for Correctness Testing
4723//===----------------------------------------------------------------------===//
4724
4725#ifndef NDEBUG
4726namespace {
4727
4728/// Apply a less-than relation on the node order, which corresponds to the
4729/// instruction order prior to scheduling. IsReverse implements greater-than.
4730template<bool IsReverse>
4731struct SUnitOrder {
4732 bool operator()(SUnit *A, SUnit *B) const {
4733 if (IsReverse)
4734 return A->NodeNum > B->NodeNum;
4735 else
4736 return A->NodeNum < B->NodeNum;
4737 }
4738};
4739
4740/// Reorder instructions as much as possible.
4741class InstructionShuffler : public MachineSchedStrategy {
4742 bool IsAlternating;
4743 bool IsTopDown;
4744
4745 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority
4746 // gives nodes with a higher number higher priority causing the latest
4747 // instructions to be scheduled first.
4748 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false>>
4749 TopQ;
4750
4751 // When scheduling bottom-up, use greater-than as the queue priority.
4752 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true>>
4753 BottomQ;
4754
4755public:
4756 InstructionShuffler(bool alternate, bool topdown)
4757 : IsAlternating(alternate), IsTopDown(topdown) {}
4758
4759 void initialize(ScheduleDAGMI*) override {
4760 TopQ.clear();
4761 BottomQ.clear();
4762 }
4763
4764 /// Implement MachineSchedStrategy interface.
4765 /// -----------------------------------------
4766
4767 SUnit *pickNode(bool &IsTopNode) override {
4768 SUnit *SU;
4769 if (IsTopDown) {
4770 do {
4771 if (TopQ.empty()) return nullptr;
4772 SU = TopQ.top();
4773 TopQ.pop();
4774 } while (SU->isScheduled);
4775 IsTopNode = true;
4776 } else {
4777 do {
4778 if (BottomQ.empty()) return nullptr;
4779 SU = BottomQ.top();
4780 BottomQ.pop();
4781 } while (SU->isScheduled);
4782 IsTopNode = false;
4783 }
4784 if (IsAlternating)
4785 IsTopDown = !IsTopDown;
4786 return SU;
4787 }
4788
4789 void schedNode(SUnit *SU, bool IsTopNode) override {}
4790
4791 void releaseTopNode(SUnit *SU) override {
4792 TopQ.push(SU);
4793 }
4794 void releaseBottomNode(SUnit *SU) override {
4795 BottomQ.push(SU);
4796 }
4797};
4798
4799} // end anonymous namespace
4800
4801static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {
4802 bool Alternate =
4803 PreRADirection != MISched::TopDown && PreRADirection != MISched::BottomUp;
4804 bool TopDown = PreRADirection != MISched::BottomUp;
4805 return new ScheduleDAGMILive(
4806 C, std::make_unique<InstructionShuffler>(Alternate, TopDown));
4807}
4808
4809static MachineSchedRegistry ShufflerRegistry(
4810 "shuffle", "Shuffle machine instructions alternating directions",
4811 createInstructionShuffler);
4812#endif // !NDEBUG
4813
4814//===----------------------------------------------------------------------===//
4815// GraphWriter support for ScheduleDAGMILive.
4816//===----------------------------------------------------------------------===//
4817
4818#ifndef NDEBUG
4819
4820template <>
4821struct llvm::GraphTraits<ScheduleDAGMI *> : public GraphTraits<ScheduleDAG *> {
4822};
4823
4824template <>
4825struct llvm::DOTGraphTraits<ScheduleDAGMI *> : public DefaultDOTGraphTraits {
4826 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
4827
4828 static std::string getGraphName(const ScheduleDAG *G) {
4829 return std::string(G->MF.getName());
4830 }
4831
4832 static bool renderGraphFromBottomUp() {
4833 return true;
4834 }
4835
4836 static bool isNodeHidden(const SUnit *Node, const ScheduleDAG *G) {
4837 if (ViewMISchedCutoff == 0)
4838 return false;
4839 return (Node->Preds.size() > ViewMISchedCutoff
4840 || Node->Succs.size() > ViewMISchedCutoff);
4841 }
4842
4843 /// If you want to override the dot attributes printed for a particular
4844 /// edge, override this method.
4845 static std::string getEdgeAttributes(const SUnit *Node,
4846 SUnitIterator EI,
4847 const ScheduleDAG *Graph) {
4848 if (EI.isArtificialDep())
4849 return "color=cyan,style=dashed";
4850 if (EI.isCtrlDep())
4851 return "color=blue,style=dashed";
4852 return "";
4853 }
4854
4855 static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) {
4856 std::string Str;
4857 raw_string_ostream SS(Str);
4858 const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
4859 const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
4860 static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
4861 SS << "SU:" << SU->NodeNum;
4862 if (DFS)
4863 SS << " I:" << DFS->getNumInstrs(SU);
4864 return Str;
4865 }
4866
4867 static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) {
4868 return G->getGraphNodeLabel(SU);
4869 }
4870
4871 static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G) {
4872 std::string Str("shape=Mrecord");
4873 const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
4874 const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
4875 static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
4876 if (DFS) {
4877 Str += ",style=filled,fillcolor=\"#";
4878 Str += DOT::getColorString(DFS->getSubtreeID(N));
4879 Str += '"';
4880 }
4881 return Str;
4882 }
4883};
4884
4885#endif // NDEBUG
4886
4887/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG
4888/// rendered using 'dot'.
4889void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) {
4890#ifndef NDEBUG
4891 ViewGraph(this, Name, false, Title);
4892#else
4893 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "
4894 << "systems with Graphviz or gv!\n";
4895#endif // NDEBUG
4896}
4897
4898/// Out-of-line implementation with no arguments is handy for gdb.
4899void ScheduleDAGMI::viewGraph() {
4900 viewGraph(Name: getDAGName(), Title: "Scheduling-Units Graph for " + getDAGName());
4901}
4902
4903/// Sort predicate for the intervals stored in an instance of
4904/// ResourceSegments. Intervals are always disjoint (no intersection
4905/// for any pairs of intervals), therefore we can sort the totality of
4906/// the intervals by looking only at the left boundary.
4907static bool sortIntervals(const ResourceSegments::IntervalTy &A,
4908 const ResourceSegments::IntervalTy &B) {
4909 return A.first < B.first;
4910}
4911
4912unsigned ResourceSegments::getFirstAvailableAt(
4913 unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle,
4914 std::function<ResourceSegments::IntervalTy(unsigned, unsigned, unsigned)>
4915 IntervalBuilder) const {
4916 assert(llvm::is_sorted(_Intervals, sortIntervals) &&
4917 "Cannot execute on an un-sorted set of intervals.");
4918
4919 // Zero resource usage is allowed by TargetSchedule.td but we do not construct
4920 // a ResourceSegment interval for that situation.
4921 if (AcquireAtCycle == ReleaseAtCycle)
4922 return CurrCycle;
4923
4924 unsigned RetCycle = CurrCycle;
4925 ResourceSegments::IntervalTy NewInterval =
4926 IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);
4927 for (auto &Interval : _Intervals) {
4928 if (!intersects(A: NewInterval, B: Interval))
4929 continue;
4930
4931 // Move the interval right next to the top of the one it
4932 // intersects.
4933 assert(Interval.second > NewInterval.first &&
4934 "Invalid intervals configuration.");
4935 RetCycle += (unsigned)Interval.second - (unsigned)NewInterval.first;
4936 NewInterval = IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);
4937 }
4938 return RetCycle;
4939}
4940
4941void ResourceSegments::add(ResourceSegments::IntervalTy A,
4942 const unsigned CutOff) {
4943 assert(A.first <= A.second && "Cannot add negative resource usage");
4944 assert(CutOff > 0 && "0-size interval history has no use.");
4945 // Zero resource usage is allowed by TargetSchedule.td, in the case that the
4946 // instruction needed the resource to be available but does not use it.
4947 // However, ResourceSegment represents an interval that is closed on the left
4948 // and open on the right. It is impossible to represent an empty interval when
4949 // the left is closed. Do not add it to Intervals.
4950 if (A.first == A.second)
4951 return;
4952
4953 assert(all_of(_Intervals,
4954 [&A](const ResourceSegments::IntervalTy &Interval) -> bool {
4955 return !intersects(A, Interval);
4956 }) &&
4957 "A resource is being overwritten");
4958 _Intervals.push_back(x: A);
4959
4960 sortAndMerge();
4961
4962 // Do not keep the full history of the intervals, just the
4963 // latest #CutOff.
4964 while (_Intervals.size() > CutOff)
4965 _Intervals.pop_front();
4966}
4967
4968bool ResourceSegments::intersects(ResourceSegments::IntervalTy A,
4969 ResourceSegments::IntervalTy B) {
4970 assert(A.first <= A.second && "Invalid interval");
4971 assert(B.first <= B.second && "Invalid interval");
4972
4973 // Share one boundary.
4974 if ((A.first == B.first) || (A.second == B.second))
4975 return true;
4976
4977 // full intersersect: [ *** ) B
4978 // [***) A
4979 if ((A.first > B.first) && (A.second < B.second))
4980 return true;
4981
4982 // right intersect: [ ***) B
4983 // [*** ) A
4984 if ((A.first > B.first) && (A.first < B.second) && (A.second > B.second))
4985 return true;
4986
4987 // left intersect: [*** ) B
4988 // [ ***) A
4989 if ((A.first < B.first) && (B.first < A.second) && (B.second > B.first))
4990 return true;
4991
4992 return false;
4993}
4994
4995void ResourceSegments::sortAndMerge() {
4996 if (_Intervals.size() <= 1)
4997 return;
4998
4999 // First sort the collection.
5000 _Intervals.sort(comp: sortIntervals);
5001
5002 // can use next because I have at least 2 elements in the list
5003 auto next = std::next(x: std::begin(cont&: _Intervals));
5004 auto E = std::end(cont&: _Intervals);
5005 for (; next != E; ++next) {
5006 if (std::prev(x: next)->second >= next->first) {
5007 next->first = std::prev(x: next)->first;
5008 _Intervals.erase(position: std::prev(x: next));
5009 continue;
5010 }
5011 }
5012}
5013