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/MachineFrameInfo.h"
29#include "llvm/CodeGen/MachineFunction.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineInstr.h"
32#include "llvm/CodeGen/MachineLoopInfo.h"
33#include "llvm/CodeGen/MachineOperand.h"
34#include "llvm/CodeGen/MachinePassRegistry.h"
35#include "llvm/CodeGen/MachineRegisterInfo.h"
36#include "llvm/CodeGen/RegisterClassInfo.h"
37#include "llvm/CodeGen/RegisterPressure.h"
38#include "llvm/CodeGen/ScheduleDAG.h"
39#include "llvm/CodeGen/ScheduleDAGInstrs.h"
40#include "llvm/CodeGen/ScheduleDAGMutation.h"
41#include "llvm/CodeGen/ScheduleDFS.h"
42#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
43#include "llvm/CodeGen/SlotIndexes.h"
44#include "llvm/CodeGen/TargetFrameLowering.h"
45#include "llvm/CodeGen/TargetInstrInfo.h"
46#include "llvm/CodeGen/TargetLowering.h"
47#include "llvm/CodeGen/TargetPassConfig.h"
48#include "llvm/CodeGen/TargetRegisterInfo.h"
49#include "llvm/CodeGen/TargetSchedule.h"
50#include "llvm/CodeGen/TargetSubtargetInfo.h"
51#include "llvm/CodeGenTypes/MachineValueType.h"
52#include "llvm/Config/llvm-config.h"
53#include "llvm/InitializePasses.h"
54#include "llvm/MC/LaneBitmask.h"
55#include "llvm/Pass.h"
56#include "llvm/Support/CommandLine.h"
57#include "llvm/Support/Compiler.h"
58#include "llvm/Support/Debug.h"
59#include "llvm/Support/ErrorHandling.h"
60#include "llvm/Support/GraphWriter.h"
61#include "llvm/Support/raw_ostream.h"
62#include "llvm/Target/TargetMachine.h"
63#include <algorithm>
64#include <cassert>
65#include <cstdint>
66#include <iterator>
67#include <limits>
68#include <memory>
69#include <string>
70#include <tuple>
71#include <utility>
72#include <vector>
73
74using namespace llvm;
75
76#define DEBUG_TYPE "machine-scheduler"
77
78STATISTIC(NumInstrsInSourceOrderPreRA,
79 "Number of instructions in source order after pre-RA scheduling");
80STATISTIC(NumInstrsInSourceOrderPostRA,
81 "Number of instructions in source order after post-RA scheduling");
82STATISTIC(NumInstrsScheduledPreRA,
83 "Number of instructions scheduled by pre-RA scheduler");
84STATISTIC(NumInstrsScheduledPostRA,
85 "Number of instructions scheduled by post-RA scheduler");
86STATISTIC(NumClustered, "Number of load/store pairs clustered");
87
88STATISTIC(NumTopPreRA,
89 "Number of scheduling units chosen from top queue pre-RA");
90STATISTIC(NumBotPreRA,
91 "Number of scheduling units chosen from bottom queue pre-RA");
92STATISTIC(NumNoCandPreRA,
93 "Number of scheduling units chosen for NoCand heuristic pre-RA");
94STATISTIC(NumOnly1PreRA,
95 "Number of scheduling units chosen for Only1 heuristic pre-RA");
96STATISTIC(NumPhysRegPreRA,
97 "Number of scheduling units chosen for PhysReg heuristic pre-RA");
98STATISTIC(NumRegExcessPreRA,
99 "Number of scheduling units chosen for RegExcess heuristic pre-RA");
100STATISTIC(NumRegCriticalPreRA,
101 "Number of scheduling units chosen for RegCritical heuristic pre-RA");
102STATISTIC(NumStallPreRA,
103 "Number of scheduling units chosen for Stall heuristic pre-RA");
104STATISTIC(NumClusterPreRA,
105 "Number of scheduling units chosen for Cluster heuristic pre-RA");
106STATISTIC(NumWeakPreRA,
107 "Number of scheduling units chosen for Weak heuristic pre-RA");
108STATISTIC(NumRegMaxPreRA,
109 "Number of scheduling units chosen for RegMax heuristic pre-RA");
110STATISTIC(
111 NumResourceReducePreRA,
112 "Number of scheduling units chosen for ResourceReduce heuristic pre-RA");
113STATISTIC(
114 NumResourceDemandPreRA,
115 "Number of scheduling units chosen for ResourceDemand heuristic pre-RA");
116STATISTIC(
117 NumTopDepthReducePreRA,
118 "Number of scheduling units chosen for TopDepthReduce heuristic pre-RA");
119STATISTIC(
120 NumTopPathReducePreRA,
121 "Number of scheduling units chosen for TopPathReduce heuristic pre-RA");
122STATISTIC(
123 NumBotHeightReducePreRA,
124 "Number of scheduling units chosen for BotHeightReduce heuristic pre-RA");
125STATISTIC(
126 NumBotPathReducePreRA,
127 "Number of scheduling units chosen for BotPathReduce heuristic pre-RA");
128STATISTIC(NumNodeOrderPreRA,
129 "Number of scheduling units chosen for NodeOrder heuristic pre-RA");
130STATISTIC(NumFirstValidPreRA,
131 "Number of scheduling units chosen for FirstValid heuristic pre-RA");
132
133STATISTIC(NumTopPostRA,
134 "Number of scheduling units chosen from top queue post-RA");
135STATISTIC(NumBotPostRA,
136 "Number of scheduling units chosen from bottom queue post-RA");
137STATISTIC(NumNoCandPostRA,
138 "Number of scheduling units chosen for NoCand heuristic post-RA");
139STATISTIC(NumOnly1PostRA,
140 "Number of scheduling units chosen for Only1 heuristic post-RA");
141STATISTIC(NumPhysRegPostRA,
142 "Number of scheduling units chosen for PhysReg heuristic post-RA");
143STATISTIC(NumRegExcessPostRA,
144 "Number of scheduling units chosen for RegExcess heuristic post-RA");
145STATISTIC(
146 NumRegCriticalPostRA,
147 "Number of scheduling units chosen for RegCritical heuristic post-RA");
148STATISTIC(NumStallPostRA,
149 "Number of scheduling units chosen for Stall heuristic post-RA");
150STATISTIC(NumClusterPostRA,
151 "Number of scheduling units chosen for Cluster heuristic post-RA");
152STATISTIC(NumWeakPostRA,
153 "Number of scheduling units chosen for Weak heuristic post-RA");
154STATISTIC(NumRegMaxPostRA,
155 "Number of scheduling units chosen for RegMax heuristic post-RA");
156STATISTIC(
157 NumResourceReducePostRA,
158 "Number of scheduling units chosen for ResourceReduce heuristic post-RA");
159STATISTIC(
160 NumResourceDemandPostRA,
161 "Number of scheduling units chosen for ResourceDemand heuristic post-RA");
162STATISTIC(
163 NumTopDepthReducePostRA,
164 "Number of scheduling units chosen for TopDepthReduce heuristic post-RA");
165STATISTIC(
166 NumTopPathReducePostRA,
167 "Number of scheduling units chosen for TopPathReduce heuristic post-RA");
168STATISTIC(
169 NumBotHeightReducePostRA,
170 "Number of scheduling units chosen for BotHeightReduce heuristic post-RA");
171STATISTIC(
172 NumBotPathReducePostRA,
173 "Number of scheduling units chosen for BotPathReduce heuristic post-RA");
174STATISTIC(NumNodeOrderPostRA,
175 "Number of scheduling units chosen for NodeOrder heuristic post-RA");
176STATISTIC(NumFirstValidPostRA,
177 "Number of scheduling units chosen for FirstValid heuristic post-RA");
178
179cl::opt<MISched::Direction> llvm::PreRADirection(
180 "misched-prera-direction", cl::Hidden,
181 cl::desc("Pre reg-alloc list scheduling direction"),
182 cl::init(Val: MISched::Unspecified),
183 cl::values(
184 clEnumValN(MISched::TopDown, "topdown",
185 "Force top-down pre reg-alloc list scheduling"),
186 clEnumValN(MISched::BottomUp, "bottomup",
187 "Force bottom-up pre reg-alloc list scheduling"),
188 clEnumValN(MISched::Bidirectional, "bidirectional",
189 "Force bidirectional pre reg-alloc list scheduling")));
190
191static cl::opt<MISched::Direction> PostRADirection(
192 "misched-postra-direction", cl::Hidden,
193 cl::desc("Post reg-alloc list scheduling direction"),
194 cl::init(Val: MISched::Unspecified),
195 cl::values(
196 clEnumValN(MISched::TopDown, "topdown",
197 "Force top-down post reg-alloc list scheduling"),
198 clEnumValN(MISched::BottomUp, "bottomup",
199 "Force bottom-up post reg-alloc list scheduling"),
200 clEnumValN(MISched::Bidirectional, "bidirectional",
201 "Force bidirectional post reg-alloc list scheduling")));
202
203static cl::opt<bool>
204 DumpCriticalPathLength("misched-dcpl", cl::Hidden,
205 cl::desc("Print critical path length to stdout"));
206
207cl::opt<bool> llvm::VerifyScheduling(
208 "verify-misched", cl::Hidden,
209 cl::desc("Verify machine instrs before and after machine scheduling"));
210
211#ifndef NDEBUG
212cl::opt<bool> llvm::ViewMISchedDAGs(
213 "view-misched-dags", cl::Hidden,
214 cl::desc("Pop up a window to show MISched dags after they are processed"));
215cl::opt<bool> llvm::PrintDAGs("misched-print-dags", cl::Hidden,
216 cl::desc("Print schedule DAGs"));
217static cl::opt<bool> MISchedDumpReservedCycles(
218 "misched-dump-reserved-cycles", cl::Hidden, cl::init(false),
219 cl::desc("Dump resource usage at schedule boundary."));
220static cl::opt<bool> MischedDetailResourceBooking(
221 "misched-detail-resource-booking", cl::Hidden, cl::init(false),
222 cl::desc("Show details of invoking getNextResoufceCycle."));
223#else
224const bool llvm::ViewMISchedDAGs = false;
225const bool llvm::PrintDAGs = false;
226static const bool MischedDetailResourceBooking = false;
227#ifdef LLVM_ENABLE_DUMP
228static const bool MISchedDumpReservedCycles = false;
229#endif // LLVM_ENABLE_DUMP
230#endif // NDEBUG
231
232#ifndef NDEBUG
233/// In some situations a few uninteresting nodes depend on nearly all other
234/// nodes in the graph, provide a cutoff to hide them.
235static cl::opt<unsigned> ViewMISchedCutoff("view-misched-cutoff", cl::Hidden,
236 cl::desc("Hide nodes with more predecessor/successor than cutoff"));
237
238static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden,
239 cl::desc("Stop scheduling after N instructions"), cl::init(~0U));
240
241static cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden,
242 cl::desc("Only schedule this function"));
243static cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden,
244 cl::desc("Only schedule this MBB#"));
245#endif // NDEBUG
246
247/// Avoid quadratic complexity in unusually large basic blocks by limiting the
248/// size of the ready lists.
249static cl::opt<unsigned> ReadyListLimit("misched-limit", cl::Hidden,
250 cl::desc("Limit ready list to N instructions"), cl::init(Val: 256));
251
252static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden,
253 cl::desc("Enable register pressure scheduling."), cl::init(Val: true));
254
255static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden,
256 cl::desc("Enable cyclic critical path analysis."), cl::init(Val: true));
257
258static cl::opt<bool> EnableMemOpCluster("misched-cluster", cl::Hidden,
259 cl::desc("Enable memop clustering."),
260 cl::init(Val: true));
261static cl::opt<bool>
262 ForceFastCluster("force-fast-cluster", cl::Hidden,
263 cl::desc("Switch to fast cluster algorithm with the lost "
264 "of some fusion opportunities"),
265 cl::init(Val: false));
266static cl::opt<unsigned>
267 FastClusterThreshold("fast-cluster-threshold", cl::Hidden,
268 cl::desc("The threshold for fast cluster"),
269 cl::init(Val: 1000));
270
271#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
272static cl::opt<bool> MISchedDumpScheduleTrace(
273 "misched-dump-schedule-trace", cl::Hidden, cl::init(false),
274 cl::desc("Dump resource usage at schedule boundary."));
275static cl::opt<unsigned>
276 HeaderColWidth("misched-dump-schedule-trace-col-header-width", cl::Hidden,
277 cl::desc("Set width of the columns with "
278 "the resources and schedule units"),
279 cl::init(19));
280static cl::opt<unsigned>
281 ColWidth("misched-dump-schedule-trace-col-width", cl::Hidden,
282 cl::desc("Set width of the columns showing resource booking."),
283 cl::init(5));
284static cl::opt<bool> MISchedSortResourcesInTrace(
285 "misched-sort-resources-in-trace", cl::Hidden, cl::init(true),
286 cl::desc("Sort the resources printed in the dump trace"));
287#endif
288
289static cl::opt<unsigned>
290 MIResourceCutOff("misched-resource-cutoff", cl::Hidden,
291 cl::desc("Number of intervals to track"), cl::init(Val: 10));
292
293// DAG subtrees must have at least this many nodes.
294static const unsigned MinSubtreeSize = 8;
295
296// Pin the vtables to this file.
297void MachineSchedStrategy::anchor() {}
298
299void ScheduleDAGMutation::anchor() {}
300
301//===----------------------------------------------------------------------===//
302// Machine Instruction Scheduling Pass and Registry
303//===----------------------------------------------------------------------===//
304
305MachineSchedContext::MachineSchedContext() = default;
306MachineSchedContext::~MachineSchedContext() = default;
307
308namespace llvm {
309namespace impl_detail {
310
311/// Base class for the machine scheduler classes.
312class MachineSchedulerBase : public MachineSchedContext {
313protected:
314 void scheduleRegions(ScheduleDAGInstrs &Scheduler, bool FixKillFlags);
315};
316
317/// Impl class for MachineScheduler.
318class MachineSchedulerImpl : public MachineSchedulerBase {
319 // These are only for using MF.verify()
320 // remove when verify supports passing in all analyses
321 MachineFunctionPass *P = nullptr;
322 MachineFunctionAnalysisManager *MFAM = nullptr;
323
324public:
325 struct RequiredAnalyses {
326 MachineLoopInfo &MLI;
327 AAResults &AA;
328 LiveIntervals &LIS;
329 RegisterClassInfo &RegClassInfo;
330 MachineBlockFrequencyInfo &MBFI;
331 };
332
333 MachineSchedulerImpl() = default;
334 // Migration only
335 void setLegacyPass(MachineFunctionPass *P) { this->P = P; }
336 void setMFAM(MachineFunctionAnalysisManager *MFAM) { this->MFAM = MFAM; }
337
338 bool run(MachineFunction &MF, const TargetMachine &TM,
339 const RequiredAnalyses &Analyses);
340
341protected:
342 ScheduleDAGInstrs *createMachineScheduler();
343};
344
345/// Impl class for PostMachineScheduler.
346class PostMachineSchedulerImpl : public MachineSchedulerBase {
347 // These are only for using MF.verify()
348 // remove when verify supports passing in all analyses
349 MachineFunctionPass *P = nullptr;
350 MachineFunctionAnalysisManager *MFAM = nullptr;
351
352public:
353 struct RequiredAnalyses {
354 MachineLoopInfo &MLI;
355 AAResults &AA;
356 };
357 PostMachineSchedulerImpl() = default;
358 // Migration only
359 void setLegacyPass(MachineFunctionPass *P) { this->P = P; }
360 void setMFAM(MachineFunctionAnalysisManager *MFAM) { this->MFAM = MFAM; }
361
362 bool run(MachineFunction &Func, const TargetMachine &TM,
363 const RequiredAnalyses &Analyses);
364
365protected:
366 ScheduleDAGInstrs *createPostMachineScheduler();
367};
368
369} // namespace impl_detail
370} // namespace llvm
371
372using impl_detail::MachineSchedulerBase;
373using impl_detail::MachineSchedulerImpl;
374using impl_detail::PostMachineSchedulerImpl;
375
376namespace {
377/// MachineScheduler runs after coalescing and before register allocation.
378class MachineSchedulerLegacy : public MachineFunctionPass {
379 MachineSchedulerImpl Impl;
380
381public:
382 MachineSchedulerLegacy();
383 void getAnalysisUsage(AnalysisUsage &AU) const override;
384 bool runOnMachineFunction(MachineFunction&) override;
385
386 static char ID; // Class identification, replacement for typeinfo
387};
388
389/// PostMachineScheduler runs after shortly before code emission.
390class PostMachineSchedulerLegacy : public MachineFunctionPass {
391 PostMachineSchedulerImpl Impl;
392
393public:
394 PostMachineSchedulerLegacy();
395 void getAnalysisUsage(AnalysisUsage &AU) const override;
396 bool runOnMachineFunction(MachineFunction &) override;
397
398 static char ID; // Class identification, replacement for typeinfo
399};
400
401} // end anonymous namespace
402
403char MachineSchedulerLegacy::ID = 0;
404
405char &llvm::MachineSchedulerID = MachineSchedulerLegacy::ID;
406
407INITIALIZE_PASS_BEGIN(MachineSchedulerLegacy, DEBUG_TYPE,
408 "Machine Instruction Scheduler", false, false)
409INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
410INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
411INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
412INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
413INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass);
414INITIALIZE_PASS_END(MachineSchedulerLegacy, DEBUG_TYPE,
415 "Machine Instruction Scheduler", false, false)
416
417MachineSchedulerLegacy::MachineSchedulerLegacy() : MachineFunctionPass(ID) {}
418
419void MachineSchedulerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
420 AU.setPreservesCFG();
421 AU.addRequired<MachineLoopInfoWrapperPass>();
422 AU.addRequired<AAResultsWrapperPass>();
423 AU.addRequired<TargetPassConfig>();
424 AU.addPreserved<SlotIndexesWrapperPass>();
425 AU.addRequired<LiveIntervalsWrapperPass>();
426 AU.addPreserved<LiveIntervalsWrapperPass>();
427 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
428 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
429 MachineFunctionPass::getAnalysisUsage(AU);
430}
431
432char PostMachineSchedulerLegacy::ID = 0;
433
434char &llvm::PostMachineSchedulerID = PostMachineSchedulerLegacy::ID;
435
436INITIALIZE_PASS_BEGIN(PostMachineSchedulerLegacy, "postmisched",
437 "PostRA Machine Instruction Scheduler", false, false)
438INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
439INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
440INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
441INITIALIZE_PASS_END(PostMachineSchedulerLegacy, "postmisched",
442 "PostRA Machine Instruction Scheduler", false, false)
443
444PostMachineSchedulerLegacy::PostMachineSchedulerLegacy()
445 : MachineFunctionPass(ID) {}
446
447void PostMachineSchedulerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
448 AU.setPreservesCFG();
449 AU.addRequired<MachineLoopInfoWrapperPass>();
450 AU.addRequired<AAResultsWrapperPass>();
451 AU.addRequired<TargetPassConfig>();
452 MachineFunctionPass::getAnalysisUsage(AU);
453}
454
455MachinePassRegistry<MachineSchedRegistry::ScheduleDAGCtor>
456 MachineSchedRegistry::Registry;
457
458/// A dummy default scheduler factory indicates whether the scheduler
459/// is overridden on the command line.
460static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) {
461 return nullptr;
462}
463
464/// MachineSchedOpt allows command line selection of the scheduler.
465static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,
466 RegisterPassParser<MachineSchedRegistry>>
467MachineSchedOpt("misched",
468 cl::init(Val: &useDefaultMachineSched), cl::Hidden,
469 cl::desc("Machine instruction scheduler to use"));
470
471static MachineSchedRegistry
472DefaultSchedRegistry("default", "Use the target's default scheduler choice.",
473 useDefaultMachineSched);
474
475static cl::opt<bool> EnableMachineSched(
476 "enable-misched",
477 cl::desc("Enable the machine instruction scheduling pass."), cl::init(Val: true),
478 cl::Hidden);
479
480static cl::opt<bool> EnablePostRAMachineSched(
481 "enable-post-misched",
482 cl::desc("Enable the post-ra machine instruction scheduling pass."),
483 cl::init(Val: true), cl::Hidden);
484
485/// Decrement this iterator until reaching the top or a non-debug instr.
486static MachineBasicBlock::const_iterator
487priorNonDebug(MachineBasicBlock::const_iterator I,
488 MachineBasicBlock::const_iterator Beg) {
489 assert(I != Beg && "reached the top of the region, cannot decrement");
490 while (--I != Beg) {
491 if (!I->isDebugOrPseudoInstr())
492 break;
493 }
494 return I;
495}
496
497/// Non-const version.
498static MachineBasicBlock::iterator
499priorNonDebug(MachineBasicBlock::iterator I,
500 MachineBasicBlock::const_iterator Beg) {
501 return priorNonDebug(I: MachineBasicBlock::const_iterator(I), Beg)
502 .getNonConstIterator();
503}
504
505/// If this iterator is a debug value, increment until reaching the End or a
506/// non-debug instruction.
507static MachineBasicBlock::const_iterator
508nextIfDebug(MachineBasicBlock::const_iterator I,
509 MachineBasicBlock::const_iterator End) {
510 for(; I != End; ++I) {
511 if (!I->isDebugOrPseudoInstr())
512 break;
513 }
514 return I;
515}
516
517/// Non-const version.
518static MachineBasicBlock::iterator
519nextIfDebug(MachineBasicBlock::iterator I,
520 MachineBasicBlock::const_iterator End) {
521 return nextIfDebug(I: MachineBasicBlock::const_iterator(I), End)
522 .getNonConstIterator();
523}
524
525/// Instantiate a ScheduleDAGInstrs that will be owned by the caller.
526ScheduleDAGInstrs *MachineSchedulerImpl::createMachineScheduler() {
527 // Select the scheduler, or set the default.
528 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;
529 if (Ctor != useDefaultMachineSched)
530 return Ctor(this);
531
532 // Get the default scheduler set by the target for this function.
533 ScheduleDAGInstrs *Scheduler = TM->createMachineScheduler(C: this);
534 if (Scheduler)
535 return Scheduler;
536
537 // Default to GenericScheduler.
538 return createSchedLive(C: this);
539}
540
541bool MachineSchedulerImpl::run(MachineFunction &Func, const TargetMachine &TM,
542 const RequiredAnalyses &Analyses) {
543 MF = &Func;
544 MLI = &Analyses.MLI;
545 this->TM = &TM;
546 AA = &Analyses.AA;
547 LIS = &Analyses.LIS;
548 RegClassInfo = &Analyses.RegClassInfo;
549 MBFI = &Analyses.MBFI;
550
551 if (VerifyScheduling) {
552 LLVM_DEBUG(LIS->dump());
553 const char *MSchedBanner = "Before machine scheduling.";
554 if (P)
555 MF->verify(p: P, Banner: MSchedBanner, OS: &errs());
556 else
557 MF->verify(MFAM&: *MFAM, Banner: MSchedBanner, OS: &errs());
558 }
559
560 // Instantiate the selected scheduler for this target, function, and
561 // optimization level.
562 std::unique_ptr<ScheduleDAGInstrs> Scheduler(createMachineScheduler());
563 scheduleRegions(Scheduler&: *Scheduler, FixKillFlags: false);
564
565 LLVM_DEBUG(LIS->dump());
566 if (VerifyScheduling) {
567 const char *MSchedBanner = "After machine scheduling.";
568 if (P)
569 MF->verify(p: P, Banner: MSchedBanner, OS: &errs());
570 else
571 MF->verify(MFAM&: *MFAM, Banner: MSchedBanner, OS: &errs());
572 }
573 return true;
574}
575
576/// Instantiate a ScheduleDAGInstrs for PostRA scheduling that will be owned by
577/// the caller. We don't have a command line option to override the postRA
578/// scheduler. The Target must configure it.
579ScheduleDAGInstrs *PostMachineSchedulerImpl::createPostMachineScheduler() {
580 // Get the postRA scheduler set by the target for this function.
581 ScheduleDAGInstrs *Scheduler = TM->createPostMachineScheduler(C: this);
582 if (Scheduler)
583 return Scheduler;
584
585 // Default to GenericScheduler.
586 return createSchedPostRA(C: this);
587}
588
589bool PostMachineSchedulerImpl::run(MachineFunction &Func,
590 const TargetMachine &TM,
591 const RequiredAnalyses &Analyses) {
592 MF = &Func;
593 MLI = &Analyses.MLI;
594 this->TM = &TM;
595 AA = &Analyses.AA;
596
597 if (VerifyScheduling) {
598 const char *PostMSchedBanner = "Before post machine scheduling.";
599 if (P)
600 MF->verify(p: P, Banner: PostMSchedBanner, OS: &errs());
601 else
602 MF->verify(MFAM&: *MFAM, Banner: PostMSchedBanner, OS: &errs());
603 }
604
605 // Instantiate the selected scheduler for this target, function, and
606 // optimization level.
607 std::unique_ptr<ScheduleDAGInstrs> Scheduler(createPostMachineScheduler());
608 scheduleRegions(Scheduler&: *Scheduler, FixKillFlags: true);
609
610 if (VerifyScheduling) {
611 const char *PostMSchedBanner = "After post machine scheduling.";
612 if (P)
613 MF->verify(p: P, Banner: PostMSchedBanner, OS: &errs());
614 else
615 MF->verify(MFAM&: *MFAM, Banner: PostMSchedBanner, OS: &errs());
616 }
617 return true;
618}
619
620/// Top-level MachineScheduler pass driver.
621///
622/// Visit blocks in function order. Divide each block into scheduling regions
623/// and visit them bottom-up. Visiting regions bottom-up is not required, but is
624/// consistent with the DAG builder, which traverses the interior of the
625/// scheduling regions bottom-up.
626///
627/// This design avoids exposing scheduling boundaries to the DAG builder,
628/// simplifying the DAG builder's support for "special" target instructions.
629/// At the same time the design allows target schedulers to operate across
630/// scheduling boundaries, for example to bundle the boundary instructions
631/// without reordering them. This creates complexity, because the target
632/// scheduler must update the RegionBegin and RegionEnd positions cached by
633/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler
634/// design would be to split blocks at scheduling boundaries, but LLVM has a
635/// general bias against block splitting purely for implementation simplicity.
636bool MachineSchedulerLegacy::runOnMachineFunction(MachineFunction &MF) {
637 if (skipFunction(F: MF.getFunction()))
638 return false;
639
640 if (EnableMachineSched.getNumOccurrences()) {
641 if (!EnableMachineSched)
642 return false;
643 } else if (!MF.getSubtarget().enableMachineScheduler()) {
644 return false;
645 }
646
647 LLVM_DEBUG(dbgs() << "Before MISched:\n"; MF.print(dbgs()));
648
649 auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
650 auto &TM = getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
651 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
652 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
653 auto &RegClassInfo =
654 getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
655 auto &MBFI = getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
656
657 Impl.setLegacyPass(this);
658 return Impl.run(Func&: MF, TM, Analyses: {.MLI: MLI, .AA: AA, .LIS: LIS, .RegClassInfo: RegClassInfo, .MBFI: MBFI});
659}
660
661MachineSchedulerPass::MachineSchedulerPass(const TargetMachine *TM)
662 : Impl(std::make_unique<MachineSchedulerImpl>()), TM(TM) {}
663MachineSchedulerPass::~MachineSchedulerPass() = default;
664MachineSchedulerPass::MachineSchedulerPass(MachineSchedulerPass &&Other) =
665 default;
666
667PostMachineSchedulerPass::PostMachineSchedulerPass(const TargetMachine *TM)
668 : Impl(std::make_unique<PostMachineSchedulerImpl>()), TM(TM) {}
669PostMachineSchedulerPass::PostMachineSchedulerPass(
670 PostMachineSchedulerPass &&Other) = default;
671PostMachineSchedulerPass::~PostMachineSchedulerPass() = default;
672
673PreservedAnalyses
674MachineSchedulerPass::run(MachineFunction &MF,
675 MachineFunctionAnalysisManager &MFAM) {
676 if (EnableMachineSched.getNumOccurrences()) {
677 if (!EnableMachineSched)
678 return PreservedAnalyses::all();
679 } else if (!MF.getSubtarget().enableMachineScheduler()) {
680 return PreservedAnalyses::all();
681 }
682
683 LLVM_DEBUG(dbgs() << "Before MISched:\n"; MF.print(dbgs()));
684 auto &MLI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
685 auto &FAM = MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
686 .getManager();
687 auto &AA = FAM.getResult<AAManager>(IR&: MF.getFunction());
688 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
689 auto &RegClassInfo = MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
690 auto &MBFI = MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
691
692 Impl->setMFAM(&MFAM);
693 bool Changed = Impl->run(Func&: MF, TM: *TM, Analyses: {.MLI: MLI, .AA: AA, .LIS: LIS, .RegClassInfo: RegClassInfo, .MBFI: MBFI});
694 if (!Changed)
695 return PreservedAnalyses::all();
696
697 return getMachineFunctionPassPreservedAnalyses()
698 .preserveSet<CFGAnalyses>()
699 .preserve<SlotIndexesAnalysis>()
700 .preserve<LiveIntervalsAnalysis>();
701}
702
703bool PostMachineSchedulerLegacy::runOnMachineFunction(MachineFunction &MF) {
704 if (skipFunction(F: MF.getFunction()))
705 return false;
706
707 if (EnablePostRAMachineSched.getNumOccurrences()) {
708 if (!EnablePostRAMachineSched)
709 return false;
710 } else if (!MF.getSubtarget().enablePostRAMachineScheduler()) {
711 LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
712 return false;
713 }
714 LLVM_DEBUG(dbgs() << "Before post-MI-sched:\n"; MF.print(dbgs()));
715 auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
716 auto &TM = getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
717 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
718 Impl.setLegacyPass(this);
719 return Impl.run(Func&: MF, TM, Analyses: {.MLI: MLI, .AA: AA});
720}
721
722PreservedAnalyses
723PostMachineSchedulerPass::run(MachineFunction &MF,
724 MachineFunctionAnalysisManager &MFAM) {
725 if (EnablePostRAMachineSched.getNumOccurrences()) {
726 if (!EnablePostRAMachineSched)
727 return PreservedAnalyses::all();
728 } else if (!MF.getSubtarget().enablePostRAMachineScheduler()) {
729 LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
730 return PreservedAnalyses::all();
731 }
732 LLVM_DEBUG(dbgs() << "Before post-MI-sched:\n"; MF.print(dbgs()));
733 auto &MLI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
734 auto &FAM = MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
735 .getManager();
736 auto &AA = FAM.getResult<AAManager>(IR&: MF.getFunction());
737
738 Impl->setMFAM(&MFAM);
739 bool Changed = Impl->run(Func&: MF, TM: *TM, Analyses: {.MLI: MLI, .AA: AA});
740 if (!Changed)
741 return PreservedAnalyses::all();
742
743 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
744 PA.preserveSet<CFGAnalyses>();
745 return PA;
746}
747
748/// Return true of the given instruction should not be included in a scheduling
749/// region.
750///
751/// MachineScheduler does not currently support scheduling across calls. To
752/// handle calls, the DAG builder needs to be modified to create register
753/// anti/output dependencies on the registers clobbered by the call's regmask
754/// operand. In PreRA scheduling, the stack pointer adjustment already prevents
755/// scheduling across calls. In PostRA scheduling, we need the isCall to enforce
756/// the boundary, but there would be no benefit to postRA scheduling across
757/// calls this late anyway.
758static bool isSchedBoundary(MachineBasicBlock::iterator MI,
759 MachineBasicBlock *MBB,
760 MachineFunction *MF,
761 const TargetInstrInfo *TII) {
762 return MI->isCall() || TII->isSchedulingBoundary(MI: *MI, MBB, MF: *MF) ||
763 MI->isFakeUse();
764}
765
766using MBBRegionsVector = SmallVector<SchedRegion, 16>;
767
768static void
769getSchedRegions(MachineBasicBlock *MBB,
770 MBBRegionsVector &Regions,
771 bool RegionsTopDown) {
772 MachineFunction *MF = MBB->getParent();
773 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
774
775 MachineBasicBlock::iterator I = nullptr;
776 for(MachineBasicBlock::iterator RegionEnd = MBB->end();
777 RegionEnd != MBB->begin(); RegionEnd = I) {
778
779 // Avoid decrementing RegionEnd for blocks with no terminator.
780 if (RegionEnd != MBB->end() ||
781 isSchedBoundary(MI: &*std::prev(x: RegionEnd), MBB: &*MBB, MF, TII)) {
782 --RegionEnd;
783 }
784
785 // The next region starts above the previous region. Look backward in the
786 // instruction stream until we find the nearest boundary.
787 unsigned NumRegionInstrs = 0;
788 I = RegionEnd;
789 for (;I != MBB->begin(); --I) {
790 MachineInstr &MI = *std::prev(x: I);
791 if (isSchedBoundary(MI: &MI, MBB: &*MBB, MF, TII))
792 break;
793 if (!MI.isDebugOrPseudoInstr()) {
794 // MBB::size() uses instr_iterator to count. Here we need a bundle to
795 // count as a single instruction.
796 ++NumRegionInstrs;
797 }
798 }
799
800 // It's possible we found a scheduling region that only has debug
801 // instructions. Don't bother scheduling these.
802 if (NumRegionInstrs != 0)
803 Regions.push_back(Elt: SchedRegion(I, RegionEnd, NumRegionInstrs));
804 }
805
806 if (RegionsTopDown)
807 std::reverse(first: Regions.begin(), last: Regions.end());
808}
809
810/// Main driver for both MachineScheduler and PostMachineScheduler.
811void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler,
812 bool FixKillFlags) {
813 // Visit all machine basic blocks.
814 //
815 // TODO: Visit blocks in global postorder or postorder within the bottom-up
816 // loop tree. Then we can optionally compute global RegPressure.
817 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
818 MBB != MBBEnd; ++MBB) {
819#ifndef NDEBUG
820 if (SchedOnlyFunc.getNumOccurrences() && SchedOnlyFunc != MF->getName())
821 continue;
822 if (SchedOnlyBlock.getNumOccurrences()
823 && (int)SchedOnlyBlock != MBB->getNumber())
824 continue;
825#endif
826
827 Scheduler.startBlock(BB: &*MBB);
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, MRI);
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, MRI);
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 MachineFrameInfo &MFI = MF.getFrameInfo();
1986 const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
1987 bool StackGrowsDown = TFI.getStackGrowthDirection() ==
1988 TargetFrameLowering::StackGrowsDown;
1989 bool AIsFixed = MFI.isFixedObjectIndex(ObjectIdx: A->getIndex());
1990 bool BIsFixed = MFI.isFixedObjectIndex(ObjectIdx: B->getIndex());
1991 // Sort fixed and non-fixed bases as separate groups, preserving the
1992 // existing frame-index ordering between the groups. Do not rely on
1993 // non-fixed object offsets before frame layout.
1994 if (AIsFixed != BIsFixed)
1995 return StackGrowsDown ? !AIsFixed : AIsFixed;
1996 if (AIsFixed) {
1997 // Fixed objects have explicit offsets, and targets may create their
1998 // frame indices in an order unrelated to those offsets. Sort by the
1999 // actual object offsets so target clustering hooks see fixed object
2000 // bases in address order.
2001 int64_t AOffset = MFI.getObjectOffset(ObjectIdx: A->getIndex());
2002 int64_t BOffset = MFI.getObjectOffset(ObjectIdx: B->getIndex());
2003 if (AOffset != BOffset)
2004 return AOffset < BOffset;
2005 }
2006 return StackGrowsDown ? A->getIndex() > B->getIndex()
2007 : A->getIndex() < B->getIndex();
2008 }
2009
2010 llvm_unreachable("MemOpClusterMutation only supports register or frame "
2011 "index bases.");
2012 }
2013
2014 bool operator<(const MemOpInfo &RHS) const {
2015 // FIXME: Don't compare everything twice. Maybe use C++20 three way
2016 // comparison instead when it's available.
2017 if (std::lexicographical_compare(first1: BaseOps.begin(), last1: BaseOps.end(),
2018 first2: RHS.BaseOps.begin(), last2: RHS.BaseOps.end(),
2019 comp: Compare))
2020 return true;
2021 if (std::lexicographical_compare(first1: RHS.BaseOps.begin(), last1: RHS.BaseOps.end(),
2022 first2: BaseOps.begin(), last2: BaseOps.end(), comp: Compare))
2023 return false;
2024 if (Offset != RHS.Offset)
2025 return Offset < RHS.Offset;
2026 return SU->NodeNum < RHS.SU->NodeNum;
2027 }
2028 };
2029
2030 const TargetInstrInfo *TII;
2031 const TargetRegisterInfo *TRI;
2032 bool IsLoad;
2033 bool ReorderWhileClustering;
2034
2035public:
2036 BaseMemOpClusterMutation(const TargetInstrInfo *tii,
2037 const TargetRegisterInfo *tri, bool IsLoad,
2038 bool ReorderWhileClustering)
2039 : TII(tii), TRI(tri), IsLoad(IsLoad),
2040 ReorderWhileClustering(ReorderWhileClustering) {}
2041
2042 void apply(ScheduleDAGInstrs *DAGInstrs) override;
2043
2044protected:
2045 void clusterNeighboringMemOps(ArrayRef<MemOpInfo> MemOps, bool FastCluster,
2046 ScheduleDAGInstrs *DAG);
2047 void collectMemOpRecords(std::vector<SUnit> &SUnits,
2048 SmallVectorImpl<MemOpInfo> &MemOpRecords);
2049 bool groupMemOps(ArrayRef<MemOpInfo> MemOps, ScheduleDAGInstrs *DAG,
2050 DenseMap<unsigned, SmallVector<MemOpInfo, 32>> &Groups);
2051};
2052
2053class StoreClusterMutation : public BaseMemOpClusterMutation {
2054public:
2055 StoreClusterMutation(const TargetInstrInfo *tii,
2056 const TargetRegisterInfo *tri,
2057 bool ReorderWhileClustering)
2058 : BaseMemOpClusterMutation(tii, tri, false, ReorderWhileClustering) {}
2059};
2060
2061class LoadClusterMutation : public BaseMemOpClusterMutation {
2062public:
2063 LoadClusterMutation(const TargetInstrInfo *tii, const TargetRegisterInfo *tri,
2064 bool ReorderWhileClustering)
2065 : BaseMemOpClusterMutation(tii, tri, true, ReorderWhileClustering) {}
2066};
2067
2068} // end anonymous namespace
2069
2070std::unique_ptr<ScheduleDAGMutation>
2071llvm::createLoadClusterDAGMutation(const TargetInstrInfo *TII,
2072 const TargetRegisterInfo *TRI,
2073 bool ReorderWhileClustering) {
2074 return EnableMemOpCluster ? std::make_unique<LoadClusterMutation>(
2075 args&: TII, args&: TRI, args&: ReorderWhileClustering)
2076 : nullptr;
2077}
2078
2079std::unique_ptr<ScheduleDAGMutation>
2080llvm::createStoreClusterDAGMutation(const TargetInstrInfo *TII,
2081 const TargetRegisterInfo *TRI,
2082 bool ReorderWhileClustering) {
2083 return EnableMemOpCluster ? std::make_unique<StoreClusterMutation>(
2084 args&: TII, args&: TRI, args&: ReorderWhileClustering)
2085 : nullptr;
2086}
2087
2088// Sorting all the loads/stores first, then for each load/store, checking the
2089// following load/store one by one, until reach the first non-dependent one and
2090// call target hook to see if they can cluster.
2091// If FastCluster is enabled, we assume that, all the loads/stores have been
2092// preprocessed and now, they didn't have dependencies on each other.
2093void BaseMemOpClusterMutation::clusterNeighboringMemOps(
2094 ArrayRef<MemOpInfo> MemOpRecords, bool FastCluster,
2095 ScheduleDAGInstrs *DAG) {
2096 // Keep track of the current cluster length and bytes for each SUnit.
2097 DenseMap<unsigned, std::pair<unsigned, unsigned>> SUnit2ClusterInfo;
2098 EquivalenceClasses<SUnit *> Clusters;
2099
2100 // At this point, `MemOpRecords` array must hold atleast two mem ops. Try to
2101 // cluster mem ops collected within `MemOpRecords` array.
2102 for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {
2103 // Decision to cluster mem ops is taken based on target dependent logic
2104 auto MemOpa = MemOpRecords[Idx];
2105
2106 // Seek for the next load/store to do the cluster.
2107 unsigned NextIdx = Idx + 1;
2108 for (; NextIdx < End; ++NextIdx)
2109 // Skip if MemOpb has been clustered already or has dependency with
2110 // MemOpa.
2111 if (!SUnit2ClusterInfo.count(Val: MemOpRecords[NextIdx].SU->NodeNum) &&
2112 (FastCluster ||
2113 (!DAG->IsReachable(SU: MemOpRecords[NextIdx].SU, TargetSU: MemOpa.SU) &&
2114 !DAG->IsReachable(SU: MemOpa.SU, TargetSU: MemOpRecords[NextIdx].SU))))
2115 break;
2116 if (NextIdx == End)
2117 continue;
2118
2119 auto MemOpb = MemOpRecords[NextIdx];
2120 unsigned ClusterLength = 2;
2121 unsigned CurrentClusterBytes = MemOpa.Width.getValue().getKnownMinValue() +
2122 MemOpb.Width.getValue().getKnownMinValue();
2123 auto It = SUnit2ClusterInfo.find(Val: MemOpa.SU->NodeNum);
2124 if (It != SUnit2ClusterInfo.end()) {
2125 const auto &[Len, Bytes] = It->second;
2126 ClusterLength = Len + 1;
2127 CurrentClusterBytes = Bytes + MemOpb.Width.getValue().getKnownMinValue();
2128 }
2129
2130 if (!TII->shouldClusterMemOps(BaseOps1: MemOpa.BaseOps, Offset1: MemOpa.Offset,
2131 OffsetIsScalable1: MemOpa.OffsetIsScalable, BaseOps2: MemOpb.BaseOps,
2132 Offset2: MemOpb.Offset, OffsetIsScalable2: MemOpb.OffsetIsScalable,
2133 ClusterSize: ClusterLength, NumBytes: CurrentClusterBytes))
2134 continue;
2135
2136 SUnit *SUa = MemOpa.SU;
2137 SUnit *SUb = MemOpb.SU;
2138
2139 if (!ReorderWhileClustering && SUa->NodeNum > SUb->NodeNum)
2140 std::swap(a&: SUa, b&: SUb);
2141
2142 // FIXME: Is this check really required?
2143 if (!DAG->addEdge(SuccSU: SUb, PredDep: SDep(SUa, SDep::Cluster)))
2144 continue;
2145
2146 Clusters.unionSets(V1: SUa, V2: SUb);
2147 LLVM_DEBUG(dbgs() << "Cluster ld/st SU(" << SUa->NodeNum << ") - SU("
2148 << SUb->NodeNum << ")\n");
2149 ++NumClustered;
2150
2151 if (IsLoad) {
2152 // Copy successor edges from SUa to SUb. Interleaving computation
2153 // dependent on SUa can prevent load combining due to register reuse.
2154 // Predecessor edges do not need to be copied from SUb to SUa since
2155 // nearby loads should have effectively the same inputs.
2156 for (const SDep &Succ : SUa->Succs) {
2157 if (Succ.getSUnit() == SUb)
2158 continue;
2159 LLVM_DEBUG(dbgs() << " Copy Succ SU(" << Succ.getSUnit()->NodeNum
2160 << ")\n");
2161 DAG->addEdge(SuccSU: Succ.getSUnit(), PredDep: SDep(SUb, SDep::Artificial));
2162 }
2163 } else {
2164 // Copy predecessor edges from SUb to SUa to avoid the SUnits that
2165 // SUb dependent on scheduled in-between SUb and SUa. Successor edges
2166 // do not need to be copied from SUa to SUb since no one will depend
2167 // on stores.
2168 // Notice that, we don't need to care about the memory dependency as
2169 // we won't try to cluster them if they have any memory dependency.
2170 for (const SDep &Pred : SUb->Preds) {
2171 if (Pred.getSUnit() == SUa)
2172 continue;
2173 LLVM_DEBUG(dbgs() << " Copy Pred SU(" << Pred.getSUnit()->NodeNum
2174 << ")\n");
2175 DAG->addEdge(SuccSU: SUa, PredDep: SDep(Pred.getSUnit(), SDep::Artificial));
2176 }
2177 }
2178
2179 SUnit2ClusterInfo[MemOpb.SU->NodeNum] = {ClusterLength,
2180 CurrentClusterBytes};
2181
2182 LLVM_DEBUG(dbgs() << " Curr cluster length: " << ClusterLength
2183 << ", Curr cluster bytes: " << CurrentClusterBytes
2184 << "\n");
2185 }
2186
2187 // Add cluster group information.
2188 // Iterate over all of the equivalence sets.
2189 auto &AllClusters = DAG->getClusters();
2190 for (const EquivalenceClasses<SUnit *>::ECValue *I : Clusters) {
2191 if (!I->isLeader())
2192 continue;
2193 ClusterInfo Group;
2194 unsigned ClusterIdx = AllClusters.size();
2195 for (SUnit *MemberI : Clusters.members(ECV: *I)) {
2196 MemberI->ParentClusterIdx = ClusterIdx;
2197 Group.insert(Ptr: MemberI);
2198 }
2199 AllClusters.push_back(Elt: Group);
2200 }
2201}
2202
2203void BaseMemOpClusterMutation::collectMemOpRecords(
2204 std::vector<SUnit> &SUnits, SmallVectorImpl<MemOpInfo> &MemOpRecords) {
2205 for (auto &SU : SUnits) {
2206 if ((IsLoad && !SU.getInstr()->mayLoad()) ||
2207 (!IsLoad && !SU.getInstr()->mayStore()))
2208 continue;
2209
2210 const MachineInstr &MI = *SU.getInstr();
2211 SmallVector<const MachineOperand *, 4> BaseOps;
2212 int64_t Offset;
2213 bool OffsetIsScalable;
2214 LocationSize Width = LocationSize::precise(Value: 0);
2215 if (TII->getMemOperandsWithOffsetWidth(MI, BaseOps, Offset,
2216 OffsetIsScalable, Width, TRI)) {
2217 if (!Width.hasValue())
2218 continue;
2219
2220 MemOpRecords.push_back(
2221 Elt: MemOpInfo(&SU, BaseOps, Offset, OffsetIsScalable, Width));
2222
2223 LLVM_DEBUG(dbgs() << "Num BaseOps: " << BaseOps.size() << ", Offset: "
2224 << Offset << ", OffsetIsScalable: " << OffsetIsScalable
2225 << ", Width: " << Width << "\n");
2226 }
2227#ifndef NDEBUG
2228 for (const auto *Op : BaseOps)
2229 assert(Op);
2230#endif
2231 }
2232}
2233
2234bool BaseMemOpClusterMutation::groupMemOps(
2235 ArrayRef<MemOpInfo> MemOps, ScheduleDAGInstrs *DAG,
2236 DenseMap<unsigned, SmallVector<MemOpInfo, 32>> &Groups) {
2237 bool FastCluster =
2238 ForceFastCluster ||
2239 MemOps.size() * DAG->SUnits.size() / 1000 > FastClusterThreshold;
2240
2241 for (const auto &MemOp : MemOps) {
2242 unsigned ChainPredID = DAG->SUnits.size();
2243 if (FastCluster) {
2244 for (const SDep &Pred : MemOp.SU->Preds) {
2245 // We only want to cluster the mem ops that have the same ctrl(non-data)
2246 // pred so that they didn't have ctrl dependency for each other. But for
2247 // store instrs, we can still cluster them if the pred is load instr.
2248 if ((Pred.isCtrl() &&
2249 (IsLoad ||
2250 (Pred.getSUnit() && Pred.getSUnit()->getInstr()->mayStore()))) &&
2251 !Pred.isArtificial()) {
2252 ChainPredID = Pred.getSUnit()->NodeNum;
2253 break;
2254 }
2255 }
2256 } else
2257 ChainPredID = 0;
2258
2259 Groups[ChainPredID].push_back(Elt: MemOp);
2260 }
2261 return FastCluster;
2262}
2263
2264/// Callback from DAG postProcessing to create cluster edges for loads/stores.
2265void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAG) {
2266 // Collect all the clusterable loads/stores
2267 SmallVector<MemOpInfo, 32> MemOpRecords;
2268 collectMemOpRecords(SUnits&: DAG->SUnits, MemOpRecords);
2269
2270 if (MemOpRecords.size() < 2)
2271 return;
2272
2273 // Put the loads/stores without dependency into the same group with some
2274 // heuristic if the DAG is too complex to avoid compiling time blow up.
2275 // Notice that, some fusion pair could be lost with this.
2276 DenseMap<unsigned, SmallVector<MemOpInfo, 32>> Groups;
2277 bool FastCluster = groupMemOps(MemOps: MemOpRecords, DAG, Groups);
2278
2279 for (auto &Group : Groups) {
2280 // Sorting the loads/stores, so that, we can stop the cluster as early as
2281 // possible.
2282 llvm::sort(C&: Group.second);
2283
2284 // Trying to cluster all the neighboring loads/stores.
2285 clusterNeighboringMemOps(MemOpRecords: Group.second, FastCluster, DAG);
2286 }
2287}
2288
2289//===----------------------------------------------------------------------===//
2290// CopyConstrain - DAG post-processing to encourage copy elimination.
2291//===----------------------------------------------------------------------===//
2292
2293namespace {
2294
2295/// Post-process the DAG to create weak edges from all uses of a copy to
2296/// the one use that defines the copy's source vreg, most likely an induction
2297/// variable increment.
2298class CopyConstrain : public ScheduleDAGMutation {
2299 // Transient state.
2300 SlotIndex RegionBeginIdx;
2301
2302 // RegionEndIdx is the slot index of the last non-debug instruction in the
2303 // scheduling region. So we may have RegionBeginIdx == RegionEndIdx.
2304 SlotIndex RegionEndIdx;
2305
2306public:
2307 CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}
2308
2309 void apply(ScheduleDAGInstrs *DAGInstrs) override;
2310
2311protected:
2312 void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG);
2313};
2314
2315} // end anonymous namespace
2316
2317std::unique_ptr<ScheduleDAGMutation>
2318llvm::createCopyConstrainDAGMutation(const TargetInstrInfo *TII,
2319 const TargetRegisterInfo *TRI) {
2320 return std::make_unique<CopyConstrain>(args&: TII, args&: TRI);
2321}
2322
2323/// constrainLocalCopy handles two possibilities:
2324/// 1) Local src:
2325/// I0: = dst
2326/// I1: src = ...
2327/// I2: = dst
2328/// I3: dst = src (copy)
2329/// (create pred->succ edges I0->I1, I2->I1)
2330///
2331/// 2) Local copy:
2332/// I0: dst = src (copy)
2333/// I1: = dst
2334/// I2: src = ...
2335/// I3: = dst
2336/// (create pred->succ edges I1->I2, I3->I2)
2337///
2338/// Although the MachineScheduler is currently constrained to single blocks,
2339/// this algorithm should handle extended blocks. An EBB is a set of
2340/// contiguously numbered blocks such that the previous block in the EBB is
2341/// always the single predecessor.
2342void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG) {
2343 LiveIntervals *LIS = DAG->getLIS();
2344 MachineInstr *Copy = CopySU->getInstr();
2345
2346 // Check for pure vreg copies.
2347 const MachineOperand &SrcOp = Copy->getOperand(i: 1);
2348 Register SrcReg = SrcOp.getReg();
2349 if (!SrcReg.isVirtual() || !SrcOp.readsReg())
2350 return;
2351
2352 const MachineOperand &DstOp = Copy->getOperand(i: 0);
2353 Register DstReg = DstOp.getReg();
2354 if (!DstReg.isVirtual() || DstOp.isDead())
2355 return;
2356
2357 // Check if either the dest or source is local. If it's live across a back
2358 // edge, it's not local. Note that if both vregs are live across the back
2359 // edge, we cannot successfully contrain the copy without cyclic scheduling.
2360 // If both the copy's source and dest are local live intervals, then we
2361 // should treat the dest as the global for the purpose of adding
2362 // constraints. This adds edges from source's other uses to the copy.
2363 unsigned LocalReg = SrcReg;
2364 unsigned GlobalReg = DstReg;
2365 LiveInterval *LocalLI = &LIS->getInterval(Reg: LocalReg);
2366 if (!LocalLI->isLocal(Start: RegionBeginIdx, End: RegionEndIdx)) {
2367 LocalReg = DstReg;
2368 GlobalReg = SrcReg;
2369 LocalLI = &LIS->getInterval(Reg: LocalReg);
2370 if (!LocalLI->isLocal(Start: RegionBeginIdx, End: RegionEndIdx))
2371 return;
2372 }
2373 LiveInterval *GlobalLI = &LIS->getInterval(Reg: GlobalReg);
2374
2375 // Find the global segment after the start of the local LI.
2376 LiveInterval::iterator GlobalSegment = GlobalLI->find(Pos: LocalLI->beginIndex());
2377 // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a
2378 // local live range. We could create edges from other global uses to the local
2379 // start, but the coalescer should have already eliminated these cases, so
2380 // don't bother dealing with it.
2381 if (GlobalSegment == GlobalLI->end())
2382 return;
2383
2384 // If GlobalSegment is killed at the LocalLI->start, the call to find()
2385 // returned the next global segment. But if GlobalSegment overlaps with
2386 // LocalLI->start, then advance to the next segment. If a hole in GlobalLI
2387 // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole.
2388 if (GlobalSegment->contains(I: LocalLI->beginIndex()))
2389 ++GlobalSegment;
2390
2391 if (GlobalSegment == GlobalLI->end())
2392 return;
2393
2394 // Check if GlobalLI contains a hole in the vicinity of LocalLI.
2395 if (GlobalSegment != GlobalLI->begin()) {
2396 // Two address defs have no hole.
2397 if (SlotIndex::isSameInstr(A: std::prev(x: GlobalSegment)->end,
2398 B: GlobalSegment->start)) {
2399 return;
2400 }
2401 // If the prior global segment may be defined by the same two-address
2402 // instruction that also defines LocalLI, then can't make a hole here.
2403 if (SlotIndex::isSameInstr(A: std::prev(x: GlobalSegment)->start,
2404 B: LocalLI->beginIndex())) {
2405 return;
2406 }
2407 // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise
2408 // it would be a disconnected component in the live range.
2409 assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&
2410 "Disconnected LRG within the scheduling region.");
2411 }
2412 MachineInstr *GlobalDef = LIS->getInstructionFromIndex(index: GlobalSegment->start);
2413 if (!GlobalDef)
2414 return;
2415
2416 SUnit *GlobalSU = DAG->getSUnit(MI: GlobalDef);
2417 if (!GlobalSU)
2418 return;
2419
2420 // GlobalDef is the bottom of the GlobalLI hole. Open the hole by
2421 // constraining the uses of the last local def to precede GlobalDef.
2422 SmallVector<SUnit*,8> LocalUses;
2423 const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(Idx: LocalLI->endIndex());
2424 MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(index: LastLocalVN->def);
2425 SUnit *LastLocalSU = DAG->getSUnit(MI: LastLocalDef);
2426 for (const SDep &Succ : LastLocalSU->Succs) {
2427 if (Succ.getKind() != SDep::Data || Succ.getReg() != LocalReg)
2428 continue;
2429 if (Succ.getSUnit() == GlobalSU)
2430 continue;
2431 if (!DAG->canAddEdge(SuccSU: GlobalSU, PredSU: Succ.getSUnit()))
2432 return;
2433 LocalUses.push_back(Elt: Succ.getSUnit());
2434 }
2435 // Open the top of the GlobalLI hole by constraining any earlier global uses
2436 // to precede the start of LocalLI.
2437 SmallVector<SUnit*,8> GlobalUses;
2438 MachineInstr *FirstLocalDef =
2439 LIS->getInstructionFromIndex(index: LocalLI->beginIndex());
2440 SUnit *FirstLocalSU = DAG->getSUnit(MI: FirstLocalDef);
2441 for (const SDep &Pred : GlobalSU->Preds) {
2442 if (Pred.getKind() != SDep::Anti || Pred.getReg() != GlobalReg)
2443 continue;
2444 if (Pred.getSUnit() == FirstLocalSU)
2445 continue;
2446 if (!DAG->canAddEdge(SuccSU: FirstLocalSU, PredSU: Pred.getSUnit()))
2447 return;
2448 GlobalUses.push_back(Elt: Pred.getSUnit());
2449 }
2450 LLVM_DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n");
2451 // Add the weak edges.
2452 for (SUnit *LU : LocalUses) {
2453 LLVM_DEBUG(dbgs() << " Local use SU(" << LU->NodeNum << ") -> SU("
2454 << GlobalSU->NodeNum << ")\n");
2455 DAG->addEdge(SuccSU: GlobalSU, PredDep: SDep(LU, SDep::Weak));
2456 }
2457 for (SUnit *GU : GlobalUses) {
2458 LLVM_DEBUG(dbgs() << " Global use SU(" << GU->NodeNum << ") -> SU("
2459 << FirstLocalSU->NodeNum << ")\n");
2460 DAG->addEdge(SuccSU: FirstLocalSU, PredDep: SDep(GU, SDep::Weak));
2461 }
2462}
2463
2464/// Callback from DAG postProcessing to create weak edges to encourage
2465/// copy elimination.
2466void CopyConstrain::apply(ScheduleDAGInstrs *DAGInstrs) {
2467 ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
2468 assert(DAG->hasVRegLiveness() && "Expect VRegs with LiveIntervals");
2469
2470 MachineBasicBlock::iterator FirstPos = nextIfDebug(I: DAG->begin(), End: DAG->end());
2471 if (FirstPos == DAG->end())
2472 return;
2473 RegionBeginIdx = DAG->getLIS()->getInstructionIndex(Instr: *FirstPos);
2474 RegionEndIdx = DAG->getLIS()->getInstructionIndex(
2475 Instr: *priorNonDebug(I: DAG->end(), Beg: DAG->begin()));
2476
2477 for (SUnit &SU : DAG->SUnits) {
2478 if (!SU.getInstr()->isCopy())
2479 continue;
2480
2481 constrainLocalCopy(CopySU: &SU, DAG: static_cast<ScheduleDAGMILive*>(DAG));
2482 }
2483}
2484
2485//===----------------------------------------------------------------------===//
2486// MachineSchedStrategy helpers used by GenericScheduler, GenericPostScheduler
2487// and possibly other custom schedulers.
2488//===----------------------------------------------------------------------===//
2489
2490static const unsigned InvalidCycle = ~0U;
2491
2492SchedBoundary::~SchedBoundary() = default;
2493
2494/// Given a Count of resource usage and a Latency value, return true if a
2495/// SchedBoundary becomes resource limited.
2496/// If we are checking after scheduling a node, we should return true when
2497/// we just reach the resource limit.
2498static bool checkResourceLimit(unsigned LFactor, unsigned Count,
2499 unsigned Latency, bool AfterSchedNode) {
2500 int ResCntFactor = (int)(Count - (Latency * LFactor));
2501 if (AfterSchedNode)
2502 return ResCntFactor >= (int)LFactor;
2503 else
2504 return ResCntFactor > (int)LFactor;
2505}
2506
2507void SchedBoundary::reset() {
2508 // A new HazardRec is created for each DAG and owned by SchedBoundary.
2509 // Destroying and reconstructing it is very expensive though. So keep
2510 // invalid, placeholder HazardRecs.
2511 if (HazardRec && HazardRec->isEnabled())
2512 HazardRec.reset();
2513 Available.clear();
2514 Pending.clear();
2515 CheckPending = false;
2516 CurrCycle = 0;
2517 CurrMOps = 0;
2518 MinReadyCycle = std::numeric_limits<unsigned>::max();
2519 ExpectedLatency = 0;
2520 DependentLatency = 0;
2521 RetiredMOps = 0;
2522 MaxExecutedResCount = 0;
2523 ZoneCritResIdx = 0;
2524 IsResourceLimited = false;
2525 ReservedCycles.clear();
2526 ReservedResourceSegments.clear();
2527 ReservedCyclesIndex.clear();
2528 ResourceGroupSubUnitMasks.clear();
2529#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2530 // Track the maximum number of stall cycles that could arise either from the
2531 // latency of a DAG edge or the number of cycles that a processor resource is
2532 // reserved (SchedBoundary::ReservedCycles).
2533 MaxObservedStall = 0;
2534#endif
2535 // Reserve a zero-count for invalid CritResIdx.
2536 ExecutedResCounts.resize(N: 1);
2537 assert(!ExecutedResCounts[0] && "nonzero count for bad resource");
2538}
2539
2540void SchedRemainder::
2541init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
2542 reset();
2543 if (!SchedModel->hasInstrSchedModel())
2544 return;
2545 RemainingCounts.resize(N: SchedModel->getNumProcResourceKinds());
2546 for (SUnit &SU : DAG->SUnits) {
2547 const MCSchedClassDesc *SC = DAG->getSchedClass(SU: &SU);
2548 RemIssueCount += SchedModel->getNumMicroOps(MI: SU.getInstr(), SC)
2549 * SchedModel->getMicroOpFactor();
2550 for (TargetSchedModel::ProcResIter
2551 PI = SchedModel->getWriteProcResBegin(SC),
2552 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2553 unsigned PIdx = PI->ProcResourceIdx;
2554 unsigned Factor = SchedModel->getResourceFactor(ResIdx: PIdx);
2555 assert(PI->ReleaseAtCycle >= PI->AcquireAtCycle);
2556 RemainingCounts[PIdx] +=
2557 (Factor * (PI->ReleaseAtCycle - PI->AcquireAtCycle));
2558 }
2559 }
2560}
2561
2562void SchedBoundary::
2563init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
2564 reset();
2565 DAG = dag;
2566 SchedModel = smodel;
2567 Rem = rem;
2568 if (SchedModel->hasInstrSchedModel()) {
2569 unsigned ResourceCount = SchedModel->getNumProcResourceKinds();
2570 ReservedCyclesIndex.resize(N: ResourceCount);
2571 ExecutedResCounts.resize(N: ResourceCount);
2572 ResourceGroupSubUnitMasks.resize(N: ResourceCount, NV: APInt(ResourceCount, 0));
2573 unsigned NumUnits = 0;
2574
2575 for (unsigned i = 0; i < ResourceCount; ++i) {
2576 ReservedCyclesIndex[i] = NumUnits;
2577 NumUnits += SchedModel->getProcResource(PIdx: i)->NumUnits;
2578 if (isReservedGroup(PIdx: i)) {
2579 auto SubUnits = SchedModel->getProcResource(PIdx: i)->SubUnitsIdxBegin;
2580 for (unsigned U = 0, UE = SchedModel->getProcResource(PIdx: i)->NumUnits;
2581 U != UE; ++U)
2582 ResourceGroupSubUnitMasks[i].setBit(SubUnits[U]);
2583 }
2584 }
2585
2586 ReservedCycles.resize(new_size: NumUnits, x: InvalidCycle);
2587 }
2588}
2589
2590/// Compute the stall cycles based on this SUnit's ready time. Heuristics treat
2591/// these "soft stalls" differently than the hard stall cycles based on CPU
2592/// resources and computed by checkHazard(). A fully in-order model
2593/// (MicroOpBufferSize==0) will not make use of this since instructions are not
2594/// available for scheduling until they are ready. However, a weaker in-order
2595/// model may use this for heuristics. For example, if a processor has in-order
2596/// behavior when reading certain resources, this may come into play.
2597unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {
2598 if (!SU->isUnbuffered)
2599 return 0;
2600
2601 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
2602 if (ReadyCycle > CurrCycle)
2603 return ReadyCycle - CurrCycle;
2604 return 0;
2605}
2606
2607/// Compute the next cycle at which the given processor resource unit
2608/// can be scheduled.
2609unsigned SchedBoundary::getNextResourceCycleByInstance(unsigned InstanceIdx,
2610 unsigned ReleaseAtCycle,
2611 unsigned AcquireAtCycle) {
2612 if (SchedModel && SchedModel->enableIntervals()) {
2613 if (isTop())
2614 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromTop(
2615 CurrCycle, AcquireAtCycle, ReleaseAtCycle);
2616
2617 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromBottom(
2618 CurrCycle, AcquireAtCycle, ReleaseAtCycle);
2619 }
2620
2621 unsigned NextUnreserved = ReservedCycles[InstanceIdx];
2622 // If this resource has never been used, always return cycle zero.
2623 if (NextUnreserved == InvalidCycle)
2624 return CurrCycle;
2625 // For bottom-up scheduling add the cycles needed for the current operation.
2626 if (!isTop())
2627 NextUnreserved = std::max(a: CurrCycle, b: NextUnreserved + ReleaseAtCycle);
2628 return NextUnreserved;
2629}
2630
2631/// Compute the next cycle at which the given processor resource can be
2632/// scheduled. Returns the next cycle and the index of the processor resource
2633/// instance in the reserved cycles vector.
2634std::pair<unsigned, unsigned>
2635SchedBoundary::getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx,
2636 unsigned ReleaseAtCycle,
2637 unsigned AcquireAtCycle) {
2638 if (MischedDetailResourceBooking) {
2639 LLVM_DEBUG(dbgs() << " Resource booking (@" << CurrCycle << "c): \n");
2640 LLVM_DEBUG(dumpReservedCycles());
2641 LLVM_DEBUG(dbgs() << " getNextResourceCycle (@" << CurrCycle << "c): \n");
2642 }
2643 unsigned MinNextUnreserved = InvalidCycle;
2644 unsigned InstanceIdx = 0;
2645 unsigned StartIndex = ReservedCyclesIndex[PIdx];
2646 unsigned NumberOfInstances = SchedModel->getProcResource(PIdx)->NumUnits;
2647 assert(NumberOfInstances > 0 &&
2648 "Cannot have zero instances of a ProcResource");
2649
2650 if (isReservedGroup(PIdx)) {
2651 // If any subunits are used by the instruction, report that the
2652 // subunits of the resource group are available at the first cycle
2653 // in which the unit is available, effectively removing the group
2654 // record from hazarding and basing the hazarding decisions on the
2655 // subunit records. Otherwise, choose the first available instance
2656 // from among the subunits. Specifications which assign cycles to
2657 // both the subunits and the group or which use an unbuffered
2658 // group with buffered subunits will appear to schedule
2659 // strangely. In the first case, the additional cycles for the
2660 // group will be ignored. In the second, the group will be
2661 // ignored entirely.
2662 for (const MCWriteProcResEntry &PE :
2663 make_range(x: SchedModel->getWriteProcResBegin(SC),
2664 y: SchedModel->getWriteProcResEnd(SC)))
2665 if (ResourceGroupSubUnitMasks[PIdx][PE.ProcResourceIdx])
2666 return std::make_pair(x: getNextResourceCycleByInstance(
2667 InstanceIdx: StartIndex, ReleaseAtCycle, AcquireAtCycle),
2668 y&: StartIndex);
2669
2670 auto SubUnits = SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin;
2671 for (unsigned I = 0, End = NumberOfInstances; I < End; ++I) {
2672 unsigned NextUnreserved, NextInstanceIdx;
2673 std::tie(args&: NextUnreserved, args&: NextInstanceIdx) =
2674 getNextResourceCycle(SC, PIdx: SubUnits[I], ReleaseAtCycle, AcquireAtCycle);
2675 if (MinNextUnreserved > NextUnreserved) {
2676 InstanceIdx = NextInstanceIdx;
2677 MinNextUnreserved = NextUnreserved;
2678 }
2679 }
2680 return std::make_pair(x&: MinNextUnreserved, y&: InstanceIdx);
2681 }
2682
2683 for (unsigned I = StartIndex, End = StartIndex + NumberOfInstances; I < End;
2684 ++I) {
2685 unsigned NextUnreserved =
2686 getNextResourceCycleByInstance(InstanceIdx: I, ReleaseAtCycle, AcquireAtCycle);
2687 if (MischedDetailResourceBooking)
2688 LLVM_DEBUG(dbgs() << " Instance " << I - StartIndex << " available @"
2689 << NextUnreserved << "c\n");
2690 if (MinNextUnreserved > NextUnreserved) {
2691 InstanceIdx = I;
2692 MinNextUnreserved = NextUnreserved;
2693 }
2694 }
2695 if (MischedDetailResourceBooking)
2696 LLVM_DEBUG(dbgs() << " selecting " << SchedModel->getResourceName(PIdx)
2697 << "[" << InstanceIdx - StartIndex << "]"
2698 << " available @" << MinNextUnreserved << "c"
2699 << "\n");
2700 return std::make_pair(x&: MinNextUnreserved, y&: InstanceIdx);
2701}
2702
2703/// Does this SU have a hazard within the current instruction group.
2704///
2705/// The scheduler supports two modes of hazard recognition. The first is the
2706/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
2707/// supports highly complicated in-order reservation tables
2708/// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
2709///
2710/// The second is a streamlined mechanism that checks for hazards based on
2711/// simple counters that the scheduler itself maintains. It explicitly checks
2712/// for instruction dispatch limitations, including the number of micro-ops that
2713/// can dispatch per cycle.
2714///
2715/// TODO: Also check whether the SU must start a new group.
2716bool SchedBoundary::checkHazard(SUnit *SU) {
2717 if (HazardRec->isEnabled()
2718 && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard) {
2719 LLVM_DEBUG(dbgs().indent(2)
2720 << "hazard: SU(" << SU->NodeNum << ") reported by HazardRec\n");
2721 return true;
2722 }
2723
2724 unsigned uops = SchedModel->getNumMicroOps(MI: SU->getInstr());
2725 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {
2726 LLVM_DEBUG(dbgs().indent(2) << "hazard: SU(" << SU->NodeNum << ") uops="
2727 << uops << ", CurrMOps = " << CurrMOps << ", "
2728 << "CurrMOps + uops > issue width of "
2729 << SchedModel->getIssueWidth() << "\n");
2730 return true;
2731 }
2732
2733 if (CurrMOps > 0 &&
2734 ((isTop() && SchedModel->mustBeginGroup(MI: SU->getInstr())) ||
2735 (!isTop() && SchedModel->mustEndGroup(MI: SU->getInstr())))) {
2736 LLVM_DEBUG(dbgs().indent(2) << "hazard: SU(" << SU->NodeNum << ") must "
2737 << (isTop() ? "begin" : "end") << " group\n");
2738 return true;
2739 }
2740
2741 if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
2742 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
2743 for (const MCWriteProcResEntry &PE :
2744 make_range(x: SchedModel->getWriteProcResBegin(SC),
2745 y: SchedModel->getWriteProcResEnd(SC))) {
2746 unsigned ResIdx = PE.ProcResourceIdx;
2747 unsigned ReleaseAtCycle = PE.ReleaseAtCycle;
2748 unsigned AcquireAtCycle = PE.AcquireAtCycle;
2749 unsigned NRCycle, InstanceIdx;
2750 std::tie(args&: NRCycle, args&: InstanceIdx) =
2751 getNextResourceCycle(SC, PIdx: ResIdx, ReleaseAtCycle, AcquireAtCycle);
2752 if (NRCycle > CurrCycle) {
2753#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2754 MaxObservedStall = std::max(ReleaseAtCycle, MaxObservedStall);
2755#endif
2756 LLVM_DEBUG(dbgs().indent(2)
2757 << "hazard: SU(" << SU->NodeNum << ") "
2758 << SchedModel->getResourceName(ResIdx) << '['
2759 << InstanceIdx - ReservedCyclesIndex[ResIdx] << ']' << "="
2760 << NRCycle << "c, is later than "
2761 << "CurrCycle = " << CurrCycle << "c\n");
2762 return true;
2763 }
2764 }
2765 }
2766 return false;
2767}
2768
2769// Find the unscheduled node in ReadySUs with the highest latency.
2770unsigned SchedBoundary::
2771findMaxLatency(ArrayRef<SUnit*> ReadySUs) {
2772 SUnit *LateSU = nullptr;
2773 unsigned RemLatency = 0;
2774 for (SUnit *SU : ReadySUs) {
2775 unsigned L = getUnscheduledLatency(SU);
2776 if (L > RemLatency) {
2777 RemLatency = L;
2778 LateSU = SU;
2779 }
2780 }
2781 if (LateSU) {
2782 LLVM_DEBUG(dbgs() << Available.getName() << " RemLatency SU("
2783 << LateSU->NodeNum << ") " << RemLatency << "c\n");
2784 }
2785 return RemLatency;
2786}
2787
2788// Count resources in this zone and the remaining unscheduled
2789// instruction. Return the max count, scaled. Set OtherCritIdx to the critical
2790// resource index, or zero if the zone is issue limited.
2791unsigned SchedBoundary::
2792getOtherResourceCount(unsigned &OtherCritIdx) {
2793 OtherCritIdx = 0;
2794 if (!SchedModel->hasInstrSchedModel())
2795 return 0;
2796
2797 unsigned OtherCritCount = Rem->RemIssueCount
2798 + (RetiredMOps * SchedModel->getMicroOpFactor());
2799 LLVM_DEBUG(dbgs() << " " << Available.getName() << " + Remain MOps: "
2800 << OtherCritCount / SchedModel->getMicroOpFactor() << '\n');
2801 for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds();
2802 PIdx != PEnd; ++PIdx) {
2803 unsigned OtherCount = getResourceCount(ResIdx: PIdx) + Rem->RemainingCounts[PIdx];
2804 if (OtherCount > OtherCritCount) {
2805 OtherCritCount = OtherCount;
2806 OtherCritIdx = PIdx;
2807 }
2808 }
2809 if (OtherCritIdx) {
2810 LLVM_DEBUG(
2811 dbgs() << " " << Available.getName() << " + Remain CritRes: "
2812 << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)
2813 << " " << SchedModel->getResourceName(OtherCritIdx) << "\n");
2814 }
2815 return OtherCritCount;
2816}
2817
2818void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue,
2819 unsigned Idx) {
2820 assert(SU->getInstr() && "Scheduled SUnit must have instr");
2821
2822#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2823 // ReadyCycle was been bumped up to the CurrCycle when this node was
2824 // scheduled, but CurrCycle may have been eagerly advanced immediately after
2825 // scheduling, so may now be greater than ReadyCycle.
2826 if (ReadyCycle > CurrCycle)
2827 MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);
2828#endif
2829
2830 if (ReadyCycle < MinReadyCycle)
2831 MinReadyCycle = ReadyCycle;
2832
2833 // Check for interlocks first. For the purpose of other heuristics, an
2834 // instruction that cannot issue appears as if it's not in the ReadyQueue.
2835 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
2836 bool HazardDetected = !IsBuffered && ReadyCycle > CurrCycle;
2837 if (HazardDetected)
2838 LLVM_DEBUG(dbgs().indent(2) << "hazard: SU(" << SU->NodeNum
2839 << ") ReadyCycle = " << ReadyCycle
2840 << " is later than CurrCycle = " << CurrCycle
2841 << " on an unbuffered resource" << "\n");
2842 else
2843 HazardDetected = checkHazard(SU);
2844
2845 if (!HazardDetected && Available.size() >= ReadyListLimit) {
2846 HazardDetected = true;
2847 LLVM_DEBUG(dbgs().indent(2) << "hazard: Available Q is full (size: "
2848 << Available.size() << ")\n");
2849 }
2850
2851 if (!HazardDetected) {
2852 Available.push(SU);
2853 LLVM_DEBUG(dbgs().indent(2)
2854 << "Move SU(" << SU->NodeNum << ") into Available Q\n");
2855
2856 if (InPQueue)
2857 Pending.remove(I: Pending.begin() + Idx);
2858 return;
2859 }
2860
2861 if (!InPQueue)
2862 Pending.push(SU);
2863}
2864
2865/// Move the boundary of scheduled code by one cycle.
2866void SchedBoundary::bumpCycle(unsigned NextCycle) {
2867 if (SchedModel->getMicroOpBufferSize() == 0) {
2868 assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
2869 "MinReadyCycle uninitialized");
2870 if (MinReadyCycle > NextCycle)
2871 NextCycle = MinReadyCycle;
2872 }
2873 // Update the current micro-ops, which will issue in the next cycle.
2874 unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle);
2875 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
2876
2877 // Decrement DependentLatency based on the next cycle.
2878 if ((NextCycle - CurrCycle) > DependentLatency)
2879 DependentLatency = 0;
2880 else
2881 DependentLatency -= (NextCycle - CurrCycle);
2882
2883 if (!HazardRec->isEnabled()) {
2884 // Bypass HazardRec virtual calls.
2885 CurrCycle = NextCycle;
2886 } else {
2887 // Bypass getHazardType calls in case of long latency.
2888 for (; CurrCycle != NextCycle; ++CurrCycle) {
2889 if (isTop())
2890 HazardRec->AdvanceCycle();
2891 else
2892 HazardRec->RecedeCycle();
2893 }
2894 }
2895 CheckPending = true;
2896 IsResourceLimited =
2897 checkResourceLimit(LFactor: SchedModel->getLatencyFactor(), Count: getCriticalCount(),
2898 Latency: getScheduledLatency(), AfterSchedNode: true);
2899
2900 LLVM_DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName()
2901 << '\n');
2902}
2903
2904void SchedBoundary::incExecutedResources(unsigned PIdx, unsigned Count) {
2905 ExecutedResCounts[PIdx] += Count;
2906 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
2907 MaxExecutedResCount = ExecutedResCounts[PIdx];
2908}
2909
2910/// Add the given processor resource to this scheduled zone.
2911///
2912/// \param ReleaseAtCycle indicates the number of consecutive (non-pipelined)
2913/// cycles during which this resource is released.
2914///
2915/// \param AcquireAtCycle indicates the number of consecutive (non-pipelined)
2916/// cycles at which the resource is aquired after issue (assuming no stalls).
2917///
2918/// \return the next cycle at which the instruction may execute without
2919/// oversubscribing resources.
2920unsigned SchedBoundary::countResource(const MCSchedClassDesc *SC, unsigned PIdx,
2921 unsigned ReleaseAtCycle,
2922 unsigned NextCycle,
2923 unsigned AcquireAtCycle) {
2924 unsigned Factor = SchedModel->getResourceFactor(ResIdx: PIdx);
2925 unsigned Count = Factor * (ReleaseAtCycle- AcquireAtCycle);
2926 LLVM_DEBUG(dbgs() << " " << SchedModel->getResourceName(PIdx) << " +"
2927 << ReleaseAtCycle << "x" << Factor << "u\n");
2928
2929 // Update Executed resources counts.
2930 incExecutedResources(PIdx, Count);
2931 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");
2932 Rem->RemainingCounts[PIdx] -= Count;
2933
2934 // Check if this resource exceeds the current critical resource. If so, it
2935 // becomes the critical resource.
2936 if (ZoneCritResIdx != PIdx && (getResourceCount(ResIdx: PIdx) > getCriticalCount())) {
2937 ZoneCritResIdx = PIdx;
2938 LLVM_DEBUG(dbgs() << " *** Critical resource "
2939 << SchedModel->getResourceName(PIdx) << ": "
2940 << getResourceCount(PIdx) / SchedModel->getLatencyFactor()
2941 << "c\n");
2942 }
2943 // For reserved resources, record the highest cycle using the resource.
2944 unsigned NextAvailable, InstanceIdx;
2945 std::tie(args&: NextAvailable, args&: InstanceIdx) =
2946 getNextResourceCycle(SC, PIdx, ReleaseAtCycle, AcquireAtCycle);
2947 if (NextAvailable > CurrCycle) {
2948 LLVM_DEBUG(dbgs() << " Resource conflict: "
2949 << SchedModel->getResourceName(PIdx)
2950 << '[' << InstanceIdx - ReservedCyclesIndex[PIdx] << ']'
2951 << " reserved until @" << NextAvailable << "\n");
2952 }
2953 return NextAvailable;
2954}
2955
2956/// Move the boundary of scheduled code by one SUnit.
2957void SchedBoundary::bumpNode(SUnit *SU) {
2958 // checkHazard should prevent scheduling multiple instructions per cycle that
2959 // exceed the issue width.
2960 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
2961 unsigned IncMOps = SchedModel->getNumMicroOps(MI: SU->getInstr());
2962 assert(
2963 (CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) &&
2964 "Cannot schedule this instruction's MicroOps in the current cycle.");
2965
2966 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
2967 LLVM_DEBUG(dbgs() << " Ready @" << ReadyCycle << "c\n");
2968
2969 unsigned NextCycle = CurrCycle;
2970 switch (SchedModel->getMicroOpBufferSize()) {
2971 case 0:
2972 assert(ReadyCycle <= CurrCycle && "Broken PendingQueue");
2973 break;
2974 case 1:
2975 if (ReadyCycle > NextCycle) {
2976 NextCycle = ReadyCycle;
2977 LLVM_DEBUG(dbgs() << " *** Stall until: " << ReadyCycle << "\n");
2978 }
2979 break;
2980 default:
2981 // We don't currently model the OOO reorder buffer, so consider all
2982 // scheduled MOps to be "retired". We do loosely model in-order resource
2983 // latency. If this instruction uses an in-order resource, account for any
2984 // likely stall cycles.
2985 if (SU->isUnbuffered && ReadyCycle > NextCycle)
2986 NextCycle = ReadyCycle;
2987 break;
2988 }
2989 RetiredMOps += IncMOps;
2990
2991 // Update resource counts and critical resource.
2992 if (SchedModel->hasInstrSchedModel()) {
2993 unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor();
2994 assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted");
2995 Rem->RemIssueCount -= DecRemIssue;
2996 if (ZoneCritResIdx) {
2997 // Scale scheduled micro-ops for comparing with the critical resource.
2998 unsigned ScaledMOps =
2999 RetiredMOps * SchedModel->getMicroOpFactor();
3000
3001 // If scaled micro-ops are now more than the previous critical resource by
3002 // a full cycle, then micro-ops issue becomes critical.
3003 if ((int)(ScaledMOps - getResourceCount(ResIdx: ZoneCritResIdx))
3004 >= (int)SchedModel->getLatencyFactor()) {
3005 ZoneCritResIdx = 0;
3006 LLVM_DEBUG(dbgs() << " *** Critical resource NumMicroOps: "
3007 << ScaledMOps / SchedModel->getLatencyFactor()
3008 << "c\n");
3009 }
3010 }
3011 for (TargetSchedModel::ProcResIter
3012 PI = SchedModel->getWriteProcResBegin(SC),
3013 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
3014 unsigned RCycle =
3015 countResource(SC, PIdx: PI->ProcResourceIdx, ReleaseAtCycle: PI->ReleaseAtCycle, NextCycle,
3016 AcquireAtCycle: PI->AcquireAtCycle);
3017 if (RCycle > NextCycle)
3018 NextCycle = RCycle;
3019 }
3020 if (SU->hasReservedResource) {
3021 // For reserved resources, record the highest cycle using the resource.
3022 // For top-down scheduling, this is the cycle in which we schedule this
3023 // instruction plus the number of cycles the operations reserves the
3024 // resource. For bottom-up is it simply the instruction's cycle.
3025 for (TargetSchedModel::ProcResIter
3026 PI = SchedModel->getWriteProcResBegin(SC),
3027 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
3028 unsigned PIdx = PI->ProcResourceIdx;
3029 if (SchedModel->getResourceBufferSize(PIdx) == 0) {
3030
3031 if (SchedModel && SchedModel->enableIntervals()) {
3032 unsigned ReservedUntil, InstanceIdx;
3033 std::tie(args&: ReservedUntil, args&: InstanceIdx) = getNextResourceCycle(
3034 SC, PIdx, ReleaseAtCycle: PI->ReleaseAtCycle, AcquireAtCycle: PI->AcquireAtCycle);
3035 if (isTop()) {
3036 ReservedResourceSegments[InstanceIdx].add(
3037 A: ResourceSegments::getResourceIntervalTop(
3038 C: NextCycle, AcquireAtCycle: PI->AcquireAtCycle, ReleaseAtCycle: PI->ReleaseAtCycle),
3039 CutOff: MIResourceCutOff);
3040 } else {
3041 ReservedResourceSegments[InstanceIdx].add(
3042 A: ResourceSegments::getResourceIntervalBottom(
3043 C: NextCycle, AcquireAtCycle: PI->AcquireAtCycle, ReleaseAtCycle: PI->ReleaseAtCycle),
3044 CutOff: MIResourceCutOff);
3045 }
3046 } else {
3047
3048 unsigned ReservedUntil, InstanceIdx;
3049 std::tie(args&: ReservedUntil, args&: InstanceIdx) = getNextResourceCycle(
3050 SC, PIdx, ReleaseAtCycle: PI->ReleaseAtCycle, AcquireAtCycle: PI->AcquireAtCycle);
3051 if (isTop()) {
3052 ReservedCycles[InstanceIdx] =
3053 std::max(a: ReservedUntil, b: NextCycle + PI->ReleaseAtCycle);
3054 } else
3055 ReservedCycles[InstanceIdx] = NextCycle;
3056 }
3057 }
3058 }
3059 }
3060 }
3061 // Update ExpectedLatency and DependentLatency.
3062 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
3063 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
3064 if (SU->getDepth() > TopLatency) {
3065 TopLatency = SU->getDepth();
3066 LLVM_DEBUG(dbgs() << " " << Available.getName() << " TopLatency SU("
3067 << SU->NodeNum << ") " << TopLatency << "c\n");
3068 }
3069 if (SU->getHeight() > BotLatency) {
3070 BotLatency = SU->getHeight();
3071 LLVM_DEBUG(dbgs() << " " << Available.getName() << " BotLatency SU("
3072 << SU->NodeNum << ") " << BotLatency << "c\n");
3073 }
3074 // If we stall for any reason, bump the cycle.
3075 if (NextCycle > CurrCycle)
3076 bumpCycle(NextCycle);
3077 else
3078 // After updating ZoneCritResIdx and ExpectedLatency, check if we're
3079 // resource limited. If a stall occurred, bumpCycle does this.
3080 IsResourceLimited =
3081 checkResourceLimit(LFactor: SchedModel->getLatencyFactor(), Count: getCriticalCount(),
3082 Latency: getScheduledLatency(), AfterSchedNode: true);
3083
3084 // Update the reservation table.
3085 if (HazardRec->isEnabled()) {
3086 if (!isTop() && SU->isCall) {
3087 // Calls are scheduled with their preceding instructions. For bottom-up
3088 // scheduling, clear the pipeline state before emitting.
3089 HazardRec->Reset();
3090 }
3091 HazardRec->EmitInstruction(SU);
3092 // Scheduling an instruction may have made pending instructions available.
3093 CheckPending = true;
3094 }
3095
3096 // Update CurrMOps after calling bumpCycle to handle stalls, since bumpCycle
3097 // resets CurrMOps. Loop to handle instructions with more MOps than issue in
3098 // one cycle. Since we commonly reach the max MOps here, opportunistically
3099 // bump the cycle to avoid uselessly checking everything in the readyQ.
3100 CurrMOps += IncMOps;
3101
3102 // Bump the cycle count for issue group constraints.
3103 // This must be done after NextCycle has been adjust for all other stalls.
3104 // Calling bumpCycle(X) will reduce CurrMOps by one issue group and set
3105 // currCycle to X.
3106 if ((isTop() && SchedModel->mustEndGroup(MI: SU->getInstr())) ||
3107 (!isTop() && SchedModel->mustBeginGroup(MI: SU->getInstr()))) {
3108 LLVM_DEBUG(dbgs() << " Bump cycle to " << (isTop() ? "end" : "begin")
3109 << " group\n");
3110 bumpCycle(NextCycle: ++NextCycle);
3111 }
3112
3113 while (CurrMOps >= SchedModel->getIssueWidth()) {
3114 LLVM_DEBUG(dbgs() << " *** Max MOps " << CurrMOps << " at cycle "
3115 << CurrCycle << '\n');
3116 bumpCycle(NextCycle: ++NextCycle);
3117 }
3118 LLVM_DEBUG(dumpScheduledState());
3119}
3120
3121/// Release pending ready nodes in to the available queue. This makes them
3122/// visible to heuristics.
3123void SchedBoundary::releasePending() {
3124 // If the available queue is empty, it is safe to reset MinReadyCycle.
3125 if (Available.empty())
3126 MinReadyCycle = std::numeric_limits<unsigned>::max();
3127
3128 // Check to see if any of the pending instructions are ready to issue. If
3129 // so, add them to the available queue.
3130 for (unsigned I = 0, E = Pending.size(); I < E; ++I) {
3131 SUnit *SU = *(Pending.begin() + I);
3132 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
3133
3134 LLVM_DEBUG(dbgs() << "Checking pending node SU(" << SU->NodeNum << ")\n");
3135
3136 if (ReadyCycle < MinReadyCycle)
3137 MinReadyCycle = ReadyCycle;
3138
3139 if (Available.size() >= ReadyListLimit)
3140 break;
3141
3142 releaseNode(SU, ReadyCycle, InPQueue: true, Idx: I);
3143 if (E != Pending.size()) {
3144 --I;
3145 --E;
3146 }
3147 }
3148 CheckPending = false;
3149}
3150
3151/// Remove SU from the ready set for this boundary.
3152void SchedBoundary::removeReady(SUnit *SU) {
3153 if (Available.isInQueue(SU))
3154 Available.remove(I: Available.find(SU));
3155 else {
3156 assert(Pending.isInQueue(SU) && "bad ready count");
3157 Pending.remove(I: Pending.find(SU));
3158 }
3159}
3160
3161/// If this queue only has one ready candidate, return it. As a side effect,
3162/// defer any nodes that now hit a hazard, and advance the cycle until at least
3163/// one node is ready. If multiple instructions are ready, return NULL.
3164SUnit *SchedBoundary::pickOnlyChoice() {
3165 if (CheckPending)
3166 releasePending();
3167
3168 // Defer any ready instrs that now have a hazard.
3169 for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) {
3170 if (checkHazard(SU: *I)) {
3171 Pending.push(SU: *I);
3172 I = Available.remove(I);
3173 continue;
3174 }
3175 ++I;
3176 }
3177 for (unsigned i = 0; Available.empty(); ++i) {
3178// FIXME: Re-enable assert once PR20057 is resolved.
3179// assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedStall) &&
3180// "permanent hazard");
3181 (void)i;
3182 bumpCycle(NextCycle: CurrCycle + 1);
3183 releasePending();
3184 }
3185
3186 LLVM_DEBUG(Pending.dump());
3187 LLVM_DEBUG(Available.dump());
3188
3189 if (Available.size() == 1)
3190 return *Available.begin();
3191 return nullptr;
3192}
3193
3194#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3195
3196/// Dump the content of the \ref ReservedCycles vector for the
3197/// resources that are used in the basic block.
3198///
3199LLVM_DUMP_METHOD void SchedBoundary::dumpReservedCycles() const {
3200 if (!SchedModel->hasInstrSchedModel())
3201 return;
3202
3203 unsigned ResourceCount = SchedModel->getNumProcResourceKinds();
3204 unsigned StartIdx = 0;
3205
3206 for (unsigned ResIdx = 0; ResIdx < ResourceCount; ++ResIdx) {
3207 const unsigned NumUnits = SchedModel->getProcResource(ResIdx)->NumUnits;
3208 std::string ResName = SchedModel->getResourceName(ResIdx);
3209 for (unsigned UnitIdx = 0; UnitIdx < NumUnits; ++UnitIdx) {
3210 dbgs() << ResName << "(" << UnitIdx << ") = ";
3211 if (SchedModel && SchedModel->enableIntervals()) {
3212 if (ReservedResourceSegments.count(StartIdx + UnitIdx))
3213 dbgs() << ReservedResourceSegments.at(StartIdx + UnitIdx);
3214 else
3215 dbgs() << "{ }\n";
3216 } else
3217 dbgs() << ReservedCycles[StartIdx + UnitIdx] << "\n";
3218 }
3219 StartIdx += NumUnits;
3220 }
3221}
3222
3223// This is useful information to dump after bumpNode.
3224// Note that the Queue contents are more useful before pickNodeFromQueue.
3225LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState() const {
3226 unsigned ResFactor;
3227 unsigned ResCount;
3228 if (ZoneCritResIdx) {
3229 ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx);
3230 ResCount = getResourceCount(ZoneCritResIdx);
3231 } else {
3232 ResFactor = SchedModel->getMicroOpFactor();
3233 ResCount = RetiredMOps * ResFactor;
3234 }
3235 unsigned LFactor = SchedModel->getLatencyFactor();
3236 dbgs() << Available.getName() << " @" << CurrCycle << "c\n"
3237 << " Retired: " << RetiredMOps;
3238 dbgs() << "\n Executed: " << getExecutedCount() / LFactor << "c";
3239 dbgs() << "\n Critical: " << ResCount / LFactor << "c, "
3240 << ResCount / ResFactor << " "
3241 << SchedModel->getResourceName(ZoneCritResIdx)
3242 << "\n ExpectedLatency: " << ExpectedLatency << "c\n"
3243 << (IsResourceLimited ? " - Resource" : " - Latency")
3244 << " limited.\n";
3245 if (MISchedDumpReservedCycles)
3246 dumpReservedCycles();
3247}
3248#endif
3249
3250//===----------------------------------------------------------------------===//
3251// GenericScheduler - Generic implementation of MachineSchedStrategy.
3252//===----------------------------------------------------------------------===//
3253
3254void GenericSchedulerBase::SchedCandidate::
3255initResourceDelta(const ScheduleDAGMI *DAG,
3256 const TargetSchedModel *SchedModel) {
3257 if (!Policy.ReduceResIdx && !Policy.DemandResIdx)
3258 return;
3259
3260 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
3261 for (TargetSchedModel::ProcResIter
3262 PI = SchedModel->getWriteProcResBegin(SC),
3263 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
3264 if (PI->ProcResourceIdx == Policy.ReduceResIdx)
3265 ResDelta.CritResources += PI->ReleaseAtCycle;
3266 if (PI->ProcResourceIdx == Policy.DemandResIdx)
3267 ResDelta.DemandedResources += PI->ReleaseAtCycle;
3268 }
3269}
3270
3271/// Returns true if the current cycle plus remaning latency is greater than
3272/// the critical path in the scheduling region.
3273bool GenericSchedulerBase::shouldReduceLatency(const CandPolicy &Policy,
3274 SchedBoundary &CurrZone,
3275 bool ComputeRemLatency,
3276 unsigned &RemLatency) const {
3277 // The current cycle is already greater than the critical path, so we are
3278 // already latency limited and don't need to compute the remaining latency.
3279 if (CurrZone.getCurrCycle() > Rem.CriticalPath)
3280 return true;
3281
3282 // If we haven't scheduled anything yet, then we aren't latency limited.
3283 if (CurrZone.getCurrCycle() == 0)
3284 return false;
3285
3286 if (ComputeRemLatency)
3287 RemLatency = computeRemLatency(CurrZone);
3288
3289 return RemLatency + CurrZone.getCurrCycle() > Rem.CriticalPath;
3290}
3291
3292/// Set the CandPolicy given a scheduling zone given the current resources and
3293/// latencies inside and outside the zone.
3294void GenericSchedulerBase::setPolicy(CandPolicy &Policy, bool IsPostRA,
3295 SchedBoundary &CurrZone,
3296 SchedBoundary *OtherZone) {
3297 // Apply preemptive heuristics based on the total latency and resources
3298 // inside and outside this zone. Potential stalls should be considered before
3299 // following this policy.
3300
3301 // Compute the critical resource outside the zone.
3302 unsigned OtherCritIdx = 0;
3303 unsigned OtherCount =
3304 OtherZone ? OtherZone->getOtherResourceCount(OtherCritIdx) : 0;
3305
3306 bool OtherResLimited = false;
3307 unsigned RemLatency = 0;
3308 bool RemLatencyComputed = false;
3309 if (SchedModel->hasInstrSchedModel() && OtherCount != 0) {
3310 RemLatency = computeRemLatency(CurrZone);
3311 RemLatencyComputed = true;
3312 OtherResLimited = checkResourceLimit(LFactor: SchedModel->getLatencyFactor(),
3313 Count: OtherCount, Latency: RemLatency, AfterSchedNode: false);
3314 }
3315
3316 // Schedule aggressively for latency in PostRA mode. We don't check for
3317 // acyclic latency during PostRA, and highly out-of-order processors will
3318 // skip PostRA scheduling.
3319 if (!OtherResLimited &&
3320 (IsPostRA || shouldReduceLatency(Policy, CurrZone, ComputeRemLatency: !RemLatencyComputed,
3321 RemLatency))) {
3322 Policy.ReduceLatency |= true;
3323 LLVM_DEBUG(dbgs() << " " << CurrZone.Available.getName()
3324 << " RemainingLatency " << RemLatency << " + "
3325 << CurrZone.getCurrCycle() << "c > CritPath "
3326 << Rem.CriticalPath << "\n");
3327 }
3328 // If the same resource is limiting inside and outside the zone, do nothing.
3329 if (CurrZone.getZoneCritResIdx() == OtherCritIdx)
3330 return;
3331
3332 LLVM_DEBUG(if (CurrZone.isResourceLimited()) {
3333 dbgs() << " " << CurrZone.Available.getName() << " ResourceLimited: "
3334 << SchedModel->getResourceName(CurrZone.getZoneCritResIdx()) << "\n";
3335 } if (OtherResLimited) dbgs()
3336 << " RemainingLimit: "
3337 << SchedModel->getResourceName(OtherCritIdx) << "\n";
3338 if (!CurrZone.isResourceLimited() && !OtherResLimited) dbgs()
3339 << " Latency limited both directions.\n");
3340
3341 if (CurrZone.isResourceLimited() && !Policy.ReduceResIdx)
3342 Policy.ReduceResIdx = CurrZone.getZoneCritResIdx();
3343
3344 if (OtherResLimited)
3345 Policy.DemandResIdx = OtherCritIdx;
3346}
3347
3348#ifndef NDEBUG
3349const char *GenericSchedulerBase::getReasonStr(
3350 GenericSchedulerBase::CandReason Reason) {
3351 // clang-format off
3352 switch (Reason) {
3353 case NoCand: return "NOCAND ";
3354 case Only1: return "ONLY1 ";
3355 case PhysReg: return "PHYS-REG ";
3356 case RegExcess: return "REG-EXCESS";
3357 case RegCritical: return "REG-CRIT ";
3358 case Stall: return "STALL ";
3359 case Cluster: return "CLUSTER ";
3360 case Weak: return "WEAK ";
3361 case RegMax: return "REG-MAX ";
3362 case ResourceReduce: return "RES-REDUCE";
3363 case ResourceDemand: return "RES-DEMAND";
3364 case TopDepthReduce: return "TOP-DEPTH ";
3365 case TopPathReduce: return "TOP-PATH ";
3366 case BotHeightReduce:return "BOT-HEIGHT";
3367 case BotPathReduce: return "BOT-PATH ";
3368 case NodeOrder: return "ORDER ";
3369 case FirstValid: return "FIRST ";
3370 };
3371 // clang-format on
3372 llvm_unreachable("Unknown reason!");
3373}
3374
3375void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) {
3376 PressureChange P;
3377 unsigned ResIdx = 0;
3378 unsigned Latency = 0;
3379 switch (Cand.Reason) {
3380 default:
3381 break;
3382 case RegExcess:
3383 P = Cand.RPDelta.Excess;
3384 break;
3385 case RegCritical:
3386 P = Cand.RPDelta.CriticalMax;
3387 break;
3388 case RegMax:
3389 P = Cand.RPDelta.CurrentMax;
3390 break;
3391 case ResourceReduce:
3392 ResIdx = Cand.Policy.ReduceResIdx;
3393 break;
3394 case ResourceDemand:
3395 ResIdx = Cand.Policy.DemandResIdx;
3396 break;
3397 case TopDepthReduce:
3398 Latency = Cand.SU->getDepth();
3399 break;
3400 case TopPathReduce:
3401 Latency = Cand.SU->getHeight();
3402 break;
3403 case BotHeightReduce:
3404 Latency = Cand.SU->getHeight();
3405 break;
3406 case BotPathReduce:
3407 Latency = Cand.SU->getDepth();
3408 break;
3409 }
3410 dbgs() << " Cand SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);
3411 if (P.isValid())
3412 dbgs() << " " << TRI->getRegPressureSetName(P.getPSet())
3413 << ":" << P.getUnitInc() << " ";
3414 else
3415 dbgs() << " ";
3416 if (ResIdx)
3417 dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";
3418 else
3419 dbgs() << " ";
3420 if (Latency)
3421 dbgs() << " " << Latency << " cycles ";
3422 else
3423 dbgs() << " ";
3424 dbgs() << '\n';
3425}
3426#endif
3427
3428/// Compute remaining latency. We need this both to determine whether the
3429/// overall schedule has become latency-limited and whether the instructions
3430/// outside this zone are resource or latency limited.
3431///
3432/// The "dependent" latency is updated incrementally during scheduling as the
3433/// max height/depth of scheduled nodes minus the cycles since it was
3434/// scheduled:
3435/// DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone
3436///
3437/// The "independent" latency is the max ready queue depth:
3438/// ILat = max N.depth for N in Available|Pending
3439///
3440/// RemainingLatency is the greater of independent and dependent latency.
3441///
3442/// These computations are expensive, especially in DAGs with many edges, so
3443/// only do them if necessary.
3444unsigned llvm::computeRemLatency(SchedBoundary &CurrZone) {
3445 unsigned RemLatency = CurrZone.getDependentLatency();
3446 RemLatency = std::max(a: RemLatency,
3447 b: CurrZone.findMaxLatency(ReadySUs: CurrZone.Available.elements()));
3448 RemLatency = std::max(a: RemLatency,
3449 b: CurrZone.findMaxLatency(ReadySUs: CurrZone.Pending.elements()));
3450 return RemLatency;
3451}
3452
3453/// Return true if this heuristic determines order.
3454/// TODO: Consider refactor return type of these functions as integer or enum,
3455/// as we may need to differentiate whether TryCand is better than Cand.
3456bool llvm::tryLess(int TryVal, int CandVal,
3457 GenericSchedulerBase::SchedCandidate &TryCand,
3458 GenericSchedulerBase::SchedCandidate &Cand,
3459 GenericSchedulerBase::CandReason Reason) {
3460 if (TryVal < CandVal) {
3461 TryCand.Reason = Reason;
3462 return true;
3463 }
3464 if (TryVal > CandVal) {
3465 if (Cand.Reason > Reason)
3466 Cand.Reason = Reason;
3467 return true;
3468 }
3469 return false;
3470}
3471
3472bool llvm::tryGreater(int TryVal, int CandVal,
3473 GenericSchedulerBase::SchedCandidate &TryCand,
3474 GenericSchedulerBase::SchedCandidate &Cand,
3475 GenericSchedulerBase::CandReason Reason) {
3476 if (TryVal > CandVal) {
3477 TryCand.Reason = Reason;
3478 return true;
3479 }
3480 if (TryVal < CandVal) {
3481 if (Cand.Reason > Reason)
3482 Cand.Reason = Reason;
3483 return true;
3484 }
3485 return false;
3486}
3487
3488bool llvm::tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
3489 GenericSchedulerBase::SchedCandidate &Cand,
3490 SchedBoundary &Zone) {
3491 if (Zone.isTop()) {
3492 // Prefer the candidate with the lesser depth, but only if one of them has
3493 // depth greater than the total latency scheduled so far, otherwise either
3494 // of them could be scheduled now with no stall.
3495 if (std::max(a: TryCand.SU->getDepth(), b: Cand.SU->getDepth()) >
3496 Zone.getScheduledLatency()) {
3497 if (tryLess(TryVal: TryCand.SU->getDepth(), CandVal: Cand.SU->getDepth(),
3498 TryCand, Cand, Reason: GenericSchedulerBase::TopDepthReduce))
3499 return true;
3500 }
3501 if (tryGreater(TryVal: TryCand.SU->getHeight(), CandVal: Cand.SU->getHeight(),
3502 TryCand, Cand, Reason: GenericSchedulerBase::TopPathReduce))
3503 return true;
3504 } else {
3505 // Prefer the candidate with the lesser height, but only if one of them has
3506 // height greater than the total latency scheduled so far, otherwise either
3507 // of them could be scheduled now with no stall.
3508 if (std::max(a: TryCand.SU->getHeight(), b: Cand.SU->getHeight()) >
3509 Zone.getScheduledLatency()) {
3510 if (tryLess(TryVal: TryCand.SU->getHeight(), CandVal: Cand.SU->getHeight(),
3511 TryCand, Cand, Reason: GenericSchedulerBase::BotHeightReduce))
3512 return true;
3513 }
3514 if (tryGreater(TryVal: TryCand.SU->getDepth(), CandVal: Cand.SU->getDepth(),
3515 TryCand, Cand, Reason: GenericSchedulerBase::BotPathReduce))
3516 return true;
3517 }
3518 return false;
3519}
3520
3521static void tracePick(const SUnit *SU,
3522 const GenericSchedulerBase::CandReason Reason,
3523 const bool IsTop, const bool IsPostRA = false) {
3524 assert(SU && "SU must not be null for tracing");
3525 LLVM_DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ") << "Cand SU("
3526 << SU->NodeNum << ") "
3527 << GenericSchedulerBase::getReasonStr(Reason) << " ["
3528 << (IsPostRA ? "post-RA" : "pre-RA") << "]\n");
3529
3530 if (IsPostRA) {
3531 if (IsTop)
3532 NumTopPostRA++;
3533 else
3534 NumBotPostRA++;
3535
3536 switch (Reason) {
3537 case GenericScheduler::NoCand:
3538 NumNoCandPostRA++;
3539 return;
3540 case GenericScheduler::Only1:
3541 NumOnly1PostRA++;
3542 return;
3543 case GenericScheduler::PhysReg:
3544 NumPhysRegPostRA++;
3545 return;
3546 case GenericScheduler::RegExcess:
3547 NumRegExcessPostRA++;
3548 return;
3549 case GenericScheduler::RegCritical:
3550 NumRegCriticalPostRA++;
3551 return;
3552 case GenericScheduler::Stall:
3553 NumStallPostRA++;
3554 return;
3555 case GenericScheduler::Cluster:
3556 NumClusterPostRA++;
3557 return;
3558 case GenericScheduler::Weak:
3559 NumWeakPostRA++;
3560 return;
3561 case GenericScheduler::RegMax:
3562 NumRegMaxPostRA++;
3563 return;
3564 case GenericScheduler::ResourceReduce:
3565 NumResourceReducePostRA++;
3566 return;
3567 case GenericScheduler::ResourceDemand:
3568 NumResourceDemandPostRA++;
3569 return;
3570 case GenericScheduler::TopDepthReduce:
3571 NumTopDepthReducePostRA++;
3572 return;
3573 case GenericScheduler::TopPathReduce:
3574 NumTopPathReducePostRA++;
3575 return;
3576 case GenericScheduler::BotHeightReduce:
3577 NumBotHeightReducePostRA++;
3578 return;
3579 case GenericScheduler::BotPathReduce:
3580 NumBotPathReducePostRA++;
3581 return;
3582 case GenericScheduler::NodeOrder:
3583 NumNodeOrderPostRA++;
3584 return;
3585 case GenericScheduler::FirstValid:
3586 NumFirstValidPostRA++;
3587 return;
3588 };
3589 } else {
3590 if (IsTop)
3591 NumTopPreRA++;
3592 else
3593 NumBotPreRA++;
3594
3595 switch (Reason) {
3596 case GenericScheduler::NoCand:
3597 NumNoCandPreRA++;
3598 return;
3599 case GenericScheduler::Only1:
3600 NumOnly1PreRA++;
3601 return;
3602 case GenericScheduler::PhysReg:
3603 NumPhysRegPreRA++;
3604 return;
3605 case GenericScheduler::RegExcess:
3606 NumRegExcessPreRA++;
3607 return;
3608 case GenericScheduler::RegCritical:
3609 NumRegCriticalPreRA++;
3610 return;
3611 case GenericScheduler::Stall:
3612 NumStallPreRA++;
3613 return;
3614 case GenericScheduler::Cluster:
3615 NumClusterPreRA++;
3616 return;
3617 case GenericScheduler::Weak:
3618 NumWeakPreRA++;
3619 return;
3620 case GenericScheduler::RegMax:
3621 NumRegMaxPreRA++;
3622 return;
3623 case GenericScheduler::ResourceReduce:
3624 NumResourceReducePreRA++;
3625 return;
3626 case GenericScheduler::ResourceDemand:
3627 NumResourceDemandPreRA++;
3628 return;
3629 case GenericScheduler::TopDepthReduce:
3630 NumTopDepthReducePreRA++;
3631 return;
3632 case GenericScheduler::TopPathReduce:
3633 NumTopPathReducePreRA++;
3634 return;
3635 case GenericScheduler::BotHeightReduce:
3636 NumBotHeightReducePreRA++;
3637 return;
3638 case GenericScheduler::BotPathReduce:
3639 NumBotPathReducePreRA++;
3640 return;
3641 case GenericScheduler::NodeOrder:
3642 NumNodeOrderPreRA++;
3643 return;
3644 case GenericScheduler::FirstValid:
3645 NumFirstValidPreRA++;
3646 return;
3647 };
3648 }
3649 llvm_unreachable("Unknown reason!");
3650}
3651
3652static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand,
3653 const bool IsPostRA = false) {
3654 tracePick(SU: Cand.SU, Reason: Cand.Reason, IsTop: Cand.AtTop, IsPostRA);
3655}
3656
3657void GenericScheduler::initialize(ScheduleDAGMI *dag) {
3658 assert(dag->hasVRegLiveness() &&
3659 "(PreRA)GenericScheduler needs vreg liveness");
3660 DAG = static_cast<ScheduleDAGMILive*>(dag);
3661 SchedModel = DAG->getSchedModel();
3662 TRI = DAG->TRI;
3663
3664 if (RegionPolicy.ComputeDFSResult)
3665 DAG->computeDFSResult();
3666
3667 Rem.init(DAG, SchedModel);
3668 Top.init(dag: DAG, smodel: SchedModel, rem: &Rem);
3669 Bot.init(dag: DAG, smodel: SchedModel, rem: &Rem);
3670
3671 // Initialize resource counts.
3672
3673 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
3674 // are disabled, then these HazardRecs will be disabled.
3675 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
3676 if (!Top.HazardRec)
3677 Top.HazardRec.reset(p: DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG));
3678 if (!Bot.HazardRec)
3679 Bot.HazardRec.reset(p: DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG));
3680 TopCand.SU = nullptr;
3681 BotCand.SU = nullptr;
3682
3683 TopClusterID = InvalidClusterId;
3684 BotClusterID = InvalidClusterId;
3685}
3686
3687/// Initialize the per-region scheduling policy.
3688void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,
3689 MachineBasicBlock::iterator End,
3690 unsigned NumRegionInstrs) {
3691 const MachineFunction &MF = *Begin->getMF();
3692 const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
3693
3694 // Avoid setting up the register pressure tracker for small regions to save
3695 // compile time. As a rough heuristic, only track pressure when the number of
3696 // schedulable instructions exceeds half the allocatable integer register file
3697 // that is the largest legal integer regiser type.
3698 RegionPolicy.ShouldTrackPressure = true;
3699 for (unsigned VT = MVT::i64; VT > (unsigned)MVT::i1; --VT) {
3700 MVT::SimpleValueType LegalIntVT = (MVT::SimpleValueType)VT;
3701 if (TLI->isTypeLegal(VT: LegalIntVT)) {
3702 unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs(
3703 RC: TLI->getRegClassFor(VT: LegalIntVT));
3704 RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
3705 break;
3706 }
3707 }
3708
3709 // For generic targets, we default to bottom-up, because it's simpler and more
3710 // compile-time optimizations have been implemented in that direction.
3711 RegionPolicy.OnlyBottomUp = true;
3712
3713 // Allow the subtarget to override default policy.
3714 SchedRegion Region(Begin, End, NumRegionInstrs);
3715 MF.getSubtarget().overrideSchedPolicy(Policy&: RegionPolicy, Region);
3716
3717 // After subtarget overrides, apply command line options.
3718 if (!EnableRegPressure) {
3719 RegionPolicy.ShouldTrackPressure = false;
3720 RegionPolicy.ShouldTrackLaneMasks = false;
3721 }
3722
3723 if (PreRADirection == MISched::TopDown) {
3724 RegionPolicy.OnlyTopDown = true;
3725 RegionPolicy.OnlyBottomUp = false;
3726 } else if (PreRADirection == MISched::BottomUp) {
3727 RegionPolicy.OnlyTopDown = false;
3728 RegionPolicy.OnlyBottomUp = true;
3729 } else if (PreRADirection == MISched::Bidirectional) {
3730 RegionPolicy.OnlyBottomUp = false;
3731 RegionPolicy.OnlyTopDown = false;
3732 }
3733
3734 BotIdx = NumRegionInstrs - 1;
3735 this->NumRegionInstrs = NumRegionInstrs;
3736}
3737
3738void GenericScheduler::dumpPolicy() const {
3739 // Cannot completely remove virtual function even in release mode.
3740#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3741 dbgs() << "GenericScheduler RegionPolicy: "
3742 << " ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure
3743 << " OnlyTopDown=" << RegionPolicy.OnlyTopDown
3744 << " OnlyBottomUp=" << RegionPolicy.OnlyBottomUp
3745 << "\n";
3746#endif
3747}
3748
3749/// Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic
3750/// critical path by more cycles than it takes to drain the instruction buffer.
3751/// We estimate an upper bounds on in-flight instructions as:
3752///
3753/// CyclesPerIteration = max( CyclicPath, Loop-Resource-Height )
3754/// InFlightIterations = AcyclicPath / CyclesPerIteration
3755/// InFlightResources = InFlightIterations * LoopResources
3756///
3757/// TODO: Check execution resources in addition to IssueCount.
3758void GenericScheduler::checkAcyclicLatency() {
3759 if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)
3760 return;
3761
3762 // Scaled number of cycles per loop iteration.
3763 unsigned IterCount =
3764 std::max(a: Rem.CyclicCritPath * SchedModel->getLatencyFactor(),
3765 b: Rem.RemIssueCount);
3766 // Scaled acyclic critical path.
3767 unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor();
3768 // InFlightCount = (AcyclicPath / IterCycles) * InstrPerLoop
3769 unsigned InFlightCount =
3770 (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;
3771 unsigned BufferLimit =
3772 SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor();
3773
3774 Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;
3775
3776 LLVM_DEBUG(
3777 dbgs() << "IssueCycles="
3778 << Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c "
3779 << "IterCycles=" << IterCount / SchedModel->getLatencyFactor()
3780 << "c NumIters=" << (AcyclicCount + IterCount - 1) / IterCount
3781 << " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor()
3782 << "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n";
3783 if (Rem.IsAcyclicLatencyLimited) dbgs() << " ACYCLIC LATENCY LIMIT\n");
3784}
3785
3786void GenericScheduler::registerRoots() {
3787 Rem.CriticalPath = DAG->ExitSU.getDepth();
3788
3789 // Some roots may not feed into ExitSU. Check all of them in case.
3790 for (const SUnit *SU : Bot.Available) {
3791 if (SU->getDepth() > Rem.CriticalPath)
3792 Rem.CriticalPath = SU->getDepth();
3793 }
3794 LLVM_DEBUG(dbgs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << '\n');
3795 if (DumpCriticalPathLength) {
3796 errs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << " \n";
3797 }
3798
3799 if (EnableCyclicPath && SchedModel->getMicroOpBufferSize() > 0) {
3800 Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();
3801 checkAcyclicLatency();
3802 }
3803}
3804
3805bool llvm::tryPressure(const PressureChange &TryP, const PressureChange &CandP,
3806 GenericSchedulerBase::SchedCandidate &TryCand,
3807 GenericSchedulerBase::SchedCandidate &Cand,
3808 GenericSchedulerBase::CandReason Reason,
3809 const TargetRegisterInfo *TRI,
3810 const MachineFunction &MF) {
3811 // If one candidate decreases and the other increases, go with it.
3812 // Invalid candidates have UnitInc==0.
3813 if (tryGreater(TryVal: TryP.getUnitInc() < 0, CandVal: CandP.getUnitInc() < 0, TryCand, Cand,
3814 Reason)) {
3815 return true;
3816 }
3817 // Do not compare the magnitude of pressure changes between top and bottom
3818 // boundary.
3819 if (Cand.AtTop != TryCand.AtTop)
3820 return false;
3821
3822 // If both candidates affect the same set in the same boundary, go with the
3823 // smallest increase.
3824 unsigned TryPSet = TryP.getPSetOrMax();
3825 unsigned CandPSet = CandP.getPSetOrMax();
3826 if (TryPSet == CandPSet) {
3827 return tryLess(TryVal: TryP.getUnitInc(), CandVal: CandP.getUnitInc(), TryCand, Cand,
3828 Reason);
3829 }
3830
3831 int TryRank = TryP.isValid() ? TRI->getRegPressureSetScore(MF, PSetID: TryPSet) :
3832 std::numeric_limits<int>::max();
3833
3834 int CandRank = CandP.isValid() ? TRI->getRegPressureSetScore(MF, PSetID: CandPSet) :
3835 std::numeric_limits<int>::max();
3836
3837 // If the candidates are decreasing pressure, reverse priority.
3838 if (TryP.getUnitInc() < 0)
3839 std::swap(a&: TryRank, b&: CandRank);
3840 return tryGreater(TryVal: TryRank, CandVal: CandRank, TryCand, Cand, Reason);
3841}
3842
3843unsigned llvm::getWeakLeft(const SUnit *SU, bool isTop) {
3844 return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft;
3845}
3846
3847/// Minimize physical register live ranges. Regalloc wants them adjacent to
3848/// their physreg def/use.
3849///
3850/// FIXME: This is an unnecessary check on the critical path. Most are root/leaf
3851/// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled
3852/// with the operation that produces or consumes the physreg. We'll do this when
3853/// regalloc has support for parallel copies.
3854int llvm::biasPhysReg(const SUnit *SU, bool isTop, bool BiasPRegsExtra) {
3855 const MachineInstr *MI = SU->getInstr();
3856
3857 if (MI->isCopy()) {
3858 unsigned ScheduledOper = isTop ? 1 : 0;
3859 unsigned UnscheduledOper = isTop ? 0 : 1;
3860 // If we have already scheduled the physreg produce/consumer, immediately
3861 // schedule the copy.
3862 if (MI->getOperand(i: ScheduledOper).getReg().isPhysical())
3863 return 1;
3864 // If the physreg is at the boundary, defer it. Otherwise schedule it
3865 // immediately to free the dependent. We can hoist the copy later.
3866 bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft;
3867 if (MI->getOperand(i: UnscheduledOper).getReg().isPhysical())
3868 return AtBoundary ? -1 : 1;
3869 }
3870
3871 if (MI->isMoveImmediate()) {
3872 // If we have a move immediate and all successors have been assigned, bias
3873 // towards scheduling this later. Make sure all register defs are to
3874 // physical registers.
3875 bool DoBias = true;
3876 for (const MachineOperand &Op : MI->defs()) {
3877 if (Op.isReg() && !Op.getReg().isPhysical()) {
3878 DoBias = false;
3879 break;
3880 }
3881 }
3882
3883 if (DoBias)
3884 return isTop ? -1 : 1;
3885 }
3886
3887 if (BiasPRegsExtra && !isTop && MI->getNumExplicitDefs() == 1)
3888 // Register coalescer will create cases of e.g. Load Address of a frame
3889 // index directly into a physreg.
3890 return MI->getOperand(i: 0).getReg().isPhysical();
3891
3892 return 0;
3893}
3894
3895bool llvm::tryBiasPhysRegs(GenericSchedulerBase::SchedCandidate &TryCand,
3896 GenericSchedulerBase::SchedCandidate &Cand,
3897 SchedBoundary *Zone, bool BiasPRegsExtra) {
3898 int TryCandPRegBias = biasPhysReg(SU: TryCand.SU, isTop: TryCand.AtTop, BiasPRegsExtra);
3899 int CandPRegBias = biasPhysReg(SU: Cand.SU, isTop: Cand.AtTop, BiasPRegsExtra);
3900 if (tryGreater(TryVal: TryCandPRegBias, CandVal: CandPRegBias, TryCand, Cand,
3901 Reason: GenericSchedulerBase::PhysReg))
3902 return true;
3903 if (BiasPRegsExtra && Zone != nullptr && TryCandPRegBias &&
3904 TryCandPRegBias == CandPRegBias) {
3905 // Both biased same way - maintain their input order.
3906 if (Zone->isTop())
3907 tryLess(TryVal: TryCand.SU->NodeNum, CandVal: Cand.SU->NodeNum, TryCand, Cand,
3908 Reason: GenericSchedulerBase::NodeOrder);
3909 else
3910 tryGreater(TryVal: TryCand.SU->NodeNum, CandVal: Cand.SU->NodeNum, TryCand, Cand,
3911 Reason: GenericSchedulerBase::NodeOrder);
3912 return true;
3913 }
3914 return false;
3915}
3916
3917void GenericScheduler::initCandidate(SchedCandidate &Cand, SUnit *SU,
3918 bool AtTop,
3919 const RegPressureTracker &RPTracker,
3920 RegPressureTracker &TempTracker) {
3921 Cand.SU = SU;
3922 Cand.AtTop = AtTop;
3923 if (DAG->isTrackingPressure()) {
3924 if (AtTop) {
3925 TempTracker.getMaxDownwardPressureDelta(
3926 MI: Cand.SU->getInstr(),
3927 Delta&: Cand.RPDelta,
3928 CriticalPSets: DAG->getRegionCriticalPSets(),
3929 MaxPressureLimit: DAG->getRegPressure().MaxSetPressure);
3930 } else {
3931 if (VerifyScheduling) {
3932 TempTracker.getMaxUpwardPressureDelta(
3933 MI: Cand.SU->getInstr(),
3934 PDiff: &DAG->getPressureDiff(SU: Cand.SU),
3935 Delta&: Cand.RPDelta,
3936 CriticalPSets: DAG->getRegionCriticalPSets(),
3937 MaxPressureLimit: DAG->getRegPressure().MaxSetPressure);
3938 } else {
3939 RPTracker.getUpwardPressureDelta(
3940 MI: Cand.SU->getInstr(),
3941 PDiff&: DAG->getPressureDiff(SU: Cand.SU),
3942 Delta&: Cand.RPDelta,
3943 CriticalPSets: DAG->getRegionCriticalPSets(),
3944 MaxPressureLimit: DAG->getRegPressure().MaxSetPressure);
3945 }
3946 }
3947 }
3948 LLVM_DEBUG(if (Cand.RPDelta.Excess.isValid()) dbgs()
3949 << " Try SU(" << Cand.SU->NodeNum << ") "
3950 << TRI->getRegPressureSetName(Cand.RPDelta.Excess.getPSet()) << ":"
3951 << Cand.RPDelta.Excess.getUnitInc() << "\n");
3952}
3953
3954/// Apply a set of heuristics to a new candidate. Heuristics are currently
3955/// hierarchical. This may be more efficient than a graduated cost model because
3956/// we don't need to evaluate all aspects of the model for each node in the
3957/// queue. But it's really done to make the heuristics easier to debug and
3958/// statistically analyze.
3959///
3960/// \param Cand provides the policy and current best candidate.
3961/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
3962/// \param Zone describes the scheduled zone that we are extending, or nullptr
3963/// if Cand is from a different zone than TryCand.
3964/// \return \c true if TryCand is better than Cand (Reason is NOT NoCand)
3965bool GenericScheduler::tryCandidate(SchedCandidate &Cand,
3966 SchedCandidate &TryCand,
3967 SchedBoundary *Zone) const {
3968 // Initialize the candidate if needed.
3969 if (!Cand.isValid()) {
3970 TryCand.Reason = FirstValid;
3971 return true;
3972 }
3973
3974 // Bias PhysReg Defs and copies to their uses and defined respectively.
3975 if (tryBiasPhysRegs(TryCand, Cand, Zone, BiasPRegsExtra: RegionPolicy.BiasPRegsExtra))
3976 return TryCand.Reason != NoCand;
3977
3978 // Avoid exceeding the target's limit.
3979 if (DAG->isTrackingPressure() && tryPressure(TryP: TryCand.RPDelta.Excess,
3980 CandP: Cand.RPDelta.Excess,
3981 TryCand, Cand, Reason: RegExcess, TRI,
3982 MF: DAG->MF))
3983 return TryCand.Reason != NoCand;
3984
3985 // Avoid increasing the max critical pressure in the scheduled region.
3986 if (DAG->isTrackingPressure() && tryPressure(TryP: TryCand.RPDelta.CriticalMax,
3987 CandP: Cand.RPDelta.CriticalMax,
3988 TryCand, Cand, Reason: RegCritical, TRI,
3989 MF: DAG->MF))
3990 return TryCand.Reason != NoCand;
3991
3992 // We only compare a subset of features when comparing nodes between
3993 // Top and Bottom boundary. Some properties are simply incomparable, in many
3994 // other instances we should only override the other boundary if something
3995 // is a clear good pick on one boundary. Skip heuristics that are more
3996 // "tie-breaking" in nature.
3997 bool SameBoundary = Zone != nullptr;
3998 if (SameBoundary) {
3999 // For loops that are acyclic path limited, aggressively schedule for
4000 // latency. Within an single cycle, whenever CurrMOps > 0, allow normal
4001 // heuristics to take precedence.
4002 if (Rem.IsAcyclicLatencyLimited && !Zone->getCurrMOps() &&
4003 tryLatency(TryCand, Cand, Zone&: *Zone))
4004 return TryCand.Reason != NoCand;
4005
4006 // Prioritize instructions that read unbuffered resources by stall cycles.
4007 if (tryLess(TryVal: Zone->getLatencyStallCycles(SU: TryCand.SU),
4008 CandVal: Zone->getLatencyStallCycles(SU: Cand.SU), TryCand, Cand, Reason: Stall))
4009 return TryCand.Reason != NoCand;
4010 }
4011
4012 // Keep clustered nodes together to encourage downstream peephole
4013 // optimizations which may reduce resource requirements.
4014 //
4015 // This is a best effort to set things up for a post-RA pass. Optimizations
4016 // like generating loads of multiple registers should ideally be done within
4017 // the scheduler pass by combining the loads during DAG postprocessing.
4018 unsigned CandZoneCluster = Cand.AtTop ? TopClusterID : BotClusterID;
4019 unsigned TryCandZoneCluster = TryCand.AtTop ? TopClusterID : BotClusterID;
4020 bool CandIsClusterSucc =
4021 isTheSameCluster(A: CandZoneCluster, B: Cand.SU->ParentClusterIdx);
4022 bool TryCandIsClusterSucc =
4023 isTheSameCluster(A: TryCandZoneCluster, B: TryCand.SU->ParentClusterIdx);
4024
4025 if (tryGreater(TryVal: TryCandIsClusterSucc, CandVal: CandIsClusterSucc, TryCand, Cand,
4026 Reason: Cluster))
4027 return TryCand.Reason != NoCand;
4028
4029 if (SameBoundary) {
4030 // Weak edges are for clustering and other constraints.
4031 if (tryLess(TryVal: getWeakLeft(SU: TryCand.SU, isTop: TryCand.AtTop),
4032 CandVal: getWeakLeft(SU: Cand.SU, isTop: Cand.AtTop),
4033 TryCand, Cand, Reason: Weak))
4034 return TryCand.Reason != NoCand;
4035 }
4036
4037 // Avoid increasing the max pressure of the entire region.
4038 if (DAG->isTrackingPressure() && tryPressure(TryP: TryCand.RPDelta.CurrentMax,
4039 CandP: Cand.RPDelta.CurrentMax,
4040 TryCand, Cand, Reason: RegMax, TRI,
4041 MF: DAG->MF))
4042 return TryCand.Reason != NoCand;
4043
4044 if (SameBoundary) {
4045 // Avoid critical resource consumption and balance the schedule.
4046 TryCand.initResourceDelta(DAG, SchedModel);
4047 if (tryLess(TryVal: TryCand.ResDelta.CritResources, CandVal: Cand.ResDelta.CritResources,
4048 TryCand, Cand, Reason: ResourceReduce))
4049 return TryCand.Reason != NoCand;
4050 if (tryGreater(TryVal: TryCand.ResDelta.DemandedResources,
4051 CandVal: Cand.ResDelta.DemandedResources,
4052 TryCand, Cand, Reason: ResourceDemand))
4053 return TryCand.Reason != NoCand;
4054
4055 // Avoid serializing long latency dependence chains.
4056 // For acyclic path limited loops, latency was already checked above.
4057 if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency &&
4058 !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, Zone&: *Zone))
4059 return TryCand.Reason != NoCand;
4060
4061 // Fall through to original instruction order.
4062 if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)
4063 || (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
4064 TryCand.Reason = NodeOrder;
4065 return true;
4066 }
4067 }
4068
4069 return false;
4070}
4071
4072/// Pick the best candidate from the queue.
4073///
4074/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
4075/// DAG building. To adjust for the current scheduling location we need to
4076/// maintain the number of vreg uses remaining to be top-scheduled.
4077void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
4078 const CandPolicy &ZonePolicy,
4079 const RegPressureTracker &RPTracker,
4080 SchedCandidate &Cand) {
4081 // getMaxPressureDelta temporarily modifies the tracker.
4082 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
4083
4084 ReadyQueue &Q = Zone.Available;
4085 for (SUnit *SU : Q) {
4086
4087 SchedCandidate TryCand(ZonePolicy);
4088 initCandidate(Cand&: TryCand, SU, AtTop: Zone.isTop(), RPTracker, TempTracker);
4089 // Pass SchedBoundary only when comparing nodes from the same boundary.
4090 SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
4091 if (tryCandidate(Cand, TryCand, Zone: ZoneArg)) {
4092 // Initialize resource delta if needed in case future heuristics query it.
4093 if (TryCand.ResDelta == SchedResourceDelta())
4094 TryCand.initResourceDelta(DAG, SchedModel);
4095 Cand.setBest(TryCand);
4096 LLVM_DEBUG(traceCandidate(Cand));
4097 }
4098 }
4099}
4100
4101/// Pick the best candidate node from either the top or bottom queue.
4102SUnit *GenericScheduler::pickNodeBidirectional(bool &IsTopNode) {
4103 // Schedule as far as possible in the direction of no choice. This is most
4104 // efficient, but also provides the best heuristics for CriticalPSets.
4105 if (SUnit *SU = Bot.pickOnlyChoice()) {
4106 IsTopNode = false;
4107 tracePick(SU, Reason: Only1, /*IsTopNode=*/IsTop: false);
4108 return SU;
4109 }
4110 if (SUnit *SU = Top.pickOnlyChoice()) {
4111 IsTopNode = true;
4112 tracePick(SU, Reason: Only1, /*IsTopNode=*/IsTop: true);
4113 return SU;
4114 }
4115 // Set the bottom-up policy based on the state of the current bottom zone and
4116 // the instructions outside the zone, including the top zone.
4117 CandPolicy BotPolicy;
4118 setPolicy(Policy&: BotPolicy, /*IsPostRA=*/false, CurrZone&: Bot, OtherZone: &Top);
4119 // Set the top-down policy based on the state of the current top zone and
4120 // the instructions outside the zone, including the bottom zone.
4121 CandPolicy TopPolicy;
4122 setPolicy(Policy&: TopPolicy, /*IsPostRA=*/false, CurrZone&: Top, OtherZone: &Bot);
4123
4124 // See if BotCand is still valid (because we previously scheduled from Top).
4125 LLVM_DEBUG(dbgs() << "Picking from Bot:\n");
4126 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
4127 BotCand.Policy != BotPolicy) {
4128 BotCand.reset(NewPolicy: CandPolicy());
4129 pickNodeFromQueue(Zone&: Bot, ZonePolicy: BotPolicy, RPTracker: DAG->getBotRPTracker(), Cand&: BotCand);
4130 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
4131 } else {
4132 LLVM_DEBUG(traceCandidate(BotCand));
4133#ifndef NDEBUG
4134 if (VerifyScheduling) {
4135 SchedCandidate TCand;
4136 TCand.reset(CandPolicy());
4137 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);
4138 assert(TCand.SU == BotCand.SU &&
4139 "Last pick result should correspond to re-picking right now");
4140 }
4141#endif
4142 }
4143
4144 // Check if the top Q has a better candidate.
4145 LLVM_DEBUG(dbgs() << "Picking from Top:\n");
4146 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
4147 TopCand.Policy != TopPolicy) {
4148 TopCand.reset(NewPolicy: CandPolicy());
4149 pickNodeFromQueue(Zone&: Top, ZonePolicy: TopPolicy, RPTracker: DAG->getTopRPTracker(), Cand&: TopCand);
4150 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
4151 } else {
4152 LLVM_DEBUG(traceCandidate(TopCand));
4153#ifndef NDEBUG
4154 if (VerifyScheduling) {
4155 SchedCandidate TCand;
4156 TCand.reset(CandPolicy());
4157 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);
4158 assert(TCand.SU == TopCand.SU &&
4159 "Last pick result should correspond to re-picking right now");
4160 }
4161#endif
4162 }
4163
4164 // Pick best from BotCand and TopCand.
4165 assert(BotCand.isValid());
4166 assert(TopCand.isValid());
4167 SchedCandidate Cand = BotCand;
4168 TopCand.Reason = NoCand;
4169 if (tryCandidate(Cand, TryCand&: TopCand, Zone: nullptr)) {
4170 Cand.setBest(TopCand);
4171 LLVM_DEBUG(traceCandidate(Cand));
4172 }
4173
4174 IsTopNode = Cand.AtTop;
4175 tracePick(Cand);
4176 return Cand.SU;
4177}
4178
4179/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
4180SUnit *GenericScheduler::pickNode(bool &IsTopNode) {
4181 if (DAG->top() == DAG->bottom()) {
4182 assert(Top.Available.empty() && Top.Pending.empty() &&
4183 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
4184 return nullptr;
4185 }
4186 SUnit *SU;
4187 if (RegionPolicy.OnlyTopDown) {
4188 SU = Top.pickOnlyChoice();
4189 if (SU) {
4190 tracePick(SU, Reason: Only1, /*IsTopNode=*/IsTop: true);
4191 } else {
4192 CandPolicy NoPolicy;
4193 TopCand.reset(NewPolicy: NoPolicy);
4194 pickNodeFromQueue(Zone&: Top, ZonePolicy: NoPolicy, RPTracker: DAG->getTopRPTracker(), Cand&: TopCand);
4195 assert(TopCand.Reason != NoCand && "failed to find a candidate");
4196 tracePick(Cand: TopCand);
4197 SU = TopCand.SU;
4198 }
4199 IsTopNode = true;
4200 } else if (RegionPolicy.OnlyBottomUp) {
4201 SU = Bot.pickOnlyChoice();
4202 if (SU) {
4203 tracePick(SU, Reason: Only1, /*IsTopNode=*/IsTop: false);
4204 } else {
4205 CandPolicy NoPolicy;
4206 BotCand.reset(NewPolicy: NoPolicy);
4207 pickNodeFromQueue(Zone&: Bot, ZonePolicy: NoPolicy, RPTracker: DAG->getBotRPTracker(), Cand&: BotCand);
4208 assert(BotCand.Reason != NoCand && "failed to find a candidate");
4209 tracePick(Cand: BotCand);
4210 SU = BotCand.SU;
4211 }
4212 IsTopNode = false;
4213 } else {
4214 SU = pickNodeBidirectional(IsTopNode);
4215 }
4216 assert(!SU->isScheduled && "SUnit scheduled twice.");
4217
4218 // If IsTopNode, then SU is in Top.Available and must be removed. Otherwise,
4219 // if isTopReady(), then SU is in either Top.Available or Top.Pending.
4220 // If !IsTopNode, then SU is in Bot.Available and must be removed. Otherwise,
4221 // if isBottomReady(), then SU is in either Bot.Available or Bot.Pending.
4222 //
4223 // It is coincidental when !IsTopNode && isTopReady or when IsTopNode &&
4224 // isBottomReady. That is, it didn't factor into the decision to choose SU
4225 // because it isTopReady or isBottomReady, respectively. In fact, if the
4226 // RegionPolicy is OnlyTopDown or OnlyBottomUp, then the Bot queues and Top
4227 // queues respectivley contain the original roots and don't get updated when
4228 // picking a node. So if SU isTopReady on a OnlyBottomUp pick, then it was
4229 // because we schduled everything but the top roots. Conversley, if SU
4230 // isBottomReady on OnlyTopDown, then it was because we scheduled everything
4231 // but the bottom roots. If its in a queue even coincidentally, it should be
4232 // removed so it does not get re-picked in a subsequent pickNode call.
4233 if (SU->isTopReady())
4234 Top.removeReady(SU);
4235 if (SU->isBottomReady())
4236 Bot.removeReady(SU);
4237
4238 LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
4239 << *SU->getInstr());
4240
4241 if (IsTopNode) {
4242 if (SU->NodeNum == TopIdx++)
4243 ++NumInstrsInSourceOrderPreRA;
4244 } else {
4245 assert(BotIdx < NumRegionInstrs && "out of bounds");
4246 if (SU->NodeNum == BotIdx--)
4247 ++NumInstrsInSourceOrderPreRA;
4248 }
4249
4250 NumInstrsScheduledPreRA += 1;
4251
4252 return SU;
4253}
4254
4255void GenericScheduler::reschedulePhysReg(SUnit *SU, bool isTop) {
4256 MachineBasicBlock::iterator InsertPos = SU->getInstr();
4257 if (!isTop)
4258 ++InsertPos;
4259 SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs;
4260
4261 // Find already scheduled copies with a single physreg dependence and move
4262 // them just above the scheduled instruction.
4263 for (SDep &Dep : Deps) {
4264 if (Dep.getKind() != SDep::Data || !Dep.getReg().isPhysical())
4265 continue;
4266 SUnit *DepSU = Dep.getSUnit();
4267 if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1)
4268 continue;
4269 MachineInstr *Copy = DepSU->getInstr();
4270 if (!Copy->isCopy() && !Copy->isMoveImmediate())
4271 continue;
4272 LLVM_DEBUG(dbgs() << " Rescheduling physreg copy ";
4273 DAG->dumpNode(*Dep.getSUnit()));
4274 DAG->moveInstruction(MI: Copy, InsertPos);
4275 }
4276}
4277
4278/// Update the scheduler's state after scheduling a node. This is the same node
4279/// that was just returned by pickNode(). However, ScheduleDAGMILive needs to
4280/// update it's state based on the current cycle before MachineSchedStrategy
4281/// does.
4282///
4283/// FIXME: Eventually, we may bundle physreg copies rather than rescheduling
4284/// them here. See comments in biasPhysReg.
4285void GenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
4286 if (IsTopNode) {
4287 SU->TopReadyCycle = std::max(a: SU->TopReadyCycle, b: Top.getCurrCycle());
4288 TopClusterID = SU->ParentClusterIdx;
4289 LLVM_DEBUG({
4290 if (TopClusterID != InvalidClusterId) {
4291 ClusterInfo *TopCluster = DAG->getCluster(TopClusterID);
4292 dbgs() << " Top Cluster: ";
4293 for (auto *N : *TopCluster)
4294 dbgs() << N->NodeNum << '\t';
4295 dbgs() << '\n';
4296 }
4297 });
4298 Top.bumpNode(SU);
4299 if (SU->hasPhysRegUses)
4300 reschedulePhysReg(SU, isTop: true);
4301 } else {
4302 SU->BotReadyCycle = std::max(a: SU->BotReadyCycle, b: Bot.getCurrCycle());
4303 BotClusterID = SU->ParentClusterIdx;
4304 LLVM_DEBUG({
4305 if (BotClusterID != InvalidClusterId) {
4306 ClusterInfo *BotCluster = DAG->getCluster(BotClusterID);
4307 dbgs() << " Bot Cluster: ";
4308 for (auto *N : *BotCluster)
4309 dbgs() << N->NodeNum << '\t';
4310 dbgs() << '\n';
4311 }
4312 });
4313 Bot.bumpNode(SU);
4314 if (SU->hasPhysRegDefs)
4315 reschedulePhysReg(SU, isTop: false);
4316 }
4317}
4318
4319static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) {
4320 return createSchedLive(C);
4321}
4322
4323static MachineSchedRegistry
4324GenericSchedRegistry("converge", "Standard converging scheduler.",
4325 createConvergingSched);
4326
4327//===----------------------------------------------------------------------===//
4328// PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy.
4329//===----------------------------------------------------------------------===//
4330
4331void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) {
4332 DAG = Dag;
4333 SchedModel = DAG->getSchedModel();
4334 TRI = DAG->TRI;
4335
4336 Rem.init(DAG, SchedModel);
4337 Top.init(dag: DAG, smodel: SchedModel, rem: &Rem);
4338 Bot.init(dag: DAG, smodel: SchedModel, rem: &Rem);
4339
4340 // Initialize the HazardRecognizers. If itineraries don't exist, are empty,
4341 // or are disabled, then these HazardRecs will be disabled.
4342 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
4343 if (!Top.HazardRec)
4344 Top.HazardRec.reset(p: DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG));
4345 if (!Bot.HazardRec)
4346 Bot.HazardRec.reset(p: DAG->TII->CreateTargetMIHazardRecognizer(Itin, DAG));
4347 TopClusterID = InvalidClusterId;
4348 BotClusterID = InvalidClusterId;
4349}
4350
4351void PostGenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,
4352 MachineBasicBlock::iterator End,
4353 unsigned NumRegionInstrs) {
4354 const MachineFunction &MF = *Begin->getMF();
4355
4356 // Default to top-down because it was implemented first and existing targets
4357 // expect that behavior by default.
4358 RegionPolicy.OnlyTopDown = true;
4359 RegionPolicy.OnlyBottomUp = false;
4360
4361 // Allow the subtarget to override default policy.
4362 SchedRegion Region(Begin, End, NumRegionInstrs);
4363 MF.getSubtarget().overridePostRASchedPolicy(Policy&: RegionPolicy, Region);
4364
4365 // After subtarget overrides, apply command line options.
4366 if (PostRADirection == MISched::TopDown) {
4367 RegionPolicy.OnlyTopDown = true;
4368 RegionPolicy.OnlyBottomUp = false;
4369 } else if (PostRADirection == MISched::BottomUp) {
4370 RegionPolicy.OnlyTopDown = false;
4371 RegionPolicy.OnlyBottomUp = true;
4372 } else if (PostRADirection == MISched::Bidirectional) {
4373 RegionPolicy.OnlyBottomUp = false;
4374 RegionPolicy.OnlyTopDown = false;
4375 }
4376
4377 BotIdx = NumRegionInstrs - 1;
4378 this->NumRegionInstrs = NumRegionInstrs;
4379}
4380
4381void PostGenericScheduler::registerRoots() {
4382 Rem.CriticalPath = DAG->ExitSU.getDepth();
4383
4384 // Some roots may not feed into ExitSU. Check all of them in case.
4385 for (const SUnit *SU : Bot.Available) {
4386 if (SU->getDepth() > Rem.CriticalPath)
4387 Rem.CriticalPath = SU->getDepth();
4388 }
4389 LLVM_DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem.CriticalPath << '\n');
4390 if (DumpCriticalPathLength) {
4391 errs() << "Critical Path(PGS-RR ): " << Rem.CriticalPath << " \n";
4392 }
4393}
4394
4395/// Apply a set of heuristics to a new candidate for PostRA scheduling.
4396///
4397/// \param Cand provides the policy and current best candidate.
4398/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
4399/// \return \c true if TryCand is better than Cand (Reason is NOT NoCand)
4400bool PostGenericScheduler::tryCandidate(SchedCandidate &Cand,
4401 SchedCandidate &TryCand) {
4402 // Initialize the candidate if needed.
4403 if (!Cand.isValid()) {
4404 TryCand.Reason = FirstValid;
4405 return true;
4406 }
4407
4408 // Prioritize instructions that read unbuffered resources by stall cycles.
4409 if (tryLess(TryVal: Top.getLatencyStallCycles(SU: TryCand.SU),
4410 CandVal: Top.getLatencyStallCycles(SU: Cand.SU), TryCand, Cand, Reason: Stall))
4411 return TryCand.Reason != NoCand;
4412
4413 // Keep clustered nodes together.
4414 unsigned CandZoneCluster = Cand.AtTop ? TopClusterID : BotClusterID;
4415 unsigned TryCandZoneCluster = TryCand.AtTop ? TopClusterID : BotClusterID;
4416 bool CandIsClusterSucc =
4417 isTheSameCluster(A: CandZoneCluster, B: Cand.SU->ParentClusterIdx);
4418 bool TryCandIsClusterSucc =
4419 isTheSameCluster(A: TryCandZoneCluster, B: TryCand.SU->ParentClusterIdx);
4420
4421 if (tryGreater(TryVal: TryCandIsClusterSucc, CandVal: CandIsClusterSucc, TryCand, Cand,
4422 Reason: Cluster))
4423 return TryCand.Reason != NoCand;
4424 // Avoid critical resource consumption and balance the schedule.
4425 if (tryLess(TryVal: TryCand.ResDelta.CritResources, CandVal: Cand.ResDelta.CritResources,
4426 TryCand, Cand, Reason: ResourceReduce))
4427 return TryCand.Reason != NoCand;
4428 if (tryGreater(TryVal: TryCand.ResDelta.DemandedResources,
4429 CandVal: Cand.ResDelta.DemandedResources,
4430 TryCand, Cand, Reason: ResourceDemand))
4431 return TryCand.Reason != NoCand;
4432
4433 // We only compare a subset of features when comparing nodes between
4434 // Top and Bottom boundary.
4435 if (Cand.AtTop == TryCand.AtTop) {
4436 // Avoid serializing long latency dependence chains.
4437 if (Cand.Policy.ReduceLatency &&
4438 tryLatency(TryCand, Cand, Zone&: Cand.AtTop ? Top : Bot))
4439 return TryCand.Reason != NoCand;
4440 }
4441
4442 // Fall through to original instruction order.
4443 if (TryCand.SU->NodeNum < Cand.SU->NodeNum) {
4444 TryCand.Reason = NodeOrder;
4445 return true;
4446 }
4447
4448 return false;
4449}
4450
4451void PostGenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
4452 SchedCandidate &Cand) {
4453 ReadyQueue &Q = Zone.Available;
4454 for (SUnit *SU : Q) {
4455 SchedCandidate TryCand(Cand.Policy);
4456 TryCand.SU = SU;
4457 TryCand.AtTop = Zone.isTop();
4458 TryCand.initResourceDelta(DAG, SchedModel);
4459 if (tryCandidate(Cand, TryCand)) {
4460 Cand.setBest(TryCand);
4461 LLVM_DEBUG(traceCandidate(Cand));
4462 }
4463 }
4464}
4465
4466/// Pick the best candidate node from either the top or bottom queue.
4467SUnit *PostGenericScheduler::pickNodeBidirectional(bool &IsTopNode) {
4468 // FIXME: This is similiar to GenericScheduler::pickNodeBidirectional. Factor
4469 // out common parts.
4470
4471 // Schedule as far as possible in the direction of no choice. This is most
4472 // efficient, but also provides the best heuristics for CriticalPSets.
4473 if (SUnit *SU = Bot.pickOnlyChoice()) {
4474 IsTopNode = false;
4475 tracePick(SU, Reason: Only1, /*IsTopNode=*/IsTop: false, /*IsPostRA=*/true);
4476 return SU;
4477 }
4478 if (SUnit *SU = Top.pickOnlyChoice()) {
4479 IsTopNode = true;
4480 tracePick(SU, Reason: Only1, /*IsTopNode=*/IsTop: true, /*IsPostRA=*/true);
4481 return SU;
4482 }
4483 // Set the bottom-up policy based on the state of the current bottom zone and
4484 // the instructions outside the zone, including the top zone.
4485 CandPolicy BotPolicy;
4486 setPolicy(Policy&: BotPolicy, /*IsPostRA=*/true, CurrZone&: Bot, OtherZone: &Top);
4487 // Set the top-down policy based on the state of the current top zone and
4488 // the instructions outside the zone, including the bottom zone.
4489 CandPolicy TopPolicy;
4490 setPolicy(Policy&: TopPolicy, /*IsPostRA=*/true, CurrZone&: Top, OtherZone: &Bot);
4491
4492 // See if BotCand is still valid (because we previously scheduled from Top).
4493 LLVM_DEBUG(dbgs() << "Picking from Bot:\n");
4494 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
4495 BotCand.Policy != BotPolicy) {
4496 BotCand.reset(NewPolicy: CandPolicy());
4497 pickNodeFromQueue(Zone&: Bot, Cand&: BotCand);
4498 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
4499 } else {
4500 LLVM_DEBUG(traceCandidate(BotCand));
4501#ifndef NDEBUG
4502 if (VerifyScheduling) {
4503 SchedCandidate TCand;
4504 TCand.reset(CandPolicy());
4505 pickNodeFromQueue(Bot, BotCand);
4506 assert(TCand.SU == BotCand.SU &&
4507 "Last pick result should correspond to re-picking right now");
4508 }
4509#endif
4510 }
4511
4512 // Check if the top Q has a better candidate.
4513 LLVM_DEBUG(dbgs() << "Picking from Top:\n");
4514 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
4515 TopCand.Policy != TopPolicy) {
4516 TopCand.reset(NewPolicy: CandPolicy());
4517 pickNodeFromQueue(Zone&: Top, Cand&: TopCand);
4518 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
4519 } else {
4520 LLVM_DEBUG(traceCandidate(TopCand));
4521#ifndef NDEBUG
4522 if (VerifyScheduling) {
4523 SchedCandidate TCand;
4524 TCand.reset(CandPolicy());
4525 pickNodeFromQueue(Top, TopCand);
4526 assert(TCand.SU == TopCand.SU &&
4527 "Last pick result should correspond to re-picking right now");
4528 }
4529#endif
4530 }
4531
4532 // Pick best from BotCand and TopCand.
4533 assert(BotCand.isValid());
4534 assert(TopCand.isValid());
4535 SchedCandidate Cand = BotCand;
4536 TopCand.Reason = NoCand;
4537 if (tryCandidate(Cand, TryCand&: TopCand)) {
4538 Cand.setBest(TopCand);
4539 LLVM_DEBUG(traceCandidate(Cand));
4540 }
4541
4542 IsTopNode = Cand.AtTop;
4543 tracePick(Cand, /*IsPostRA=*/true);
4544 return Cand.SU;
4545}
4546
4547/// Pick the next node to schedule.
4548SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) {
4549 if (DAG->top() == DAG->bottom()) {
4550 assert(Top.Available.empty() && Top.Pending.empty() &&
4551 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
4552 return nullptr;
4553 }
4554 SUnit *SU;
4555 if (RegionPolicy.OnlyBottomUp) {
4556 SU = Bot.pickOnlyChoice();
4557 if (SU) {
4558 tracePick(SU, Reason: Only1, /*IsTopNode=*/IsTop: false, /*IsPostRA=*/true);
4559 } else {
4560 CandPolicy NoPolicy;
4561 BotCand.reset(NewPolicy: NoPolicy);
4562 // Set the bottom-up policy based on the state of the current bottom
4563 // zone and the instructions outside the zone, including the top zone.
4564 setPolicy(Policy&: BotCand.Policy, /*IsPostRA=*/true, CurrZone&: Bot, OtherZone: nullptr);
4565 pickNodeFromQueue(Zone&: Bot, Cand&: BotCand);
4566 assert(BotCand.Reason != NoCand && "failed to find a candidate");
4567 tracePick(Cand: BotCand, /*IsPostRA=*/true);
4568 SU = BotCand.SU;
4569 }
4570 IsTopNode = false;
4571 } else if (RegionPolicy.OnlyTopDown) {
4572 SU = Top.pickOnlyChoice();
4573 if (SU) {
4574 tracePick(SU, Reason: Only1, /*IsTopNode=*/IsTop: true, /*IsPostRA=*/true);
4575 } else {
4576 CandPolicy NoPolicy;
4577 TopCand.reset(NewPolicy: NoPolicy);
4578 // Set the top-down policy based on the state of the current top zone
4579 // and the instructions outside the zone, including the bottom zone.
4580 setPolicy(Policy&: TopCand.Policy, /*IsPostRA=*/true, CurrZone&: Top, OtherZone: nullptr);
4581 pickNodeFromQueue(Zone&: Top, Cand&: TopCand);
4582 assert(TopCand.Reason != NoCand && "failed to find a candidate");
4583 tracePick(Cand: TopCand, /*IsPostRA=*/true);
4584 SU = TopCand.SU;
4585 }
4586 IsTopNode = true;
4587 } else {
4588 SU = pickNodeBidirectional(IsTopNode);
4589 }
4590 assert(!SU->isScheduled && "SUnit scheduled twice.");
4591
4592 if (SU->isTopReady())
4593 Top.removeReady(SU);
4594 if (SU->isBottomReady())
4595 Bot.removeReady(SU);
4596
4597 LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
4598 << *SU->getInstr());
4599
4600 if (IsTopNode) {
4601 if (SU->NodeNum == TopIdx++)
4602 ++NumInstrsInSourceOrderPostRA;
4603 } else {
4604 assert(BotIdx < NumRegionInstrs && "out of bounds");
4605 if (SU->NodeNum == BotIdx--)
4606 ++NumInstrsInSourceOrderPostRA;
4607 }
4608
4609 NumInstrsScheduledPostRA += 1;
4610
4611 return SU;
4612}
4613
4614/// Called after ScheduleDAGMI has scheduled an instruction and updated
4615/// scheduled/remaining flags in the DAG nodes.
4616void PostGenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
4617 if (IsTopNode) {
4618 SU->TopReadyCycle = std::max(a: SU->TopReadyCycle, b: Top.getCurrCycle());
4619 TopClusterID = SU->ParentClusterIdx;
4620 Top.bumpNode(SU);
4621 } else {
4622 SU->BotReadyCycle = std::max(a: SU->BotReadyCycle, b: Bot.getCurrCycle());
4623 BotClusterID = SU->ParentClusterIdx;
4624 Bot.bumpNode(SU);
4625 }
4626}
4627
4628//===----------------------------------------------------------------------===//
4629// ILP Scheduler. Currently for experimental analysis of heuristics.
4630//===----------------------------------------------------------------------===//
4631
4632namespace {
4633
4634/// Order nodes by the ILP metric.
4635struct ILPOrder {
4636 const SchedDFSResult *DFSResult = nullptr;
4637 const BitVector *ScheduledTrees = nullptr;
4638 bool MaximizeILP;
4639
4640 ILPOrder(bool MaxILP) : MaximizeILP(MaxILP) {}
4641
4642 /// Apply a less-than relation on node priority.
4643 ///
4644 /// (Return true if A comes after B in the Q.)
4645 bool operator()(const SUnit *A, const SUnit *B) const {
4646 unsigned SchedTreeA = DFSResult->getSubtreeID(SU: A);
4647 unsigned SchedTreeB = DFSResult->getSubtreeID(SU: B);
4648 if (SchedTreeA != SchedTreeB) {
4649 // Unscheduled trees have lower priority.
4650 if (ScheduledTrees->test(Idx: SchedTreeA) != ScheduledTrees->test(Idx: SchedTreeB))
4651 return ScheduledTrees->test(Idx: SchedTreeB);
4652
4653 // Trees with shallower connections have lower priority.
4654 if (DFSResult->getSubtreeLevel(SubtreeID: SchedTreeA)
4655 != DFSResult->getSubtreeLevel(SubtreeID: SchedTreeB)) {
4656 return DFSResult->getSubtreeLevel(SubtreeID: SchedTreeA)
4657 < DFSResult->getSubtreeLevel(SubtreeID: SchedTreeB);
4658 }
4659 }
4660 if (MaximizeILP)
4661 return DFSResult->getILP(SU: A) < DFSResult->getILP(SU: B);
4662 else
4663 return DFSResult->getILP(SU: A) > DFSResult->getILP(SU: B);
4664 }
4665};
4666
4667/// Schedule based on the ILP metric.
4668class ILPScheduler : public MachineSchedStrategy {
4669 ScheduleDAGMILive *DAG = nullptr;
4670 ILPOrder Cmp;
4671
4672 std::vector<SUnit*> ReadyQ;
4673
4674public:
4675 ILPScheduler(bool MaximizeILP) : Cmp(MaximizeILP) {}
4676
4677 void initialize(ScheduleDAGMI *dag) override {
4678 assert(dag->hasVRegLiveness() && "ILPScheduler needs vreg liveness");
4679 DAG = static_cast<ScheduleDAGMILive*>(dag);
4680 DAG->computeDFSResult();
4681 Cmp.DFSResult = DAG->getDFSResult();
4682 Cmp.ScheduledTrees = &DAG->getScheduledTrees();
4683 ReadyQ.clear();
4684 }
4685
4686 void registerRoots() override {
4687 // Restore the heap in ReadyQ with the updated DFS results.
4688 std::make_heap(first: ReadyQ.begin(), last: ReadyQ.end(), comp: Cmp);
4689 }
4690
4691 /// Implement MachineSchedStrategy interface.
4692 /// -----------------------------------------
4693
4694 /// Callback to select the highest priority node from the ready Q.
4695 SUnit *pickNode(bool &IsTopNode) override {
4696 if (ReadyQ.empty()) return nullptr;
4697 std::pop_heap(first: ReadyQ.begin(), last: ReadyQ.end(), comp: Cmp);
4698 SUnit *SU = ReadyQ.back();
4699 ReadyQ.pop_back();
4700 IsTopNode = false;
4701 LLVM_DEBUG(dbgs() << "Pick node "
4702 << "SU(" << SU->NodeNum << ") "
4703 << " ILP: " << DAG->getDFSResult()->getILP(SU)
4704 << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU)
4705 << " @"
4706 << DAG->getDFSResult()->getSubtreeLevel(
4707 DAG->getDFSResult()->getSubtreeID(SU))
4708 << '\n'
4709 << "Scheduling " << *SU->getInstr());
4710 return SU;
4711 }
4712
4713 /// Scheduler callback to notify that a new subtree is scheduled.
4714 void scheduleTree(unsigned SubtreeID) override {
4715 std::make_heap(first: ReadyQ.begin(), last: ReadyQ.end(), comp: Cmp);
4716 }
4717
4718 /// Callback after a node is scheduled. Mark a newly scheduled tree, notify
4719 /// DFSResults, and resort the priority Q.
4720 void schedNode(SUnit *SU, bool IsTopNode) override {
4721 assert(!IsTopNode && "SchedDFSResult needs bottom-up");
4722 }
4723
4724 void releaseTopNode(SUnit *) override { /*only called for top roots*/ }
4725
4726 void releaseBottomNode(SUnit *SU) override {
4727 ReadyQ.push_back(x: SU);
4728 std::push_heap(first: ReadyQ.begin(), last: ReadyQ.end(), comp: Cmp);
4729 }
4730};
4731
4732} // end anonymous namespace
4733
4734static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) {
4735 return new ScheduleDAGMILive(C, std::make_unique<ILPScheduler>(args: true));
4736}
4737static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) {
4738 return new ScheduleDAGMILive(C, std::make_unique<ILPScheduler>(args: false));
4739}
4740
4741static MachineSchedRegistry ILPMaxRegistry(
4742 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler);
4743static MachineSchedRegistry ILPMinRegistry(
4744 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler);
4745
4746//===----------------------------------------------------------------------===//
4747// Machine Instruction Shuffler for Correctness Testing
4748//===----------------------------------------------------------------------===//
4749
4750#ifndef NDEBUG
4751namespace {
4752
4753/// Apply a less-than relation on the node order, which corresponds to the
4754/// instruction order prior to scheduling. IsReverse implements greater-than.
4755template<bool IsReverse>
4756struct SUnitOrder {
4757 bool operator()(SUnit *A, SUnit *B) const {
4758 if (IsReverse)
4759 return A->NodeNum > B->NodeNum;
4760 else
4761 return A->NodeNum < B->NodeNum;
4762 }
4763};
4764
4765/// Reorder instructions as much as possible.
4766class InstructionShuffler : public MachineSchedStrategy {
4767 bool IsAlternating;
4768 bool IsTopDown;
4769
4770 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority
4771 // gives nodes with a higher number higher priority causing the latest
4772 // instructions to be scheduled first.
4773 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false>>
4774 TopQ;
4775
4776 // When scheduling bottom-up, use greater-than as the queue priority.
4777 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true>>
4778 BottomQ;
4779
4780public:
4781 InstructionShuffler(bool alternate, bool topdown)
4782 : IsAlternating(alternate), IsTopDown(topdown) {}
4783
4784 void initialize(ScheduleDAGMI*) override {
4785 TopQ.clear();
4786 BottomQ.clear();
4787 }
4788
4789 /// Implement MachineSchedStrategy interface.
4790 /// -----------------------------------------
4791
4792 SUnit *pickNode(bool &IsTopNode) override {
4793 SUnit *SU;
4794 if (IsTopDown) {
4795 do {
4796 if (TopQ.empty()) return nullptr;
4797 SU = TopQ.top();
4798 TopQ.pop();
4799 } while (SU->isScheduled);
4800 IsTopNode = true;
4801 } else {
4802 do {
4803 if (BottomQ.empty()) return nullptr;
4804 SU = BottomQ.top();
4805 BottomQ.pop();
4806 } while (SU->isScheduled);
4807 IsTopNode = false;
4808 }
4809 if (IsAlternating)
4810 IsTopDown = !IsTopDown;
4811 return SU;
4812 }
4813
4814 void schedNode(SUnit *SU, bool IsTopNode) override {}
4815
4816 void releaseTopNode(SUnit *SU) override {
4817 TopQ.push(SU);
4818 }
4819 void releaseBottomNode(SUnit *SU) override {
4820 BottomQ.push(SU);
4821 }
4822};
4823
4824} // end anonymous namespace
4825
4826static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {
4827 bool Alternate =
4828 PreRADirection != MISched::TopDown && PreRADirection != MISched::BottomUp;
4829 bool TopDown = PreRADirection != MISched::BottomUp;
4830 return new ScheduleDAGMILive(
4831 C, std::make_unique<InstructionShuffler>(Alternate, TopDown));
4832}
4833
4834static MachineSchedRegistry ShufflerRegistry(
4835 "shuffle", "Shuffle machine instructions alternating directions",
4836 createInstructionShuffler);
4837#endif // !NDEBUG
4838
4839//===----------------------------------------------------------------------===//
4840// GraphWriter support for ScheduleDAGMILive.
4841//===----------------------------------------------------------------------===//
4842
4843#ifndef NDEBUG
4844
4845template <>
4846struct llvm::GraphTraits<ScheduleDAGMI *> : public GraphTraits<ScheduleDAG *> {
4847};
4848
4849template <>
4850struct llvm::DOTGraphTraits<ScheduleDAGMI *> : public DefaultDOTGraphTraits {
4851 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
4852
4853 static std::string getGraphName(const ScheduleDAG *G) {
4854 return std::string(G->MF.getName());
4855 }
4856
4857 static bool renderGraphFromBottomUp() {
4858 return true;
4859 }
4860
4861 static bool isNodeHidden(const SUnit *Node, const ScheduleDAG *G) {
4862 if (ViewMISchedCutoff == 0)
4863 return false;
4864 return (Node->Preds.size() > ViewMISchedCutoff
4865 || Node->Succs.size() > ViewMISchedCutoff);
4866 }
4867
4868 /// If you want to override the dot attributes printed for a particular
4869 /// edge, override this method.
4870 static std::string getEdgeAttributes(const SUnit *Node,
4871 SUnitIterator EI,
4872 const ScheduleDAG *Graph) {
4873 if (EI.isArtificialDep())
4874 return "color=cyan,style=dashed";
4875 if (EI.isCtrlDep())
4876 return "color=blue,style=dashed";
4877 return "";
4878 }
4879
4880 static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) {
4881 std::string Str;
4882 raw_string_ostream SS(Str);
4883 const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
4884 const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
4885 static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
4886 SS << "SU:" << SU->NodeNum;
4887 if (DFS)
4888 SS << " I:" << DFS->getNumInstrs(SU);
4889 return Str;
4890 }
4891
4892 static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) {
4893 return G->getGraphNodeLabel(SU);
4894 }
4895
4896 static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G) {
4897 std::string Str("shape=Mrecord");
4898 const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
4899 const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
4900 static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
4901 if (DFS) {
4902 Str += ",style=filled,fillcolor=\"#";
4903 Str += DOT::getColorString(DFS->getSubtreeID(N));
4904 Str += '"';
4905 }
4906 return Str;
4907 }
4908};
4909
4910#endif // NDEBUG
4911
4912/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG
4913/// rendered using 'dot'.
4914void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) {
4915#ifndef NDEBUG
4916 ViewGraph(this, Name, false, Title);
4917#else
4918 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "
4919 << "systems with Graphviz or gv!\n";
4920#endif // NDEBUG
4921}
4922
4923/// Out-of-line implementation with no arguments is handy for gdb.
4924void ScheduleDAGMI::viewGraph() {
4925 viewGraph(Name: getDAGName(), Title: "Scheduling-Units Graph for " + getDAGName());
4926}
4927
4928/// Sort predicate for the intervals stored in an instance of
4929/// ResourceSegments. Intervals are always disjoint (no intersection
4930/// for any pairs of intervals), therefore we can sort the totality of
4931/// the intervals by looking only at the left boundary.
4932static bool sortIntervals(const ResourceSegments::IntervalTy &A,
4933 const ResourceSegments::IntervalTy &B) {
4934 return A.first < B.first;
4935}
4936
4937unsigned ResourceSegments::getFirstAvailableAt(
4938 unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle,
4939 std::function<ResourceSegments::IntervalTy(unsigned, unsigned, unsigned)>
4940 IntervalBuilder) const {
4941 assert(llvm::is_sorted(_Intervals, sortIntervals) &&
4942 "Cannot execute on an un-sorted set of intervals.");
4943
4944 // Zero resource usage is allowed by TargetSchedule.td but we do not construct
4945 // a ResourceSegment interval for that situation.
4946 if (AcquireAtCycle == ReleaseAtCycle)
4947 return CurrCycle;
4948
4949 unsigned RetCycle = CurrCycle;
4950 ResourceSegments::IntervalTy NewInterval =
4951 IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);
4952 for (auto &Interval : _Intervals) {
4953 if (!intersects(A: NewInterval, B: Interval))
4954 continue;
4955
4956 // Move the interval right next to the top of the one it
4957 // intersects.
4958 assert(Interval.second > NewInterval.first &&
4959 "Invalid intervals configuration.");
4960 RetCycle += (unsigned)Interval.second - (unsigned)NewInterval.first;
4961 NewInterval = IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);
4962 }
4963 return RetCycle;
4964}
4965
4966void ResourceSegments::add(ResourceSegments::IntervalTy A,
4967 const unsigned CutOff) {
4968 assert(A.first <= A.second && "Cannot add negative resource usage");
4969 assert(CutOff > 0 && "0-size interval history has no use.");
4970 // Zero resource usage is allowed by TargetSchedule.td, in the case that the
4971 // instruction needed the resource to be available but does not use it.
4972 // However, ResourceSegment represents an interval that is closed on the left
4973 // and open on the right. It is impossible to represent an empty interval when
4974 // the left is closed. Do not add it to Intervals.
4975 if (A.first == A.second)
4976 return;
4977
4978 assert(all_of(_Intervals,
4979 [&A](const ResourceSegments::IntervalTy &Interval) -> bool {
4980 return !intersects(A, Interval);
4981 }) &&
4982 "A resource is being overwritten");
4983 _Intervals.push_back(x: A);
4984
4985 sortAndMerge();
4986
4987 // Do not keep the full history of the intervals, just the
4988 // latest #CutOff.
4989 while (_Intervals.size() > CutOff)
4990 _Intervals.pop_front();
4991}
4992
4993bool ResourceSegments::intersects(ResourceSegments::IntervalTy A,
4994 ResourceSegments::IntervalTy B) {
4995 assert(A.first <= A.second && "Invalid interval");
4996 assert(B.first <= B.second && "Invalid interval");
4997
4998 // Share one boundary.
4999 if ((A.first == B.first) || (A.second == B.second))
5000 return true;
5001
5002 // full intersersect: [ *** ) B
5003 // [***) A
5004 if ((A.first > B.first) && (A.second < B.second))
5005 return true;
5006
5007 // right intersect: [ ***) B
5008 // [*** ) A
5009 if ((A.first > B.first) && (A.first < B.second) && (A.second > B.second))
5010 return true;
5011
5012 // left intersect: [*** ) B
5013 // [ ***) A
5014 if ((A.first < B.first) && (B.first < A.second) && (B.second > B.first))
5015 return true;
5016
5017 return false;
5018}
5019
5020void ResourceSegments::sortAndMerge() {
5021 if (_Intervals.size() <= 1)
5022 return;
5023
5024 // First sort the collection.
5025 _Intervals.sort(comp: sortIntervals);
5026
5027 // can use next because I have at least 2 elements in the list
5028 auto next = std::next(x: std::begin(cont&: _Intervals));
5029 auto E = std::end(cont&: _Intervals);
5030 for (; next != E; ++next) {
5031 if (std::prev(x: next)->second >= next->first) {
5032 next->first = std::prev(x: next)->first;
5033 _Intervals.erase(position: std::prev(x: next));
5034 continue;
5035 }
5036 }
5037}
5038