1//======----------- WindowScheduler.cpp - window 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// An implementation of the Window Scheduling software pipelining algorithm.
10//
11// The fundamental concept of the window scheduling algorithm involves folding
12// the original MBB at a specific position, followed by list scheduling on the
13// folded MIs. The optimal scheduling result is then chosen from various folding
14// positions as the final scheduling outcome.
15//
16// The primary challenge in this algorithm lies in generating the folded MIs and
17// establishing their dependencies. We have innovatively employed a new MBB,
18// created by copying the original MBB three times, known as TripleMBB. This
19// TripleMBB enables the convenient implementation of MI folding and dependency
20// establishment. To facilitate the algorithm's implementation, we have also
21// devised data structures such as OriMIs, TriMIs, TriToOri, and OriToCycle.
22//
23// Another challenge in the algorithm is the scheduling of phis. Semantically,
24// it is difficult to place the phis in the window and perform list scheduling.
25// Therefore, we schedule these phis separately after each list scheduling.
26//
27// The provided implementation is designed for use before the Register Allocator
28// (RA). If the target requires implementation after RA, it is recommended to
29// reimplement analyseII(), schedulePhi(), and expand(). Additionally,
30// target-specific logic can be added in initialize(), preProcess(), and
31// postProcess().
32//
33// Lastly, it is worth mentioning that getSearchIndexes() is an important
34// function. We have experimented with more complex heuristics on downstream
35// target and achieved favorable results.
36//
37//===----------------------------------------------------------------------===//
38#include "llvm/CodeGen/WindowScheduler.h"
39#include "llvm/ADT/Statistic.h"
40#include "llvm/Analysis/AliasAnalysis.h"
41#include "llvm/Analysis/MemoryLocation.h"
42#include "llvm/Analysis/ValueTracking.h"
43#include "llvm/CodeGen/LiveIntervals.h"
44#include "llvm/CodeGen/MachineLoopInfo.h"
45#include "llvm/CodeGen/MachinePipeliner.h"
46#include "llvm/CodeGen/ModuloSchedule.h"
47#include "llvm/CodeGen/ScheduleDAGMutation.h"
48#include "llvm/CodeGen/TargetPassConfig.h"
49#include "llvm/Support/CommandLine.h"
50#include "llvm/Support/Debug.h"
51#include "llvm/Support/TimeProfiler.h"
52#include "llvm/Target/TargetMachine.h"
53
54using namespace llvm;
55
56#define DEBUG_TYPE "pipeliner"
57
58namespace {
59STATISTIC(NumTryWindowSchedule,
60 "Number of loops that we attempt to use window scheduling");
61STATISTIC(NumTryWindowSearch,
62 "Number of times that we run list schedule in the window scheduling");
63STATISTIC(NumWindowSchedule,
64 "Number of loops that we successfully use window scheduling");
65STATISTIC(NumFailAnalyseII,
66 "Window scheduling abort due to the failure of the II analysis");
67
68cl::opt<unsigned>
69 WindowSearchNum("window-search-num",
70 cl::desc("The number of searches per loop in the window "
71 "algorithm. 0 means no search number limit."),
72 cl::Hidden, cl::init(Val: 6));
73
74cl::opt<unsigned> WindowSearchRatio(
75 "window-search-ratio",
76 cl::desc("The ratio of searches per loop in the window algorithm. 100 "
77 "means search all positions in the loop, while 0 means not "
78 "performing any search."),
79 cl::Hidden, cl::init(Val: 40));
80
81cl::opt<unsigned> WindowIICoeff(
82 "window-ii-coeff",
83 cl::desc(
84 "The coefficient used when initializing II in the window algorithm."),
85 cl::Hidden, cl::init(Val: 5));
86
87cl::opt<unsigned> WindowRegionLimit(
88 "window-region-limit",
89 cl::desc(
90 "The lower limit of the scheduling region in the window algorithm."),
91 cl::Hidden, cl::init(Val: 3));
92
93cl::opt<unsigned> WindowDiffLimit(
94 "window-diff-limit",
95 cl::desc("The lower limit of the difference between best II and base II in "
96 "the window algorithm. If the difference is smaller than "
97 "this lower limit, window scheduling will not be performed."),
98 cl::Hidden, cl::init(Val: 2));
99} // namespace
100
101// WindowIILimit serves as an indicator of abnormal scheduling results and could
102// potentially be referenced by the derived target window scheduler.
103static cl::opt<unsigned>
104 WindowIILimit("window-ii-limit",
105 cl::desc("The upper limit of II in the window algorithm."),
106 cl::Hidden, cl::init(Val: 1000));
107
108/// Collect the underlying objects and alias metadata for the single memory
109/// operand of MI. Returns false when MI does not have exactly one memory
110/// operand with a known IR value.
111static bool getMemInfo(const MachineInstr *MI, const Value *&MemOpValue,
112 int64_t &MemOpOffset,
113 SmallVectorImpl<const Value *> &UnderlyingObjs,
114 AAMDNodes &AATags, bool &IsAllIdentified) {
115 if (!MI->hasOneMemOperand())
116 return false;
117 MachineMemOperand *MM = *MI->memoperands_begin();
118 if (!MM->getValue())
119 return false;
120 MemOpValue = MM->getValue();
121 MemOpOffset = MM->getOffset();
122 getUnderlyingObjects(V: MemOpValue, Objects&: UnderlyingObjs);
123 AATags = MM->getAAInfo();
124 IsAllIdentified = llvm::all_of(Range&: UnderlyingObjs, P: isIdentifiedObject);
125 return true;
126}
127
128/// Return true if there is a loop-carried order dependency from memory access
129/// SrcMI to DstMI in loop LoopBB.
130static bool hasLoopCarriedMemDep(const MachineInstr *SrcMI,
131 const MachineInstr *DstMI, BatchAAResults &BAA,
132 const MachineBasicBlock *LoopBB,
133 const MachineRegisterInfo &MRI,
134 const TargetInstrInfo *TII) {
135 const Value *SrcVal = nullptr, *DstVal = nullptr;
136 int64_t SrcOffset = 0, DstOffset = 0;
137 SmallVector<const Value *, 4> SrcObjs, DstObjs;
138 AAMDNodes SrcAATags, DstAATags;
139 bool SrcAllIdentified = false, DstAllIdentified = false;
140 bool SrcKnown = getMemInfo(MI: SrcMI, MemOpValue&: SrcVal, MemOpOffset&: SrcOffset, UnderlyingObjs&: SrcObjs, AATags&: SrcAATags,
141 IsAllIdentified&: SrcAllIdentified);
142 bool DstKnown = getMemInfo(MI: DstMI, MemOpValue&: DstVal, MemOpOffset&: DstOffset, UnderlyingObjs&: DstObjs, AATags&: DstAATags,
143 IsAllIdentified&: DstAllIdentified);
144
145 // If all underlying objects are identified and disjoint, the accesses cannot
146 // alias.
147 if (SrcKnown && DstKnown && SrcAllIdentified && DstAllIdentified &&
148 llvm::none_of(Range&: SrcObjs, P: [&](const Value *Obj) {
149 return llvm::is_contained(Range&: DstObjs, Element: Obj);
150 }))
151 return false;
152
153 // The overlap helper inspects only the first memory operand. Multi-MMO
154 // instructions could carry an overlap through a later operand, so be
155 // conservative and keep the dependency for them.
156 if (!SrcMI->hasOneMemOperand() || !DstMI->hasOneMemOperand())
157 return true;
158
159 if (!mayOverlapInLaterIter(BaseMI: SrcMI, OtherMI: DstMI, LoopBB, MRI, TII: *TII))
160 return false;
161
162 // The more expensive check that uses alias analysis on the base values.
163 if (!SrcKnown || !DstKnown)
164 return true;
165 if (SrcVal == DstVal && SrcOffset <= DstOffset)
166 return true;
167
168 if (BAA.isNoAlias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: SrcVal, AATags: SrcAATags),
169 LocB: MemoryLocation::getBeforeOrAfter(Ptr: DstVal, AATags: DstAATags)))
170 return false;
171
172 // AliasAnalysis sometimes gives up on following the underlying object. In
173 // such a case, separate checks for underlying objects may prove that there
174 // are no aliases between two accesses.
175 for (const Value *SrcObj : SrcObjs)
176 for (const Value *DstObj : DstObjs)
177 if (!BAA.isNoAlias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: SrcObj, AATags: SrcAATags),
178 LocB: MemoryLocation::getBeforeOrAfter(Ptr: DstObj, AATags: DstAATags)))
179 return true;
180
181 return false;
182}
183
184namespace {
185/// A DAG mutation that enforces the loop-carried memory dependences discovered
186/// on the original loop while list scheduling each window of TripleMBB.
187///
188/// For each recorded hazard pair (Pred, Succ) we add an artificial order edge
189/// between the clone of Pred and the clone of Succ belonging to a later copy,
190/// so that the iteration-N Pred is kept before the iteration-(N+1) Succ.
191class WindowMemDepMutation : public ScheduleDAGMutation {
192 const DenseSet<std::pair<MachineInstr *, MachineInstr *>> &LoopCarriedMemDeps;
193 const DenseMap<MachineInstr *, TriCloneInfo> &TriToOri;
194 bool &EdgeFailed;
195
196public:
197 WindowMemDepMutation(
198 const DenseSet<std::pair<MachineInstr *, MachineInstr *>> &Deps,
199 const DenseMap<MachineInstr *, TriCloneInfo> &TriToOri, bool &EdgeFailed)
200 : LoopCarriedMemDeps(Deps), TriToOri(TriToOri), EdgeFailed(EdgeFailed) {}
201
202 void apply(ScheduleDAGInstrs *DAG) override {
203 if (LoopCarriedMemDeps.empty())
204 return;
205 for (SUnit &PredSU : DAG->SUnits) {
206 MachineInstr *PredMI = PredSU.getInstr();
207 if (!PredMI || !PredMI->mayLoadOrStore())
208 continue;
209 auto PredIt = TriToOri.find(Val: PredMI);
210 if (PredIt == TriToOri.end())
211 continue;
212 for (SUnit &SuccSU : DAG->SUnits) {
213 MachineInstr *SuccMI = SuccSU.getInstr();
214 if (&PredSU == &SuccSU || !SuccMI || !SuccMI->mayLoadOrStore())
215 continue;
216 auto SuccIt = TriToOri.find(Val: SuccMI);
217 if (SuccIt == TriToOri.end())
218 continue;
219 // Only order a Pred from an earlier copy before a Succ from a later
220 // copy, which models the iteration-N to iteration-(N+1) dependence.
221 if (PredIt->second.Copy >= SuccIt->second.Copy)
222 continue;
223 if (!LoopCarriedMemDeps.contains(
224 V: {PredIt->second.Ori, SuccIt->second.Ori}))
225 continue;
226 // If the edge would create a cycle, addEdge() returns false and does
227 // not insert it. The required dependence then cannot be enforced in
228 // this window, so mark it to make the caller abandon this window's
229 // schedule.
230 if (!DAG->addEdge(SuccSU: &SuccSU, PredDep: SDep(&PredSU, SDep::Barrier)))
231 EdgeFailed = true;
232 }
233 }
234 }
235};
236} // end anonymous namespace
237
238WindowScheduler::WindowScheduler(MachineSchedContext *C, MachineLoop &ML,
239 MachineDominatorTree *MDT)
240 : Context(C), MF(C->MF), MBB(ML.getHeader()), Loop(ML),
241 Subtarget(&MF->getSubtarget()), TII(Subtarget->getInstrInfo()),
242 TRI(Subtarget->getRegisterInfo()), MRI(&MF->getRegInfo()), MDT(MDT) {
243 TripleDAG = std::unique_ptr<ScheduleDAGInstrs>(
244 createMachineScheduler(/*OnlyBuildGraph=*/true));
245}
246
247bool WindowScheduler::run() {
248 if (!initialize()) {
249 LLVM_DEBUG(dbgs() << "The WindowScheduler failed to initialize!\n");
250 return false;
251 }
252 // The window algorithm is time-consuming, and its compilation time should be
253 // taken into consideration.
254 TimeTraceScope Scope("WindowSearch");
255 ++NumTryWindowSchedule;
256 // Performing the relevant processing before window scheduling.
257 preProcess();
258 // The main window scheduling begins.
259 std::unique_ptr<ScheduleDAGInstrs> SchedDAG(createMachineScheduler());
260 // A target may decline to provide a scheduler, in which case fall back to the
261 // generic live scheduler so that window scheduling still has one to drive.
262 if (!SchedDAG)
263 SchedDAG.reset(p: createSchedLive(C: Context));
264 // Attach the mutation that enforces the loop-carried memory dependences.
265 // This requires the scheduler to support DAG mutations, i.e. to be a
266 // ScheduleDAGMI. Every in-tree target's pre-RA machine scheduler is a
267 // ScheduleDAGMI (or ScheduleDAGMILive), and the generic fallback
268 // createSchedLive() above returns one as well, so the cast below is safe.
269 // The assert documents and guards this invariant.
270 assert(SchedDAG && "Expected a scheduler for window scheduling");
271 auto *SchedDAGMI = static_cast<ScheduleDAGMI *>(SchedDAG.get());
272 SchedDAGMI->addMutation(Mutation: std::make_unique<WindowMemDepMutation>(
273 args&: LoopCarriedMemDeps, args&: TriToOri, args&: MemDepEdgeFailed));
274 auto SearchIndexes = getSearchIndexes(SearchNum: WindowSearchNum, SearchRatio: WindowSearchRatio);
275 for (unsigned Idx : SearchIndexes) {
276 OriToCycle.clear();
277 ++NumTryWindowSearch;
278 // The scheduling starts with non-phi instruction, so SchedPhiNum needs to
279 // be added to Idx.
280 unsigned Offset = Idx + SchedPhiNum;
281 auto Range = getScheduleRange(Offset, Num: SchedInstrNum);
282 MemDepEdgeFailed = false;
283 SchedDAG->startBlock(BB: MBB);
284 SchedDAG->enterRegion(bb: MBB, begin: Range.begin(), end: Range.end(), regioninstrs: SchedInstrNum);
285 SchedDAG->schedule();
286 LLVM_DEBUG(SchedDAG->dump());
287 if (MemDepEdgeFailed) {
288 restoreTripleMBB();
289 LLVM_DEBUG(dbgs() << "Can't enforce a loop-carried memory dependence. "
290 "Keep searching...\n");
291 continue;
292 }
293 unsigned II = analyseII(DAG&: *SchedDAG, Offset);
294 if (II == WindowIILimit) {
295 restoreTripleMBB();
296 LLVM_DEBUG(dbgs() << "Can't find a valid II. Keep searching...\n");
297 ++NumFailAnalyseII;
298 continue;
299 }
300 schedulePhi(Offset, II);
301 updateScheduleResult(Offset, II);
302 restoreTripleMBB();
303 LLVM_DEBUG(dbgs() << "Current window Offset is " << Offset << " and II is "
304 << II << ".\n");
305 }
306 // Performing the relevant processing after window scheduling.
307 postProcess();
308 // Check whether the scheduling result is valid.
309 if (!isScheduleValid()) {
310 LLVM_DEBUG(dbgs() << "Window scheduling is not needed!\n");
311 return false;
312 }
313 LLVM_DEBUG(dbgs() << "\nBest window offset is " << BestOffset
314 << " and Best II is " << BestII << ".\n");
315 // Expand the scheduling result to prologue, kernel, and epilogue.
316 expand();
317 ++NumWindowSchedule;
318 return true;
319}
320
321ScheduleDAGInstrs *
322WindowScheduler::createMachineScheduler(bool OnlyBuildGraph) {
323 return OnlyBuildGraph
324 ? new ScheduleDAGMI(
325 Context, std::make_unique<PostGenericScheduler>(args&: Context),
326 true)
327 : Context->TM->createMachineScheduler(C: Context);
328}
329
330bool WindowScheduler::initialize() {
331 if (!Subtarget->enableWindowScheduler()) {
332 LLVM_DEBUG(dbgs() << "Target disables the window scheduling!\n");
333 return false;
334 }
335 // Initialized the member variables used by window algorithm.
336 OriMIs.clear();
337 TriMIs.clear();
338 TriToOri.clear();
339 OriToCycle.clear();
340 SchedResult.clear();
341 SchedPhiNum = 0;
342 SchedInstrNum = 0;
343 BestII = UINT_MAX;
344 BestOffset = 0;
345 BaseII = 0;
346 // List scheduling used in the window algorithm depends on LiveIntervals.
347 if (!Context->LIS) {
348 LLVM_DEBUG(dbgs() << "There is no LiveIntervals information!\n");
349 return false;
350 }
351 // Check each MI in MBB.
352 SmallSet<Register, 8> PrevDefs;
353 SmallSet<Register, 8> PrevUses;
354 auto IsLoopCarried = [&](MachineInstr &Phi) {
355 // Two cases are checked here: (1)The virtual register defined by the
356 // preceding phi is used by the succeeding phi;(2)The preceding phi uses the
357 // virtual register defined by the succeeding phi.
358 if (PrevUses.count(V: Phi.getOperand(i: 0).getReg()))
359 return true;
360 PrevDefs.insert(V: Phi.getOperand(i: 0).getReg());
361 for (unsigned I = 1, E = Phi.getNumOperands(); I != E; I += 2) {
362 if (PrevDefs.count(V: Phi.getOperand(i: I).getReg()))
363 return true;
364 PrevUses.insert(V: Phi.getOperand(i: I).getReg());
365 }
366 return false;
367 };
368 auto PLI = TII->analyzeLoopForPipelining(LoopBB: MBB);
369 for (auto &MI : *MBB) {
370 if (MI.isDebugOrPseudoInstr() || MI.isTerminator())
371 continue;
372 if (MI.isPHI()) {
373 if (IsLoopCarried(MI)) {
374 LLVM_DEBUG(dbgs() << "Loop carried phis are not supported yet!\n");
375 return false;
376 }
377 ++SchedPhiNum;
378 ++BestOffset;
379 } else
380 ++SchedInstrNum;
381 if (TII->isSchedulingBoundary(MI, MBB, MF: *MF)) {
382 LLVM_DEBUG(
383 dbgs() << "Boundary MI is not allowed in window scheduling!\n");
384 return false;
385 }
386 if (PLI->shouldIgnoreForPipelining(MI: &MI)) {
387 LLVM_DEBUG(dbgs() << "Special MI defined by target is not allowed in "
388 "window scheduling!\n");
389 return false;
390 }
391 for (auto &Def : MI.all_defs())
392 if (Def.isReg() && Def.getReg().isPhysical()) {
393 LLVM_DEBUG(dbgs() << "Physical registers are not supported in "
394 "window scheduling!\n");
395 return false;
396 }
397 }
398 if (SchedInstrNum <= WindowRegionLimit) {
399 LLVM_DEBUG(dbgs() << "There are too few MIs in the window region!\n");
400 return false;
401 }
402 return true;
403}
404
405void WindowScheduler::preProcess() {
406 // Prior to window scheduling, it's necessary to backup the original MBB,
407 // generate a new TripleMBB, and build a TripleDAG based on the TripleMBB.
408 // Collect loop-carried memory dependences first, while the original MBB is
409 // still live (see collectLoopCarriedMemDeps() and run()).
410 collectLoopCarriedMemDeps();
411 backupMBB();
412 generateTripleMBB();
413 TripleDAG->startBlock(BB: MBB);
414 TripleDAG->enterRegion(
415 bb: MBB, begin: MBB->begin(), end: MBB->getFirstTerminator(),
416 regioninstrs: std::distance(first: MBB->begin(), last: MBB->getFirstTerminator()));
417 TripleDAG->buildSchedGraph(AA: Context->AA);
418}
419
420void WindowScheduler::collectLoopCarriedMemDeps() {
421 LoopCarriedMemDeps.clear();
422 MachineBasicBlock *LoopBB = MBB;
423
424 // Collect the memory instructions of the original loop in program order.
425 SmallVector<MachineInstr *> MemMIs;
426 for (MachineInstr &MI : *LoopBB)
427 if (MI.mayLoadOrStore() && !MI.isDebugInstr())
428 MemMIs.push_back(Elt: &MI);
429
430 // Nothing to do unless there is at least one store to order against.
431 if (llvm::none_of(Range&: MemMIs,
432 P: [](const MachineInstr *MI) { return MI->mayStore(); }))
433 return;
434
435 BatchAAResults BAA(*Context->AA);
436 BAA.enableCrossIterationMode();
437
438 for (MachineInstr *SrcMI : MemMIs) {
439 for (MachineInstr *DstMI : MemMIs) {
440 if (SrcMI == DstMI)
441 continue;
442 // A loop-carried order edge is only required when at least one of the
443 // accesses stores.
444 if (!SrcMI->mayStore() && !DstMI->mayStore())
445 continue;
446 if (hasLoopCarriedMemDep(SrcMI, DstMI, BAA, LoopBB, MRI: *MRI, TII))
447 LoopCarriedMemDeps.insert(V: {SrcMI, DstMI});
448 }
449 }
450}
451
452void WindowScheduler::postProcess() {
453 // After window scheduling, it's necessary to clear the TripleDAG and restore
454 // to the original MBB.
455 TripleDAG->exitRegion();
456 TripleDAG->finishBlock();
457 restoreMBB();
458}
459
460void WindowScheduler::backupMBB() {
461 for (auto &MI : MBB->instrs())
462 OriMIs.push_back(Elt: &MI);
463 // Remove MIs and the corresponding live intervals.
464 for (auto &MI : make_early_inc_range(Range&: *MBB)) {
465 Context->LIS->getSlotIndexes()->removeMachineInstrFromMaps(MI, AllowBundled: true);
466 MBB->remove(I: &MI);
467 }
468}
469
470void WindowScheduler::restoreMBB() {
471 // Erase MIs and the corresponding live intervals.
472 for (auto &MI : make_early_inc_range(Range&: *MBB)) {
473 Context->LIS->getSlotIndexes()->removeMachineInstrFromMaps(MI, AllowBundled: true);
474 MI.eraseFromParent();
475 }
476 // Restore MBB to the state before window scheduling.
477 llvm::append_range(C&: *MBB, R&: OriMIs);
478 updateLiveIntervals();
479}
480
481void WindowScheduler::generateTripleMBB() {
482 const unsigned DuplicateNum = 3;
483 TriMIs.clear();
484 TriToOri.clear();
485 assert(OriMIs.size() > 0 && "The Original MIs were not backed up!");
486 // Step 1: Performing the first copy of MBB instructions, excluding
487 // terminators. At the same time, we back up the anti-register of phis.
488 // DefPairs hold the old and new define register pairs.
489 DenseMap<Register, Register> DefPairs;
490 for (auto *MI : OriMIs) {
491 if (MI->isDebugOrPseudoInstr() || MI->isTerminator())
492 continue;
493 if (MI->isPHI())
494 if (Register AntiReg = getAntiRegister(Phi: MI))
495 DefPairs[MI->getOperand(i: 0).getReg()] = AntiReg;
496 auto *NewMI = MF->CloneMachineInstr(Orig: MI);
497 MBB->push_back(MI: NewMI);
498 TriMIs.push_back(Elt: NewMI);
499 TriToOri[NewMI] = {.Ori: MI, .Copy: 0};
500 }
501 // Step 2: Performing the remaining two copies of MBB instructions excluding
502 // phis, and the last one contains terminators. At the same time, registers
503 // are updated accordingly.
504 for (size_t Cnt = 1; Cnt < DuplicateNum; ++Cnt) {
505 for (auto *MI : OriMIs) {
506 if (MI->isPHI() || MI->isDebugOrPseudoInstr() ||
507 (MI->isTerminator() && Cnt < DuplicateNum - 1))
508 continue;
509 auto *NewMI = MF->CloneMachineInstr(Orig: MI);
510 DenseMap<Register, Register> NewDefs;
511 // New defines are updated.
512 for (auto MO : NewMI->all_defs())
513 if (MO.isReg() && MO.getReg().isVirtual()) {
514 Register NewDef =
515 MRI->createVirtualRegister(RegClass: MRI->getRegClass(Reg: MO.getReg()));
516 NewMI->substituteRegister(FromReg: MO.getReg(), ToReg: NewDef, SubIdx: 0, RegInfo: *TRI);
517 NewDefs[MO.getReg()] = NewDef;
518 }
519 // New uses are updated.
520 for (auto DefRegPair : DefPairs)
521 if (NewMI->readsRegister(Reg: DefRegPair.first, TRI)) {
522 Register NewUse = DefRegPair.second;
523 // Note the update process for '%1 -> %9' in '%10 = sub i32 %9, %3':
524 //
525 // BB.3: DefPairs
526 // ==================================
527 // %1 = phi i32 [%2, %BB.1], [%7, %BB.3] (%1,%7)
528 // ...
529 // ==================================
530 // ...
531 // %4 = sub i32 %1, %3
532 // ...
533 // %7 = add i32 %5, %6
534 // ...
535 // ----------------------------------
536 // ...
537 // %8 = sub i32 %7, %3 (%1,%7),(%4,%8)
538 // ...
539 // %9 = add i32 %5, %6 (%1,%7),(%4,%8),(%7,%9)
540 // ...
541 // ----------------------------------
542 // ...
543 // %10 = sub i32 %9, %3 (%1,%7),(%4,%10),(%7,%9)
544 // ... ^
545 // %11 = add i32 %5, %6 (%1,%7),(%4,%10),(%7,%11)
546 // ...
547 // ==================================
548 // < Terminators >
549 // ==================================
550 if (auto It = DefPairs.find(Val: NewUse); It != DefPairs.end())
551 NewUse = It->second;
552 NewMI->substituteRegister(FromReg: DefRegPair.first, ToReg: NewUse, SubIdx: 0, RegInfo: *TRI);
553 }
554 // DefPairs is updated at last.
555 for (auto &NewDef : NewDefs)
556 DefPairs[NewDef.first] = NewDef.second;
557 MBB->push_back(MI: NewMI);
558 TriMIs.push_back(Elt: NewMI);
559 TriToOri[NewMI] = {.Ori: MI, .Copy: static_cast<unsigned>(Cnt)};
560 }
561 }
562 // Step 3: The registers used by phis are updated, and they are generated in
563 // the third copy of MBB.
564 // In the privious example, the old phi is:
565 // %1 = phi i32 [%2, %BB.1], [%7, %BB.3]
566 // The new phi is:
567 // %1 = phi i32 [%2, %BB.1], [%11, %BB.3]
568 for (auto &Phi : MBB->phis()) {
569 for (auto DefRegPair : DefPairs)
570 if (Phi.readsRegister(Reg: DefRegPair.first, TRI))
571 Phi.substituteRegister(FromReg: DefRegPair.first, ToReg: DefRegPair.second, SubIdx: 0, RegInfo: *TRI);
572 }
573 updateLiveIntervals();
574}
575
576void WindowScheduler::restoreTripleMBB() {
577 // After list scheduling, the MBB is restored in one traversal.
578 for (size_t I = 0; I < TriMIs.size(); ++I) {
579 auto *MI = TriMIs[I];
580 auto OldPos = MBB->begin();
581 std::advance(i&: OldPos, n: I);
582 auto CurPos = MI->getIterator();
583 if (CurPos != OldPos) {
584 MBB->splice(Where: OldPos, Other: MBB, From: CurPos);
585 Context->LIS->handleMove(MI&: *MI, /*UpdateFlags=*/false);
586 }
587 }
588}
589
590SmallVector<unsigned> WindowScheduler::getSearchIndexes(unsigned SearchNum,
591 unsigned SearchRatio) {
592 // We use SearchRatio to get the index range, and then evenly get the indexes
593 // according to the SearchNum. This is a simple huristic. Depending on the
594 // characteristics of the target, more complex algorithms can be used for both
595 // performance and compilation time.
596 assert(SearchRatio <= 100 && "SearchRatio should be equal or less than 100!");
597 unsigned MaxIdx = SchedInstrNum * SearchRatio / 100;
598 unsigned Step = SearchNum > 0 && SearchNum <= MaxIdx ? MaxIdx / SearchNum : 1;
599 SmallVector<unsigned> SearchIndexes;
600 for (unsigned Idx = 0; Idx < MaxIdx; Idx += Step)
601 SearchIndexes.push_back(Elt: Idx);
602 return SearchIndexes;
603}
604
605int WindowScheduler::getEstimatedII(ScheduleDAGInstrs &DAG) {
606 // Sometimes MaxDepth is 0, so it should be limited to the minimum of 1.
607 unsigned MaxDepth = 1;
608 for (auto &SU : DAG.SUnits)
609 MaxDepth = std::max(a: SU.getDepth() + SU.Latency, b: MaxDepth);
610 return MaxDepth * WindowIICoeff;
611}
612
613int WindowScheduler::calculateMaxCycle(ScheduleDAGInstrs &DAG,
614 unsigned Offset) {
615 int InitII = getEstimatedII(DAG);
616 ResourceManager RM(Subtarget, &DAG);
617 RM.init(II: InitII);
618 // ResourceManager and DAG are used to calculate the maximum cycle for the
619 // scheduled MIs. Since MIs in the Region have already been scheduled, the
620 // emit cycles can be estimated in order here.
621 int CurCycle = 0;
622 auto Range = getScheduleRange(Offset, Num: SchedInstrNum);
623 for (auto &MI : Range) {
624 auto *SU = DAG.getSUnit(MI: &MI);
625 int ExpectCycle = CurCycle;
626 // The predecessors of current MI determine its earliest issue cycle.
627 for (auto &Pred : SU->Preds) {
628 if (Pred.isWeak())
629 continue;
630 auto *PredMI = Pred.getSUnit()->getInstr();
631 int PredCycle = getOriCycle(NewMI: PredMI);
632 ExpectCycle = std::max(a: ExpectCycle, b: PredCycle + (int)Pred.getLatency());
633 }
634 // Zero cost instructions do not need to check resource.
635 if (!TII->isZeroCost(Opcode: MI.getOpcode())) {
636 // ResourceManager can be used to detect resource conflicts between the
637 // current MI and the previously inserted MIs.
638 while (!RM.canReserveResources(SU&: *SU, Cycle: CurCycle) || CurCycle < ExpectCycle) {
639 ++CurCycle;
640 if (CurCycle == (int)WindowIILimit)
641 return CurCycle;
642 }
643 RM.reserveResources(SU&: *SU, Cycle: CurCycle);
644 }
645 OriToCycle[getOriMI(NewMI: &MI)] = CurCycle;
646 LLVM_DEBUG(dbgs() << "\tCycle " << CurCycle << " [S."
647 << getOriStage(getOriMI(&MI), Offset) << "]: " << MI);
648 }
649 LLVM_DEBUG(dbgs() << "MaxCycle is " << CurCycle << ".\n");
650 return CurCycle;
651}
652
653// By utilizing TripleDAG, we can easily establish dependencies between A and B.
654// Based on the MaxCycle and the issue cycle of A and B, we can determine
655// whether it is necessary to add a stall cycle. This is because, without
656// inserting the stall cycle, the latency constraint between A and B cannot be
657// satisfied. The details are as follows:
658//
659// New MBB:
660// ========================================
661// < Phis >
662// ======================================== (sliding direction)
663// MBB copy 1 |
664// V
665//
666// ~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~ ----schedule window-----
667// | |
668// ===================V==================== |
669// MBB copy 2 < MI B > |
670// |
671// < MI A > V
672// ~~~~~~~~~~~~~~~~~~~:~~~~~~~~~~~~~~~~~~~~ ------------------------
673// :
674// ===================V====================
675// MBB copy 3 < MI B'>
676//
677//
678//
679//
680// ========================================
681// < Terminators >
682// ========================================
683int WindowScheduler::calculateStallCycle(unsigned Offset, int MaxCycle) {
684 int MaxStallCycle = 0;
685 int CurrentII = MaxCycle + 1;
686 auto Range = getScheduleRange(Offset, Num: SchedInstrNum);
687 for (auto &MI : Range) {
688 auto *SU = TripleDAG->getSUnit(MI: &MI);
689 int DefCycle = getOriCycle(NewMI: &MI);
690 for (auto &Succ : SU->Succs) {
691 if (Succ.isWeak() || Succ.getSUnit() == &TripleDAG->ExitSU)
692 continue;
693 // If the expected cycle does not exceed CurrentII, no check is needed.
694 if (DefCycle + (int)Succ.getLatency() <= CurrentII)
695 continue;
696 // If the cycle of the scheduled MI A is less than that of the scheduled
697 // MI B, the scheduling will fail because the lifetime of the
698 // corresponding register exceeds II.
699 auto *SuccMI = Succ.getSUnit()->getInstr();
700 int UseCycle = getOriCycle(NewMI: SuccMI);
701 if (DefCycle < UseCycle)
702 return WindowIILimit;
703 // Get the stall cycle introduced by the register between two trips.
704 int StallCycle = DefCycle + (int)Succ.getLatency() - CurrentII - UseCycle;
705 MaxStallCycle = std::max(a: MaxStallCycle, b: StallCycle);
706 }
707 }
708 LLVM_DEBUG(dbgs() << "MaxStallCycle is " << MaxStallCycle << ".\n");
709 return MaxStallCycle;
710}
711
712unsigned WindowScheduler::analyseII(ScheduleDAGInstrs &DAG, unsigned Offset) {
713 LLVM_DEBUG(dbgs() << "Start analyzing II:\n");
714 int MaxCycle = calculateMaxCycle(DAG, Offset);
715 if (MaxCycle == (int)WindowIILimit)
716 return MaxCycle;
717 int StallCycle = calculateStallCycle(Offset, MaxCycle);
718 if (StallCycle == (int)WindowIILimit)
719 return StallCycle;
720 // The value of II is equal to the maximum execution cycle plus 1.
721 return MaxCycle + StallCycle + 1;
722}
723
724void WindowScheduler::schedulePhi(int Offset, unsigned &II) {
725 LLVM_DEBUG(dbgs() << "Start scheduling Phis:\n");
726 for (auto &Phi : MBB->phis()) {
727 int LateCycle = INT_MAX;
728 auto *SU = TripleDAG->getSUnit(MI: &Phi);
729 for (auto &Succ : SU->Succs) {
730 // Phi doesn't have any Anti successors.
731 if (Succ.getKind() != SDep::Data)
732 continue;
733 // Phi is scheduled before the successor of stage 0. The issue cycle of
734 // phi is the latest cycle in this interval.
735 auto *SuccMI = Succ.getSUnit()->getInstr();
736 int Cycle = getOriCycle(NewMI: SuccMI);
737 if (getOriStage(OriMI: getOriMI(NewMI: SuccMI), Offset) == 0)
738 LateCycle = std::min(a: LateCycle, b: Cycle);
739 }
740 // The anti-dependency of phi need to be handled separately in the same way.
741 if (Register AntiReg = getAntiRegister(Phi: &Phi)) {
742 auto *AntiMI = MRI->getVRegDef(Reg: AntiReg);
743 // AntiReg may be defined outside the kernel MBB.
744 if (AntiMI->getParent() == MBB) {
745 auto AntiCycle = getOriCycle(NewMI: AntiMI);
746 if (getOriStage(OriMI: getOriMI(NewMI: AntiMI), Offset) == 0)
747 LateCycle = std::min(a: LateCycle, b: AntiCycle);
748 }
749 }
750 // If there is no limit to the late cycle, a default value is given.
751 if (LateCycle == INT_MAX)
752 LateCycle = (int)(II - 1);
753 LLVM_DEBUG(dbgs() << "\tCycle range [0, " << LateCycle << "] " << Phi);
754 // The issue cycle of phi is set to the latest cycle in the interval.
755 auto *OriPhi = getOriMI(NewMI: &Phi);
756 OriToCycle[OriPhi] = LateCycle;
757 }
758}
759
760DenseMap<MachineInstr *, int> WindowScheduler::getIssueOrder(unsigned Offset,
761 unsigned II) {
762 // At each issue cycle, phi is placed before MIs in stage 0. So the simplest
763 // way is to put phi at the beginning of the current cycle.
764 DenseMap<int, SmallVector<MachineInstr *>> CycleToMIs;
765 auto Range = getScheduleRange(Offset, Num: SchedInstrNum);
766 for (auto &Phi : MBB->phis())
767 CycleToMIs[getOriCycle(NewMI: &Phi)].push_back(Elt: getOriMI(NewMI: &Phi));
768 for (auto &MI : Range)
769 CycleToMIs[getOriCycle(NewMI: &MI)].push_back(Elt: getOriMI(NewMI: &MI));
770 // Each MI is assigned a separate ordered Id, which is used as a sort marker
771 // in the following expand process.
772 DenseMap<MachineInstr *, int> IssueOrder;
773 int Id = 0;
774 for (int Cycle = 0; Cycle < (int)II; ++Cycle) {
775 auto It = CycleToMIs.find(Val: Cycle);
776 if (It == CycleToMIs.end())
777 continue;
778 for (auto *MI : It->second)
779 IssueOrder[MI] = Id++;
780 }
781 return IssueOrder;
782}
783
784void WindowScheduler::updateScheduleResult(unsigned Offset, unsigned II) {
785 // At the first update, Offset is equal to SchedPhiNum. At this time, only
786 // BestII, BestOffset, and BaseII need to be updated.
787 if (Offset == SchedPhiNum) {
788 BestII = II;
789 BestOffset = SchedPhiNum;
790 BaseII = II;
791 return;
792 }
793 // The update will only continue if the II is smaller than BestII and the II
794 // is sufficiently small.
795 if ((II >= BestII) || (II + WindowDiffLimit > BaseII))
796 return;
797 BestII = II;
798 BestOffset = Offset;
799 // Record the result of the current list scheduling, noting that each MI is
800 // stored unordered in SchedResult.
801 SchedResult.clear();
802 auto IssueOrder = getIssueOrder(Offset, II);
803 for (auto &Pair : OriToCycle) {
804 assert(IssueOrder.count(Pair.first) && "Cannot find original MI!");
805 SchedResult.push_back(Elt: std::make_tuple(args&: Pair.first, args&: Pair.second,
806 args: getOriStage(OriMI: Pair.first, Offset),
807 args&: IssueOrder[Pair.first]));
808 }
809}
810
811void WindowScheduler::expand() {
812 // The MIs in the SchedResult are sorted by the issue order ID.
813 llvm::stable_sort(Range&: SchedResult,
814 C: [](const std::tuple<MachineInstr *, int, int, int> &A,
815 const std::tuple<MachineInstr *, int, int, int> &B) {
816 return std::get<3>(t: A) < std::get<3>(t: B);
817 });
818 // Use the scheduling infrastructure for expansion, noting that InstrChanges
819 // is not supported here.
820 DenseMap<MachineInstr *, int> Cycles, Stages;
821 std::vector<MachineInstr *> OrderedInsts;
822 for (auto &Info : SchedResult) {
823 auto *MI = std::get<0>(t&: Info);
824 OrderedInsts.push_back(x: MI);
825 Cycles[MI] = std::get<1>(t&: Info);
826 Stages[MI] = std::get<2>(t&: Info);
827 LLVM_DEBUG(dbgs() << "\tCycle " << Cycles[MI] << " [S." << Stages[MI]
828 << "]: " << *MI);
829 }
830 ModuloSchedule MS(*MF, &Loop, std::move(OrderedInsts), std::move(Cycles),
831 std::move(Stages));
832 ModuloScheduleExpander MSE(*MF, MS, *Context->LIS,
833 ModuloScheduleExpander::InstrChangesTy(), MDT);
834 MSE.expand();
835 MSE.cleanup();
836}
837
838void WindowScheduler::updateLiveIntervals() {
839 SmallVector<Register, 128> UsedRegs;
840 for (MachineInstr &MI : *MBB)
841 for (const MachineOperand &MO : MI.operands()) {
842 if (!MO.isReg() || MO.getReg() == 0)
843 continue;
844 Register Reg = MO.getReg();
845 if (!is_contained(Range&: UsedRegs, Element: Reg))
846 UsedRegs.push_back(Elt: Reg);
847 }
848 Context->LIS->repairIntervalsInRange(MBB, Begin: MBB->begin(), End: MBB->end(), OrigRegs: UsedRegs);
849}
850
851iterator_range<MachineBasicBlock::iterator>
852WindowScheduler::getScheduleRange(unsigned Offset, unsigned Num) {
853 auto RegionBegin = MBB->begin();
854 std::advance(i&: RegionBegin, n: Offset);
855 auto RegionEnd = RegionBegin;
856 std::advance(i&: RegionEnd, n: Num);
857 return make_range(x: RegionBegin, y: RegionEnd);
858}
859
860int WindowScheduler::getOriCycle(MachineInstr *NewMI) {
861 assert(TriToOri.count(NewMI) && "Cannot find original MI!");
862 auto *OriMI = TriToOri[NewMI].Ori;
863 assert(OriToCycle.count(OriMI) && "Cannot find schedule cycle!");
864 return OriToCycle[OriMI];
865}
866
867MachineInstr *WindowScheduler::getOriMI(MachineInstr *NewMI) {
868 assert(TriToOri.count(NewMI) && "Cannot find original MI!");
869 return TriToOri[NewMI].Ori;
870}
871
872unsigned WindowScheduler::getOriStage(MachineInstr *OriMI, unsigned Offset) {
873 assert(llvm::is_contained(OriMIs, OriMI) && "Cannot find OriMI in OriMIs!");
874 // If there is no instruction fold, all MI stages are 0.
875 if (Offset == SchedPhiNum)
876 return 0;
877 // For those MIs with an ID less than the Offset, their stages are set to 0,
878 // while the rest are set to 1.
879 unsigned Id = 0;
880 for (auto *MI : OriMIs) {
881 if (MI->isDebugOrPseudoInstr())
882 continue;
883 if (MI == OriMI)
884 break;
885 ++Id;
886 }
887 return Id >= (size_t)Offset ? 1 : 0;
888}
889
890Register WindowScheduler::getAntiRegister(MachineInstr *Phi) {
891 assert(Phi->isPHI() && "Expecting PHI!");
892 Register AntiReg;
893 for (auto MO : Phi->uses()) {
894 if (MO.isReg())
895 AntiReg = MO.getReg();
896 else if (MO.isMBB() && MO.getMBB() == MBB)
897 return AntiReg;
898 }
899 return 0;
900}
901