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