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