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