1//===- ModuloSchedule.cpp - Software pipeline schedule expansion ----------===//
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#include "llvm/CodeGen/ModuloSchedule.h"
10#include "llvm/ADT/StringExtras.h"
11#include "llvm/Analysis/MemoryLocation.h"
12#include "llvm/CodeGen/LiveIntervals.h"
13#include "llvm/CodeGen/MachineBasicBlock.h"
14#include "llvm/CodeGen/MachineInstrBuilder.h"
15#include "llvm/CodeGen/MachineLoopInfo.h"
16#include "llvm/CodeGen/MachineRegisterInfo.h"
17#include "llvm/InitializePasses.h"
18#include "llvm/MC/MCContext.h"
19#include "llvm/Support/Debug.h"
20#include "llvm/Support/ErrorHandling.h"
21#include "llvm/Support/raw_ostream.h"
22
23#define DEBUG_TYPE "pipeliner"
24using namespace llvm;
25
26static cl::opt<bool> SwapBranchTargetsMVE(
27 "pipeliner-swap-branch-targets-mve", cl::Hidden, cl::init(Val: false),
28 cl::desc("Swap target blocks of a conditional branch for MVE expander"));
29
30static void eraseBlock(MachineBasicBlock *MBB, LiveIntervals &LIS,
31 MachineDomTreeUpdater &MDTU) {
32 for (MachineInstr &MI : *MBB)
33 LIS.RemoveMachineInstrFromMaps(MI);
34 MBB->clear();
35
36 SmallVector<MachineDominatorTree::UpdateType, 4> Updates;
37 while (!MBB->succ_empty()) {
38 Updates.push_back(Elt: {MachineDominatorTree::Delete, MBB, *MBB->succ_begin()});
39 MBB->removeSuccessor(I: MBB->succ_begin());
40 }
41
42 MDTU.applyUpdates(Updates);
43 MDTU.deleteBB(DelBB: MBB);
44}
45
46void ModuloSchedule::print(raw_ostream &OS) {
47 for (MachineInstr *MI : ScheduledInstrs)
48 OS << "[stage " << getStage(MI) << " @" << getCycle(MI) << "c] " << *MI;
49}
50
51//===----------------------------------------------------------------------===//
52// ModuloScheduleExpander implementation
53//===----------------------------------------------------------------------===//
54
55/// Return the register values for the operands of a Phi instruction.
56/// This function assume the instruction is a Phi.
57static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
58 Register &InitVal, Register &LoopVal) {
59 assert(Phi.isPHI() && "Expecting a Phi.");
60
61 InitVal = Register();
62 LoopVal = Register();
63 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
64 if (Phi.getOperand(i: i + 1).getMBB() != Loop)
65 InitVal = Phi.getOperand(i).getReg();
66 else
67 LoopVal = Phi.getOperand(i).getReg();
68
69 assert(InitVal && LoopVal && "Unexpected Phi structure.");
70}
71
72/// Return the Phi register value that comes from the incoming block.
73static Register getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
74 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
75 if (Phi.getOperand(i: i + 1).getMBB() != LoopBB)
76 return Phi.getOperand(i).getReg();
77 return Register();
78}
79
80/// Return the Phi register value that comes the loop block.
81static Register getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
82 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
83 if (Phi.getOperand(i: i + 1).getMBB() == LoopBB)
84 return Phi.getOperand(i).getReg();
85 return Register();
86}
87
88void ModuloScheduleExpander::expand() {
89 BB = Schedule.getLoop()->getTopBlock();
90 Preheader = *BB->pred_begin();
91 if (Preheader == BB)
92 Preheader = *std::next(x: BB->pred_begin());
93
94 // Iterate over the definitions in each instruction, and compute the
95 // stage difference for each use. Keep the maximum value.
96 for (MachineInstr *MI : Schedule.getInstructions()) {
97 int DefStage = Schedule.getStage(MI);
98 for (const MachineOperand &Op : MI->all_defs()) {
99 Register Reg = Op.getReg();
100 unsigned MaxDiff = 0;
101 bool PhiIsSwapped = false;
102 for (MachineInstr &UseMI : MRI.use_instructions(Reg)) {
103 int UseStage = Schedule.getStage(MI: &UseMI);
104 unsigned Diff = 0;
105 if (UseStage != -1 && UseStage >= DefStage)
106 Diff = UseStage - DefStage;
107 if (MI->isPHI()) {
108 if (isLoopCarried(Phi&: *MI))
109 ++Diff;
110 else
111 PhiIsSwapped = true;
112 }
113 MaxDiff = std::max(a: Diff, b: MaxDiff);
114 }
115 RegToStageDiff[Reg] = std::make_pair(x&: MaxDiff, y&: PhiIsSwapped);
116 }
117 }
118
119 generatePipelinedLoop();
120}
121
122void ModuloScheduleExpander::generatePipelinedLoop() {
123 LoopInfo = TII->analyzeLoopForPipelining(LoopBB: BB);
124 assert(LoopInfo && "Must be able to analyze loop!");
125
126 // Create a new basic block for the kernel and add it to the CFG.
127 MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB: BB->getBasicBlock());
128
129 unsigned MaxStageCount = Schedule.getNumStages() - 1;
130
131 // Remember the registers that are used in different stages. The index is
132 // the iteration, or stage, that the instruction is scheduled in. This is
133 // a map between register names in the original block and the names created
134 // in each stage of the pipelined loop.
135 ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2];
136
137 // The renaming destination by Phis for the registers across stages.
138 // This map is updated during Phis generation to point to the most recent
139 // renaming destination.
140 ValueMapTy *VRMapPhi = new ValueMapTy[(MaxStageCount + 1) * 2];
141
142 InstrMapTy InstrMap;
143
144 SmallVector<MachineBasicBlock *, 4> PrologBBs;
145
146 // Generate the prolog instructions that set up the pipeline.
147 generateProlog(LastStage: MaxStageCount, KernelBB, VRMap, PrologBBs);
148 MF.insert(MBBI: BB->getIterator(), MBB: KernelBB);
149 LIS.insertMBBInMaps(MBB: KernelBB);
150
151 // Rearrange the instructions to generate the new, pipelined loop,
152 // and update register names as needed.
153 for (MachineInstr *CI : Schedule.getInstructions()) {
154 if (CI->isPHI())
155 continue;
156 unsigned StageNum = Schedule.getStage(MI: CI);
157 MachineInstr *NewMI = cloneInstr(OldMI: CI, CurStageNum: MaxStageCount, InstStageNum: StageNum);
158 updateInstruction(NewMI, LastDef: false, CurStageNum: MaxStageCount, InstrStageNum: StageNum, VRMap);
159 KernelBB->push_back(MI: NewMI);
160 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
161 InstrMap[NewMI] = CI;
162 }
163
164 // Copy any terminator instructions to the new kernel, and update
165 // names as needed.
166 for (MachineInstr &MI : BB->terminators()) {
167 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: &MI);
168 updateInstruction(NewMI, LastDef: false, CurStageNum: MaxStageCount, InstrStageNum: 0, VRMap);
169 KernelBB->push_back(MI: NewMI);
170 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
171 InstrMap[NewMI] = &MI;
172 }
173
174 NewKernel = KernelBB;
175 KernelBB->transferSuccessors(FromMBB: BB);
176 KernelBB->replaceSuccessor(Old: BB, New: KernelBB);
177
178 SmallVector<MachineDominatorTree::UpdateType, 8> Updates = {
179 {MachineDominatorTree::Insert, PrologBBs.back(), KernelBB}};
180 for (MachineBasicBlock *Succ : KernelBB->successors())
181 Updates.push_back(Elt: {MachineDominatorTree::Insert, KernelBB, Succ});
182
183 Updates.push_back(Elt: {MachineDominatorTree::Delete, PrologBBs.back(), BB});
184
185 for (MachineBasicBlock *Succ : KernelBB->successors()) {
186 Updates.push_back(
187 Elt: {MachineDominatorTree::Delete, BB, Succ == KernelBB ? BB : Succ});
188 }
189
190 MDTU.applyUpdates(Updates);
191
192 generateExistingPhis(NewBB: KernelBB, BB1: PrologBBs.back(), BB2: KernelBB, KernelBB, VRMap,
193 VRMapPhi, InstrMap, LastStageNum: MaxStageCount, CurStageNum: MaxStageCount, IsLast: false);
194 generatePhis(NewBB: KernelBB, BB1: PrologBBs.back(), BB2: KernelBB, KernelBB, VRMap, VRMapPhi,
195 InstrMap, LastStageNum: MaxStageCount, CurStageNum: MaxStageCount, IsLast: false);
196
197 LLVM_DEBUG(dbgs() << "New block\n"; KernelBB->dump(););
198
199 SmallVector<MachineBasicBlock *, 4> EpilogBBs;
200 // Generate the epilog instructions to complete the pipeline.
201 generateEpilog(LastStage: MaxStageCount, KernelBB, OrigBB: BB, VRMap, VRMapPhi, EpilogBBs,
202 PrologBBs);
203
204 // We need this step because the register allocation doesn't handle some
205 // situations well, so we insert copies to help out.
206 splitLifetimes(KernelBB, EpilogBBs);
207
208 // Remove dead instructions due to loop induction variables.
209 removeDeadInstructions(KernelBB, EpilogBBs);
210
211 // Add branches between prolog and epilog blocks.
212 addBranches(PreheaderBB&: *Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap);
213
214 delete[] VRMap;
215 delete[] VRMapPhi;
216}
217
218void ModuloScheduleExpander::cleanup() {
219 // Remove the original loop since it's no longer referenced.
220 eraseBlock(MBB: BB, LIS, MDTU);
221}
222
223/// Generate the pipeline prolog code.
224void ModuloScheduleExpander::generateProlog(unsigned LastStage,
225 MachineBasicBlock *KernelBB,
226 ValueMapTy *VRMap,
227 MBBVectorTy &PrologBBs) {
228 MachineBasicBlock *PredBB = Preheader;
229 InstrMapTy InstrMap;
230
231 // Generate a basic block for each stage, not including the last stage,
232 // which will be generated in the kernel. Each basic block may contain
233 // instructions from multiple stages/iterations.
234 for (unsigned i = 0; i < LastStage; ++i) {
235 // Create and insert the prolog basic block prior to the original loop
236 // basic block. The original loop is removed later.
237 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB: BB->getBasicBlock());
238 PrologBBs.push_back(Elt: NewBB);
239 MF.insert(MBBI: BB->getIterator(), MBB: NewBB);
240 NewBB->transferSuccessors(FromMBB: PredBB);
241 PredBB->addSuccessor(Succ: NewBB);
242 MDTU.splitCriticalEdge(FromBB: PredBB, ToBB: BB, NewBB);
243 PredBB = NewBB;
244 LIS.insertMBBInMaps(MBB: NewBB);
245
246 // Generate instructions for each appropriate stage. Process instructions
247 // in original program order.
248 for (int StageNum = i; StageNum >= 0; --StageNum) {
249 for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
250 BBE = BB->getFirstTerminator();
251 BBI != BBE; ++BBI) {
252 if (Schedule.getStage(MI: &*BBI) == StageNum) {
253 if (BBI->isPHI())
254 continue;
255 MachineInstr *NewMI =
256 cloneAndChangeInstr(OldMI: &*BBI, CurStageNum: i, InstStageNum: (unsigned)StageNum);
257 updateInstruction(NewMI, LastDef: false, CurStageNum: i, InstrStageNum: (unsigned)StageNum, VRMap);
258 NewBB->push_back(MI: NewMI);
259 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
260 InstrMap[NewMI] = &*BBI;
261 }
262 }
263 }
264 rewritePhiValues(NewBB, StageNum: i, VRMap, InstrMap);
265 LLVM_DEBUG({
266 dbgs() << "prolog:\n";
267 NewBB->dump();
268 });
269 }
270
271 PredBB->replaceSuccessor(Old: BB, New: KernelBB);
272
273 // Check if we need to remove the branch from the preheader to the original
274 // loop, and replace it with a branch to the new loop.
275 unsigned numBranches = TII->removeBranch(MBB&: *Preheader);
276 if (numBranches) {
277 SmallVector<MachineOperand, 0> Cond;
278 TII->insertBranch(MBB&: *Preheader, TBB: PrologBBs[0], FBB: nullptr, Cond, DL: DebugLoc());
279 }
280}
281
282/// Generate the pipeline epilog code. The epilog code finishes the iterations
283/// that were started in either the prolog or the kernel. We create a basic
284/// block for each stage that needs to complete.
285void ModuloScheduleExpander::generateEpilog(
286 unsigned LastStage, MachineBasicBlock *KernelBB, MachineBasicBlock *OrigBB,
287 ValueMapTy *VRMap, ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,
288 MBBVectorTy &PrologBBs) {
289 // We need to change the branch from the kernel to the first epilog block, so
290 // this call to analyze branch uses the kernel rather than the original BB.
291 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
292 SmallVector<MachineOperand, 4> Cond;
293 bool checkBranch = TII->analyzeBranch(MBB&: *KernelBB, TBB, FBB, Cond);
294 assert(!checkBranch && "generateEpilog must be able to analyze the branch");
295 if (checkBranch)
296 return;
297
298 MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin();
299 if (*LoopExitI == KernelBB)
300 ++LoopExitI;
301 assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor");
302 MachineBasicBlock *LoopExitBB = *LoopExitI;
303
304 MachineBasicBlock *PredBB = KernelBB;
305 MachineBasicBlock *EpilogStart = LoopExitBB;
306 InstrMapTy InstrMap;
307
308 // Generate a basic block for each stage, not including the last stage,
309 // which was generated for the kernel. Each basic block may contain
310 // instructions from multiple stages/iterations.
311 int EpilogStage = LastStage + 1;
312 for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {
313 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock();
314 EpilogBBs.push_back(Elt: NewBB);
315 MF.insert(MBBI: BB->getIterator(), MBB: NewBB);
316
317 PredBB->replaceSuccessor(Old: LoopExitBB, New: NewBB);
318 NewBB->addSuccessor(Succ: LoopExitBB);
319 MDTU.splitCriticalEdge(FromBB: PredBB, ToBB: LoopExitBB, NewBB);
320 LIS.insertMBBInMaps(MBB: NewBB);
321
322 if (EpilogStart == LoopExitBB)
323 EpilogStart = NewBB;
324
325 // Add instructions to the epilog depending on the current block.
326 // Process instructions in original program order.
327 for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) {
328 for (auto &BBI : *BB) {
329 if (BBI.isPHI())
330 continue;
331 MachineInstr *In = &BBI;
332 if ((unsigned)Schedule.getStage(MI: In) == StageNum) {
333 // Instructions with memoperands in the epilog are updated with
334 // conservative values.
335 MachineInstr *NewMI = cloneInstr(OldMI: In, UINT_MAX, InstStageNum: 0);
336 updateInstruction(NewMI, LastDef: i == 1, CurStageNum: EpilogStage, InstrStageNum: 0, VRMap);
337 NewBB->push_back(MI: NewMI);
338 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
339 InstrMap[NewMI] = In;
340 }
341 }
342 }
343 generateExistingPhis(NewBB, BB1: PrologBBs[i - 1], BB2: PredBB, KernelBB, VRMap,
344 VRMapPhi, InstrMap, LastStageNum: LastStage, CurStageNum: EpilogStage, IsLast: i == 1);
345 generatePhis(NewBB, BB1: PrologBBs[i - 1], BB2: PredBB, KernelBB, VRMap, VRMapPhi,
346 InstrMap, LastStageNum: LastStage, CurStageNum: EpilogStage, IsLast: i == 1);
347 PredBB = NewBB;
348
349 LLVM_DEBUG({
350 dbgs() << "epilog:\n";
351 NewBB->dump();
352 });
353 }
354
355 // Fix any Phi nodes in the loop exit block.
356 LoopExitBB->replacePhiUsesWith(Old: BB, New: PredBB);
357
358 // Create a branch to the new epilog from the kernel.
359 // Remove the original branch and add a new branch to the epilog.
360 TII->removeBranch(MBB&: *KernelBB);
361 assert((OrigBB == TBB || OrigBB == FBB) &&
362 "Unable to determine looping branch direction");
363 if (OrigBB != TBB)
364 TII->insertBranch(MBB&: *KernelBB, TBB: EpilogStart, FBB: KernelBB, Cond, DL: DebugLoc());
365 else
366 TII->insertBranch(MBB&: *KernelBB, TBB: KernelBB, FBB: EpilogStart, Cond, DL: DebugLoc());
367 // Add a branch to the loop exit.
368 if (EpilogBBs.size() > 0) {
369 MachineBasicBlock *LastEpilogBB = EpilogBBs.back();
370 SmallVector<MachineOperand, 4> Cond1;
371 TII->insertBranch(MBB&: *LastEpilogBB, TBB: LoopExitBB, FBB: nullptr, Cond: Cond1, DL: DebugLoc());
372 }
373}
374
375/// Replace all uses of FromReg that appear outside the specified
376/// basic block with ToReg.
377static void replaceRegUsesAfterLoop(Register FromReg, Register ToReg,
378 MachineBasicBlock *MBB,
379 MachineRegisterInfo &MRI) {
380 for (MachineOperand &O :
381 llvm::make_early_inc_range(Range: MRI.use_operands(Reg: FromReg)))
382 if (O.getParent()->getParent() != MBB)
383 O.setReg(ToReg);
384}
385
386/// Return true if the register has a use that occurs outside the
387/// specified loop.
388static bool hasUseAfterLoop(Register Reg, MachineBasicBlock *BB,
389 MachineRegisterInfo &MRI) {
390 for (const MachineInstr &UseMI : MRI.use_instructions(Reg))
391 if (UseMI.getParent() != BB)
392 return true;
393 return false;
394}
395
396/// Generate Phis for the specific block in the generated pipelined code.
397/// This function looks at the Phis from the original code to guide the
398/// creation of new Phis.
399void ModuloScheduleExpander::generateExistingPhis(
400 MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
401 MachineBasicBlock *KernelBB, ValueMapTy *VRMap, ValueMapTy *VRMapPhi,
402 InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum,
403 bool IsLast) {
404 // Compute the stage number for the initial value of the Phi, which
405 // comes from the prolog. The prolog to use depends on to which kernel/
406 // epilog that we're adding the Phi.
407 unsigned PrologStage = 0;
408 unsigned PrevStage = 0;
409 bool InKernel = (LastStageNum == CurStageNum);
410 if (InKernel) {
411 PrologStage = LastStageNum - 1;
412 PrevStage = CurStageNum;
413 } else {
414 PrologStage = LastStageNum - (CurStageNum - LastStageNum);
415 PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;
416 }
417
418 for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
419 BBE = BB->getFirstNonPHI();
420 BBI != BBE; ++BBI) {
421 Register Def = BBI->getOperand(i: 0).getReg();
422
423 Register InitVal;
424 Register LoopVal;
425 getPhiRegs(Phi&: *BBI, Loop: BB, InitVal, LoopVal);
426
427 Register PhiOp1;
428 // The Phi value from the loop body typically is defined in the loop, but
429 // not always. So, we need to check if the value is defined in the loop.
430 Register PhiOp2 = LoopVal;
431 if (auto It = VRMap[LastStageNum].find(Val: LoopVal);
432 It != VRMap[LastStageNum].end())
433 PhiOp2 = It->second;
434
435 int StageScheduled = Schedule.getStage(MI: &*BBI);
436 int LoopValStage = Schedule.getStage(MI: MRI.getVRegDef(Reg: LoopVal));
437 unsigned NumStages = getStagesForReg(Reg: Def, CurStage: CurStageNum);
438 if (NumStages == 0) {
439 // We don't need to generate a Phi anymore, but we need to rename any uses
440 // of the Phi value.
441 Register NewReg = VRMap[PrevStage][LoopVal];
442 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum, PhiNum: 0, Phi: &*BBI, OldReg: Def,
443 NewReg: InitVal, PrevReg: NewReg);
444 auto It = VRMap[CurStageNum].find(Val: LoopVal);
445 if (It != VRMap[CurStageNum].end()) {
446 Register Reg = It->second;
447 VRMap[CurStageNum][Def] = Reg;
448 }
449 }
450 // Adjust the number of Phis needed depending on the number of prologs left,
451 // and the distance from where the Phi is first scheduled. The number of
452 // Phis cannot exceed the number of prolog stages. Each stage can
453 // potentially define two values.
454 unsigned MaxPhis = PrologStage + 2;
455 if (!InKernel && (int)PrologStage <= LoopValStage)
456 MaxPhis = std::max(a: (int)MaxPhis - LoopValStage, b: 1);
457 unsigned NumPhis = std::min(a: NumStages, b: MaxPhis);
458
459 Register NewReg;
460 unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;
461 // In the epilog, we may need to look back one stage to get the correct
462 // Phi name, because the epilog and prolog blocks execute the same stage.
463 // The correct name is from the previous block only when the Phi has
464 // been completely scheduled prior to the epilog, and Phi value is not
465 // needed in multiple stages.
466 int StageDiff = 0;
467 if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&
468 NumPhis == 1)
469 StageDiff = 1;
470 // Adjust the computations below when the phi and the loop definition
471 // are scheduled in different stages.
472 if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)
473 StageDiff = StageScheduled - LoopValStage;
474 for (unsigned np = 0; np < NumPhis; ++np) {
475 // If the Phi hasn't been scheduled, then use the initial Phi operand
476 // value. Otherwise, use the scheduled version of the instruction. This
477 // is a little complicated when a Phi references another Phi.
478 if (np > PrologStage || StageScheduled >= (int)LastStageNum)
479 PhiOp1 = InitVal;
480 // Check if the Phi has already been scheduled in a prolog stage.
481 else if (PrologStage >= AccessStage + StageDiff + np &&
482 VRMap[PrologStage - StageDiff - np].count(Val: LoopVal) != 0)
483 PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];
484 // Check if the Phi has already been scheduled, but the loop instruction
485 // is either another Phi, or doesn't occur in the loop.
486 else if (PrologStage >= AccessStage + StageDiff + np) {
487 // If the Phi references another Phi, we need to examine the other
488 // Phi to get the correct value.
489 PhiOp1 = LoopVal;
490 MachineInstr *InstOp1 = MRI.getVRegDef(Reg: PhiOp1);
491 int Indirects = 1;
492 while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) {
493 int PhiStage = Schedule.getStage(MI: InstOp1);
494 if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects)
495 PhiOp1 = getInitPhiReg(Phi&: *InstOp1, LoopBB: BB);
496 else
497 PhiOp1 = getLoopPhiReg(Phi&: *InstOp1, LoopBB: BB);
498 InstOp1 = MRI.getVRegDef(Reg: PhiOp1);
499 int PhiOpStage = Schedule.getStage(MI: InstOp1);
500 int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);
501 if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np) {
502 auto &M = VRMap[PrologStage - StageAdj - Indirects - np];
503 if (auto It = M.find(Val: PhiOp1); It != M.end()) {
504 PhiOp1 = It->second;
505 break;
506 }
507 }
508 ++Indirects;
509 }
510 } else
511 PhiOp1 = InitVal;
512 // If this references a generated Phi in the kernel, get the Phi operand
513 // from the incoming block.
514 if (MachineInstr *InstOp1 = MRI.getVRegDef(Reg: PhiOp1))
515 if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB)
516 PhiOp1 = getInitPhiReg(Phi&: *InstOp1, LoopBB: KernelBB);
517
518 MachineInstr *PhiInst = MRI.getVRegDef(Reg: LoopVal);
519 bool LoopDefIsPhi = PhiInst && PhiInst->isPHI();
520 // In the epilog, a map lookup is needed to get the value from the kernel,
521 // or previous epilog block. How is does this depends on if the
522 // instruction is scheduled in the previous block.
523 if (!InKernel) {
524 int StageDiffAdj = 0;
525 if (LoopValStage != -1 && StageScheduled > LoopValStage)
526 StageDiffAdj = StageScheduled - LoopValStage;
527 // Use the loop value defined in the kernel, unless the kernel
528 // contains the last definition of the Phi.
529 if (np == 0 && PrevStage == LastStageNum &&
530 (StageScheduled != 0 || LoopValStage != 0) &&
531 getMapPhiReg(VRMap, VRMapPhi, StageNum: PrevStage - StageDiffAdj, OldReg: LoopVal))
532 PhiOp2 =
533 getMapPhiReg(VRMap, VRMapPhi, StageNum: PrevStage - StageDiffAdj, OldReg: LoopVal);
534 // Use the value defined by the Phi. We add one because we switch
535 // from looking at the loop value to the Phi definition.
536 else if (np > 0 && PrevStage == LastStageNum &&
537 getMapPhiReg(VRMap, VRMapPhi, StageNum: PrevStage - np + 1, OldReg: Def))
538 PhiOp2 = getMapPhiReg(VRMap, VRMapPhi, StageNum: PrevStage - np + 1, OldReg: Def);
539 // Use the loop value defined in the kernel.
540 else if (static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&
541 getMapPhiReg(VRMap, VRMapPhi, StageNum: PrevStage - StageDiffAdj - np,
542 OldReg: LoopVal))
543 PhiOp2 = getMapPhiReg(VRMap, VRMapPhi, StageNum: PrevStage - StageDiffAdj - np,
544 OldReg: LoopVal);
545 // Use the value defined by the Phi, unless we're generating the first
546 // epilog and the Phi refers to a Phi in a different stage.
547 else if (getMapPhiReg(VRMap, VRMapPhi, StageNum: PrevStage - np, OldReg: Def) &&
548 (!LoopDefIsPhi || (PrevStage != LastStageNum) ||
549 (LoopValStage == StageScheduled)))
550 PhiOp2 = getMapPhiReg(VRMap, VRMapPhi, StageNum: PrevStage - np, OldReg: Def);
551 }
552
553 // Check if we can reuse an existing Phi. This occurs when a Phi
554 // references another Phi, and the other Phi is scheduled in an
555 // earlier stage. We can try to reuse an existing Phi up until the last
556 // stage of the current Phi.
557 if (LoopDefIsPhi) {
558 if (static_cast<int>(PrologStage - np) >= StageScheduled) {
559 int LVNumStages = getStagesForPhi(Reg: LoopVal);
560 int StageDiff = (StageScheduled - LoopValStage);
561 LVNumStages -= StageDiff;
562 // Make sure the loop value Phi has been processed already.
563 if (LVNumStages > (int)np && VRMap[CurStageNum].count(Val: LoopVal)) {
564 NewReg = PhiOp2;
565 unsigned ReuseStage = CurStageNum;
566 if (isLoopCarried(Phi&: *PhiInst))
567 ReuseStage -= LVNumStages;
568 // Check if the Phi to reuse has been generated yet. If not, then
569 // there is nothing to reuse.
570 if (VRMap[ReuseStage - np].count(Val: LoopVal)) {
571 NewReg = VRMap[ReuseStage - np][LoopVal];
572
573 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum, PhiNum: np, Phi: &*BBI,
574 OldReg: Def, NewReg);
575 // Update the map with the new Phi name.
576 VRMap[CurStageNum - np][Def] = NewReg;
577 PhiOp2 = NewReg;
578 if (VRMap[LastStageNum - np - 1].count(Val: LoopVal))
579 PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];
580
581 if (IsLast && np == NumPhis - 1)
582 replaceRegUsesAfterLoop(FromReg: Def, ToReg: NewReg, MBB: BB, MRI);
583 continue;
584 }
585 }
586 }
587 if (InKernel && StageDiff > 0 &&
588 VRMap[CurStageNum - StageDiff - np].count(Val: LoopVal))
589 PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];
590 }
591
592 const TargetRegisterClass *RC = MRI.getRegClass(Reg: Def);
593 NewReg = MRI.createVirtualRegister(RegClass: RC);
594
595 MachineInstrBuilder NewPhi =
596 BuildMI(BB&: *NewBB, I: NewBB->getFirstNonPHI(), MIMD: DebugLoc(),
597 MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: NewReg);
598 NewPhi.addReg(RegNo: PhiOp1).addMBB(MBB: BB1);
599 NewPhi.addReg(RegNo: PhiOp2).addMBB(MBB: BB2);
600 LIS.InsertMachineInstrInMaps(MI&: *NewPhi);
601 if (np == 0)
602 InstrMap[NewPhi] = &*BBI;
603
604 // We define the Phis after creating the new pipelined code, so
605 // we need to rename the Phi values in scheduled instructions.
606
607 Register PrevReg;
608 if (InKernel && VRMap[PrevStage - np].count(Val: LoopVal))
609 PrevReg = VRMap[PrevStage - np][LoopVal];
610 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum, PhiNum: np, Phi: &*BBI, OldReg: Def,
611 NewReg, PrevReg);
612 // If the Phi has been scheduled, use the new name for rewriting.
613 if (VRMap[CurStageNum - np].count(Val: Def)) {
614 Register R = VRMap[CurStageNum - np][Def];
615 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum, PhiNum: np, Phi: &*BBI, OldReg: R,
616 NewReg);
617 }
618
619 // Check if we need to rename any uses that occurs after the loop. The
620 // register to replace depends on whether the Phi is scheduled in the
621 // epilog.
622 if (IsLast && np == NumPhis - 1)
623 replaceRegUsesAfterLoop(FromReg: Def, ToReg: NewReg, MBB: BB, MRI);
624
625 // In the kernel, a dependent Phi uses the value from this Phi.
626 if (InKernel)
627 PhiOp2 = NewReg;
628
629 // Update the map with the new Phi name.
630 VRMap[CurStageNum - np][Def] = NewReg;
631 }
632
633 while (NumPhis++ < NumStages) {
634 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum, PhiNum: NumPhis, Phi: &*BBI, OldReg: Def,
635 NewReg, PrevReg: 0);
636 }
637
638 // Check if we need to rename a Phi that has been eliminated due to
639 // scheduling.
640 if (NumStages == 0 && IsLast) {
641 auto &CurStageMap = VRMap[CurStageNum];
642 auto It = CurStageMap.find(Val: LoopVal);
643 if (It != CurStageMap.end())
644 replaceRegUsesAfterLoop(FromReg: Def, ToReg: It->second, MBB: BB, MRI);
645 }
646 }
647}
648
649/// Generate Phis for the specified block in the generated pipelined code.
650/// These are new Phis needed because the definition is scheduled after the
651/// use in the pipelined sequence.
652void ModuloScheduleExpander::generatePhis(
653 MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
654 MachineBasicBlock *KernelBB, ValueMapTy *VRMap, ValueMapTy *VRMapPhi,
655 InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum,
656 bool IsLast) {
657 // Compute the stage number that contains the initial Phi value, and
658 // the Phi from the previous stage.
659 unsigned PrologStage = 0;
660 unsigned PrevStage = 0;
661 unsigned StageDiff = CurStageNum - LastStageNum;
662 bool InKernel = (StageDiff == 0);
663 if (InKernel) {
664 PrologStage = LastStageNum - 1;
665 PrevStage = CurStageNum;
666 } else {
667 PrologStage = LastStageNum - StageDiff;
668 PrevStage = LastStageNum + StageDiff - 1;
669 }
670
671 for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(),
672 BBE = BB->instr_end();
673 BBI != BBE; ++BBI) {
674 for (unsigned i = 0, e = BBI->getNumOperands(); i != e; ++i) {
675 MachineOperand &MO = BBI->getOperand(i);
676 if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
677 continue;
678
679 int StageScheduled = Schedule.getStage(MI: &*BBI);
680 assert(StageScheduled != -1 && "Expecting scheduled instruction.");
681 Register Def = MO.getReg();
682 unsigned NumPhis = getStagesForReg(Reg: Def, CurStage: CurStageNum);
683 // An instruction scheduled in stage 0 and is used after the loop
684 // requires a phi in the epilog for the last definition from either
685 // the kernel or prolog.
686 if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&
687 hasUseAfterLoop(Reg: Def, BB, MRI))
688 NumPhis = 1;
689 if (!InKernel && (unsigned)StageScheduled > PrologStage)
690 continue;
691
692 Register PhiOp2;
693 if (InKernel) {
694 PhiOp2 = VRMap[PrevStage][Def];
695 if (MachineInstr *InstOp2 = MRI.getVRegDef(Reg: PhiOp2))
696 if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)
697 PhiOp2 = getLoopPhiReg(Phi&: *InstOp2, LoopBB: BB2);
698 }
699 // The number of Phis can't exceed the number of prolog stages. The
700 // prolog stage number is zero based.
701 if (NumPhis > PrologStage + 1 - StageScheduled)
702 NumPhis = PrologStage + 1 - StageScheduled;
703 for (unsigned np = 0; np < NumPhis; ++np) {
704 // Example for
705 // Org:
706 // %Org = ... (Scheduled at Stage#0, NumPhi = 2)
707 //
708 // Prolog0 (Stage0):
709 // %Clone0 = ...
710 // Prolog1 (Stage1):
711 // %Clone1 = ...
712 // Kernel (Stage2):
713 // %Phi0 = Phi %Clone1, Prolog1, %Clone2, Kernel
714 // %Phi1 = Phi %Clone0, Prolog1, %Phi0, Kernel
715 // %Clone2 = ...
716 // Epilog0 (Stage3):
717 // %Phi2 = Phi %Clone1, Prolog1, %Clone2, Kernel
718 // %Phi3 = Phi %Clone0, Prolog1, %Phi0, Kernel
719 // Epilog1 (Stage4):
720 // %Phi4 = Phi %Clone0, Prolog0, %Phi2, Epilog0
721 //
722 // VRMap = {0: %Clone0, 1: %Clone1, 2: %Clone2}
723 // VRMapPhi (after Kernel) = {0: %Phi1, 1: %Phi0}
724 // VRMapPhi (after Epilog0) = {0: %Phi3, 1: %Phi2}
725
726 Register PhiOp1 = VRMap[PrologStage][Def];
727 if (np <= PrologStage)
728 PhiOp1 = VRMap[PrologStage - np][Def];
729 if (!InKernel) {
730 if (PrevStage == LastStageNum && np == 0)
731 PhiOp2 = VRMap[LastStageNum][Def];
732 else
733 PhiOp2 = VRMapPhi[PrevStage - np][Def];
734 }
735
736 const TargetRegisterClass *RC = MRI.getRegClass(Reg: Def);
737 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
738
739 MachineInstrBuilder NewPhi =
740 BuildMI(BB&: *NewBB, I: NewBB->getFirstNonPHI(), MIMD: DebugLoc(),
741 MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: NewReg);
742 NewPhi.addReg(RegNo: PhiOp1).addMBB(MBB: BB1);
743 NewPhi.addReg(RegNo: PhiOp2).addMBB(MBB: BB2);
744 LIS.InsertMachineInstrInMaps(MI&: *NewPhi);
745 if (np == 0)
746 InstrMap[NewPhi] = &*BBI;
747
748 // Rewrite uses and update the map. The actions depend upon whether
749 // we generating code for the kernel or epilog blocks.
750 if (InKernel) {
751 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum, PhiNum: np, Phi: &*BBI, OldReg: PhiOp1,
752 NewReg);
753 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum, PhiNum: np, Phi: &*BBI, OldReg: PhiOp2,
754 NewReg);
755
756 PhiOp2 = NewReg;
757 VRMapPhi[PrevStage - np - 1][Def] = NewReg;
758 } else {
759 VRMapPhi[CurStageNum - np][Def] = NewReg;
760 if (np == NumPhis - 1)
761 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum, PhiNum: np, Phi: &*BBI, OldReg: Def,
762 NewReg);
763 }
764 if (IsLast && np == NumPhis - 1)
765 replaceRegUsesAfterLoop(FromReg: Def, ToReg: NewReg, MBB: BB, MRI);
766 }
767 }
768 }
769}
770
771/// Remove instructions that generate values with no uses.
772/// Typically, these are induction variable operations that generate values
773/// used in the loop itself. A dead instruction has a definition with
774/// no uses, or uses that occur in the original loop only.
775void ModuloScheduleExpander::removeDeadInstructions(MachineBasicBlock *KernelBB,
776 MBBVectorTy &EpilogBBs) {
777 // For each epilog block, check that the value defined by each instruction
778 // is used. If not, delete it.
779 for (MachineBasicBlock *MBB : llvm::reverse(C&: EpilogBBs))
780 for (MachineBasicBlock::reverse_instr_iterator MI = MBB->instr_rbegin(),
781 ME = MBB->instr_rend();
782 MI != ME;) {
783 // From DeadMachineInstructionElem. Don't delete inline assembly.
784 if (MI->isInlineAsm()) {
785 ++MI;
786 continue;
787 }
788 bool SawStore = false;
789 // Check if it's safe to remove the instruction due to side effects.
790 // We can, and want to, remove Phis here.
791 if (!MI->isSafeToMove(SawStore) && !MI->isPHI()) {
792 ++MI;
793 continue;
794 }
795 bool used = true;
796 for (const MachineOperand &MO : MI->all_defs()) {
797 Register reg = MO.getReg();
798 // Assume physical registers are used, unless they are marked dead.
799 if (reg.isPhysical()) {
800 used = !MO.isDead();
801 if (used)
802 break;
803 continue;
804 }
805 unsigned realUses = 0;
806 for (const MachineInstr &UseMI : MRI.use_instructions(Reg: reg)) {
807 // Check if there are any uses that occur only in the original
808 // loop. If so, that's not a real use.
809 if (UseMI.getParent() != BB) {
810 realUses++;
811 used = true;
812 break;
813 }
814 }
815 if (realUses > 0)
816 break;
817 used = false;
818 }
819 if (!used) {
820 LIS.RemoveMachineInstrFromMaps(MI&: *MI);
821 MI++->eraseFromParent();
822 continue;
823 }
824 ++MI;
825 }
826 // In the kernel block, check if we can remove a Phi that generates a value
827 // used in an instruction removed in the epilog block.
828 for (MachineInstr &MI : llvm::make_early_inc_range(Range: KernelBB->phis())) {
829 Register reg = MI.getOperand(i: 0).getReg();
830 if (MRI.use_begin(RegNo: reg) == MRI.use_end()) {
831 LIS.RemoveMachineInstrFromMaps(MI);
832 MI.eraseFromParent();
833 }
834 }
835}
836
837/// For loop carried definitions, we split the lifetime of a virtual register
838/// that has uses past the definition in the next iteration. A copy with a new
839/// virtual register is inserted before the definition, which helps with
840/// generating a better register assignment.
841///
842/// v1 = phi(a, v2) v1 = phi(a, v2)
843/// v2 = phi(b, v3) v2 = phi(b, v3)
844/// v3 = .. v4 = copy v1
845/// .. = V1 v3 = ..
846/// .. = v4
847void ModuloScheduleExpander::splitLifetimes(MachineBasicBlock *KernelBB,
848 MBBVectorTy &EpilogBBs) {
849 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
850 for (auto &PHI : KernelBB->phis()) {
851 Register Def = PHI.getOperand(i: 0).getReg();
852 // Check for any Phi definition that used as an operand of another Phi
853 // in the same block.
854 for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(RegNo: Def),
855 E = MRI.use_instr_end();
856 I != E; ++I) {
857 if (I->isPHI() && I->getParent() == KernelBB) {
858 // Get the loop carried definition.
859 Register LCDef = getLoopPhiReg(Phi&: PHI, LoopBB: KernelBB);
860 if (!LCDef)
861 continue;
862 MachineInstr *MI = MRI.getVRegDef(Reg: LCDef);
863 if (!MI || MI->getParent() != KernelBB || MI->isPHI())
864 continue;
865 // Search through the rest of the block looking for uses of the Phi
866 // definition. If one occurs, then split the lifetime.
867 Register SplitReg;
868 for (auto &BBJ : make_range(x: MachineBasicBlock::instr_iterator(MI),
869 y: KernelBB->instr_end()))
870 if (BBJ.readsRegister(Reg: Def, /*TRI=*/nullptr)) {
871 // We split the lifetime when we find the first use.
872 if (!SplitReg) {
873 SplitReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: Def));
874 MachineInstr *newCopy =
875 BuildMI(BB&: *KernelBB, I: MI, MIMD: MI->getDebugLoc(),
876 MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: SplitReg)
877 .addReg(RegNo: Def);
878 LIS.InsertMachineInstrInMaps(MI&: *newCopy);
879 }
880 BBJ.substituteRegister(FromReg: Def, ToReg: SplitReg, SubIdx: 0, RegInfo: *TRI);
881 }
882 if (!SplitReg)
883 continue;
884 // Search through each of the epilog blocks for any uses to be renamed.
885 for (auto &Epilog : EpilogBBs)
886 for (auto &I : *Epilog)
887 if (I.readsRegister(Reg: Def, /*TRI=*/nullptr))
888 I.substituteRegister(FromReg: Def, ToReg: SplitReg, SubIdx: 0, RegInfo: *TRI);
889 break;
890 }
891 }
892 }
893}
894
895/// Create branches from each prolog basic block to the appropriate epilog
896/// block. These edges are needed if the loop ends before reaching the
897/// kernel.
898void ModuloScheduleExpander::addBranches(MachineBasicBlock &PreheaderBB,
899 MBBVectorTy &PrologBBs,
900 MachineBasicBlock *KernelBB,
901 MBBVectorTy &EpilogBBs,
902 ValueMapTy *VRMap) {
903 assert(PrologBBs.size() == EpilogBBs.size() && "Prolog/Epilog mismatch");
904 MachineBasicBlock *LastPro = KernelBB;
905 MachineBasicBlock *LastEpi = KernelBB;
906
907 // Start from the blocks connected to the kernel and work "out"
908 // to the first prolog and the last epilog blocks.
909 unsigned MaxIter = PrologBBs.size() - 1;
910 for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) {
911 // Add branches to the prolog that go to the corresponding
912 // epilog, and the fall-thru prolog/kernel block.
913 MachineBasicBlock *Prolog = PrologBBs[j];
914 MachineBasicBlock *Epilog = EpilogBBs[i];
915
916 SmallVector<MachineOperand, 4> Cond;
917 std::optional<bool> StaticallyGreater =
918 LoopInfo->createTripCountGreaterCondition(TC: j + 1, MBB&: *Prolog, Cond);
919 unsigned numAdded = 0;
920 if (!StaticallyGreater) {
921 Prolog->addSuccessor(Succ: Epilog);
922 MDTU.applyUpdates(Updates: {{MachineDominatorTree::Insert, Prolog, Epilog}});
923 numAdded = TII->insertBranch(MBB&: *Prolog, TBB: Epilog, FBB: LastPro, Cond, DL: DebugLoc());
924 } else if (*StaticallyGreater == false) {
925 Prolog->addSuccessor(Succ: Epilog);
926 Prolog->removeSuccessor(Succ: LastPro);
927 LastEpi->removeSuccessor(Succ: Epilog);
928 MDTU.applyUpdates(Updates: {{MachineDominatorTree::Insert, Prolog, Epilog},
929 {MachineDominatorTree::Delete, Prolog, LastPro},
930 {MachineDominatorTree::Delete, LastEpi, Epilog}});
931 numAdded = TII->insertBranch(MBB&: *Prolog, TBB: Epilog, FBB: nullptr, Cond, DL: DebugLoc());
932 Epilog->removePHIsIncomingValuesForPredecessor(PredMBB: *LastEpi);
933 // Remove the blocks that are no longer referenced.
934 if (LastPro == KernelBB) {
935 LoopInfo->disposed(LIS: &LIS);
936 NewKernel = nullptr;
937 }
938 eraseBlock(MBB: LastPro, LIS, MDTU);
939 if (LastPro != LastEpi)
940 eraseBlock(MBB: LastEpi, LIS, MDTU);
941 } else {
942 numAdded = TII->insertBranch(MBB&: *Prolog, TBB: LastPro, FBB: nullptr, Cond, DL: DebugLoc());
943 Epilog->removePHIsIncomingValuesForPredecessor(PredMBB: *Prolog);
944 }
945 LastPro = Prolog;
946 LastEpi = Epilog;
947 for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(),
948 E = Prolog->instr_rend();
949 I != E && numAdded > 0; ++I, --numAdded)
950 updateInstruction(NewMI: &*I, LastDef: false, CurStageNum: j, InstrStageNum: 0, VRMap);
951 }
952
953 if (NewKernel) {
954 LoopInfo->setPreheader(PrologBBs[MaxIter]);
955 LoopInfo->adjustTripCount(TripCountAdjust: -(MaxIter + 1));
956 }
957}
958
959/// Return true if we can compute the amount the instruction changes
960/// during each iteration. Set Delta to the amount of the change.
961bool ModuloScheduleExpander::computeDelta(MachineInstr &MI, unsigned &Delta) {
962 const MachineOperand *BaseOp;
963 int64_t Offset;
964 bool OffsetIsScalable;
965 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable))
966 return false;
967
968 // FIXME: This algorithm assumes instructions have fixed-size offsets.
969 if (OffsetIsScalable)
970 return false;
971
972 if (!BaseOp->isReg())
973 return false;
974
975 Register BaseReg = BaseOp->getReg();
976 if (!BaseReg.isVirtual())
977 return false;
978
979 MachineRegisterInfo &MRI = MF.getRegInfo();
980 // Check if there is a Phi. If so, get the definition in the loop.
981 MachineInstr *BaseDef = MRI.getVRegDef(Reg: BaseReg);
982 if (BaseDef && BaseDef->isPHI()) {
983 BaseReg = getLoopPhiReg(Phi&: *BaseDef, LoopBB: MI.getParent());
984 BaseDef = MRI.getVRegDef(Reg: BaseReg);
985 }
986 if (!BaseDef)
987 return false;
988
989 int D = 0;
990 if (!TII->getIncrementValue(MI: *BaseDef, Value&: D) && D >= 0)
991 return false;
992
993 Delta = D;
994 return true;
995}
996
997/// Update the memory operand with a new offset when the pipeliner
998/// generates a new copy of the instruction that refers to a
999/// different memory location.
1000void ModuloScheduleExpander::updateMemOperands(MachineInstr &NewMI,
1001 MachineInstr &OldMI,
1002 unsigned Num) {
1003 if (Num == 0)
1004 return;
1005 // If the instruction has memory operands, then adjust the offset
1006 // when the instruction appears in different stages.
1007 if (NewMI.memoperands_empty())
1008 return;
1009 SmallVector<MachineMemOperand *, 2> NewMMOs;
1010 for (MachineMemOperand *MMO : NewMI.memoperands()) {
1011 // TODO: Figure out whether isAtomic is really necessary (see D57601).
1012 if (MMO->isVolatile() || MMO->isAtomic() ||
1013 (MMO->isInvariant() && MMO->isDereferenceable()) ||
1014 (!MMO->getValue())) {
1015 NewMMOs.push_back(Elt: MMO);
1016 continue;
1017 }
1018 unsigned Delta;
1019 if (Num != UINT_MAX && computeDelta(MI&: OldMI, Delta)) {
1020 int64_t AdjOffset = static_cast<int64_t>(Delta) * Num;
1021 NewMMOs.push_back(
1022 Elt: MF.getMachineMemOperand(MMO, Offset: AdjOffset, Size: MMO->getSize()));
1023 } else {
1024 NewMMOs.push_back(Elt: MF.getMachineMemOperand(
1025 MMO, Offset: 0, Size: LocationSize::beforeOrAfterPointer()));
1026 }
1027 }
1028 NewMI.setMemRefs(MF, MemRefs: NewMMOs);
1029}
1030
1031/// Clone the instruction for the new pipelined loop and update the
1032/// memory operands, if needed.
1033MachineInstr *ModuloScheduleExpander::cloneInstr(MachineInstr *OldMI,
1034 unsigned CurStageNum,
1035 unsigned InstStageNum) {
1036 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: OldMI);
1037 updateMemOperands(NewMI&: *NewMI, OldMI&: *OldMI, Num: CurStageNum - InstStageNum);
1038 return NewMI;
1039}
1040
1041/// Clone the instruction for the new pipelined loop. If needed, this
1042/// function updates the instruction using the values saved in the
1043/// InstrChanges structure.
1044MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
1045 MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum) {
1046 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: OldMI);
1047 auto It = InstrChanges.find(Val: OldMI);
1048 if (It != InstrChanges.end()) {
1049 std::pair<Register, int64_t> RegAndOffset = It->second;
1050 unsigned BasePos, OffsetPos;
1051 if (!TII->getBaseAndOffsetPosition(MI: *OldMI, BasePos, OffsetPos))
1052 return nullptr;
1053 int64_t NewOffset = OldMI->getOperand(i: OffsetPos).getImm();
1054 MachineInstr *LoopDef = findDefInLoop(Reg: RegAndOffset.first);
1055 if (Schedule.getStage(MI: LoopDef) > (signed)InstStageNum)
1056 NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
1057 NewMI->getOperand(i: OffsetPos).setImm(NewOffset);
1058 }
1059 updateMemOperands(NewMI&: *NewMI, OldMI&: *OldMI, Num: CurStageNum - InstStageNum);
1060 return NewMI;
1061}
1062
1063/// Update the machine instruction with new virtual registers. This
1064/// function may change the definitions and/or uses.
1065void ModuloScheduleExpander::updateInstruction(MachineInstr *NewMI,
1066 bool LastDef,
1067 unsigned CurStageNum,
1068 unsigned InstrStageNum,
1069 ValueMapTy *VRMap) {
1070 for (MachineOperand &MO : NewMI->operands()) {
1071 if (!MO.isReg() || !MO.getReg().isVirtual())
1072 continue;
1073 Register reg = MO.getReg();
1074 if (MO.isDef()) {
1075 // Create a new virtual register for the definition.
1076 const TargetRegisterClass *RC = MRI.getRegClass(Reg: reg);
1077 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
1078 MO.setReg(NewReg);
1079 VRMap[CurStageNum][reg] = NewReg;
1080 if (LastDef)
1081 replaceRegUsesAfterLoop(FromReg: reg, ToReg: NewReg, MBB: BB, MRI);
1082 } else if (MO.isUse()) {
1083 MachineInstr *Def = MRI.getVRegDef(Reg: reg);
1084 // Compute the stage that contains the last definition for instruction.
1085 int DefStageNum = Schedule.getStage(MI: Def);
1086 unsigned StageNum = CurStageNum;
1087 if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) {
1088 // Compute the difference in stages between the defintion and the use.
1089 unsigned StageDiff = (InstrStageNum - DefStageNum);
1090 // Make an adjustment to get the last definition.
1091 StageNum -= StageDiff;
1092 }
1093 if (auto It = VRMap[StageNum].find(Val: reg); It != VRMap[StageNum].end())
1094 MO.setReg(It->second);
1095 }
1096 }
1097}
1098
1099/// Return the instruction in the loop that defines the register.
1100/// If the definition is a Phi, then follow the Phi operand to
1101/// the instruction in the loop.
1102MachineInstr *ModuloScheduleExpander::findDefInLoop(Register Reg) {
1103 SmallPtrSet<MachineInstr *, 8> Visited;
1104 MachineInstr *Def = MRI.getVRegDef(Reg);
1105 while (Def->isPHI()) {
1106 if (!Visited.insert(Ptr: Def).second)
1107 break;
1108 for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
1109 if (Def->getOperand(i: i + 1).getMBB() == BB) {
1110 Def = MRI.getVRegDef(Reg: Def->getOperand(i).getReg());
1111 break;
1112 }
1113 }
1114 return Def;
1115}
1116
1117/// Return the new name for the value from the previous stage.
1118Register ModuloScheduleExpander::getPrevMapVal(
1119 unsigned StageNum, unsigned PhiStage, Register LoopVal, unsigned LoopStage,
1120 ValueMapTy *VRMap, MachineBasicBlock *BB) {
1121 Register PrevVal;
1122 if (StageNum > PhiStage) {
1123 MachineInstr *LoopInst = MRI.getVRegDef(Reg: LoopVal);
1124 if (PhiStage == LoopStage && VRMap[StageNum - 1].count(Val: LoopVal))
1125 // The name is defined in the previous stage.
1126 PrevVal = VRMap[StageNum - 1][LoopVal];
1127 else if (VRMap[StageNum].count(Val: LoopVal))
1128 // The previous name is defined in the current stage when the instruction
1129 // order is swapped.
1130 PrevVal = VRMap[StageNum][LoopVal];
1131 else if (!LoopInst->isPHI() || LoopInst->getParent() != BB)
1132 // The loop value hasn't yet been scheduled.
1133 PrevVal = LoopVal;
1134 else if (StageNum == PhiStage + 1)
1135 // The loop value is another phi, which has not been scheduled.
1136 PrevVal = getInitPhiReg(Phi&: *LoopInst, LoopBB: BB);
1137 else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB)
1138 // The loop value is another phi, which has been scheduled.
1139 PrevVal =
1140 getPrevMapVal(StageNum: StageNum - 1, PhiStage, LoopVal: getLoopPhiReg(Phi&: *LoopInst, LoopBB: BB),
1141 LoopStage, VRMap, BB);
1142 }
1143 return PrevVal;
1144}
1145
1146/// Rewrite the Phi values in the specified block to use the mappings
1147/// from the initial operand. Once the Phi is scheduled, we switch
1148/// to using the loop value instead of the Phi value, so those names
1149/// do not need to be rewritten.
1150void ModuloScheduleExpander::rewritePhiValues(MachineBasicBlock *NewBB,
1151 unsigned StageNum,
1152 ValueMapTy *VRMap,
1153 InstrMapTy &InstrMap) {
1154 for (auto &PHI : BB->phis()) {
1155 Register InitVal;
1156 Register LoopVal;
1157 getPhiRegs(Phi&: PHI, Loop: BB, InitVal, LoopVal);
1158 Register PhiDef = PHI.getOperand(i: 0).getReg();
1159
1160 unsigned PhiStage = (unsigned)Schedule.getStage(MI: MRI.getVRegDef(Reg: PhiDef));
1161 unsigned LoopStage = (unsigned)Schedule.getStage(MI: MRI.getVRegDef(Reg: LoopVal));
1162 unsigned NumPhis = getStagesForPhi(Reg: PhiDef);
1163 if (NumPhis > StageNum)
1164 NumPhis = StageNum;
1165 for (unsigned np = 0; np <= NumPhis; ++np) {
1166 Register NewVal =
1167 getPrevMapVal(StageNum: StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
1168 if (!NewVal)
1169 NewVal = InitVal;
1170 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum: StageNum - np, PhiNum: np, Phi: &PHI, OldReg: PhiDef,
1171 NewReg: NewVal);
1172 }
1173 }
1174}
1175
1176/// Rewrite a previously scheduled instruction to use the register value
1177/// from the new instruction. Make sure the instruction occurs in the
1178/// basic block, and we don't change the uses in the new instruction.
1179void ModuloScheduleExpander::rewriteScheduledInstr(
1180 MachineBasicBlock *BB, InstrMapTy &InstrMap, unsigned CurStageNum,
1181 unsigned PhiNum, MachineInstr *Phi, Register OldReg, Register NewReg,
1182 Register PrevReg) {
1183 bool InProlog = (CurStageNum < (unsigned)Schedule.getNumStages() - 1);
1184 int StagePhi = Schedule.getStage(MI: Phi) + PhiNum;
1185 // Rewrite uses that have been scheduled already to use the new
1186 // Phi register.
1187 for (MachineOperand &UseOp :
1188 llvm::make_early_inc_range(Range: MRI.use_operands(Reg: OldReg))) {
1189 MachineInstr *UseMI = UseOp.getParent();
1190 if (UseMI->getParent() != BB)
1191 continue;
1192 if (UseMI->isPHI()) {
1193 if (!Phi->isPHI() && UseMI->getOperand(i: 0).getReg() == NewReg)
1194 continue;
1195 if (getLoopPhiReg(Phi&: *UseMI, LoopBB: BB) != OldReg)
1196 continue;
1197 }
1198 InstrMapTy::iterator OrigInstr = InstrMap.find(Val: UseMI);
1199 assert(OrigInstr != InstrMap.end() && "Instruction not scheduled.");
1200 MachineInstr *OrigMI = OrigInstr->second;
1201 int StageSched = Schedule.getStage(MI: OrigMI);
1202 int CycleSched = Schedule.getCycle(MI: OrigMI);
1203 Register ReplaceReg;
1204 // This is the stage for the scheduled instruction.
1205 if (StagePhi == StageSched && Phi->isPHI()) {
1206 int CyclePhi = Schedule.getCycle(MI: Phi);
1207 if (PrevReg && InProlog)
1208 ReplaceReg = PrevReg;
1209 else if (PrevReg && !isLoopCarried(Phi&: *Phi) &&
1210 (CyclePhi <= CycleSched || OrigMI->isPHI()))
1211 ReplaceReg = PrevReg;
1212 else
1213 ReplaceReg = NewReg;
1214 }
1215 // The scheduled instruction occurs before the scheduled Phi, and the
1216 // Phi is not loop carried.
1217 if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(Phi&: *Phi))
1218 ReplaceReg = NewReg;
1219 if (StagePhi > StageSched && Phi->isPHI())
1220 ReplaceReg = NewReg;
1221 if (!InProlog && !Phi->isPHI() && StagePhi < StageSched)
1222 ReplaceReg = NewReg;
1223 if (ReplaceReg) {
1224 const TargetRegisterClass *NRC =
1225 MRI.constrainRegClass(Reg: ReplaceReg, RC: MRI.getRegClass(Reg: OldReg));
1226 if (NRC)
1227 UseOp.setReg(ReplaceReg);
1228 else {
1229 Register SplitReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OldReg));
1230 MachineInstr *newCopy = BuildMI(BB&: *BB, I: UseMI, MIMD: UseMI->getDebugLoc(),
1231 MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: SplitReg)
1232 .addReg(RegNo: ReplaceReg);
1233 UseOp.setReg(SplitReg);
1234 LIS.InsertMachineInstrInMaps(MI&: *newCopy);
1235 }
1236 }
1237 }
1238}
1239
1240bool ModuloScheduleExpander::isLoopCarried(MachineInstr &Phi) {
1241 if (!Phi.isPHI())
1242 return false;
1243 int DefCycle = Schedule.getCycle(MI: &Phi);
1244 int DefStage = Schedule.getStage(MI: &Phi);
1245
1246 Register InitVal;
1247 Register LoopVal;
1248 getPhiRegs(Phi, Loop: Phi.getParent(), InitVal, LoopVal);
1249 MachineInstr *Use = MRI.getVRegDef(Reg: LoopVal);
1250 if (!Use || Use->isPHI())
1251 return true;
1252 int LoopCycle = Schedule.getCycle(MI: Use);
1253 int LoopStage = Schedule.getStage(MI: Use);
1254 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
1255}
1256
1257//===----------------------------------------------------------------------===//
1258// PeelingModuloScheduleExpander implementation
1259//===----------------------------------------------------------------------===//
1260// This is a reimplementation of ModuloScheduleExpander that works by creating
1261// a fully correct steady-state kernel and peeling off the prolog and epilogs.
1262//===----------------------------------------------------------------------===//
1263
1264namespace {
1265// Remove any dead phis in MBB. Dead phis either have only one block as input
1266// (in which case they are the identity) or have no uses.
1267void EliminateDeadPhis(MachineBasicBlock *MBB, MachineRegisterInfo &MRI,
1268 LiveIntervals *LIS, bool KeepSingleSrcPhi = false) {
1269 bool Changed = true;
1270 while (Changed) {
1271 Changed = false;
1272 for (MachineInstr &MI : llvm::make_early_inc_range(Range: MBB->phis())) {
1273 assert(MI.isPHI());
1274 if (MRI.use_empty(RegNo: MI.getOperand(i: 0).getReg())) {
1275 if (LIS)
1276 LIS->RemoveMachineInstrFromMaps(MI);
1277 MI.eraseFromParent();
1278 Changed = true;
1279 } else if (!KeepSingleSrcPhi && MI.getNumExplicitOperands() == 3) {
1280 const TargetRegisterClass *ConstrainRegClass =
1281 MRI.constrainRegClass(Reg: MI.getOperand(i: 1).getReg(),
1282 RC: MRI.getRegClass(Reg: MI.getOperand(i: 0).getReg()));
1283 assert(ConstrainRegClass &&
1284 "Expected a valid constrained register class!");
1285 (void)ConstrainRegClass;
1286 MRI.replaceRegWith(FromReg: MI.getOperand(i: 0).getReg(),
1287 ToReg: MI.getOperand(i: 1).getReg());
1288 if (LIS)
1289 LIS->RemoveMachineInstrFromMaps(MI);
1290 MI.eraseFromParent();
1291 Changed = true;
1292 }
1293 }
1294 }
1295}
1296
1297/// Rewrites the kernel block in-place to adhere to the given schedule.
1298/// KernelRewriter holds all of the state required to perform the rewriting.
1299class KernelRewriter {
1300 ModuloSchedule &S;
1301 MachineBasicBlock *BB;
1302 MachineBasicBlock *PreheaderBB, *ExitBB;
1303 MachineRegisterInfo &MRI;
1304 const TargetInstrInfo *TII;
1305 LiveIntervals *LIS;
1306
1307 // Map from register class to canonical undef register for that class.
1308 DenseMap<const TargetRegisterClass *, Register> Undefs;
1309 // Map from <LoopReg, InitReg> to phi register for all created phis. Note that
1310 // this map is only used when InitReg is non-undef.
1311 DenseMap<std::pair<Register, Register>, Register> Phis;
1312 // Map from LoopReg to phi register where the InitReg is undef.
1313 DenseMap<Register, Register> UndefPhis;
1314
1315 // Reg is used by MI. Return the new register MI should use to adhere to the
1316 // schedule. Insert phis as necessary.
1317 Register remapUse(Register Reg, MachineInstr &MI);
1318 // Insert a phi that carries LoopReg from the loop body and InitReg otherwise.
1319 // If InitReg is not given it is chosen arbitrarily. It will either be undef
1320 // or will be chosen so as to share another phi.
1321 Register phi(Register LoopReg, std::optional<Register> InitReg = {},
1322 const TargetRegisterClass *RC = nullptr);
1323 // Create an undef register of the given register class.
1324 Register undef(const TargetRegisterClass *RC);
1325
1326public:
1327 KernelRewriter(MachineLoop &L, ModuloSchedule &S, MachineBasicBlock *LoopBB,
1328 LiveIntervals *LIS = nullptr);
1329 void rewrite();
1330};
1331} // namespace
1332
1333KernelRewriter::KernelRewriter(MachineLoop &L, ModuloSchedule &S,
1334 MachineBasicBlock *LoopBB, LiveIntervals *LIS)
1335 : S(S), BB(LoopBB), PreheaderBB(L.getLoopPreheader()),
1336 ExitBB(L.getExitBlock()), MRI(BB->getParent()->getRegInfo()),
1337 TII(BB->getParent()->getSubtarget().getInstrInfo()), LIS(LIS) {
1338 PreheaderBB = *BB->pred_begin();
1339 if (PreheaderBB == BB)
1340 PreheaderBB = *std::next(x: BB->pred_begin());
1341}
1342
1343void KernelRewriter::rewrite() {
1344 // Rearrange the loop to be in schedule order. Note that the schedule may
1345 // contain instructions that are not owned by the loop block (InstrChanges and
1346 // friends), so we gracefully handle unowned instructions and delete any
1347 // instructions that weren't in the schedule.
1348 auto InsertPt = BB->getFirstTerminator();
1349 MachineInstr *FirstMI = nullptr;
1350 for (MachineInstr *MI : S.getInstructions()) {
1351 if (MI->isPHI())
1352 continue;
1353 if (MI->getParent())
1354 MI->removeFromParent();
1355 BB->insert(I: InsertPt, MI);
1356 if (!FirstMI)
1357 FirstMI = MI;
1358 }
1359 assert(FirstMI && "Failed to find first MI in schedule");
1360
1361 // At this point all of the scheduled instructions are between FirstMI
1362 // and the end of the block. Kill from the first non-phi to FirstMI.
1363 for (auto I = BB->getFirstNonPHI(); I != FirstMI->getIterator();) {
1364 if (LIS)
1365 LIS->RemoveMachineInstrFromMaps(MI&: *I);
1366 (I++)->eraseFromParent();
1367 }
1368
1369 // Now remap every instruction in the loop.
1370 for (MachineInstr &MI : *BB) {
1371 if (MI.isPHI() || MI.isTerminator())
1372 continue;
1373 for (MachineOperand &MO : MI.uses()) {
1374 if (!MO.isReg() || MO.getReg().isPhysical() || MO.isImplicit())
1375 continue;
1376 Register Reg = remapUse(Reg: MO.getReg(), MI);
1377 MO.setReg(Reg);
1378 }
1379 }
1380 EliminateDeadPhis(MBB: BB, MRI, LIS);
1381
1382 // Ensure a phi exists for all instructions that are either referenced by
1383 // an illegal phi or by an instruction outside the loop. This allows us to
1384 // treat remaps of these values the same as "normal" values that come from
1385 // loop-carried phis.
1386 for (auto MI = BB->getFirstNonPHI(); MI != BB->end(); ++MI) {
1387 if (MI->isPHI()) {
1388 Register R = MI->getOperand(i: 0).getReg();
1389 phi(LoopReg: R);
1390 continue;
1391 }
1392
1393 for (MachineOperand &Def : MI->defs()) {
1394 for (MachineInstr &MI : MRI.use_instructions(Reg: Def.getReg())) {
1395 if (MI.getParent() != BB) {
1396 phi(LoopReg: Def.getReg());
1397 break;
1398 }
1399 }
1400 }
1401 }
1402}
1403
1404Register KernelRewriter::remapUse(Register Reg, MachineInstr &MI) {
1405 MachineInstr *Producer = MRI.getUniqueVRegDef(Reg);
1406 if (!Producer)
1407 return Reg;
1408
1409 int ConsumerStage = S.getStage(MI: &MI);
1410 if (!Producer->isPHI()) {
1411 // Non-phi producers are simple to remap. Insert as many phis as the
1412 // difference between the consumer and producer stages.
1413 if (Producer->getParent() != BB)
1414 // Producer was not inside the loop. Use the register as-is.
1415 return Reg;
1416 int ProducerStage = S.getStage(MI: Producer);
1417 assert(ConsumerStage != -1 &&
1418 "In-loop consumer should always be scheduled!");
1419 assert(ConsumerStage >= ProducerStage);
1420 unsigned StageDiff = ConsumerStage - ProducerStage;
1421
1422 for (unsigned I = 0; I < StageDiff; ++I)
1423 Reg = phi(LoopReg: Reg);
1424 return Reg;
1425 }
1426
1427 // First, dive through the phi chain to find the defaults for the generated
1428 // phis.
1429 SmallVector<std::optional<Register>, 4> Defaults;
1430 Register LoopReg = Reg;
1431 auto LoopProducer = Producer;
1432 while (LoopProducer->isPHI() && LoopProducer->getParent() == BB) {
1433 LoopReg = getLoopPhiReg(Phi&: *LoopProducer, LoopBB: BB);
1434 Defaults.emplace_back(Args: getInitPhiReg(Phi&: *LoopProducer, LoopBB: BB));
1435 LoopProducer = MRI.getUniqueVRegDef(Reg: LoopReg);
1436 assert(LoopProducer);
1437 }
1438 int LoopProducerStage = S.getStage(MI: LoopProducer);
1439
1440 std::optional<Register> IllegalPhiDefault;
1441
1442 if (LoopProducerStage == -1) {
1443 // Do nothing.
1444 } else if (LoopProducerStage > ConsumerStage) {
1445 // This schedule is only representable if ProducerStage == ConsumerStage+1.
1446 // In addition, Consumer's cycle must be scheduled after Producer in the
1447 // rescheduled loop. This is enforced by the pipeliner's ASAP and ALAP
1448 // functions.
1449#ifndef NDEBUG // Silence unused variables in non-asserts mode.
1450 int LoopProducerCycle = S.getCycle(LoopProducer);
1451 int ConsumerCycle = S.getCycle(&MI);
1452#endif
1453 assert(LoopProducerCycle <= ConsumerCycle);
1454 assert(LoopProducerStage == ConsumerStage + 1);
1455 // Peel off the first phi from Defaults and insert a phi between producer
1456 // and consumer. This phi will not be at the front of the block so we
1457 // consider it illegal. It will only exist during the rewrite process; it
1458 // needs to exist while we peel off prologs because these could take the
1459 // default value. After that we can replace all uses with the loop producer
1460 // value.
1461 IllegalPhiDefault = Defaults.front();
1462 Defaults.erase(CI: Defaults.begin());
1463 } else {
1464 assert(ConsumerStage >= LoopProducerStage);
1465 int StageDiff = ConsumerStage - LoopProducerStage;
1466 if (StageDiff > 0) {
1467 LLVM_DEBUG(dbgs() << " -- padding defaults array from " << Defaults.size()
1468 << " to " << (Defaults.size() + StageDiff) << "\n");
1469 // If we need more phis than we have defaults for, pad out with undefs for
1470 // the earliest phis, which are at the end of the defaults chain (the
1471 // chain is in reverse order).
1472 Defaults.resize(N: Defaults.size() + StageDiff,
1473 NV: Defaults.empty() ? std::optional<Register>()
1474 : Defaults.back());
1475 }
1476 }
1477
1478 // Now we know the number of stages to jump back, insert the phi chain.
1479 auto DefaultI = Defaults.rbegin();
1480 while (DefaultI != Defaults.rend())
1481 LoopReg = phi(LoopReg, InitReg: *DefaultI++, RC: MRI.getRegClass(Reg));
1482
1483 if (IllegalPhiDefault) {
1484 // The consumer optionally consumes LoopProducer in the same iteration
1485 // (because the producer is scheduled at an earlier cycle than the consumer)
1486 // or the initial value. To facilitate this we create an illegal block here
1487 // by embedding a phi in the middle of the block. We will fix this up
1488 // immediately prior to pruning.
1489 auto RC = MRI.getRegClass(Reg);
1490 Register R = MRI.createVirtualRegister(RegClass: RC);
1491 MachineInstr *IllegalPhi =
1492 BuildMI(BB&: *BB, I&: MI, MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: R)
1493 .addReg(RegNo: *IllegalPhiDefault)
1494 .addMBB(MBB: PreheaderBB) // Block choice is arbitrary and has no effect.
1495 .addReg(RegNo: LoopReg)
1496 .addMBB(MBB: BB); // Block choice is arbitrary and has no effect.
1497 // Illegal phi should belong to the producer stage so that it can be
1498 // filtered correctly during peeling.
1499 S.setStage(MI: IllegalPhi, MIStage: LoopProducerStage);
1500 return R;
1501 }
1502
1503 return LoopReg;
1504}
1505
1506Register KernelRewriter::phi(Register LoopReg, std::optional<Register> InitReg,
1507 const TargetRegisterClass *RC) {
1508 // If the init register is not undef, try and find an existing phi.
1509 if (InitReg) {
1510 auto I = Phis.find(Val: {LoopReg, *InitReg});
1511 if (I != Phis.end())
1512 return I->second;
1513 } else {
1514 for (auto &KV : Phis) {
1515 if (KV.first.first == LoopReg)
1516 return KV.second;
1517 }
1518 }
1519
1520 // InitReg is either undef or no existing phi takes InitReg as input. Try and
1521 // find a phi that takes undef as input.
1522 auto I = UndefPhis.find(Val: LoopReg);
1523 if (I != UndefPhis.end()) {
1524 Register R = I->second;
1525 if (!InitReg)
1526 // Found a phi taking undef as input, and this input is undef so return
1527 // without any more changes.
1528 return R;
1529 // Found a phi taking undef as input, so rewrite it to take InitReg.
1530 MachineInstr *MI = MRI.getVRegDef(Reg: R);
1531 MI->getOperand(i: 1).setReg(*InitReg);
1532 Phis.insert(KV: {{LoopReg, *InitReg}, R});
1533 const TargetRegisterClass *ConstrainRegClass =
1534 MRI.constrainRegClass(Reg: R, RC: MRI.getRegClass(Reg: *InitReg));
1535 assert(ConstrainRegClass && "Expected a valid constrained register class!");
1536 (void)ConstrainRegClass;
1537 UndefPhis.erase(I);
1538 return R;
1539 }
1540
1541 // Failed to find any existing phi to reuse, so create a new one.
1542 if (!RC)
1543 RC = MRI.getRegClass(Reg: LoopReg);
1544 Register R = MRI.createVirtualRegister(RegClass: RC);
1545 if (InitReg) {
1546 const TargetRegisterClass *ConstrainRegClass =
1547 MRI.constrainRegClass(Reg: R, RC: MRI.getRegClass(Reg: *InitReg));
1548 assert(ConstrainRegClass && "Expected a valid constrained register class!");
1549 (void)ConstrainRegClass;
1550 }
1551 BuildMI(BB&: *BB, I: BB->getFirstNonPHI(), MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: R)
1552 .addReg(RegNo: InitReg ? *InitReg : undef(RC))
1553 .addMBB(MBB: PreheaderBB)
1554 .addReg(RegNo: LoopReg)
1555 .addMBB(MBB: BB);
1556 if (!InitReg)
1557 UndefPhis[LoopReg] = R;
1558 else
1559 Phis[{LoopReg, *InitReg}] = R;
1560 return R;
1561}
1562
1563Register KernelRewriter::undef(const TargetRegisterClass *RC) {
1564 Register &R = Undefs[RC];
1565 if (R == 0) {
1566 // Create an IMPLICIT_DEF that defines this register if we need it.
1567 // All uses of this should be removed by the time we have finished unrolling
1568 // prologs and epilogs.
1569 R = MRI.createVirtualRegister(RegClass: RC);
1570 auto *InsertBB = &PreheaderBB->getParent()->front();
1571 BuildMI(BB&: *InsertBB, I: InsertBB->getFirstTerminator(), MIMD: DebugLoc(),
1572 MCID: TII->get(Opcode: TargetOpcode::IMPLICIT_DEF), DestReg: R);
1573 }
1574 return R;
1575}
1576
1577namespace {
1578/// Describes an operand in the kernel of a pipelined loop. Characteristics of
1579/// the operand are discovered, such as how many in-loop PHIs it has to jump
1580/// through and defaults for these phis.
1581class KernelOperandInfo {
1582 MachineBasicBlock *BB;
1583 MachineRegisterInfo &MRI;
1584 SmallVector<Register, 4> PhiDefaults;
1585 MachineOperand *Source;
1586 MachineOperand *Target;
1587
1588public:
1589 KernelOperandInfo(MachineOperand *MO, MachineRegisterInfo &MRI,
1590 const SmallPtrSetImpl<MachineInstr *> &IllegalPhis)
1591 : MRI(MRI) {
1592 Source = MO;
1593 BB = MO->getParent()->getParent();
1594 while (isRegInLoop(MO)) {
1595 MachineInstr *MI = MRI.getVRegDef(Reg: MO->getReg());
1596 if (MI->isFullCopy()) {
1597 MO = &MI->getOperand(i: 1);
1598 continue;
1599 }
1600 if (!MI->isPHI())
1601 break;
1602 // If this is an illegal phi, don't count it in distance.
1603 if (IllegalPhis.count(Ptr: MI)) {
1604 MO = &MI->getOperand(i: 3);
1605 continue;
1606 }
1607
1608 Register Default = getInitPhiReg(Phi&: *MI, LoopBB: BB);
1609 MO = MI->getOperand(i: 2).getMBB() == BB ? &MI->getOperand(i: 1)
1610 : &MI->getOperand(i: 3);
1611 PhiDefaults.push_back(Elt: Default);
1612 }
1613 Target = MO;
1614 }
1615
1616 bool operator==(const KernelOperandInfo &Other) const {
1617 return PhiDefaults.size() == Other.PhiDefaults.size();
1618 }
1619
1620 void print(raw_ostream &OS) const {
1621 OS << "use of " << *Source << ": distance(" << PhiDefaults.size() << ") in "
1622 << *Source->getParent();
1623 }
1624
1625private:
1626 bool isRegInLoop(MachineOperand *MO) {
1627 return MO->isReg() && MO->getReg().isVirtual() &&
1628 MRI.getVRegDef(Reg: MO->getReg())->getParent() == BB;
1629 }
1630};
1631} // namespace
1632
1633MachineBasicBlock *
1634PeelingModuloScheduleExpander::peelKernel(LoopPeelDirection LPD) {
1635 MachineBasicBlock *NewBB = PeelSingleBlockLoop(Direction: LPD, Loop: BB, MRI, TII, MDTU: &MDTU);
1636 if (LPD == LPD_Front)
1637 PeeledFront.push_back(x: NewBB);
1638 else
1639 PeeledBack.push_front(x: NewBB);
1640 for (auto I = BB->begin(), NI = NewBB->begin(); !I->isTerminator();
1641 ++I, ++NI) {
1642 CanonicalMIs[&*I] = &*I;
1643 CanonicalMIs[&*NI] = &*I;
1644 BlockMIs[{NewBB, &*I}] = &*NI;
1645 BlockMIs[{BB, &*I}] = &*I;
1646 }
1647 return NewBB;
1648}
1649
1650void PeelingModuloScheduleExpander::filterInstructions(MachineBasicBlock *MB,
1651 int MinStage) {
1652 for (auto I = MB->getFirstInstrTerminator()->getReverseIterator();
1653 I != std::next(x: MB->getFirstNonPHI()->getReverseIterator());) {
1654 MachineInstr *MI = &*I++;
1655 int Stage = getStage(MI);
1656 if (Stage == -1 || Stage >= MinStage)
1657 continue;
1658
1659 for (MachineOperand &DefMO : MI->defs()) {
1660 SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
1661 for (MachineInstr &UseMI : MRI.use_instructions(Reg: DefMO.getReg())) {
1662 // Only PHIs can use values from this block by construction.
1663 // Match with the equivalent PHI in B.
1664 assert(UseMI.isPHI());
1665 Register Reg = getEquivalentRegisterIn(Reg: UseMI.getOperand(i: 0).getReg(),
1666 BB: MI->getParent());
1667 Subs.emplace_back(Args: &UseMI, Args&: Reg);
1668 }
1669 for (auto &Sub : Subs)
1670 Sub.first->substituteRegister(FromReg: DefMO.getReg(), ToReg: Sub.second, /*SubIdx=*/0,
1671 RegInfo: *MRI.getTargetRegisterInfo());
1672 }
1673 if (LIS)
1674 LIS->RemoveMachineInstrFromMaps(MI&: *MI);
1675 MI->eraseFromParent();
1676 }
1677}
1678
1679void PeelingModuloScheduleExpander::moveStageBetweenBlocks(
1680 MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage) {
1681 auto InsertPt = DestBB->getFirstNonPHI();
1682 DenseMap<Register, Register> Remaps;
1683 for (MachineInstr &MI : llvm::make_early_inc_range(
1684 Range: llvm::make_range(x: SourceBB->getFirstNonPHI(), y: SourceBB->end()))) {
1685 if (MI.isPHI()) {
1686 // This is an illegal PHI. If we move any instructions using an illegal
1687 // PHI, we need to create a legal Phi.
1688 if (getStage(MI: &MI) != Stage) {
1689 // The legal Phi is not necessary if the illegal phi's stage
1690 // is being moved.
1691 Register PhiR = MI.getOperand(i: 0).getReg();
1692 auto RC = MRI.getRegClass(Reg: PhiR);
1693 Register NR = MRI.createVirtualRegister(RegClass: RC);
1694 MachineInstr *NI = BuildMI(BB&: *DestBB, I: DestBB->getFirstNonPHI(),
1695 MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: NR)
1696 .addReg(RegNo: PhiR)
1697 .addMBB(MBB: SourceBB);
1698 BlockMIs[{DestBB, CanonicalMIs[&MI]}] = NI;
1699 CanonicalMIs[NI] = CanonicalMIs[&MI];
1700 Remaps[PhiR] = NR;
1701 }
1702 }
1703 if (getStage(MI: &MI) != Stage)
1704 continue;
1705 MI.removeFromParent();
1706 DestBB->insert(I: InsertPt, MI: &MI);
1707 auto *KernelMI = CanonicalMIs[&MI];
1708 BlockMIs[{DestBB, KernelMI}] = &MI;
1709 BlockMIs.erase(Val: {SourceBB, KernelMI});
1710 }
1711 SmallVector<MachineInstr *, 4> PhiToDelete;
1712 for (MachineInstr &MI : DestBB->phis()) {
1713 assert(MI.getNumOperands() == 3);
1714 MachineInstr *Def = MRI.getVRegDef(Reg: MI.getOperand(i: 1).getReg());
1715 // If the instruction referenced by the phi is moved inside the block
1716 // we don't need the phi anymore.
1717 if (getStage(MI: Def) == Stage) {
1718 Register PhiReg = MI.getOperand(i: 0).getReg();
1719 assert(Def->findRegisterDefOperandIdx(MI.getOperand(1).getReg(),
1720 /*TRI=*/nullptr) != -1);
1721 MRI.replaceRegWith(FromReg: MI.getOperand(i: 0).getReg(), ToReg: MI.getOperand(i: 1).getReg());
1722 MI.getOperand(i: 0).setReg(PhiReg);
1723 PhiToDelete.push_back(Elt: &MI);
1724 }
1725 }
1726 for (auto *P : PhiToDelete)
1727 P->eraseFromParent();
1728 InsertPt = DestBB->getFirstNonPHI();
1729 // Helper to clone Phi instructions into the destination block. We clone Phi
1730 // greedily to avoid combinatorial explosion of Phi instructions.
1731 auto clonePhi = [&](MachineInstr *Phi) {
1732 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: Phi);
1733 DestBB->insert(I: InsertPt, MI: NewMI);
1734 Register OrigR = Phi->getOperand(i: 0).getReg();
1735 Register R = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigR));
1736 NewMI->getOperand(i: 0).setReg(R);
1737 NewMI->getOperand(i: 1).setReg(OrigR);
1738 NewMI->getOperand(i: 2).setMBB(*DestBB->pred_begin());
1739 Remaps[OrigR] = R;
1740 CanonicalMIs[NewMI] = CanonicalMIs[Phi];
1741 BlockMIs[{DestBB, CanonicalMIs[Phi]}] = NewMI;
1742 PhiNodeLoopIteration[NewMI] = PhiNodeLoopIteration[Phi];
1743 return R;
1744 };
1745 for (auto I = DestBB->getFirstNonPHI(); I != DestBB->end(); ++I) {
1746 for (MachineOperand &MO : I->uses()) {
1747 if (!MO.isReg())
1748 continue;
1749 if (auto It = Remaps.find(Val: MO.getReg()); It != Remaps.end())
1750 MO.setReg(It->second);
1751 else if (MO.getReg().isVirtual()) {
1752 // If we are using a phi from the source block we need to add a new phi
1753 // pointing to the old one.
1754 MachineInstr *Use = MRI.getUniqueVRegDef(Reg: MO.getReg());
1755 if (Use && Use->isPHI() && Use->getParent() == SourceBB) {
1756 Register R = clonePhi(Use);
1757 MO.setReg(R);
1758 }
1759 }
1760 }
1761 }
1762}
1763
1764Register
1765PeelingModuloScheduleExpander::getPhiCanonicalReg(MachineInstr *CanonicalPhi,
1766 MachineInstr *Phi) {
1767 unsigned distance = PhiNodeLoopIteration[Phi];
1768 MachineInstr *CanonicalUse = CanonicalPhi;
1769 Register CanonicalUseReg = CanonicalUse->getOperand(i: 0).getReg();
1770 for (unsigned I = 0; I < distance; ++I) {
1771 assert(CanonicalUse->isPHI());
1772 assert(CanonicalUse->getNumOperands() == 5);
1773 unsigned LoopRegIdx = 3, InitRegIdx = 1;
1774 if (CanonicalUse->getOperand(i: 2).getMBB() == CanonicalUse->getParent())
1775 std::swap(a&: LoopRegIdx, b&: InitRegIdx);
1776 CanonicalUseReg = CanonicalUse->getOperand(i: LoopRegIdx).getReg();
1777 CanonicalUse = MRI.getVRegDef(Reg: CanonicalUseReg);
1778 }
1779 return CanonicalUseReg;
1780}
1781
1782void PeelingModuloScheduleExpander::peelPrologAndEpilogs() {
1783 BitVector LS(Schedule.getNumStages(), true);
1784 BitVector AS(Schedule.getNumStages(), true);
1785 LiveStages[BB] = LS;
1786 AvailableStages[BB] = AS;
1787
1788 // Peel out the prologs.
1789 LS.reset();
1790 for (int I = 0; I < Schedule.getNumStages() - 1; ++I) {
1791 LS[I] = true;
1792 Prologs.push_back(Elt: peelKernel(LPD: LPD_Front));
1793 LiveStages[Prologs.back()] = LS;
1794 AvailableStages[Prologs.back()] = LS;
1795 }
1796
1797 // Create a block that will end up as the new loop exiting block (dominated by
1798 // all prologs and epilogs). It will only contain PHIs, in the same order as
1799 // BB's PHIs. This gives us a poor-man's LCSSA with the inductive property
1800 // that the exiting block is a (sub) clone of BB. This in turn gives us the
1801 // property that any value deffed in BB but used outside of BB is used by a
1802 // PHI in the exiting block.
1803 MachineBasicBlock *ExitingBB = CreateLCSSAExitingBlock();
1804 EliminateDeadPhis(MBB: ExitingBB, MRI, LIS, /*KeepSingleSrcPhi=*/true);
1805 // Push out the epilogs, again in reverse order.
1806 // We can't assume anything about the minumum loop trip count at this point,
1807 // so emit a fairly complex epilog.
1808
1809 // We first peel number of stages minus one epilogue. Then we remove dead
1810 // stages and reorder instructions based on their stage. If we have 3 stages
1811 // we generate first:
1812 // E0[3, 2, 1]
1813 // E1[3', 2']
1814 // E2[3'']
1815 // And then we move instructions based on their stages to have:
1816 // E0[3]
1817 // E1[2, 3']
1818 // E2[1, 2', 3'']
1819 // The transformation is legal because we only move instructions past
1820 // instructions of a previous loop iteration.
1821 for (int I = 1; I <= Schedule.getNumStages() - 1; ++I) {
1822 Epilogs.push_back(Elt: peelKernel(LPD: LPD_Back));
1823 MachineBasicBlock *B = Epilogs.back();
1824 filterInstructions(MB: B, MinStage: Schedule.getNumStages() - I);
1825 // Keep track at which iteration each phi belongs to. We need it to know
1826 // what version of the variable to use during prologue/epilogue stitching.
1827 EliminateDeadPhis(MBB: B, MRI, LIS, /*KeepSingleSrcPhi=*/true);
1828 for (MachineInstr &Phi : B->phis())
1829 PhiNodeLoopIteration[&Phi] = Schedule.getNumStages() - I;
1830 }
1831 for (size_t I = 0; I < Epilogs.size(); I++) {
1832 LS.reset();
1833 for (size_t J = I; J < Epilogs.size(); J++) {
1834 int Iteration = J;
1835 unsigned Stage = Schedule.getNumStages() - 1 + I - J;
1836 // Move stage one block at a time so that Phi nodes are updated correctly.
1837 for (size_t K = Iteration; K > I; K--)
1838 moveStageBetweenBlocks(DestBB: Epilogs[K - 1], SourceBB: Epilogs[K], Stage);
1839 LS[Stage] = true;
1840 }
1841 LiveStages[Epilogs[I]] = LS;
1842 AvailableStages[Epilogs[I]] = AS;
1843 }
1844
1845 // Now we've defined all the prolog and epilog blocks as a fallthrough
1846 // sequence, add the edges that will be followed if the loop trip count is
1847 // lower than the number of stages (connecting prologs directly with epilogs).
1848 auto PI = Prologs.begin();
1849 auto EI = Epilogs.begin();
1850 assert(Prologs.size() == Epilogs.size());
1851 for (; PI != Prologs.end(); ++PI, ++EI) {
1852 MachineBasicBlock *Pred = *(*EI)->pred_begin();
1853 (*PI)->addSuccessor(Succ: *EI);
1854 MDTU.applyUpdates(Updates: {{MachineDominatorTree::Insert, *PI, *EI}});
1855 for (MachineInstr &MI : (*EI)->phis()) {
1856 Register Reg = MI.getOperand(i: 1).getReg();
1857 MachineInstr *Use = MRI.getUniqueVRegDef(Reg);
1858 if (Use && Use->getParent() == Pred) {
1859 MachineInstr *CanonicalUse = CanonicalMIs[Use];
1860 if (CanonicalUse->isPHI()) {
1861 // If the use comes from a phi we need to skip as many phi as the
1862 // distance between the epilogue and the kernel. Trace through the phi
1863 // chain to find the right value.
1864 Reg = getPhiCanonicalReg(CanonicalPhi: CanonicalUse, Phi: Use);
1865 }
1866 Reg = getEquivalentRegisterIn(Reg, BB: *PI);
1867 }
1868 MI.addOperand(Op: MachineOperand::CreateReg(Reg, /*isDef=*/false));
1869 MI.addOperand(Op: MachineOperand::CreateMBB(MBB: *PI));
1870 }
1871 }
1872
1873 // Create a list of all blocks in order.
1874 SmallVector<MachineBasicBlock *, 8> Blocks;
1875 llvm::append_range(C&: Blocks, R&: PeeledFront);
1876 Blocks.push_back(Elt: BB);
1877 llvm::append_range(C&: Blocks, R&: PeeledBack);
1878
1879 // Iterate in reverse order over all instructions, remapping as we go.
1880 for (MachineBasicBlock *B : reverse(C&: Blocks)) {
1881 for (auto I = B->instr_rbegin();
1882 I != std::next(x: B->getFirstNonPHI()->getReverseIterator());) {
1883 MachineBasicBlock::reverse_instr_iterator MI = I++;
1884 rewriteUsesOf(MI: &*MI);
1885 }
1886 }
1887 for (auto *MI : IllegalPhisToDelete) {
1888 if (LIS)
1889 LIS->RemoveMachineInstrFromMaps(MI&: *MI);
1890 MI->eraseFromParent();
1891 }
1892 IllegalPhisToDelete.clear();
1893
1894 // Now all remapping has been done, we're free to optimize the generated code.
1895 for (MachineBasicBlock *B : reverse(C&: Blocks))
1896 EliminateDeadPhis(MBB: B, MRI, LIS);
1897 EliminateDeadPhis(MBB: ExitingBB, MRI, LIS);
1898}
1899
1900MachineBasicBlock *PeelingModuloScheduleExpander::CreateLCSSAExitingBlock() {
1901 MachineFunction &MF = *BB->getParent();
1902 MachineBasicBlock *Exit = *BB->succ_begin();
1903 if (Exit == BB)
1904 Exit = *std::next(x: BB->succ_begin());
1905
1906 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB: BB->getBasicBlock());
1907 MF.insert(MBBI: std::next(x: BB->getIterator()), MBB: NewBB);
1908
1909 // Clone all phis in BB into NewBB and rewrite.
1910 for (MachineInstr &MI : BB->phis()) {
1911 auto RC = MRI.getRegClass(Reg: MI.getOperand(i: 0).getReg());
1912 Register OldR = MI.getOperand(i: 3).getReg();
1913 Register R = MRI.createVirtualRegister(RegClass: RC);
1914 SmallVector<MachineInstr *, 4> Uses;
1915 for (MachineInstr &Use : MRI.use_instructions(Reg: OldR))
1916 if (Use.getParent() != BB)
1917 Uses.push_back(Elt: &Use);
1918 for (MachineInstr *Use : Uses)
1919 Use->substituteRegister(FromReg: OldR, ToReg: R, /*SubIdx=*/0,
1920 RegInfo: *MRI.getTargetRegisterInfo());
1921 MachineInstr *NI = BuildMI(BB: NewBB, MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: R)
1922 .addReg(RegNo: OldR)
1923 .addMBB(MBB: BB);
1924 BlockMIs[{NewBB, &MI}] = NI;
1925 CanonicalMIs[NI] = &MI;
1926 }
1927 BB->replaceSuccessor(Old: Exit, New: NewBB);
1928 Exit->replacePhiUsesWith(Old: BB, New: NewBB);
1929 NewBB->addSuccessor(Succ: Exit);
1930 MDTU.splitCriticalEdge(FromBB: BB, ToBB: Exit, NewBB);
1931
1932 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1933 SmallVector<MachineOperand, 4> Cond;
1934 bool CanAnalyzeBr = !TII->analyzeBranch(MBB&: *BB, TBB, FBB, Cond);
1935 (void)CanAnalyzeBr;
1936 assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
1937 TII->removeBranch(MBB&: *BB);
1938 TII->insertBranch(MBB&: *BB, TBB: TBB == Exit ? NewBB : TBB, FBB: FBB == Exit ? NewBB : FBB,
1939 Cond, DL: DebugLoc());
1940 TII->insertUnconditionalBranch(MBB&: *NewBB, DestBB: Exit, DL: DebugLoc());
1941 return NewBB;
1942}
1943
1944Register
1945PeelingModuloScheduleExpander::getEquivalentRegisterIn(Register Reg,
1946 MachineBasicBlock *BB) {
1947 MachineInstr *MI = MRI.getUniqueVRegDef(Reg);
1948 unsigned OpIdx = MI->findRegisterDefOperandIdx(Reg, /*TRI=*/nullptr);
1949 return BlockMIs[{BB, CanonicalMIs[MI]}]->getOperand(i: OpIdx).getReg();
1950}
1951
1952void PeelingModuloScheduleExpander::rewriteUsesOf(MachineInstr *MI) {
1953 if (MI->isPHI()) {
1954 // This is an illegal PHI. The loop-carried (desired) value is operand 3,
1955 // and it is produced by this block.
1956 Register PhiR = MI->getOperand(i: 0).getReg();
1957 Register R = MI->getOperand(i: 3).getReg();
1958 int RMIStage = getStage(MI: MRI.getUniqueVRegDef(Reg: R));
1959 if (RMIStage != -1 && !AvailableStages[MI->getParent()].test(Idx: RMIStage))
1960 R = MI->getOperand(i: 1).getReg();
1961 MRI.setRegClass(Reg: R, RC: MRI.getRegClass(Reg: PhiR));
1962 MRI.replaceRegWith(FromReg: PhiR, ToReg: R);
1963 // Postpone deleting the Phi as it may be referenced by BlockMIs and used
1964 // later to figure out how to remap registers.
1965 MI->getOperand(i: 0).setReg(PhiR);
1966 IllegalPhisToDelete.push_back(Elt: MI);
1967 return;
1968 }
1969
1970 int Stage = getStage(MI);
1971 if (Stage == -1 || LiveStages.count(Val: MI->getParent()) == 0 ||
1972 LiveStages[MI->getParent()].test(Idx: Stage))
1973 // Instruction is live, no rewriting to do.
1974 return;
1975
1976 for (MachineOperand &DefMO : MI->defs()) {
1977 SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
1978 for (MachineInstr &UseMI : MRI.use_instructions(Reg: DefMO.getReg())) {
1979 // Only PHIs can use values from this block by construction.
1980 // Match with the equivalent PHI in B.
1981 assert(UseMI.isPHI());
1982 Register Reg = getEquivalentRegisterIn(Reg: UseMI.getOperand(i: 0).getReg(),
1983 BB: MI->getParent());
1984 Subs.emplace_back(Args: &UseMI, Args&: Reg);
1985 }
1986 for (auto &Sub : Subs)
1987 Sub.first->substituteRegister(FromReg: DefMO.getReg(), ToReg: Sub.second, /*SubIdx=*/0,
1988 RegInfo: *MRI.getTargetRegisterInfo());
1989 }
1990 if (LIS)
1991 LIS->RemoveMachineInstrFromMaps(MI&: *MI);
1992 MI->eraseFromParent();
1993}
1994
1995void PeelingModuloScheduleExpander::fixupBranches() {
1996 // Work outwards from the kernel.
1997 bool KernelDisposed = false;
1998 int TC = Schedule.getNumStages() - 1;
1999 for (auto PI = Prologs.rbegin(), EI = Epilogs.rbegin(); PI != Prologs.rend();
2000 ++PI, ++EI, --TC) {
2001 MachineBasicBlock *Prolog = *PI;
2002 MachineBasicBlock *Fallthrough = *Prolog->succ_begin();
2003 MachineBasicBlock *Epilog = *EI;
2004 SmallVector<MachineOperand, 4> Cond;
2005 TII->removeBranch(MBB&: *Prolog);
2006 std::optional<bool> StaticallyGreater =
2007 LoopInfo->createTripCountGreaterCondition(TC, MBB&: *Prolog, Cond);
2008 if (!StaticallyGreater) {
2009 LLVM_DEBUG(dbgs() << "Dynamic: TC > " << TC << "\n");
2010 // Dynamically branch based on Cond.
2011 TII->insertBranch(MBB&: *Prolog, TBB: Epilog, FBB: Fallthrough, Cond, DL: DebugLoc());
2012 } else if (*StaticallyGreater == false) {
2013 LLVM_DEBUG(dbgs() << "Static-false: TC > " << TC << "\n");
2014 // Prolog never falls through; branch to epilog and orphan interior
2015 // blocks. Leave it to unreachable-block-elim to clean up.
2016 Prolog->removeSuccessor(Succ: Fallthrough);
2017 MDTU.applyUpdates(Updates: {{MachineDominatorTree::Delete, Prolog, Fallthrough}});
2018 for (MachineInstr &P : Fallthrough->phis()) {
2019 P.removeOperand(OpNo: 2);
2020 P.removeOperand(OpNo: 1);
2021 }
2022 TII->insertUnconditionalBranch(MBB&: *Prolog, DestBB: Epilog, DL: DebugLoc());
2023 KernelDisposed = true;
2024 } else {
2025 LLVM_DEBUG(dbgs() << "Static-true: TC > " << TC << "\n");
2026 // Prolog always falls through; remove incoming values in epilog.
2027 Prolog->removeSuccessor(Succ: Epilog);
2028 MDTU.applyUpdates(Updates: {{MachineDominatorTree::Delete, Prolog, Epilog}});
2029 for (MachineInstr &P : Epilog->phis()) {
2030 P.removeOperand(OpNo: 4);
2031 P.removeOperand(OpNo: 3);
2032 }
2033 }
2034 }
2035
2036 if (!KernelDisposed) {
2037 LoopInfo->adjustTripCount(TripCountAdjust: -(Schedule.getNumStages() - 1));
2038 LoopInfo->setPreheader(Prologs.back());
2039 } else {
2040 LoopInfo->disposed();
2041 }
2042}
2043
2044void PeelingModuloScheduleExpander::rewriteKernel() {
2045 KernelRewriter KR(*Schedule.getLoop(), Schedule, BB);
2046 KR.rewrite();
2047}
2048
2049void PeelingModuloScheduleExpander::expand() {
2050 BB = Schedule.getLoop()->getTopBlock();
2051 Preheader = Schedule.getLoop()->getLoopPreheader();
2052 LLVM_DEBUG(Schedule.dump());
2053 LoopInfo = TII->analyzeLoopForPipelining(LoopBB: BB);
2054 assert(LoopInfo);
2055
2056 rewriteKernel();
2057 peelPrologAndEpilogs();
2058 fixupBranches();
2059}
2060
2061void PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander() {
2062 BB = Schedule.getLoop()->getTopBlock();
2063 Preheader = Schedule.getLoop()->getLoopPreheader();
2064
2065 // Dump the schedule before we invalidate and remap all its instructions.
2066 // Stash it in a string so we can print it if we found an error.
2067 std::string ScheduleDump;
2068 raw_string_ostream OS(ScheduleDump);
2069 Schedule.print(OS);
2070
2071 // First, run the normal ModuleScheduleExpander. We don't support any
2072 // InstrChanges.
2073 assert(LIS && "Requires LiveIntervals!");
2074 ModuloScheduleExpander MSE(MF, Schedule, *LIS,
2075 ModuloScheduleExpander::InstrChangesTy(),
2076 MDTU.hasDomTree() ? &MDTU.getDomTree() : nullptr);
2077 MSE.expand();
2078 MachineBasicBlock *ExpandedKernel = MSE.getRewrittenKernel();
2079 if (!ExpandedKernel) {
2080 // The expander optimized away the kernel. We can't do any useful checking.
2081 MSE.cleanup();
2082 return;
2083 }
2084 // Before running the KernelRewriter, re-add BB into the CFG.
2085 Preheader->addSuccessor(Succ: BB);
2086 MDTU.applyUpdates(Updates: {{MachineDominatorTree::Insert, Preheader, BB}});
2087
2088 // Now run the new expansion algorithm.
2089 KernelRewriter KR(*Schedule.getLoop(), Schedule, BB);
2090 KR.rewrite();
2091 peelPrologAndEpilogs();
2092
2093 // Collect all illegal phis that the new algorithm created. We'll give these
2094 // to KernelOperandInfo.
2095 SmallPtrSet<MachineInstr *, 4> IllegalPhis;
2096 for (auto NI = BB->getFirstNonPHI(); NI != BB->end(); ++NI) {
2097 if (NI->isPHI())
2098 IllegalPhis.insert(Ptr: &*NI);
2099 }
2100
2101 // Co-iterate across both kernels. We expect them to be identical apart from
2102 // phis and full COPYs (we look through both).
2103 SmallVector<std::pair<KernelOperandInfo, KernelOperandInfo>, 8> KOIs;
2104 auto OI = ExpandedKernel->begin();
2105 auto NI = BB->begin();
2106 for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {
2107 while (OI->isPHI() || OI->isFullCopy())
2108 ++OI;
2109 while (NI->isPHI() || NI->isFullCopy())
2110 ++NI;
2111 assert(OI->getOpcode() == NI->getOpcode() && "Opcodes don't match?!");
2112 // Analyze every operand separately.
2113 for (auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();
2114 OOpI != OI->operands_end(); ++OOpI, ++NOpI)
2115 KOIs.emplace_back(Args: KernelOperandInfo(&*OOpI, MRI, IllegalPhis),
2116 Args: KernelOperandInfo(&*NOpI, MRI, IllegalPhis));
2117 }
2118
2119 bool Failed = false;
2120 for (auto &OldAndNew : KOIs) {
2121 if (OldAndNew.first == OldAndNew.second)
2122 continue;
2123 Failed = true;
2124 errs() << "Modulo kernel validation error: [\n";
2125 errs() << " [golden] ";
2126 OldAndNew.first.print(OS&: errs());
2127 errs() << " ";
2128 OldAndNew.second.print(OS&: errs());
2129 errs() << "]\n";
2130 }
2131
2132 if (Failed) {
2133 errs() << "Golden reference kernel:\n";
2134 ExpandedKernel->print(OS&: errs());
2135 errs() << "New kernel:\n";
2136 BB->print(OS&: errs());
2137 errs() << ScheduleDump;
2138 report_fatal_error(
2139 reason: "Modulo kernel validation (-pipeliner-experimental-cg) failed");
2140 }
2141
2142 // Cleanup by removing BB from the CFG again as the original
2143 // ModuloScheduleExpander intended.
2144 Preheader->removeSuccessor(Succ: BB);
2145 MDTU.applyUpdates(Updates: {{MachineDominatorTree::Delete, Preheader, BB}});
2146 MSE.cleanup();
2147}
2148
2149MachineInstr *ModuloScheduleExpanderMVE::cloneInstr(MachineInstr *OldMI) {
2150 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: OldMI);
2151
2152 // TODO: Offset information needs to be corrected.
2153 NewMI->dropMemRefs(MF);
2154
2155 return NewMI;
2156}
2157
2158/// Create a dedicated exit for Loop. Exit is the original exit for Loop.
2159/// If it is already dedicated exit, return it. Otherwise, insert a new
2160/// block between them and return the new block.
2161static MachineBasicBlock *createDedicatedExit(MachineBasicBlock *Loop,
2162 MachineBasicBlock *Exit,
2163 LiveIntervals &LIS,
2164 MachineDomTreeUpdater &MDTU) {
2165 if (Exit->pred_size() == 1)
2166 return Exit;
2167
2168 MachineFunction *MF = Loop->getParent();
2169 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
2170
2171 MachineBasicBlock *NewExit =
2172 MF->CreateMachineBasicBlock(BB: Loop->getBasicBlock());
2173 MF->insert(MBBI: Loop->getIterator(), MBB: NewExit);
2174 LIS.insertMBBInMaps(MBB: NewExit);
2175
2176 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
2177 SmallVector<MachineOperand, 4> Cond;
2178 TII->analyzeBranch(MBB&: *Loop, TBB, FBB, Cond);
2179 if (TBB == Loop)
2180 FBB = NewExit;
2181 else if (FBB == Loop)
2182 TBB = NewExit;
2183 else
2184 llvm_unreachable("unexpected loop structure");
2185 TII->removeBranch(MBB&: *Loop);
2186 TII->insertBranch(MBB&: *Loop, TBB, FBB, Cond, DL: DebugLoc());
2187 Loop->replaceSuccessor(Old: Exit, New: NewExit);
2188 TII->insertUnconditionalBranch(MBB&: *NewExit, DestBB: Exit, DL: DebugLoc());
2189 NewExit->addSuccessor(Succ: Exit);
2190 MDTU.splitCriticalEdge(FromBB: Loop, ToBB: Exit, NewBB: NewExit);
2191
2192 Exit->replacePhiUsesWith(Old: Loop, New: NewExit);
2193
2194 return NewExit;
2195}
2196
2197/// Insert branch code into the end of MBB. It branches to GreaterThan if the
2198/// remaining trip count for instructions in LastStage0Insts is greater than
2199/// RequiredTC, and to Otherwise otherwise.
2200void ModuloScheduleExpanderMVE::insertCondBranch(MachineBasicBlock &MBB,
2201 int RequiredTC,
2202 InstrMapTy &LastStage0Insts,
2203 MachineBasicBlock &GreaterThan,
2204 MachineBasicBlock &Otherwise) {
2205 SmallVector<MachineOperand, 4> Cond;
2206 LoopInfo->createRemainingIterationsGreaterCondition(TC: RequiredTC, MBB, Cond,
2207 LastStage0Insts);
2208
2209 if (SwapBranchTargetsMVE) {
2210 // Set SwapBranchTargetsMVE to true if a target prefers to replace TBB and
2211 // FBB for optimal performance.
2212 if (TII->reverseBranchCondition(Cond))
2213 llvm_unreachable("can not reverse branch condition");
2214 TII->insertBranch(MBB, TBB: &Otherwise, FBB: &GreaterThan, Cond, DL: DebugLoc());
2215 } else {
2216 TII->insertBranch(MBB, TBB: &GreaterThan, FBB: &Otherwise, Cond, DL: DebugLoc());
2217 }
2218}
2219
2220/// Generate a pipelined loop that is unrolled by using MVE algorithm and any
2221/// other necessary blocks. The control flow is modified to execute the
2222/// pipelined loop if the trip count satisfies the condition, otherwise the
2223/// original loop. The original loop is also used to execute the remainder
2224/// iterations which occur due to unrolling.
2225void ModuloScheduleExpanderMVE::generatePipelinedLoop() {
2226 // The control flow for pipelining with MVE:
2227 //
2228 // OrigPreheader:
2229 // // The block that is originally the loop preheader
2230 // goto Check
2231 //
2232 // Check:
2233 // // Check whether the trip count satisfies the requirements to pipeline.
2234 // if (LoopCounter > NumStages + NumUnroll - 2)
2235 // // The minimum number of iterations to pipeline =
2236 // // iterations executed in prolog/epilog (NumStages-1) +
2237 // // iterations executed in one kernel run (NumUnroll)
2238 // goto Prolog
2239 // // fallback to the original loop
2240 // goto NewPreheader
2241 //
2242 // Prolog:
2243 // // All prolog stages. There are no direct branches to the epilogue.
2244 // goto NewKernel
2245 //
2246 // NewKernel:
2247 // // NumUnroll copies of the kernel
2248 // if (LoopCounter > MVE-1)
2249 // goto NewKernel
2250 // goto Epilog
2251 //
2252 // Epilog:
2253 // // All epilog stages.
2254 // if (LoopCounter > 0)
2255 // // The remainder is executed in the original loop
2256 // goto NewPreheader
2257 // goto NewExit
2258 //
2259 // NewPreheader:
2260 // // Newly created preheader for the original loop.
2261 // // The initial values of the phis in the loop are merged from two paths.
2262 // NewInitVal = Phi OrigInitVal, Check, PipelineLastVal, Epilog
2263 // goto OrigKernel
2264 //
2265 // OrigKernel:
2266 // // The original loop block.
2267 // if (LoopCounter != 0)
2268 // goto OrigKernel
2269 // goto NewExit
2270 //
2271 // NewExit:
2272 // // Newly created dedicated exit for the original loop.
2273 // // Merge values which are referenced after the loop
2274 // Merged = Phi OrigVal, OrigKernel, PipelineVal, Epilog
2275 // goto OrigExit
2276 //
2277 // OrigExit:
2278 // // The block that is originally the loop exit.
2279 // // If it is already deicated exit, NewExit is not created.
2280
2281 // An example of where each stage is executed:
2282 // Assume #Stages 3, #MVE 4, #Iterations 12
2283 // Iter 0 1 2 3 4 5 6 7 8 9 10-11
2284 // -------------------------------------------------
2285 // Stage 0 Prolog#0
2286 // Stage 1 0 Prolog#1
2287 // Stage 2 1 0 Kernel Unroll#0 Iter#0
2288 // Stage 2 1 0 Kernel Unroll#1 Iter#0
2289 // Stage 2 1 0 Kernel Unroll#2 Iter#0
2290 // Stage 2 1 0 Kernel Unroll#3 Iter#0
2291 // Stage 2 1 0 Kernel Unroll#0 Iter#1
2292 // Stage 2 1 0 Kernel Unroll#1 Iter#1
2293 // Stage 2 1 0 Kernel Unroll#2 Iter#1
2294 // Stage 2 1 0 Kernel Unroll#3 Iter#1
2295 // Stage 2 1 Epilog#0
2296 // Stage 2 Epilog#1
2297 // Stage 0-2 OrigKernel
2298
2299 LoopInfo = TII->analyzeLoopForPipelining(LoopBB: OrigKernel);
2300 assert(LoopInfo && "Must be able to analyze loop!");
2301
2302 calcNumUnroll();
2303
2304 Check = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2305 Prolog = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2306 NewKernel = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2307 Epilog = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2308 NewPreheader = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2309
2310 MF.insert(MBBI: OrigKernel->getIterator(), MBB: Check);
2311 LIS.insertMBBInMaps(MBB: Check);
2312 MF.insert(MBBI: OrigKernel->getIterator(), MBB: Prolog);
2313 LIS.insertMBBInMaps(MBB: Prolog);
2314 MF.insert(MBBI: OrigKernel->getIterator(), MBB: NewKernel);
2315 LIS.insertMBBInMaps(MBB: NewKernel);
2316 MF.insert(MBBI: OrigKernel->getIterator(), MBB: Epilog);
2317 LIS.insertMBBInMaps(MBB: Epilog);
2318 MF.insert(MBBI: OrigKernel->getIterator(), MBB: NewPreheader);
2319 LIS.insertMBBInMaps(MBB: NewPreheader);
2320
2321 NewExit = createDedicatedExit(Loop: OrigKernel, Exit: OrigExit, LIS, MDTU);
2322
2323 NewPreheader->transferSuccessorsAndUpdatePHIs(FromMBB: OrigPreheader);
2324 TII->insertUnconditionalBranch(MBB&: *NewPreheader, DestBB: OrigKernel, DL: DebugLoc());
2325
2326 OrigPreheader->addSuccessor(Succ: Check);
2327 TII->removeBranch(MBB&: *OrigPreheader);
2328 TII->insertUnconditionalBranch(MBB&: *OrigPreheader, DestBB: Check, DL: DebugLoc());
2329
2330 Check->addSuccessor(Succ: Prolog);
2331 Check->addSuccessor(Succ: NewPreheader);
2332
2333 Prolog->addSuccessor(Succ: NewKernel);
2334
2335 NewKernel->addSuccessor(Succ: NewKernel);
2336 NewKernel->addSuccessor(Succ: Epilog);
2337
2338 Epilog->addSuccessor(Succ: NewPreheader);
2339 Epilog->addSuccessor(Succ: NewExit);
2340
2341 MDTU.applyUpdates(
2342 Updates: {{MachineDominatorTree::Insert, NewPreheader, OrigKernel},
2343 {MachineDominatorTree::Insert, OrigPreheader, Check},
2344 {MachineDominatorTree::Insert, Check, Prolog},
2345 {MachineDominatorTree::Insert, Check, NewPreheader},
2346 {MachineDominatorTree::Insert, Prolog, NewKernel},
2347 {MachineDominatorTree::Insert, NewKernel, NewKernel},
2348 {MachineDominatorTree::Insert, NewKernel, Epilog},
2349 {MachineDominatorTree::Insert, Epilog, NewPreheader},
2350 {MachineDominatorTree::Insert, Epilog, NewExit},
2351 {MachineDominatorTree::Delete, OrigPreheader, OrigKernel}});
2352
2353 InstrMapTy LastStage0Insts;
2354 insertCondBranch(MBB&: *Check, RequiredTC: Schedule.getNumStages() + NumUnroll - 2,
2355 LastStage0Insts, GreaterThan&: *Prolog, Otherwise&: *NewPreheader);
2356
2357 // VRMaps map (prolog/kernel/epilog phase#, original register#) to new
2358 // register#
2359 SmallVector<ValueMapTy> PrologVRMap, KernelVRMap, EpilogVRMap;
2360 generateProlog(VRMap&: PrologVRMap);
2361 generateKernel(PrologVRMap, KernelVRMap, LastStage0Insts);
2362 generateEpilog(KernelVRMap, EpilogVRMap, LastStage0Insts);
2363}
2364
2365/// Replace MI's use operands according to the maps.
2366void ModuloScheduleExpanderMVE::updateInstrUse(
2367 MachineInstr *MI, int StageNum, int PhaseNum,
2368 SmallVectorImpl<ValueMapTy> &CurVRMap,
2369 SmallVectorImpl<ValueMapTy> *PrevVRMap) {
2370 // If MI is in the prolog/kernel/epilog block, CurVRMap is
2371 // PrologVRMap/KernelVRMap/EpilogVRMap respectively.
2372 // PrevVRMap is nullptr/PhiVRMap/KernelVRMap respectively.
2373 // Refer to the appropriate map according to the stage difference between
2374 // MI and the definition of an operand.
2375
2376 for (MachineOperand &UseMO : MI->uses()) {
2377 if (!UseMO.isReg() || !UseMO.getReg().isVirtual())
2378 continue;
2379 int DiffStage = 0;
2380 Register OrigReg = UseMO.getReg();
2381 MachineInstr *DefInst = MRI.getVRegDef(Reg: OrigReg);
2382 if (!DefInst || DefInst->getParent() != OrigKernel)
2383 continue;
2384 Register InitReg;
2385 Register DefReg = OrigReg;
2386 if (DefInst->isPHI()) {
2387 ++DiffStage;
2388 Register LoopReg;
2389 getPhiRegs(Phi&: *DefInst, Loop: OrigKernel, InitVal&: InitReg, LoopVal&: LoopReg);
2390 // LoopReg is guaranteed to be defined within the loop by canApply()
2391 DefReg = LoopReg;
2392 DefInst = MRI.getVRegDef(Reg: LoopReg);
2393 }
2394 unsigned DefStageNum = Schedule.getStage(MI: DefInst);
2395 DiffStage += StageNum - DefStageNum;
2396 Register NewReg;
2397 if (PhaseNum >= DiffStage && CurVRMap[PhaseNum - DiffStage].count(Val: DefReg))
2398 // NewReg is defined in a previous phase of the same block
2399 NewReg = CurVRMap[PhaseNum - DiffStage][DefReg];
2400 else if (!PrevVRMap)
2401 // Since this is the first iteration, refer the initial register of the
2402 // loop
2403 NewReg = InitReg;
2404 else
2405 // Cases where DiffStage is larger than PhaseNum.
2406 // If MI is in the kernel block, the value is defined by the previous
2407 // iteration and PhiVRMap is referenced. If MI is in the epilog block, the
2408 // value is defined in the kernel block and KernelVRMap is referenced.
2409 NewReg = (*PrevVRMap)[PrevVRMap->size() - (DiffStage - PhaseNum)][DefReg];
2410
2411 const TargetRegisterClass *NRC =
2412 MRI.constrainRegClass(Reg: NewReg, RC: MRI.getRegClass(Reg: OrigReg));
2413 if (NRC)
2414 UseMO.setReg(NewReg);
2415 else {
2416 Register SplitReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigReg));
2417 MachineInstr *NewCopy = BuildMI(BB&: *OrigKernel, I: MI, MIMD: MI->getDebugLoc(),
2418 MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: SplitReg)
2419 .addReg(RegNo: NewReg);
2420 LIS.InsertMachineInstrInMaps(MI&: *NewCopy);
2421 UseMO.setReg(SplitReg);
2422 }
2423 }
2424}
2425
2426/// Return a phi if Reg is referenced by the phi.
2427/// canApply() guarantees that at most only one such phi exists.
2428static MachineInstr *getLoopPhiUser(Register Reg, MachineBasicBlock *Loop) {
2429 for (MachineInstr &Phi : Loop->phis()) {
2430 Register InitVal, LoopVal;
2431 getPhiRegs(Phi, Loop, InitVal, LoopVal);
2432 if (LoopVal == Reg)
2433 return &Phi;
2434 }
2435 return nullptr;
2436}
2437
2438/// Generate phis for registers defined by OrigMI.
2439void ModuloScheduleExpanderMVE::generatePhi(
2440 MachineInstr *OrigMI, int UnrollNum,
2441 SmallVectorImpl<ValueMapTy> &PrologVRMap,
2442 SmallVectorImpl<ValueMapTy> &KernelVRMap,
2443 SmallVectorImpl<ValueMapTy> &PhiVRMap) {
2444 int StageNum = Schedule.getStage(MI: OrigMI);
2445 bool UsePrologReg;
2446 if (Schedule.getNumStages() - NumUnroll + UnrollNum - 1 >= StageNum)
2447 UsePrologReg = true;
2448 else if (Schedule.getNumStages() - NumUnroll + UnrollNum == StageNum)
2449 UsePrologReg = false;
2450 else
2451 return;
2452
2453 // Examples that show which stages are merged by phi.
2454 // Meaning of the symbol following the stage number:
2455 // a/b: Stages with the same letter are merged (UsePrologReg == true)
2456 // +: Merged with the initial value (UsePrologReg == false)
2457 // *: No phis required
2458 //
2459 // #Stages 3, #MVE 4
2460 // Iter 0 1 2 3 4 5 6 7 8
2461 // -----------------------------------------
2462 // Stage 0a Prolog#0
2463 // Stage 1a 0b Prolog#1
2464 // Stage 2* 1* 0* Kernel Unroll#0
2465 // Stage 2* 1* 0+ Kernel Unroll#1
2466 // Stage 2* 1+ 0a Kernel Unroll#2
2467 // Stage 2+ 1a 0b Kernel Unroll#3
2468 //
2469 // #Stages 3, #MVE 2
2470 // Iter 0 1 2 3 4 5 6 7 8
2471 // -----------------------------------------
2472 // Stage 0a Prolog#0
2473 // Stage 1a 0b Prolog#1
2474 // Stage 2* 1+ 0a Kernel Unroll#0
2475 // Stage 2+ 1a 0b Kernel Unroll#1
2476 //
2477 // #Stages 3, #MVE 1
2478 // Iter 0 1 2 3 4 5 6 7 8
2479 // -----------------------------------------
2480 // Stage 0* Prolog#0
2481 // Stage 1a 0b Prolog#1
2482 // Stage 2+ 1a 0b Kernel Unroll#0
2483
2484 for (MachineOperand &DefMO : OrigMI->defs()) {
2485 if (!DefMO.isReg() || DefMO.isDead())
2486 continue;
2487 Register OrigReg = DefMO.getReg();
2488 auto NewReg = KernelVRMap[UnrollNum].find(Val: OrigReg);
2489 if (NewReg == KernelVRMap[UnrollNum].end())
2490 continue;
2491 Register CorrespondReg;
2492 if (UsePrologReg) {
2493 int PrologNum = Schedule.getNumStages() - NumUnroll + UnrollNum - 1;
2494 CorrespondReg = PrologVRMap[PrologNum][OrigReg];
2495 } else {
2496 MachineInstr *Phi = getLoopPhiUser(Reg: OrigReg, Loop: OrigKernel);
2497 if (!Phi)
2498 continue;
2499 CorrespondReg = getInitPhiReg(Phi&: *Phi, LoopBB: OrigKernel);
2500 }
2501
2502 assert(CorrespondReg.isValid());
2503 Register PhiReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigReg));
2504 MachineInstr *NewPhi =
2505 BuildMI(BB&: *NewKernel, I: NewKernel->getFirstNonPHI(), MIMD: DebugLoc(),
2506 MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: PhiReg)
2507 .addReg(RegNo: NewReg->second)
2508 .addMBB(MBB: NewKernel)
2509 .addReg(RegNo: CorrespondReg)
2510 .addMBB(MBB: Prolog);
2511 LIS.InsertMachineInstrInMaps(MI&: *NewPhi);
2512 PhiVRMap[UnrollNum][OrigReg] = PhiReg;
2513 }
2514}
2515
2516static void replacePhiSrc(MachineInstr &Phi, Register OrigReg, Register NewReg,
2517 MachineBasicBlock *NewMBB) {
2518 for (unsigned Idx = 1; Idx < Phi.getNumOperands(); Idx += 2) {
2519 if (Phi.getOperand(i: Idx).getReg() == OrigReg) {
2520 Phi.getOperand(i: Idx).setReg(NewReg);
2521 Phi.getOperand(i: Idx + 1).setMBB(NewMBB);
2522 return;
2523 }
2524 }
2525}
2526
2527/// Generate phis that merge values from multiple routes
2528void ModuloScheduleExpanderMVE::mergeRegUsesAfterPipeline(Register OrigReg,
2529 Register NewReg) {
2530 SmallVector<MachineOperand *> UsesAfterLoop;
2531 SmallVector<MachineInstr *> LoopPhis;
2532 for (MachineRegisterInfo::use_iterator I = MRI.use_begin(RegNo: OrigReg),
2533 E = MRI.use_end();
2534 I != E; ++I) {
2535 MachineOperand &O = *I;
2536 if (O.getParent()->getParent() != OrigKernel &&
2537 O.getParent()->getParent() != Prolog &&
2538 O.getParent()->getParent() != NewKernel &&
2539 O.getParent()->getParent() != Epilog)
2540 UsesAfterLoop.push_back(Elt: &O);
2541 if (O.getParent()->getParent() == OrigKernel && O.getParent()->isPHI())
2542 LoopPhis.push_back(Elt: O.getParent());
2543 }
2544
2545 // Merge the route that only execute the pipelined loop (when there are no
2546 // remaining iterations) with the route that execute the original loop.
2547 if (!UsesAfterLoop.empty()) {
2548 Register PhiReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigReg));
2549 MachineInstr *NewPhi =
2550 BuildMI(BB&: *NewExit, I: NewExit->getFirstNonPHI(), MIMD: DebugLoc(),
2551 MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: PhiReg)
2552 .addReg(RegNo: OrigReg)
2553 .addMBB(MBB: OrigKernel)
2554 .addReg(RegNo: NewReg)
2555 .addMBB(MBB: Epilog);
2556 LIS.InsertMachineInstrInMaps(MI&: *NewPhi);
2557
2558 for (MachineOperand *MO : UsesAfterLoop)
2559 MO->setReg(PhiReg);
2560
2561 // The interval of OrigReg is invalid and should be recalculated when
2562 // LiveInterval::getInterval() is called.
2563 if (LIS.hasInterval(Reg: OrigReg))
2564 LIS.removeInterval(Reg: OrigReg);
2565 }
2566
2567 // Merge routes from the pipelined loop and the bypassed route before the
2568 // original loop
2569 if (!LoopPhis.empty()) {
2570 for (MachineInstr *Phi : LoopPhis) {
2571 Register InitReg, LoopReg;
2572 getPhiRegs(Phi&: *Phi, Loop: OrigKernel, InitVal&: InitReg, LoopVal&: LoopReg);
2573 Register NewInit = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: InitReg));
2574 MachineInstr *NewPhi =
2575 BuildMI(BB&: *NewPreheader, I: NewPreheader->getFirstNonPHI(),
2576 MIMD: Phi->getDebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: NewInit)
2577 .addReg(RegNo: InitReg)
2578 .addMBB(MBB: Check)
2579 .addReg(RegNo: NewReg)
2580 .addMBB(MBB: Epilog);
2581 LIS.InsertMachineInstrInMaps(MI&: *NewPhi);
2582 replacePhiSrc(Phi&: *Phi, OrigReg: InitReg, NewReg: NewInit, NewMBB: NewPreheader);
2583 }
2584 }
2585}
2586
2587void ModuloScheduleExpanderMVE::generateProlog(
2588 SmallVectorImpl<ValueMapTy> &PrologVRMap) {
2589 PrologVRMap.clear();
2590 PrologVRMap.resize(N: Schedule.getNumStages() - 1);
2591 DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;
2592 for (int PrologNum = 0; PrologNum < Schedule.getNumStages() - 1;
2593 ++PrologNum) {
2594 for (MachineInstr *MI : Schedule.getInstructions()) {
2595 if (MI->isPHI())
2596 continue;
2597 int StageNum = Schedule.getStage(MI);
2598 if (StageNum > PrologNum)
2599 continue;
2600 MachineInstr *NewMI = cloneInstr(OldMI: MI);
2601 updateInstrDef(NewMI, VRMap&: PrologVRMap[PrologNum], LastDef: false);
2602 NewMIMap[NewMI] = {PrologNum, StageNum};
2603 Prolog->push_back(MI: NewMI);
2604 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
2605 }
2606 }
2607
2608 for (auto I : NewMIMap) {
2609 MachineInstr *MI = I.first;
2610 int PrologNum = I.second.first;
2611 int StageNum = I.second.second;
2612 updateInstrUse(MI, StageNum, PhaseNum: PrologNum, CurVRMap&: PrologVRMap, PrevVRMap: nullptr);
2613 }
2614
2615 LLVM_DEBUG({
2616 dbgs() << "prolog:\n";
2617 Prolog->dump();
2618 });
2619}
2620
2621void ModuloScheduleExpanderMVE::generateKernel(
2622 SmallVectorImpl<ValueMapTy> &PrologVRMap,
2623 SmallVectorImpl<ValueMapTy> &KernelVRMap, InstrMapTy &LastStage0Insts) {
2624 KernelVRMap.clear();
2625 KernelVRMap.resize(N: NumUnroll);
2626 SmallVector<ValueMapTy> PhiVRMap;
2627 PhiVRMap.resize(N: NumUnroll);
2628 DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;
2629 for (int UnrollNum = 0; UnrollNum < NumUnroll; ++UnrollNum) {
2630 for (MachineInstr *MI : Schedule.getInstructions()) {
2631 if (MI->isPHI())
2632 continue;
2633 int StageNum = Schedule.getStage(MI);
2634 MachineInstr *NewMI = cloneInstr(OldMI: MI);
2635 if (UnrollNum == NumUnroll - 1)
2636 LastStage0Insts[MI] = NewMI;
2637 updateInstrDef(NewMI, VRMap&: KernelVRMap[UnrollNum],
2638 LastDef: (UnrollNum == NumUnroll - 1 && StageNum == 0));
2639 generatePhi(OrigMI: MI, UnrollNum, PrologVRMap, KernelVRMap, PhiVRMap);
2640 NewMIMap[NewMI] = {UnrollNum, StageNum};
2641 NewKernel->push_back(MI: NewMI);
2642 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
2643 }
2644 }
2645
2646 for (auto I : NewMIMap) {
2647 MachineInstr *MI = I.first;
2648 int UnrollNum = I.second.first;
2649 int StageNum = I.second.second;
2650 updateInstrUse(MI, StageNum, PhaseNum: UnrollNum, CurVRMap&: KernelVRMap, PrevVRMap: &PhiVRMap);
2651 }
2652
2653 // If remaining trip count is greater than NumUnroll-1, loop continues
2654 insertCondBranch(MBB&: *NewKernel, RequiredTC: NumUnroll - 1, LastStage0Insts, GreaterThan&: *NewKernel,
2655 Otherwise&: *Epilog);
2656
2657 LLVM_DEBUG({
2658 dbgs() << "kernel:\n";
2659 NewKernel->dump();
2660 });
2661}
2662
2663void ModuloScheduleExpanderMVE::generateEpilog(
2664 SmallVectorImpl<ValueMapTy> &KernelVRMap,
2665 SmallVectorImpl<ValueMapTy> &EpilogVRMap, InstrMapTy &LastStage0Insts) {
2666 EpilogVRMap.clear();
2667 EpilogVRMap.resize(N: Schedule.getNumStages() - 1);
2668 DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;
2669 for (int EpilogNum = 0; EpilogNum < Schedule.getNumStages() - 1;
2670 ++EpilogNum) {
2671 for (MachineInstr *MI : Schedule.getInstructions()) {
2672 if (MI->isPHI())
2673 continue;
2674 int StageNum = Schedule.getStage(MI);
2675 if (StageNum <= EpilogNum)
2676 continue;
2677 MachineInstr *NewMI = cloneInstr(OldMI: MI);
2678 updateInstrDef(NewMI, VRMap&: EpilogVRMap[EpilogNum], LastDef: StageNum - 1 == EpilogNum);
2679 NewMIMap[NewMI] = {EpilogNum, StageNum};
2680 Epilog->push_back(MI: NewMI);
2681 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
2682 }
2683 }
2684
2685 for (auto I : NewMIMap) {
2686 MachineInstr *MI = I.first;
2687 int EpilogNum = I.second.first;
2688 int StageNum = I.second.second;
2689 updateInstrUse(MI, StageNum, PhaseNum: EpilogNum, CurVRMap&: EpilogVRMap, PrevVRMap: &KernelVRMap);
2690 }
2691
2692 // If there are remaining iterations, they are executed in the original loop.
2693 // Instructions related to loop control, such as loop counter comparison,
2694 // are indicated by shouldIgnoreForPipelining() and are assumed to be placed
2695 // in stage 0. Thus, the map is for the last one in the kernel.
2696 insertCondBranch(MBB&: *Epilog, RequiredTC: 0, LastStage0Insts, GreaterThan&: *NewPreheader, Otherwise&: *NewExit);
2697
2698 LLVM_DEBUG({
2699 dbgs() << "epilog:\n";
2700 Epilog->dump();
2701 });
2702}
2703
2704/// Calculate the number of unroll required and set it to NumUnroll
2705void ModuloScheduleExpanderMVE::calcNumUnroll() {
2706 DenseMap<MachineInstr *, unsigned> Inst2Idx;
2707 NumUnroll = 1;
2708 for (unsigned I = 0; I < Schedule.getInstructions().size(); ++I)
2709 Inst2Idx[Schedule.getInstructions()[I]] = I;
2710
2711 for (MachineInstr *MI : Schedule.getInstructions()) {
2712 if (MI->isPHI())
2713 continue;
2714 int StageNum = Schedule.getStage(MI);
2715 for (const MachineOperand &MO : MI->uses()) {
2716 if (!MO.isReg() || !MO.getReg().isVirtual())
2717 continue;
2718 MachineInstr *DefMI = MRI.getVRegDef(Reg: MO.getReg());
2719 if (DefMI->getParent() != OrigKernel)
2720 continue;
2721
2722 int NumUnrollLocal = 1;
2723 if (DefMI->isPHI()) {
2724 ++NumUnrollLocal;
2725 // canApply() guarantees that DefMI is not phi and is an instruction in
2726 // the loop
2727 DefMI = MRI.getVRegDef(Reg: getLoopPhiReg(Phi&: *DefMI, LoopBB: OrigKernel));
2728 }
2729 NumUnrollLocal += StageNum - Schedule.getStage(MI: DefMI);
2730 if (Inst2Idx[MI] <= Inst2Idx[DefMI])
2731 --NumUnrollLocal;
2732 NumUnroll = std::max(a: NumUnroll, b: NumUnrollLocal);
2733 }
2734 }
2735 LLVM_DEBUG(dbgs() << "NumUnroll: " << NumUnroll << "\n");
2736}
2737
2738/// Create new virtual registers for definitions of NewMI and update NewMI.
2739/// If the definitions are referenced after the pipelined loop, phis are
2740/// created to merge with other routes.
2741void ModuloScheduleExpanderMVE::updateInstrDef(MachineInstr *NewMI,
2742 ValueMapTy &VRMap,
2743 bool LastDef) {
2744 for (MachineOperand &MO : NewMI->all_defs()) {
2745 if (!MO.getReg().isVirtual())
2746 continue;
2747 Register Reg = MO.getReg();
2748 const TargetRegisterClass *RC = MRI.getRegClass(Reg);
2749 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
2750 MO.setReg(NewReg);
2751 VRMap[Reg] = NewReg;
2752 if (LastDef)
2753 mergeRegUsesAfterPipeline(OrigReg: Reg, NewReg);
2754 }
2755}
2756
2757void ModuloScheduleExpanderMVE::expand() {
2758 OrigKernel = Schedule.getLoop()->getTopBlock();
2759 OrigPreheader = Schedule.getLoop()->getLoopPreheader();
2760 OrigExit = Schedule.getLoop()->getExitBlock();
2761
2762 LLVM_DEBUG(Schedule.dump());
2763
2764 generatePipelinedLoop();
2765}
2766
2767/// Check if ModuloScheduleExpanderMVE can be applied to L
2768bool ModuloScheduleExpanderMVE::canApply(MachineLoop &L) {
2769 if (!L.getExitBlock()) {
2770 LLVM_DEBUG(dbgs() << "Can not apply MVE expander: No single exit block.\n");
2771 return false;
2772 }
2773
2774 MachineBasicBlock *BB = L.getTopBlock();
2775 MachineRegisterInfo &MRI = BB->getParent()->getRegInfo();
2776
2777 // Put some constraints on the operands of the phis to simplify the
2778 // transformation
2779 DenseSet<Register> UsedByPhi;
2780 for (MachineInstr &MI : BB->phis()) {
2781 // Registers defined by phis must be used only inside the loop and be never
2782 // used by phis.
2783 for (MachineOperand &MO : MI.defs())
2784 if (MO.isReg())
2785 for (MachineInstr &Ref : MRI.use_instructions(Reg: MO.getReg()))
2786 if (Ref.getParent() != BB || Ref.isPHI()) {
2787 LLVM_DEBUG(dbgs() << "Can not apply MVE expander: A phi result is "
2788 "referenced outside of the loop or by phi.\n");
2789 return false;
2790 }
2791
2792 // A source register from the loop block must be defined inside the loop.
2793 // A register defined inside the loop must be referenced by only one phi at
2794 // most.
2795 Register InitVal, LoopVal;
2796 getPhiRegs(Phi&: MI, Loop: MI.getParent(), InitVal, LoopVal);
2797 if (!Register(LoopVal).isVirtual() || MRI.getDefBlock(Reg: LoopVal) != BB) {
2798 LLVM_DEBUG(
2799 dbgs() << "Can not apply MVE expander: A phi source value coming "
2800 "from the loop is not defined in the loop.\n");
2801 return false;
2802 }
2803 if (UsedByPhi.count(V: LoopVal)) {
2804 LLVM_DEBUG(dbgs() << "Can not apply MVE expander: A value defined in the "
2805 "loop is referenced by two or more phis.\n");
2806 return false;
2807 }
2808 UsedByPhi.insert(V: LoopVal);
2809 }
2810
2811 return true;
2812}
2813
2814//===----------------------------------------------------------------------===//
2815// ModuloScheduleTestPass implementation
2816//===----------------------------------------------------------------------===//
2817// This pass constructs a ModuloSchedule from its module and runs
2818// ModuloScheduleExpander.
2819//
2820// The module is expected to contain a single-block analyzable loop.
2821// The total order of instructions is taken from the loop as-is.
2822// Instructions are expected to be annotated with a PostInstrSymbol.
2823// This PostInstrSymbol must have the following format:
2824// "Stage=%d Cycle=%d".
2825//===----------------------------------------------------------------------===//
2826
2827namespace {
2828class ModuloScheduleTest : public MachineFunctionPass {
2829public:
2830 static char ID;
2831
2832 ModuloScheduleTest() : MachineFunctionPass(ID) {}
2833
2834 bool runOnMachineFunction(MachineFunction &MF) override;
2835 void runOnLoop(MachineFunction &MF, MachineLoop &L);
2836
2837 void getAnalysisUsage(AnalysisUsage &AU) const override {
2838 AU.addRequired<MachineLoopInfoWrapperPass>();
2839 AU.addRequired<LiveIntervalsWrapperPass>();
2840 MachineFunctionPass::getAnalysisUsage(AU);
2841 }
2842};
2843} // namespace
2844
2845char ModuloScheduleTest::ID = 0;
2846
2847INITIALIZE_PASS_BEGIN(ModuloScheduleTest, "modulo-schedule-test",
2848 "Modulo Schedule test pass", false, false)
2849INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
2850INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
2851INITIALIZE_PASS_END(ModuloScheduleTest, "modulo-schedule-test",
2852 "Modulo Schedule test pass", false, false)
2853
2854bool ModuloScheduleTest::runOnMachineFunction(MachineFunction &MF) {
2855 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
2856 for (auto *L : MLI) {
2857 if (L->getTopBlock() != L->getBottomBlock())
2858 continue;
2859 runOnLoop(MF, L&: *L);
2860 return false;
2861 }
2862 return false;
2863}
2864
2865static void parseSymbolString(StringRef S, int &Cycle, int &Stage) {
2866 std::pair<StringRef, StringRef> StageAndCycle = getToken(Source: S, Delimiters: "_");
2867 std::pair<StringRef, StringRef> StageTokenAndValue =
2868 getToken(Source: StageAndCycle.first, Delimiters: "-");
2869 std::pair<StringRef, StringRef> CycleTokenAndValue =
2870 getToken(Source: StageAndCycle.second, Delimiters: "-");
2871 if (StageTokenAndValue.first != "Stage" ||
2872 CycleTokenAndValue.first != "_Cycle") {
2873 llvm_unreachable(
2874 "Bad post-instr symbol syntax: see comment in ModuloScheduleTest");
2875 return;
2876 }
2877
2878 StageTokenAndValue.second.drop_front().getAsInteger(Radix: 10, Result&: Stage);
2879 CycleTokenAndValue.second.drop_front().getAsInteger(Radix: 10, Result&: Cycle);
2880
2881 dbgs() << " Stage=" << Stage << ", Cycle=" << Cycle << "\n";
2882}
2883
2884void ModuloScheduleTest::runOnLoop(MachineFunction &MF, MachineLoop &L) {
2885 LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
2886 MachineBasicBlock *BB = L.getTopBlock();
2887 dbgs() << "--- ModuloScheduleTest running on BB#" << BB->getNumber() << "\n";
2888
2889 DenseMap<MachineInstr *, int> Cycle, Stage;
2890 std::vector<MachineInstr *> Instrs;
2891 for (MachineInstr &MI : *BB) {
2892 if (MI.isTerminator())
2893 continue;
2894 Instrs.push_back(x: &MI);
2895 if (MCSymbol *Sym = MI.getPostInstrSymbol()) {
2896 dbgs() << "Parsing post-instr symbol for " << MI;
2897 parseSymbolString(S: Sym->getName(), Cycle&: Cycle[&MI], Stage&: Stage[&MI]);
2898 }
2899 }
2900
2901 ModuloSchedule MS(MF, &L, std::move(Instrs), std::move(Cycle),
2902 std::move(Stage));
2903 ModuloScheduleExpander MSE(
2904 MF, MS, LIS, /*InstrChanges=*/ModuloScheduleExpander::InstrChangesTy());
2905 MSE.expand();
2906 MSE.cleanup();
2907}
2908
2909//===----------------------------------------------------------------------===//
2910// ModuloScheduleTestAnnotater implementation
2911//===----------------------------------------------------------------------===//
2912
2913void ModuloScheduleTestAnnotater::annotate() {
2914 for (MachineInstr *MI : S.getInstructions()) {
2915 SmallVector<char, 16> SV;
2916 raw_svector_ostream OS(SV);
2917 OS << "Stage-" << S.getStage(MI) << "_Cycle-" << S.getCycle(MI);
2918 MCSymbol *Sym = MF.getContext().getOrCreateSymbol(Name: OS.str());
2919 MI->setPostInstrSymbol(MF, Symbol: Sym);
2920 }
2921}
2922