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 MachineOperand *BaseOp;
937 int64_t Offset;
938 bool OffsetIsScalable;
939 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable))
940 return false;
941
942 // FIXME: This algorithm assumes instructions have fixed-size offsets.
943 if (OffsetIsScalable)
944 return false;
945
946 if (!BaseOp->isReg())
947 return false;
948
949 Register BaseReg = BaseOp->getReg();
950 if (!BaseReg.isVirtual())
951 return false;
952
953 MachineRegisterInfo &MRI = MF.getRegInfo();
954 // Check if there is a Phi. If so, get the definition in the loop.
955 MachineInstr *BaseDef = MRI.getVRegDef(Reg: BaseReg);
956 if (BaseDef && BaseDef->isPHI()) {
957 BaseReg = getLoopPhiReg(Phi&: *BaseDef, LoopBB: MI.getParent());
958 BaseDef = MRI.getVRegDef(Reg: BaseReg);
959 }
960 if (!BaseDef)
961 return false;
962
963 int D = 0;
964 if (!TII->getIncrementValue(MI: *BaseDef, Value&: D) && D >= 0)
965 return false;
966
967 Delta = D;
968 return true;
969}
970
971/// Update the memory operand with a new offset when the pipeliner
972/// generates a new copy of the instruction that refers to a
973/// different memory location.
974void ModuloScheduleExpander::updateMemOperands(MachineInstr &NewMI,
975 MachineInstr &OldMI,
976 unsigned Num) {
977 if (Num == 0)
978 return;
979 // If the instruction has memory operands, then adjust the offset
980 // when the instruction appears in different stages.
981 if (NewMI.memoperands_empty())
982 return;
983 SmallVector<MachineMemOperand *, 2> NewMMOs;
984 for (MachineMemOperand *MMO : NewMI.memoperands()) {
985 // TODO: Figure out whether isAtomic is really necessary (see D57601).
986 if (MMO->isVolatile() || MMO->isAtomic() ||
987 (MMO->isInvariant() && MMO->isDereferenceable()) ||
988 (!MMO->getValue())) {
989 NewMMOs.push_back(Elt: MMO);
990 continue;
991 }
992 unsigned Delta;
993 if (Num != UINT_MAX && computeDelta(MI&: OldMI, Delta)) {
994 int64_t AdjOffset = static_cast<int64_t>(Delta) * Num;
995 NewMMOs.push_back(
996 Elt: MF.getMachineMemOperand(MMO, Offset: AdjOffset, Size: MMO->getSize()));
997 } else {
998 NewMMOs.push_back(Elt: MF.getMachineMemOperand(
999 MMO, Offset: 0, Size: LocationSize::beforeOrAfterPointer()));
1000 }
1001 }
1002 NewMI.setMemRefs(MF, MemRefs: NewMMOs);
1003}
1004
1005/// Clone the instruction for the new pipelined loop and update the
1006/// memory operands, if needed.
1007MachineInstr *ModuloScheduleExpander::cloneInstr(MachineInstr *OldMI,
1008 unsigned CurStageNum,
1009 unsigned InstStageNum) {
1010 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: OldMI);
1011 updateMemOperands(NewMI&: *NewMI, OldMI&: *OldMI, Num: CurStageNum - InstStageNum);
1012 return NewMI;
1013}
1014
1015/// Clone the instruction for the new pipelined loop. If needed, this
1016/// function updates the instruction using the values saved in the
1017/// InstrChanges structure.
1018MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
1019 MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum) {
1020 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: OldMI);
1021 auto It = InstrChanges.find(Val: OldMI);
1022 if (It != InstrChanges.end()) {
1023 std::pair<Register, int64_t> RegAndOffset = It->second;
1024 unsigned BasePos, OffsetPos;
1025 if (!TII->getBaseAndOffsetPosition(MI: *OldMI, BasePos, OffsetPos))
1026 return nullptr;
1027 int64_t NewOffset = OldMI->getOperand(i: OffsetPos).getImm();
1028 MachineInstr *LoopDef = findDefInLoop(Reg: RegAndOffset.first);
1029 if (Schedule.getStage(MI: LoopDef) > (signed)InstStageNum)
1030 NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
1031 NewMI->getOperand(i: OffsetPos).setImm(NewOffset);
1032 }
1033 updateMemOperands(NewMI&: *NewMI, OldMI&: *OldMI, Num: CurStageNum - InstStageNum);
1034 return NewMI;
1035}
1036
1037/// Update the machine instruction with new virtual registers. This
1038/// function may change the definitions and/or uses.
1039void ModuloScheduleExpander::updateInstruction(MachineInstr *NewMI,
1040 bool LastDef,
1041 unsigned CurStageNum,
1042 unsigned InstrStageNum,
1043 ValueMapTy *VRMap) {
1044 for (MachineOperand &MO : NewMI->operands()) {
1045 if (!MO.isReg() || !MO.getReg().isVirtual())
1046 continue;
1047 Register reg = MO.getReg();
1048 if (MO.isDef()) {
1049 // Create a new virtual register for the definition.
1050 const TargetRegisterClass *RC = MRI.getRegClass(Reg: reg);
1051 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
1052 MO.setReg(NewReg);
1053 VRMap[CurStageNum][reg] = NewReg;
1054 if (LastDef)
1055 replaceRegUsesAfterLoop(FromReg: reg, ToReg: NewReg, MBB: BB, MRI);
1056 } else if (MO.isUse()) {
1057 MachineInstr *Def = MRI.getVRegDef(Reg: reg);
1058 // Compute the stage that contains the last definition for instruction.
1059 int DefStageNum = Schedule.getStage(MI: Def);
1060 unsigned StageNum = CurStageNum;
1061 if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) {
1062 // Compute the difference in stages between the defintion and the use.
1063 unsigned StageDiff = (InstrStageNum - DefStageNum);
1064 // Make an adjustment to get the last definition.
1065 StageNum -= StageDiff;
1066 }
1067 if (auto It = VRMap[StageNum].find(Val: reg); It != VRMap[StageNum].end())
1068 MO.setReg(It->second);
1069 }
1070 }
1071}
1072
1073/// Return the instruction in the loop that defines the register.
1074/// If the definition is a Phi, then follow the Phi operand to
1075/// the instruction in the loop.
1076MachineInstr *ModuloScheduleExpander::findDefInLoop(Register Reg) {
1077 SmallPtrSet<MachineInstr *, 8> Visited;
1078 MachineInstr *Def = MRI.getVRegDef(Reg);
1079 while (Def->isPHI()) {
1080 if (!Visited.insert(Ptr: Def).second)
1081 break;
1082 for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
1083 if (Def->getOperand(i: i + 1).getMBB() == BB) {
1084 Def = MRI.getVRegDef(Reg: Def->getOperand(i).getReg());
1085 break;
1086 }
1087 }
1088 return Def;
1089}
1090
1091/// Return the new name for the value from the previous stage.
1092Register ModuloScheduleExpander::getPrevMapVal(
1093 unsigned StageNum, unsigned PhiStage, Register LoopVal, unsigned LoopStage,
1094 ValueMapTy *VRMap, MachineBasicBlock *BB) {
1095 Register PrevVal;
1096 if (StageNum > PhiStage) {
1097 MachineInstr *LoopInst = MRI.getVRegDef(Reg: LoopVal);
1098 if (PhiStage == LoopStage && VRMap[StageNum - 1].count(Val: LoopVal))
1099 // The name is defined in the previous stage.
1100 PrevVal = VRMap[StageNum - 1][LoopVal];
1101 else if (VRMap[StageNum].count(Val: LoopVal))
1102 // The previous name is defined in the current stage when the instruction
1103 // order is swapped.
1104 PrevVal = VRMap[StageNum][LoopVal];
1105 else if (!LoopInst->isPHI() || LoopInst->getParent() != BB)
1106 // The loop value hasn't yet been scheduled.
1107 PrevVal = LoopVal;
1108 else if (StageNum == PhiStage + 1)
1109 // The loop value is another phi, which has not been scheduled.
1110 PrevVal = getInitPhiReg(Phi&: *LoopInst, LoopBB: BB);
1111 else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB)
1112 // The loop value is another phi, which has been scheduled.
1113 PrevVal =
1114 getPrevMapVal(StageNum: StageNum - 1, PhiStage, LoopVal: getLoopPhiReg(Phi&: *LoopInst, LoopBB: BB),
1115 LoopStage, VRMap, BB);
1116 }
1117 return PrevVal;
1118}
1119
1120/// Rewrite the Phi values in the specified block to use the mappings
1121/// from the initial operand. Once the Phi is scheduled, we switch
1122/// to using the loop value instead of the Phi value, so those names
1123/// do not need to be rewritten.
1124void ModuloScheduleExpander::rewritePhiValues(MachineBasicBlock *NewBB,
1125 unsigned StageNum,
1126 ValueMapTy *VRMap,
1127 InstrMapTy &InstrMap) {
1128 for (auto &PHI : BB->phis()) {
1129 Register InitVal;
1130 Register LoopVal;
1131 getPhiRegs(Phi&: PHI, Loop: BB, InitVal, LoopVal);
1132 Register PhiDef = PHI.getOperand(i: 0).getReg();
1133
1134 unsigned PhiStage = (unsigned)Schedule.getStage(MI: MRI.getVRegDef(Reg: PhiDef));
1135 unsigned LoopStage = (unsigned)Schedule.getStage(MI: MRI.getVRegDef(Reg: LoopVal));
1136 unsigned NumPhis = getStagesForPhi(Reg: PhiDef);
1137 if (NumPhis > StageNum)
1138 NumPhis = StageNum;
1139 for (unsigned np = 0; np <= NumPhis; ++np) {
1140 Register NewVal =
1141 getPrevMapVal(StageNum: StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
1142 if (!NewVal)
1143 NewVal = InitVal;
1144 rewriteScheduledInstr(BB: NewBB, InstrMap, CurStageNum: StageNum - np, PhiNum: np, Phi: &PHI, OldReg: PhiDef,
1145 NewReg: NewVal);
1146 }
1147 }
1148}
1149
1150/// Rewrite a previously scheduled instruction to use the register value
1151/// from the new instruction. Make sure the instruction occurs in the
1152/// basic block, and we don't change the uses in the new instruction.
1153void ModuloScheduleExpander::rewriteScheduledInstr(
1154 MachineBasicBlock *BB, InstrMapTy &InstrMap, unsigned CurStageNum,
1155 unsigned PhiNum, MachineInstr *Phi, Register OldReg, Register NewReg,
1156 Register PrevReg) {
1157 bool InProlog = (CurStageNum < (unsigned)Schedule.getNumStages() - 1);
1158 int StagePhi = Schedule.getStage(MI: Phi) + PhiNum;
1159 // Rewrite uses that have been scheduled already to use the new
1160 // Phi register.
1161 for (MachineOperand &UseOp :
1162 llvm::make_early_inc_range(Range: MRI.use_operands(Reg: OldReg))) {
1163 MachineInstr *UseMI = UseOp.getParent();
1164 if (UseMI->getParent() != BB)
1165 continue;
1166 if (UseMI->isPHI()) {
1167 if (!Phi->isPHI() && UseMI->getOperand(i: 0).getReg() == NewReg)
1168 continue;
1169 if (getLoopPhiReg(Phi&: *UseMI, LoopBB: BB) != OldReg)
1170 continue;
1171 }
1172 InstrMapTy::iterator OrigInstr = InstrMap.find(Val: UseMI);
1173 assert(OrigInstr != InstrMap.end() && "Instruction not scheduled.");
1174 MachineInstr *OrigMI = OrigInstr->second;
1175 int StageSched = Schedule.getStage(MI: OrigMI);
1176 int CycleSched = Schedule.getCycle(MI: OrigMI);
1177 Register ReplaceReg;
1178 // This is the stage for the scheduled instruction.
1179 if (StagePhi == StageSched && Phi->isPHI()) {
1180 int CyclePhi = Schedule.getCycle(MI: Phi);
1181 if (PrevReg && InProlog)
1182 ReplaceReg = PrevReg;
1183 else if (PrevReg && !isLoopCarried(Phi&: *Phi) &&
1184 (CyclePhi <= CycleSched || OrigMI->isPHI()))
1185 ReplaceReg = PrevReg;
1186 else
1187 ReplaceReg = NewReg;
1188 }
1189 // The scheduled instruction occurs before the scheduled Phi, and the
1190 // Phi is not loop carried.
1191 if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(Phi&: *Phi))
1192 ReplaceReg = NewReg;
1193 if (StagePhi > StageSched && Phi->isPHI())
1194 ReplaceReg = NewReg;
1195 if (!InProlog && !Phi->isPHI() && StagePhi < StageSched)
1196 ReplaceReg = NewReg;
1197 if (ReplaceReg) {
1198 const TargetRegisterClass *NRC =
1199 MRI.constrainRegClass(Reg: ReplaceReg, RC: MRI.getRegClass(Reg: OldReg));
1200 if (NRC)
1201 UseOp.setReg(ReplaceReg);
1202 else {
1203 Register SplitReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OldReg));
1204 MachineInstr *newCopy = BuildMI(BB&: *BB, I: UseMI, MIMD: UseMI->getDebugLoc(),
1205 MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: SplitReg)
1206 .addReg(RegNo: ReplaceReg);
1207 UseOp.setReg(SplitReg);
1208 LIS.InsertMachineInstrInMaps(MI&: *newCopy);
1209 }
1210 }
1211 }
1212}
1213
1214bool ModuloScheduleExpander::isLoopCarried(MachineInstr &Phi) {
1215 if (!Phi.isPHI())
1216 return false;
1217 int DefCycle = Schedule.getCycle(MI: &Phi);
1218 int DefStage = Schedule.getStage(MI: &Phi);
1219
1220 Register InitVal;
1221 Register LoopVal;
1222 getPhiRegs(Phi, Loop: Phi.getParent(), InitVal, LoopVal);
1223 MachineInstr *Use = MRI.getVRegDef(Reg: LoopVal);
1224 if (!Use || Use->isPHI())
1225 return true;
1226 int LoopCycle = Schedule.getCycle(MI: Use);
1227 int LoopStage = Schedule.getStage(MI: Use);
1228 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
1229}
1230
1231//===----------------------------------------------------------------------===//
1232// PeelingModuloScheduleExpander implementation
1233//===----------------------------------------------------------------------===//
1234// This is a reimplementation of ModuloScheduleExpander that works by creating
1235// a fully correct steady-state kernel and peeling off the prolog and epilogs.
1236//===----------------------------------------------------------------------===//
1237
1238namespace {
1239// Remove any dead phis in MBB. Dead phis either have only one block as input
1240// (in which case they are the identity) or have no uses.
1241void EliminateDeadPhis(MachineBasicBlock *MBB, MachineRegisterInfo &MRI,
1242 LiveIntervals *LIS, bool KeepSingleSrcPhi = false) {
1243 bool Changed = true;
1244 while (Changed) {
1245 Changed = false;
1246 for (MachineInstr &MI : llvm::make_early_inc_range(Range: MBB->phis())) {
1247 assert(MI.isPHI());
1248 if (MRI.use_empty(RegNo: MI.getOperand(i: 0).getReg())) {
1249 if (LIS)
1250 LIS->RemoveMachineInstrFromMaps(MI);
1251 MI.eraseFromParent();
1252 Changed = true;
1253 } else if (!KeepSingleSrcPhi && MI.getNumExplicitOperands() == 3) {
1254 const TargetRegisterClass *ConstrainRegClass =
1255 MRI.constrainRegClass(Reg: MI.getOperand(i: 1).getReg(),
1256 RC: MRI.getRegClass(Reg: MI.getOperand(i: 0).getReg()));
1257 assert(ConstrainRegClass &&
1258 "Expected a valid constrained register class!");
1259 (void)ConstrainRegClass;
1260 MRI.replaceRegWith(FromReg: MI.getOperand(i: 0).getReg(),
1261 ToReg: MI.getOperand(i: 1).getReg());
1262 if (LIS)
1263 LIS->RemoveMachineInstrFromMaps(MI);
1264 MI.eraseFromParent();
1265 Changed = true;
1266 }
1267 }
1268 }
1269}
1270
1271/// Rewrites the kernel block in-place to adhere to the given schedule.
1272/// KernelRewriter holds all of the state required to perform the rewriting.
1273class KernelRewriter {
1274 ModuloSchedule &S;
1275 MachineBasicBlock *BB;
1276 MachineBasicBlock *PreheaderBB, *ExitBB;
1277 MachineRegisterInfo &MRI;
1278 const TargetInstrInfo *TII;
1279 LiveIntervals *LIS;
1280
1281 // Map from register class to canonical undef register for that class.
1282 DenseMap<const TargetRegisterClass *, Register> Undefs;
1283 // Map from <LoopReg, InitReg> to phi register for all created phis. Note that
1284 // this map is only used when InitReg is non-undef.
1285 DenseMap<std::pair<Register, Register>, Register> Phis;
1286 // Map from LoopReg to phi register where the InitReg is undef.
1287 DenseMap<Register, Register> UndefPhis;
1288
1289 // Reg is used by MI. Return the new register MI should use to adhere to the
1290 // schedule. Insert phis as necessary.
1291 Register remapUse(Register Reg, MachineInstr &MI);
1292 // Insert a phi that carries LoopReg from the loop body and InitReg otherwise.
1293 // If InitReg is not given it is chosen arbitrarily. It will either be undef
1294 // or will be chosen so as to share another phi.
1295 Register phi(Register LoopReg, std::optional<Register> InitReg = {},
1296 const TargetRegisterClass *RC = nullptr);
1297 // Create an undef register of the given register class.
1298 Register undef(const TargetRegisterClass *RC);
1299
1300public:
1301 KernelRewriter(MachineLoop &L, ModuloSchedule &S, MachineBasicBlock *LoopBB,
1302 LiveIntervals *LIS = nullptr);
1303 void rewrite();
1304};
1305} // namespace
1306
1307KernelRewriter::KernelRewriter(MachineLoop &L, ModuloSchedule &S,
1308 MachineBasicBlock *LoopBB, LiveIntervals *LIS)
1309 : S(S), BB(LoopBB), PreheaderBB(L.getLoopPreheader()),
1310 ExitBB(L.getExitBlock()), MRI(BB->getParent()->getRegInfo()),
1311 TII(BB->getParent()->getSubtarget().getInstrInfo()), LIS(LIS) {
1312 PreheaderBB = *BB->pred_begin();
1313 if (PreheaderBB == BB)
1314 PreheaderBB = *std::next(x: BB->pred_begin());
1315}
1316
1317void KernelRewriter::rewrite() {
1318 // Rearrange the loop to be in schedule order. Note that the schedule may
1319 // contain instructions that are not owned by the loop block (InstrChanges and
1320 // friends), so we gracefully handle unowned instructions and delete any
1321 // instructions that weren't in the schedule.
1322 auto InsertPt = BB->getFirstTerminator();
1323 MachineInstr *FirstMI = nullptr;
1324 for (MachineInstr *MI : S.getInstructions()) {
1325 if (MI->isPHI())
1326 continue;
1327 if (MI->getParent())
1328 MI->removeFromParent();
1329 BB->insert(I: InsertPt, MI);
1330 if (!FirstMI)
1331 FirstMI = MI;
1332 }
1333 assert(FirstMI && "Failed to find first MI in schedule");
1334
1335 // At this point all of the scheduled instructions are between FirstMI
1336 // and the end of the block. Kill from the first non-phi to FirstMI.
1337 for (auto I = BB->getFirstNonPHI(); I != FirstMI->getIterator();) {
1338 if (LIS)
1339 LIS->RemoveMachineInstrFromMaps(MI&: *I);
1340 (I++)->eraseFromParent();
1341 }
1342
1343 // Now remap every instruction in the loop.
1344 for (MachineInstr &MI : *BB) {
1345 if (MI.isPHI() || MI.isTerminator())
1346 continue;
1347 for (MachineOperand &MO : MI.uses()) {
1348 if (!MO.isReg() || MO.getReg().isPhysical() || MO.isImplicit())
1349 continue;
1350 Register Reg = remapUse(Reg: MO.getReg(), MI);
1351 MO.setReg(Reg);
1352 }
1353 }
1354 EliminateDeadPhis(MBB: BB, MRI, LIS);
1355
1356 // Ensure a phi exists for all instructions that are either referenced by
1357 // an illegal phi or by an instruction outside the loop. This allows us to
1358 // treat remaps of these values the same as "normal" values that come from
1359 // loop-carried phis.
1360 for (auto MI = BB->getFirstNonPHI(); MI != BB->end(); ++MI) {
1361 if (MI->isPHI()) {
1362 Register R = MI->getOperand(i: 0).getReg();
1363 phi(LoopReg: R);
1364 continue;
1365 }
1366
1367 for (MachineOperand &Def : MI->defs()) {
1368 for (MachineInstr &MI : MRI.use_instructions(Reg: Def.getReg())) {
1369 if (MI.getParent() != BB) {
1370 phi(LoopReg: Def.getReg());
1371 break;
1372 }
1373 }
1374 }
1375 }
1376}
1377
1378Register KernelRewriter::remapUse(Register Reg, MachineInstr &MI) {
1379 MachineInstr *Producer = MRI.getUniqueVRegDef(Reg);
1380 if (!Producer)
1381 return Reg;
1382
1383 int ConsumerStage = S.getStage(MI: &MI);
1384 if (!Producer->isPHI()) {
1385 // Non-phi producers are simple to remap. Insert as many phis as the
1386 // difference between the consumer and producer stages.
1387 if (Producer->getParent() != BB)
1388 // Producer was not inside the loop. Use the register as-is.
1389 return Reg;
1390 int ProducerStage = S.getStage(MI: Producer);
1391 assert(ConsumerStage != -1 &&
1392 "In-loop consumer should always be scheduled!");
1393 assert(ConsumerStage >= ProducerStage);
1394 unsigned StageDiff = ConsumerStage - ProducerStage;
1395
1396 for (unsigned I = 0; I < StageDiff; ++I)
1397 Reg = phi(LoopReg: Reg);
1398 return Reg;
1399 }
1400
1401 // First, dive through the phi chain to find the defaults for the generated
1402 // phis.
1403 SmallVector<std::optional<Register>, 4> Defaults;
1404 Register LoopReg = Reg;
1405 auto LoopProducer = Producer;
1406 while (LoopProducer->isPHI() && LoopProducer->getParent() == BB) {
1407 LoopReg = getLoopPhiReg(Phi&: *LoopProducer, LoopBB: BB);
1408 Defaults.emplace_back(Args: getInitPhiReg(Phi&: *LoopProducer, LoopBB: BB));
1409 LoopProducer = MRI.getUniqueVRegDef(Reg: LoopReg);
1410 assert(LoopProducer);
1411 }
1412 int LoopProducerStage = S.getStage(MI: LoopProducer);
1413
1414 std::optional<Register> IllegalPhiDefault;
1415
1416 if (LoopProducerStage == -1) {
1417 // Do nothing.
1418 } else if (LoopProducerStage > ConsumerStage) {
1419 // This schedule is only representable if ProducerStage == ConsumerStage+1.
1420 // In addition, Consumer's cycle must be scheduled after Producer in the
1421 // rescheduled loop. This is enforced by the pipeliner's ASAP and ALAP
1422 // functions.
1423#ifndef NDEBUG // Silence unused variables in non-asserts mode.
1424 int LoopProducerCycle = S.getCycle(LoopProducer);
1425 int ConsumerCycle = S.getCycle(&MI);
1426#endif
1427 assert(LoopProducerCycle <= ConsumerCycle);
1428 assert(LoopProducerStage == ConsumerStage + 1);
1429 // Peel off the first phi from Defaults and insert a phi between producer
1430 // and consumer. This phi will not be at the front of the block so we
1431 // consider it illegal. It will only exist during the rewrite process; it
1432 // needs to exist while we peel off prologs because these could take the
1433 // default value. After that we can replace all uses with the loop producer
1434 // value.
1435 IllegalPhiDefault = Defaults.front();
1436 Defaults.erase(CI: Defaults.begin());
1437 } else {
1438 assert(ConsumerStage >= LoopProducerStage);
1439 int StageDiff = ConsumerStage - LoopProducerStage;
1440 if (StageDiff > 0) {
1441 LLVM_DEBUG(dbgs() << " -- padding defaults array from " << Defaults.size()
1442 << " to " << (Defaults.size() + StageDiff) << "\n");
1443 // If we need more phis than we have defaults for, pad out with undefs for
1444 // the earliest phis, which are at the end of the defaults chain (the
1445 // chain is in reverse order).
1446 Defaults.resize(N: Defaults.size() + StageDiff,
1447 NV: Defaults.empty() ? std::optional<Register>()
1448 : Defaults.back());
1449 }
1450 }
1451
1452 // Now we know the number of stages to jump back, insert the phi chain.
1453 auto DefaultI = Defaults.rbegin();
1454 while (DefaultI != Defaults.rend())
1455 LoopReg = phi(LoopReg, InitReg: *DefaultI++, RC: MRI.getRegClass(Reg));
1456
1457 if (IllegalPhiDefault) {
1458 // The consumer optionally consumes LoopProducer in the same iteration
1459 // (because the producer is scheduled at an earlier cycle than the consumer)
1460 // or the initial value. To facilitate this we create an illegal block here
1461 // by embedding a phi in the middle of the block. We will fix this up
1462 // immediately prior to pruning.
1463 auto RC = MRI.getRegClass(Reg);
1464 Register R = MRI.createVirtualRegister(RegClass: RC);
1465 MachineInstr *IllegalPhi =
1466 BuildMI(BB&: *BB, I&: MI, MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: R)
1467 .addReg(RegNo: *IllegalPhiDefault)
1468 .addMBB(MBB: PreheaderBB) // Block choice is arbitrary and has no effect.
1469 .addReg(RegNo: LoopReg)
1470 .addMBB(MBB: BB); // Block choice is arbitrary and has no effect.
1471 // Illegal phi should belong to the producer stage so that it can be
1472 // filtered correctly during peeling.
1473 S.setStage(MI: IllegalPhi, MIStage: LoopProducerStage);
1474 return R;
1475 }
1476
1477 return LoopReg;
1478}
1479
1480Register KernelRewriter::phi(Register LoopReg, std::optional<Register> InitReg,
1481 const TargetRegisterClass *RC) {
1482 // If the init register is not undef, try and find an existing phi.
1483 if (InitReg) {
1484 auto I = Phis.find(Val: {LoopReg, *InitReg});
1485 if (I != Phis.end())
1486 return I->second;
1487 } else {
1488 for (auto &KV : Phis) {
1489 if (KV.first.first == LoopReg)
1490 return KV.second;
1491 }
1492 }
1493
1494 // InitReg is either undef or no existing phi takes InitReg as input. Try and
1495 // find a phi that takes undef as input.
1496 auto I = UndefPhis.find(Val: LoopReg);
1497 if (I != UndefPhis.end()) {
1498 Register R = I->second;
1499 if (!InitReg)
1500 // Found a phi taking undef as input, and this input is undef so return
1501 // without any more changes.
1502 return R;
1503 // Found a phi taking undef as input, so rewrite it to take InitReg.
1504 MachineInstr *MI = MRI.getVRegDef(Reg: R);
1505 MI->getOperand(i: 1).setReg(*InitReg);
1506 Phis.insert(KV: {{LoopReg, *InitReg}, R});
1507 const TargetRegisterClass *ConstrainRegClass =
1508 MRI.constrainRegClass(Reg: R, RC: MRI.getRegClass(Reg: *InitReg));
1509 assert(ConstrainRegClass && "Expected a valid constrained register class!");
1510 (void)ConstrainRegClass;
1511 UndefPhis.erase(I);
1512 return R;
1513 }
1514
1515 // Failed to find any existing phi to reuse, so create a new one.
1516 if (!RC)
1517 RC = MRI.getRegClass(Reg: LoopReg);
1518 Register R = MRI.createVirtualRegister(RegClass: RC);
1519 if (InitReg) {
1520 const TargetRegisterClass *ConstrainRegClass =
1521 MRI.constrainRegClass(Reg: R, RC: MRI.getRegClass(Reg: *InitReg));
1522 assert(ConstrainRegClass && "Expected a valid constrained register class!");
1523 (void)ConstrainRegClass;
1524 }
1525 BuildMI(BB&: *BB, I: BB->getFirstNonPHI(), MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: R)
1526 .addReg(RegNo: InitReg ? *InitReg : undef(RC))
1527 .addMBB(MBB: PreheaderBB)
1528 .addReg(RegNo: LoopReg)
1529 .addMBB(MBB: BB);
1530 if (!InitReg)
1531 UndefPhis[LoopReg] = R;
1532 else
1533 Phis[{LoopReg, *InitReg}] = R;
1534 return R;
1535}
1536
1537Register KernelRewriter::undef(const TargetRegisterClass *RC) {
1538 Register &R = Undefs[RC];
1539 if (R == 0) {
1540 // Create an IMPLICIT_DEF that defines this register if we need it.
1541 // All uses of this should be removed by the time we have finished unrolling
1542 // prologs and epilogs.
1543 R = MRI.createVirtualRegister(RegClass: RC);
1544 auto *InsertBB = &PreheaderBB->getParent()->front();
1545 BuildMI(BB&: *InsertBB, I: InsertBB->getFirstTerminator(), MIMD: DebugLoc(),
1546 MCID: TII->get(Opcode: TargetOpcode::IMPLICIT_DEF), DestReg: R);
1547 }
1548 return R;
1549}
1550
1551namespace {
1552/// Describes an operand in the kernel of a pipelined loop. Characteristics of
1553/// the operand are discovered, such as how many in-loop PHIs it has to jump
1554/// through and defaults for these phis.
1555class KernelOperandInfo {
1556 MachineBasicBlock *BB;
1557 MachineRegisterInfo &MRI;
1558 SmallVector<Register, 4> PhiDefaults;
1559 MachineOperand *Source;
1560 MachineOperand *Target;
1561
1562public:
1563 KernelOperandInfo(MachineOperand *MO, MachineRegisterInfo &MRI,
1564 const SmallPtrSetImpl<MachineInstr *> &IllegalPhis)
1565 : MRI(MRI) {
1566 Source = MO;
1567 BB = MO->getParent()->getParent();
1568 while (isRegInLoop(MO)) {
1569 MachineInstr *MI = MRI.getVRegDef(Reg: MO->getReg());
1570 if (MI->isFullCopy()) {
1571 MO = &MI->getOperand(i: 1);
1572 continue;
1573 }
1574 if (!MI->isPHI())
1575 break;
1576 // If this is an illegal phi, don't count it in distance.
1577 if (IllegalPhis.count(Ptr: MI)) {
1578 MO = &MI->getOperand(i: 3);
1579 continue;
1580 }
1581
1582 Register Default = getInitPhiReg(Phi&: *MI, LoopBB: BB);
1583 MO = MI->getOperand(i: 2).getMBB() == BB ? &MI->getOperand(i: 1)
1584 : &MI->getOperand(i: 3);
1585 PhiDefaults.push_back(Elt: Default);
1586 }
1587 Target = MO;
1588 }
1589
1590 bool operator==(const KernelOperandInfo &Other) const {
1591 return PhiDefaults.size() == Other.PhiDefaults.size();
1592 }
1593
1594 void print(raw_ostream &OS) const {
1595 OS << "use of " << *Source << ": distance(" << PhiDefaults.size() << ") in "
1596 << *Source->getParent();
1597 }
1598
1599private:
1600 bool isRegInLoop(MachineOperand *MO) {
1601 return MO->isReg() && MO->getReg().isVirtual() &&
1602 MRI.getVRegDef(Reg: MO->getReg())->getParent() == BB;
1603 }
1604};
1605} // namespace
1606
1607MachineBasicBlock *
1608PeelingModuloScheduleExpander::peelKernel(LoopPeelDirection LPD) {
1609 MachineBasicBlock *NewBB = PeelSingleBlockLoop(Direction: LPD, Loop: BB, MRI, TII);
1610 if (LPD == LPD_Front)
1611 PeeledFront.push_back(x: NewBB);
1612 else
1613 PeeledBack.push_front(x: NewBB);
1614 for (auto I = BB->begin(), NI = NewBB->begin(); !I->isTerminator();
1615 ++I, ++NI) {
1616 CanonicalMIs[&*I] = &*I;
1617 CanonicalMIs[&*NI] = &*I;
1618 BlockMIs[{NewBB, &*I}] = &*NI;
1619 BlockMIs[{BB, &*I}] = &*I;
1620 }
1621 return NewBB;
1622}
1623
1624void PeelingModuloScheduleExpander::filterInstructions(MachineBasicBlock *MB,
1625 int MinStage) {
1626 for (auto I = MB->getFirstInstrTerminator()->getReverseIterator();
1627 I != std::next(x: MB->getFirstNonPHI()->getReverseIterator());) {
1628 MachineInstr *MI = &*I++;
1629 int Stage = getStage(MI);
1630 if (Stage == -1 || Stage >= MinStage)
1631 continue;
1632
1633 for (MachineOperand &DefMO : MI->defs()) {
1634 SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
1635 for (MachineInstr &UseMI : MRI.use_instructions(Reg: DefMO.getReg())) {
1636 // Only PHIs can use values from this block by construction.
1637 // Match with the equivalent PHI in B.
1638 assert(UseMI.isPHI());
1639 Register Reg = getEquivalentRegisterIn(Reg: UseMI.getOperand(i: 0).getReg(),
1640 BB: MI->getParent());
1641 Subs.emplace_back(Args: &UseMI, Args&: Reg);
1642 }
1643 for (auto &Sub : Subs)
1644 Sub.first->substituteRegister(FromReg: DefMO.getReg(), ToReg: Sub.second, /*SubIdx=*/0,
1645 RegInfo: *MRI.getTargetRegisterInfo());
1646 }
1647 if (LIS)
1648 LIS->RemoveMachineInstrFromMaps(MI&: *MI);
1649 MI->eraseFromParent();
1650 }
1651}
1652
1653void PeelingModuloScheduleExpander::moveStageBetweenBlocks(
1654 MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage) {
1655 auto InsertPt = DestBB->getFirstNonPHI();
1656 DenseMap<Register, Register> Remaps;
1657 for (MachineInstr &MI : llvm::make_early_inc_range(
1658 Range: llvm::make_range(x: SourceBB->getFirstNonPHI(), y: SourceBB->end()))) {
1659 if (MI.isPHI()) {
1660 // This is an illegal PHI. If we move any instructions using an illegal
1661 // PHI, we need to create a legal Phi.
1662 if (getStage(MI: &MI) != Stage) {
1663 // The legal Phi is not necessary if the illegal phi's stage
1664 // is being moved.
1665 Register PhiR = MI.getOperand(i: 0).getReg();
1666 auto RC = MRI.getRegClass(Reg: PhiR);
1667 Register NR = MRI.createVirtualRegister(RegClass: RC);
1668 MachineInstr *NI = BuildMI(BB&: *DestBB, I: DestBB->getFirstNonPHI(),
1669 MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: NR)
1670 .addReg(RegNo: PhiR)
1671 .addMBB(MBB: SourceBB);
1672 BlockMIs[{DestBB, CanonicalMIs[&MI]}] = NI;
1673 CanonicalMIs[NI] = CanonicalMIs[&MI];
1674 Remaps[PhiR] = NR;
1675 }
1676 }
1677 if (getStage(MI: &MI) != Stage)
1678 continue;
1679 MI.removeFromParent();
1680 DestBB->insert(I: InsertPt, MI: &MI);
1681 auto *KernelMI = CanonicalMIs[&MI];
1682 BlockMIs[{DestBB, KernelMI}] = &MI;
1683 BlockMIs.erase(Val: {SourceBB, KernelMI});
1684 }
1685 SmallVector<MachineInstr *, 4> PhiToDelete;
1686 for (MachineInstr &MI : DestBB->phis()) {
1687 assert(MI.getNumOperands() == 3);
1688 MachineInstr *Def = MRI.getVRegDef(Reg: MI.getOperand(i: 1).getReg());
1689 // If the instruction referenced by the phi is moved inside the block
1690 // we don't need the phi anymore.
1691 if (getStage(MI: Def) == Stage) {
1692 Register PhiReg = MI.getOperand(i: 0).getReg();
1693 assert(Def->findRegisterDefOperandIdx(MI.getOperand(1).getReg(),
1694 /*TRI=*/nullptr) != -1);
1695 MRI.replaceRegWith(FromReg: MI.getOperand(i: 0).getReg(), ToReg: MI.getOperand(i: 1).getReg());
1696 MI.getOperand(i: 0).setReg(PhiReg);
1697 PhiToDelete.push_back(Elt: &MI);
1698 }
1699 }
1700 for (auto *P : PhiToDelete)
1701 P->eraseFromParent();
1702 InsertPt = DestBB->getFirstNonPHI();
1703 // Helper to clone Phi instructions into the destination block. We clone Phi
1704 // greedily to avoid combinatorial explosion of Phi instructions.
1705 auto clonePhi = [&](MachineInstr *Phi) {
1706 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: Phi);
1707 DestBB->insert(I: InsertPt, MI: NewMI);
1708 Register OrigR = Phi->getOperand(i: 0).getReg();
1709 Register R = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigR));
1710 NewMI->getOperand(i: 0).setReg(R);
1711 NewMI->getOperand(i: 1).setReg(OrigR);
1712 NewMI->getOperand(i: 2).setMBB(*DestBB->pred_begin());
1713 Remaps[OrigR] = R;
1714 CanonicalMIs[NewMI] = CanonicalMIs[Phi];
1715 BlockMIs[{DestBB, CanonicalMIs[Phi]}] = NewMI;
1716 PhiNodeLoopIteration[NewMI] = PhiNodeLoopIteration[Phi];
1717 return R;
1718 };
1719 for (auto I = DestBB->getFirstNonPHI(); I != DestBB->end(); ++I) {
1720 for (MachineOperand &MO : I->uses()) {
1721 if (!MO.isReg())
1722 continue;
1723 if (auto It = Remaps.find(Val: MO.getReg()); It != Remaps.end())
1724 MO.setReg(It->second);
1725 else if (MO.getReg().isVirtual()) {
1726 // If we are using a phi from the source block we need to add a new phi
1727 // pointing to the old one.
1728 MachineInstr *Use = MRI.getUniqueVRegDef(Reg: MO.getReg());
1729 if (Use && Use->isPHI() && Use->getParent() == SourceBB) {
1730 Register R = clonePhi(Use);
1731 MO.setReg(R);
1732 }
1733 }
1734 }
1735 }
1736}
1737
1738Register
1739PeelingModuloScheduleExpander::getPhiCanonicalReg(MachineInstr *CanonicalPhi,
1740 MachineInstr *Phi) {
1741 unsigned distance = PhiNodeLoopIteration[Phi];
1742 MachineInstr *CanonicalUse = CanonicalPhi;
1743 Register CanonicalUseReg = CanonicalUse->getOperand(i: 0).getReg();
1744 for (unsigned I = 0; I < distance; ++I) {
1745 assert(CanonicalUse->isPHI());
1746 assert(CanonicalUse->getNumOperands() == 5);
1747 unsigned LoopRegIdx = 3, InitRegIdx = 1;
1748 if (CanonicalUse->getOperand(i: 2).getMBB() == CanonicalUse->getParent())
1749 std::swap(a&: LoopRegIdx, b&: InitRegIdx);
1750 CanonicalUseReg = CanonicalUse->getOperand(i: LoopRegIdx).getReg();
1751 CanonicalUse = MRI.getVRegDef(Reg: CanonicalUseReg);
1752 }
1753 return CanonicalUseReg;
1754}
1755
1756void PeelingModuloScheduleExpander::peelPrologAndEpilogs() {
1757 BitVector LS(Schedule.getNumStages(), true);
1758 BitVector AS(Schedule.getNumStages(), true);
1759 LiveStages[BB] = LS;
1760 AvailableStages[BB] = AS;
1761
1762 // Peel out the prologs.
1763 LS.reset();
1764 for (int I = 0; I < Schedule.getNumStages() - 1; ++I) {
1765 LS[I] = true;
1766 Prologs.push_back(Elt: peelKernel(LPD: LPD_Front));
1767 LiveStages[Prologs.back()] = LS;
1768 AvailableStages[Prologs.back()] = LS;
1769 }
1770
1771 // Create a block that will end up as the new loop exiting block (dominated by
1772 // all prologs and epilogs). It will only contain PHIs, in the same order as
1773 // BB's PHIs. This gives us a poor-man's LCSSA with the inductive property
1774 // that the exiting block is a (sub) clone of BB. This in turn gives us the
1775 // property that any value deffed in BB but used outside of BB is used by a
1776 // PHI in the exiting block.
1777 MachineBasicBlock *ExitingBB = CreateLCSSAExitingBlock();
1778 EliminateDeadPhis(MBB: ExitingBB, MRI, LIS, /*KeepSingleSrcPhi=*/true);
1779 // Push out the epilogs, again in reverse order.
1780 // We can't assume anything about the minumum loop trip count at this point,
1781 // so emit a fairly complex epilog.
1782
1783 // We first peel number of stages minus one epilogue. Then we remove dead
1784 // stages and reorder instructions based on their stage. If we have 3 stages
1785 // we generate first:
1786 // E0[3, 2, 1]
1787 // E1[3', 2']
1788 // E2[3'']
1789 // And then we move instructions based on their stages to have:
1790 // E0[3]
1791 // E1[2, 3']
1792 // E2[1, 2', 3'']
1793 // The transformation is legal because we only move instructions past
1794 // instructions of a previous loop iteration.
1795 for (int I = 1; I <= Schedule.getNumStages() - 1; ++I) {
1796 Epilogs.push_back(Elt: peelKernel(LPD: LPD_Back));
1797 MachineBasicBlock *B = Epilogs.back();
1798 filterInstructions(MB: B, MinStage: Schedule.getNumStages() - I);
1799 // Keep track at which iteration each phi belongs to. We need it to know
1800 // what version of the variable to use during prologue/epilogue stitching.
1801 EliminateDeadPhis(MBB: B, MRI, LIS, /*KeepSingleSrcPhi=*/true);
1802 for (MachineInstr &Phi : B->phis())
1803 PhiNodeLoopIteration[&Phi] = Schedule.getNumStages() - I;
1804 }
1805 for (size_t I = 0; I < Epilogs.size(); I++) {
1806 LS.reset();
1807 for (size_t J = I; J < Epilogs.size(); J++) {
1808 int Iteration = J;
1809 unsigned Stage = Schedule.getNumStages() - 1 + I - J;
1810 // Move stage one block at a time so that Phi nodes are updated correctly.
1811 for (size_t K = Iteration; K > I; K--)
1812 moveStageBetweenBlocks(DestBB: Epilogs[K - 1], SourceBB: Epilogs[K], Stage);
1813 LS[Stage] = true;
1814 }
1815 LiveStages[Epilogs[I]] = LS;
1816 AvailableStages[Epilogs[I]] = AS;
1817 }
1818
1819 // Now we've defined all the prolog and epilog blocks as a fallthrough
1820 // sequence, add the edges that will be followed if the loop trip count is
1821 // lower than the number of stages (connecting prologs directly with epilogs).
1822 auto PI = Prologs.begin();
1823 auto EI = Epilogs.begin();
1824 assert(Prologs.size() == Epilogs.size());
1825 for (; PI != Prologs.end(); ++PI, ++EI) {
1826 MachineBasicBlock *Pred = *(*EI)->pred_begin();
1827 (*PI)->addSuccessor(Succ: *EI);
1828 for (MachineInstr &MI : (*EI)->phis()) {
1829 Register Reg = MI.getOperand(i: 1).getReg();
1830 MachineInstr *Use = MRI.getUniqueVRegDef(Reg);
1831 if (Use && Use->getParent() == Pred) {
1832 MachineInstr *CanonicalUse = CanonicalMIs[Use];
1833 if (CanonicalUse->isPHI()) {
1834 // If the use comes from a phi we need to skip as many phi as the
1835 // distance between the epilogue and the kernel. Trace through the phi
1836 // chain to find the right value.
1837 Reg = getPhiCanonicalReg(CanonicalPhi: CanonicalUse, Phi: Use);
1838 }
1839 Reg = getEquivalentRegisterIn(Reg, BB: *PI);
1840 }
1841 MI.addOperand(Op: MachineOperand::CreateReg(Reg, /*isDef=*/false));
1842 MI.addOperand(Op: MachineOperand::CreateMBB(MBB: *PI));
1843 }
1844 }
1845
1846 // Create a list of all blocks in order.
1847 SmallVector<MachineBasicBlock *, 8> Blocks;
1848 llvm::append_range(C&: Blocks, R&: PeeledFront);
1849 Blocks.push_back(Elt: BB);
1850 llvm::append_range(C&: Blocks, R&: PeeledBack);
1851
1852 // Iterate in reverse order over all instructions, remapping as we go.
1853 for (MachineBasicBlock *B : reverse(C&: Blocks)) {
1854 for (auto I = B->instr_rbegin();
1855 I != std::next(x: B->getFirstNonPHI()->getReverseIterator());) {
1856 MachineBasicBlock::reverse_instr_iterator MI = I++;
1857 rewriteUsesOf(MI: &*MI);
1858 }
1859 }
1860 for (auto *MI : IllegalPhisToDelete) {
1861 if (LIS)
1862 LIS->RemoveMachineInstrFromMaps(MI&: *MI);
1863 MI->eraseFromParent();
1864 }
1865 IllegalPhisToDelete.clear();
1866
1867 // Now all remapping has been done, we're free to optimize the generated code.
1868 for (MachineBasicBlock *B : reverse(C&: Blocks))
1869 EliminateDeadPhis(MBB: B, MRI, LIS);
1870 EliminateDeadPhis(MBB: ExitingBB, MRI, LIS);
1871}
1872
1873MachineBasicBlock *PeelingModuloScheduleExpander::CreateLCSSAExitingBlock() {
1874 MachineFunction &MF = *BB->getParent();
1875 MachineBasicBlock *Exit = *BB->succ_begin();
1876 if (Exit == BB)
1877 Exit = *std::next(x: BB->succ_begin());
1878
1879 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB: BB->getBasicBlock());
1880 MF.insert(MBBI: std::next(x: BB->getIterator()), MBB: NewBB);
1881
1882 // Clone all phis in BB into NewBB and rewrite.
1883 for (MachineInstr &MI : BB->phis()) {
1884 auto RC = MRI.getRegClass(Reg: MI.getOperand(i: 0).getReg());
1885 Register OldR = MI.getOperand(i: 3).getReg();
1886 Register R = MRI.createVirtualRegister(RegClass: RC);
1887 SmallVector<MachineInstr *, 4> Uses;
1888 for (MachineInstr &Use : MRI.use_instructions(Reg: OldR))
1889 if (Use.getParent() != BB)
1890 Uses.push_back(Elt: &Use);
1891 for (MachineInstr *Use : Uses)
1892 Use->substituteRegister(FromReg: OldR, ToReg: R, /*SubIdx=*/0,
1893 RegInfo: *MRI.getTargetRegisterInfo());
1894 MachineInstr *NI = BuildMI(BB: NewBB, MIMD: DebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: R)
1895 .addReg(RegNo: OldR)
1896 .addMBB(MBB: BB);
1897 BlockMIs[{NewBB, &MI}] = NI;
1898 CanonicalMIs[NI] = &MI;
1899 }
1900 BB->replaceSuccessor(Old: Exit, New: NewBB);
1901 Exit->replacePhiUsesWith(Old: BB, New: NewBB);
1902 NewBB->addSuccessor(Succ: Exit);
1903
1904 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1905 SmallVector<MachineOperand, 4> Cond;
1906 bool CanAnalyzeBr = !TII->analyzeBranch(MBB&: *BB, TBB, FBB, Cond);
1907 (void)CanAnalyzeBr;
1908 assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
1909 TII->removeBranch(MBB&: *BB);
1910 TII->insertBranch(MBB&: *BB, TBB: TBB == Exit ? NewBB : TBB, FBB: FBB == Exit ? NewBB : FBB,
1911 Cond, DL: DebugLoc());
1912 TII->insertUnconditionalBranch(MBB&: *NewBB, DestBB: Exit, DL: DebugLoc());
1913 return NewBB;
1914}
1915
1916Register
1917PeelingModuloScheduleExpander::getEquivalentRegisterIn(Register Reg,
1918 MachineBasicBlock *BB) {
1919 MachineInstr *MI = MRI.getUniqueVRegDef(Reg);
1920 unsigned OpIdx = MI->findRegisterDefOperandIdx(Reg, /*TRI=*/nullptr);
1921 return BlockMIs[{BB, CanonicalMIs[MI]}]->getOperand(i: OpIdx).getReg();
1922}
1923
1924void PeelingModuloScheduleExpander::rewriteUsesOf(MachineInstr *MI) {
1925 if (MI->isPHI()) {
1926 // This is an illegal PHI. The loop-carried (desired) value is operand 3,
1927 // and it is produced by this block.
1928 Register PhiR = MI->getOperand(i: 0).getReg();
1929 Register R = MI->getOperand(i: 3).getReg();
1930 int RMIStage = getStage(MI: MRI.getUniqueVRegDef(Reg: R));
1931 if (RMIStage != -1 && !AvailableStages[MI->getParent()].test(Idx: RMIStage))
1932 R = MI->getOperand(i: 1).getReg();
1933 MRI.setRegClass(Reg: R, RC: MRI.getRegClass(Reg: PhiR));
1934 MRI.replaceRegWith(FromReg: PhiR, ToReg: R);
1935 // Postpone deleting the Phi as it may be referenced by BlockMIs and used
1936 // later to figure out how to remap registers.
1937 MI->getOperand(i: 0).setReg(PhiR);
1938 IllegalPhisToDelete.push_back(Elt: MI);
1939 return;
1940 }
1941
1942 int Stage = getStage(MI);
1943 if (Stage == -1 || LiveStages.count(Val: MI->getParent()) == 0 ||
1944 LiveStages[MI->getParent()].test(Idx: Stage))
1945 // Instruction is live, no rewriting to do.
1946 return;
1947
1948 for (MachineOperand &DefMO : MI->defs()) {
1949 SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
1950 for (MachineInstr &UseMI : MRI.use_instructions(Reg: DefMO.getReg())) {
1951 // Only PHIs can use values from this block by construction.
1952 // Match with the equivalent PHI in B.
1953 assert(UseMI.isPHI());
1954 Register Reg = getEquivalentRegisterIn(Reg: UseMI.getOperand(i: 0).getReg(),
1955 BB: MI->getParent());
1956 Subs.emplace_back(Args: &UseMI, Args&: Reg);
1957 }
1958 for (auto &Sub : Subs)
1959 Sub.first->substituteRegister(FromReg: DefMO.getReg(), ToReg: Sub.second, /*SubIdx=*/0,
1960 RegInfo: *MRI.getTargetRegisterInfo());
1961 }
1962 if (LIS)
1963 LIS->RemoveMachineInstrFromMaps(MI&: *MI);
1964 MI->eraseFromParent();
1965}
1966
1967void PeelingModuloScheduleExpander::fixupBranches() {
1968 // Work outwards from the kernel.
1969 bool KernelDisposed = false;
1970 int TC = Schedule.getNumStages() - 1;
1971 for (auto PI = Prologs.rbegin(), EI = Epilogs.rbegin(); PI != Prologs.rend();
1972 ++PI, ++EI, --TC) {
1973 MachineBasicBlock *Prolog = *PI;
1974 MachineBasicBlock *Fallthrough = *Prolog->succ_begin();
1975 MachineBasicBlock *Epilog = *EI;
1976 SmallVector<MachineOperand, 4> Cond;
1977 TII->removeBranch(MBB&: *Prolog);
1978 std::optional<bool> StaticallyGreater =
1979 LoopInfo->createTripCountGreaterCondition(TC, MBB&: *Prolog, Cond);
1980 if (!StaticallyGreater) {
1981 LLVM_DEBUG(dbgs() << "Dynamic: TC > " << TC << "\n");
1982 // Dynamically branch based on Cond.
1983 TII->insertBranch(MBB&: *Prolog, TBB: Epilog, FBB: Fallthrough, Cond, DL: DebugLoc());
1984 } else if (*StaticallyGreater == false) {
1985 LLVM_DEBUG(dbgs() << "Static-false: TC > " << TC << "\n");
1986 // Prolog never falls through; branch to epilog and orphan interior
1987 // blocks. Leave it to unreachable-block-elim to clean up.
1988 Prolog->removeSuccessor(Succ: Fallthrough);
1989 for (MachineInstr &P : Fallthrough->phis()) {
1990 P.removeOperand(OpNo: 2);
1991 P.removeOperand(OpNo: 1);
1992 }
1993 TII->insertUnconditionalBranch(MBB&: *Prolog, DestBB: Epilog, DL: DebugLoc());
1994 KernelDisposed = true;
1995 } else {
1996 LLVM_DEBUG(dbgs() << "Static-true: TC > " << TC << "\n");
1997 // Prolog always falls through; remove incoming values in epilog.
1998 Prolog->removeSuccessor(Succ: Epilog);
1999 for (MachineInstr &P : Epilog->phis()) {
2000 P.removeOperand(OpNo: 4);
2001 P.removeOperand(OpNo: 3);
2002 }
2003 }
2004 }
2005
2006 if (!KernelDisposed) {
2007 LoopInfo->adjustTripCount(TripCountAdjust: -(Schedule.getNumStages() - 1));
2008 LoopInfo->setPreheader(Prologs.back());
2009 } else {
2010 LoopInfo->disposed();
2011 }
2012}
2013
2014void PeelingModuloScheduleExpander::rewriteKernel() {
2015 KernelRewriter KR(*Schedule.getLoop(), Schedule, BB);
2016 KR.rewrite();
2017}
2018
2019void PeelingModuloScheduleExpander::expand() {
2020 BB = Schedule.getLoop()->getTopBlock();
2021 Preheader = Schedule.getLoop()->getLoopPreheader();
2022 LLVM_DEBUG(Schedule.dump());
2023 LoopInfo = TII->analyzeLoopForPipelining(LoopBB: BB);
2024 assert(LoopInfo);
2025
2026 rewriteKernel();
2027 peelPrologAndEpilogs();
2028 fixupBranches();
2029}
2030
2031void PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander() {
2032 BB = Schedule.getLoop()->getTopBlock();
2033 Preheader = Schedule.getLoop()->getLoopPreheader();
2034
2035 // Dump the schedule before we invalidate and remap all its instructions.
2036 // Stash it in a string so we can print it if we found an error.
2037 std::string ScheduleDump;
2038 raw_string_ostream OS(ScheduleDump);
2039 Schedule.print(OS);
2040
2041 // First, run the normal ModuleScheduleExpander. We don't support any
2042 // InstrChanges.
2043 assert(LIS && "Requires LiveIntervals!");
2044 ModuloScheduleExpander MSE(MF, Schedule, *LIS,
2045 ModuloScheduleExpander::InstrChangesTy());
2046 MSE.expand();
2047 MachineBasicBlock *ExpandedKernel = MSE.getRewrittenKernel();
2048 if (!ExpandedKernel) {
2049 // The expander optimized away the kernel. We can't do any useful checking.
2050 MSE.cleanup();
2051 return;
2052 }
2053 // Before running the KernelRewriter, re-add BB into the CFG.
2054 Preheader->addSuccessor(Succ: BB);
2055
2056 // Now run the new expansion algorithm.
2057 KernelRewriter KR(*Schedule.getLoop(), Schedule, BB);
2058 KR.rewrite();
2059 peelPrologAndEpilogs();
2060
2061 // Collect all illegal phis that the new algorithm created. We'll give these
2062 // to KernelOperandInfo.
2063 SmallPtrSet<MachineInstr *, 4> IllegalPhis;
2064 for (auto NI = BB->getFirstNonPHI(); NI != BB->end(); ++NI) {
2065 if (NI->isPHI())
2066 IllegalPhis.insert(Ptr: &*NI);
2067 }
2068
2069 // Co-iterate across both kernels. We expect them to be identical apart from
2070 // phis and full COPYs (we look through both).
2071 SmallVector<std::pair<KernelOperandInfo, KernelOperandInfo>, 8> KOIs;
2072 auto OI = ExpandedKernel->begin();
2073 auto NI = BB->begin();
2074 for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {
2075 while (OI->isPHI() || OI->isFullCopy())
2076 ++OI;
2077 while (NI->isPHI() || NI->isFullCopy())
2078 ++NI;
2079 assert(OI->getOpcode() == NI->getOpcode() && "Opcodes don't match?!");
2080 // Analyze every operand separately.
2081 for (auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();
2082 OOpI != OI->operands_end(); ++OOpI, ++NOpI)
2083 KOIs.emplace_back(Args: KernelOperandInfo(&*OOpI, MRI, IllegalPhis),
2084 Args: KernelOperandInfo(&*NOpI, MRI, IllegalPhis));
2085 }
2086
2087 bool Failed = false;
2088 for (auto &OldAndNew : KOIs) {
2089 if (OldAndNew.first == OldAndNew.second)
2090 continue;
2091 Failed = true;
2092 errs() << "Modulo kernel validation error: [\n";
2093 errs() << " [golden] ";
2094 OldAndNew.first.print(OS&: errs());
2095 errs() << " ";
2096 OldAndNew.second.print(OS&: errs());
2097 errs() << "]\n";
2098 }
2099
2100 if (Failed) {
2101 errs() << "Golden reference kernel:\n";
2102 ExpandedKernel->print(OS&: errs());
2103 errs() << "New kernel:\n";
2104 BB->print(OS&: errs());
2105 errs() << ScheduleDump;
2106 report_fatal_error(
2107 reason: "Modulo kernel validation (-pipeliner-experimental-cg) failed");
2108 }
2109
2110 // Cleanup by removing BB from the CFG again as the original
2111 // ModuloScheduleExpander intended.
2112 Preheader->removeSuccessor(Succ: BB);
2113 MSE.cleanup();
2114}
2115
2116MachineInstr *ModuloScheduleExpanderMVE::cloneInstr(MachineInstr *OldMI) {
2117 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: OldMI);
2118
2119 // TODO: Offset information needs to be corrected.
2120 NewMI->dropMemRefs(MF);
2121
2122 return NewMI;
2123}
2124
2125/// Create a dedicated exit for Loop. Exit is the original exit for Loop.
2126/// If it is already dedicated exit, return it. Otherwise, insert a new
2127/// block between them and return the new block.
2128static MachineBasicBlock *createDedicatedExit(MachineBasicBlock *Loop,
2129 MachineBasicBlock *Exit,
2130 LiveIntervals &LIS) {
2131 if (Exit->pred_size() == 1)
2132 return Exit;
2133
2134 MachineFunction *MF = Loop->getParent();
2135 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
2136
2137 MachineBasicBlock *NewExit =
2138 MF->CreateMachineBasicBlock(BB: Loop->getBasicBlock());
2139 MF->insert(MBBI: Loop->getIterator(), MBB: NewExit);
2140 LIS.insertMBBInMaps(MBB: NewExit);
2141
2142 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
2143 SmallVector<MachineOperand, 4> Cond;
2144 TII->analyzeBranch(MBB&: *Loop, TBB, FBB, Cond);
2145 if (TBB == Loop)
2146 FBB = NewExit;
2147 else if (FBB == Loop)
2148 TBB = NewExit;
2149 else
2150 llvm_unreachable("unexpected loop structure");
2151 TII->removeBranch(MBB&: *Loop);
2152 TII->insertBranch(MBB&: *Loop, TBB, FBB, Cond, DL: DebugLoc());
2153 Loop->replaceSuccessor(Old: Exit, New: NewExit);
2154 TII->insertUnconditionalBranch(MBB&: *NewExit, DestBB: Exit, DL: DebugLoc());
2155 NewExit->addSuccessor(Succ: Exit);
2156
2157 Exit->replacePhiUsesWith(Old: Loop, New: NewExit);
2158
2159 return NewExit;
2160}
2161
2162/// Insert branch code into the end of MBB. It branches to GreaterThan if the
2163/// remaining trip count for instructions in LastStage0Insts is greater than
2164/// RequiredTC, and to Otherwise otherwise.
2165void ModuloScheduleExpanderMVE::insertCondBranch(MachineBasicBlock &MBB,
2166 int RequiredTC,
2167 InstrMapTy &LastStage0Insts,
2168 MachineBasicBlock &GreaterThan,
2169 MachineBasicBlock &Otherwise) {
2170 SmallVector<MachineOperand, 4> Cond;
2171 LoopInfo->createRemainingIterationsGreaterCondition(TC: RequiredTC, MBB, Cond,
2172 LastStage0Insts);
2173
2174 if (SwapBranchTargetsMVE) {
2175 // Set SwapBranchTargetsMVE to true if a target prefers to replace TBB and
2176 // FBB for optimal performance.
2177 if (TII->reverseBranchCondition(Cond))
2178 llvm_unreachable("can not reverse branch condition");
2179 TII->insertBranch(MBB, TBB: &Otherwise, FBB: &GreaterThan, Cond, DL: DebugLoc());
2180 } else {
2181 TII->insertBranch(MBB, TBB: &GreaterThan, FBB: &Otherwise, Cond, DL: DebugLoc());
2182 }
2183}
2184
2185/// Generate a pipelined loop that is unrolled by using MVE algorithm and any
2186/// other necessary blocks. The control flow is modified to execute the
2187/// pipelined loop if the trip count satisfies the condition, otherwise the
2188/// original loop. The original loop is also used to execute the remainder
2189/// iterations which occur due to unrolling.
2190void ModuloScheduleExpanderMVE::generatePipelinedLoop() {
2191 // The control flow for pipelining with MVE:
2192 //
2193 // OrigPreheader:
2194 // // The block that is originally the loop preheader
2195 // goto Check
2196 //
2197 // Check:
2198 // // Check whether the trip count satisfies the requirements to pipeline.
2199 // if (LoopCounter > NumStages + NumUnroll - 2)
2200 // // The minimum number of iterations to pipeline =
2201 // // iterations executed in prolog/epilog (NumStages-1) +
2202 // // iterations executed in one kernel run (NumUnroll)
2203 // goto Prolog
2204 // // fallback to the original loop
2205 // goto NewPreheader
2206 //
2207 // Prolog:
2208 // // All prolog stages. There are no direct branches to the epilogue.
2209 // goto NewKernel
2210 //
2211 // NewKernel:
2212 // // NumUnroll copies of the kernel
2213 // if (LoopCounter > MVE-1)
2214 // goto NewKernel
2215 // goto Epilog
2216 //
2217 // Epilog:
2218 // // All epilog stages.
2219 // if (LoopCounter > 0)
2220 // // The remainder is executed in the original loop
2221 // goto NewPreheader
2222 // goto NewExit
2223 //
2224 // NewPreheader:
2225 // // Newly created preheader for the original loop.
2226 // // The initial values of the phis in the loop are merged from two paths.
2227 // NewInitVal = Phi OrigInitVal, Check, PipelineLastVal, Epilog
2228 // goto OrigKernel
2229 //
2230 // OrigKernel:
2231 // // The original loop block.
2232 // if (LoopCounter != 0)
2233 // goto OrigKernel
2234 // goto NewExit
2235 //
2236 // NewExit:
2237 // // Newly created dedicated exit for the original loop.
2238 // // Merge values which are referenced after the loop
2239 // Merged = Phi OrigVal, OrigKernel, PipelineVal, Epilog
2240 // goto OrigExit
2241 //
2242 // OrigExit:
2243 // // The block that is originally the loop exit.
2244 // // If it is already deicated exit, NewExit is not created.
2245
2246 // An example of where each stage is executed:
2247 // Assume #Stages 3, #MVE 4, #Iterations 12
2248 // Iter 0 1 2 3 4 5 6 7 8 9 10-11
2249 // -------------------------------------------------
2250 // Stage 0 Prolog#0
2251 // Stage 1 0 Prolog#1
2252 // Stage 2 1 0 Kernel Unroll#0 Iter#0
2253 // Stage 2 1 0 Kernel Unroll#1 Iter#0
2254 // Stage 2 1 0 Kernel Unroll#2 Iter#0
2255 // Stage 2 1 0 Kernel Unroll#3 Iter#0
2256 // Stage 2 1 0 Kernel Unroll#0 Iter#1
2257 // Stage 2 1 0 Kernel Unroll#1 Iter#1
2258 // Stage 2 1 0 Kernel Unroll#2 Iter#1
2259 // Stage 2 1 0 Kernel Unroll#3 Iter#1
2260 // Stage 2 1 Epilog#0
2261 // Stage 2 Epilog#1
2262 // Stage 0-2 OrigKernel
2263
2264 LoopInfo = TII->analyzeLoopForPipelining(LoopBB: OrigKernel);
2265 assert(LoopInfo && "Must be able to analyze loop!");
2266
2267 calcNumUnroll();
2268
2269 Check = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2270 Prolog = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2271 NewKernel = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2272 Epilog = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2273 NewPreheader = MF.CreateMachineBasicBlock(BB: OrigKernel->getBasicBlock());
2274
2275 MF.insert(MBBI: OrigKernel->getIterator(), MBB: Check);
2276 LIS.insertMBBInMaps(MBB: Check);
2277 MF.insert(MBBI: OrigKernel->getIterator(), MBB: Prolog);
2278 LIS.insertMBBInMaps(MBB: Prolog);
2279 MF.insert(MBBI: OrigKernel->getIterator(), MBB: NewKernel);
2280 LIS.insertMBBInMaps(MBB: NewKernel);
2281 MF.insert(MBBI: OrigKernel->getIterator(), MBB: Epilog);
2282 LIS.insertMBBInMaps(MBB: Epilog);
2283 MF.insert(MBBI: OrigKernel->getIterator(), MBB: NewPreheader);
2284 LIS.insertMBBInMaps(MBB: NewPreheader);
2285
2286 NewExit = createDedicatedExit(Loop: OrigKernel, Exit: OrigExit, LIS);
2287
2288 NewPreheader->transferSuccessorsAndUpdatePHIs(FromMBB: OrigPreheader);
2289 TII->insertUnconditionalBranch(MBB&: *NewPreheader, DestBB: OrigKernel, DL: DebugLoc());
2290
2291 OrigPreheader->addSuccessor(Succ: Check);
2292 TII->removeBranch(MBB&: *OrigPreheader);
2293 TII->insertUnconditionalBranch(MBB&: *OrigPreheader, DestBB: Check, DL: DebugLoc());
2294
2295 Check->addSuccessor(Succ: Prolog);
2296 Check->addSuccessor(Succ: NewPreheader);
2297
2298 Prolog->addSuccessor(Succ: NewKernel);
2299
2300 NewKernel->addSuccessor(Succ: NewKernel);
2301 NewKernel->addSuccessor(Succ: Epilog);
2302
2303 Epilog->addSuccessor(Succ: NewPreheader);
2304 Epilog->addSuccessor(Succ: NewExit);
2305
2306 InstrMapTy LastStage0Insts;
2307 insertCondBranch(MBB&: *Check, RequiredTC: Schedule.getNumStages() + NumUnroll - 2,
2308 LastStage0Insts, GreaterThan&: *Prolog, Otherwise&: *NewPreheader);
2309
2310 // VRMaps map (prolog/kernel/epilog phase#, original register#) to new
2311 // register#
2312 SmallVector<ValueMapTy> PrologVRMap, KernelVRMap, EpilogVRMap;
2313 generateProlog(VRMap&: PrologVRMap);
2314 generateKernel(PrologVRMap, KernelVRMap, LastStage0Insts);
2315 generateEpilog(KernelVRMap, EpilogVRMap, LastStage0Insts);
2316}
2317
2318/// Replace MI's use operands according to the maps.
2319void ModuloScheduleExpanderMVE::updateInstrUse(
2320 MachineInstr *MI, int StageNum, int PhaseNum,
2321 SmallVectorImpl<ValueMapTy> &CurVRMap,
2322 SmallVectorImpl<ValueMapTy> *PrevVRMap) {
2323 // If MI is in the prolog/kernel/epilog block, CurVRMap is
2324 // PrologVRMap/KernelVRMap/EpilogVRMap respectively.
2325 // PrevVRMap is nullptr/PhiVRMap/KernelVRMap respectively.
2326 // Refer to the appropriate map according to the stage difference between
2327 // MI and the definition of an operand.
2328
2329 for (MachineOperand &UseMO : MI->uses()) {
2330 if (!UseMO.isReg() || !UseMO.getReg().isVirtual())
2331 continue;
2332 int DiffStage = 0;
2333 Register OrigReg = UseMO.getReg();
2334 MachineInstr *DefInst = MRI.getVRegDef(Reg: OrigReg);
2335 if (!DefInst || DefInst->getParent() != OrigKernel)
2336 continue;
2337 Register InitReg;
2338 Register DefReg = OrigReg;
2339 if (DefInst->isPHI()) {
2340 ++DiffStage;
2341 Register LoopReg;
2342 getPhiRegs(Phi&: *DefInst, Loop: OrigKernel, InitVal&: InitReg, LoopVal&: LoopReg);
2343 // LoopReg is guaranteed to be defined within the loop by canApply()
2344 DefReg = LoopReg;
2345 DefInst = MRI.getVRegDef(Reg: LoopReg);
2346 }
2347 unsigned DefStageNum = Schedule.getStage(MI: DefInst);
2348 DiffStage += StageNum - DefStageNum;
2349 Register NewReg;
2350 if (PhaseNum >= DiffStage && CurVRMap[PhaseNum - DiffStage].count(Val: DefReg))
2351 // NewReg is defined in a previous phase of the same block
2352 NewReg = CurVRMap[PhaseNum - DiffStage][DefReg];
2353 else if (!PrevVRMap)
2354 // Since this is the first iteration, refer the initial register of the
2355 // loop
2356 NewReg = InitReg;
2357 else
2358 // Cases where DiffStage is larger than PhaseNum.
2359 // If MI is in the kernel block, the value is defined by the previous
2360 // iteration and PhiVRMap is referenced. If MI is in the epilog block, the
2361 // value is defined in the kernel block and KernelVRMap is referenced.
2362 NewReg = (*PrevVRMap)[PrevVRMap->size() - (DiffStage - PhaseNum)][DefReg];
2363
2364 const TargetRegisterClass *NRC =
2365 MRI.constrainRegClass(Reg: NewReg, RC: MRI.getRegClass(Reg: OrigReg));
2366 if (NRC)
2367 UseMO.setReg(NewReg);
2368 else {
2369 Register SplitReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigReg));
2370 MachineInstr *NewCopy = BuildMI(BB&: *OrigKernel, I: MI, MIMD: MI->getDebugLoc(),
2371 MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: SplitReg)
2372 .addReg(RegNo: NewReg);
2373 LIS.InsertMachineInstrInMaps(MI&: *NewCopy);
2374 UseMO.setReg(SplitReg);
2375 }
2376 }
2377}
2378
2379/// Return a phi if Reg is referenced by the phi.
2380/// canApply() guarantees that at most only one such phi exists.
2381static MachineInstr *getLoopPhiUser(Register Reg, MachineBasicBlock *Loop) {
2382 for (MachineInstr &Phi : Loop->phis()) {
2383 Register InitVal, LoopVal;
2384 getPhiRegs(Phi, Loop, InitVal, LoopVal);
2385 if (LoopVal == Reg)
2386 return &Phi;
2387 }
2388 return nullptr;
2389}
2390
2391/// Generate phis for registers defined by OrigMI.
2392void ModuloScheduleExpanderMVE::generatePhi(
2393 MachineInstr *OrigMI, int UnrollNum,
2394 SmallVectorImpl<ValueMapTy> &PrologVRMap,
2395 SmallVectorImpl<ValueMapTy> &KernelVRMap,
2396 SmallVectorImpl<ValueMapTy> &PhiVRMap) {
2397 int StageNum = Schedule.getStage(MI: OrigMI);
2398 bool UsePrologReg;
2399 if (Schedule.getNumStages() - NumUnroll + UnrollNum - 1 >= StageNum)
2400 UsePrologReg = true;
2401 else if (Schedule.getNumStages() - NumUnroll + UnrollNum == StageNum)
2402 UsePrologReg = false;
2403 else
2404 return;
2405
2406 // Examples that show which stages are merged by phi.
2407 // Meaning of the symbol following the stage number:
2408 // a/b: Stages with the same letter are merged (UsePrologReg == true)
2409 // +: Merged with the initial value (UsePrologReg == false)
2410 // *: No phis required
2411 //
2412 // #Stages 3, #MVE 4
2413 // Iter 0 1 2 3 4 5 6 7 8
2414 // -----------------------------------------
2415 // Stage 0a Prolog#0
2416 // Stage 1a 0b Prolog#1
2417 // Stage 2* 1* 0* Kernel Unroll#0
2418 // Stage 2* 1* 0+ Kernel Unroll#1
2419 // Stage 2* 1+ 0a Kernel Unroll#2
2420 // Stage 2+ 1a 0b Kernel Unroll#3
2421 //
2422 // #Stages 3, #MVE 2
2423 // Iter 0 1 2 3 4 5 6 7 8
2424 // -----------------------------------------
2425 // Stage 0a Prolog#0
2426 // Stage 1a 0b Prolog#1
2427 // Stage 2* 1+ 0a Kernel Unroll#0
2428 // Stage 2+ 1a 0b Kernel Unroll#1
2429 //
2430 // #Stages 3, #MVE 1
2431 // Iter 0 1 2 3 4 5 6 7 8
2432 // -----------------------------------------
2433 // Stage 0* Prolog#0
2434 // Stage 1a 0b Prolog#1
2435 // Stage 2+ 1a 0b Kernel Unroll#0
2436
2437 for (MachineOperand &DefMO : OrigMI->defs()) {
2438 if (!DefMO.isReg() || DefMO.isDead())
2439 continue;
2440 Register OrigReg = DefMO.getReg();
2441 auto NewReg = KernelVRMap[UnrollNum].find(Val: OrigReg);
2442 if (NewReg == KernelVRMap[UnrollNum].end())
2443 continue;
2444 Register CorrespondReg;
2445 if (UsePrologReg) {
2446 int PrologNum = Schedule.getNumStages() - NumUnroll + UnrollNum - 1;
2447 CorrespondReg = PrologVRMap[PrologNum][OrigReg];
2448 } else {
2449 MachineInstr *Phi = getLoopPhiUser(Reg: OrigReg, Loop: OrigKernel);
2450 if (!Phi)
2451 continue;
2452 CorrespondReg = getInitPhiReg(Phi&: *Phi, LoopBB: OrigKernel);
2453 }
2454
2455 assert(CorrespondReg.isValid());
2456 Register PhiReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigReg));
2457 MachineInstr *NewPhi =
2458 BuildMI(BB&: *NewKernel, I: NewKernel->getFirstNonPHI(), MIMD: DebugLoc(),
2459 MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: PhiReg)
2460 .addReg(RegNo: NewReg->second)
2461 .addMBB(MBB: NewKernel)
2462 .addReg(RegNo: CorrespondReg)
2463 .addMBB(MBB: Prolog);
2464 LIS.InsertMachineInstrInMaps(MI&: *NewPhi);
2465 PhiVRMap[UnrollNum][OrigReg] = PhiReg;
2466 }
2467}
2468
2469static void replacePhiSrc(MachineInstr &Phi, Register OrigReg, Register NewReg,
2470 MachineBasicBlock *NewMBB) {
2471 for (unsigned Idx = 1; Idx < Phi.getNumOperands(); Idx += 2) {
2472 if (Phi.getOperand(i: Idx).getReg() == OrigReg) {
2473 Phi.getOperand(i: Idx).setReg(NewReg);
2474 Phi.getOperand(i: Idx + 1).setMBB(NewMBB);
2475 return;
2476 }
2477 }
2478}
2479
2480/// Generate phis that merge values from multiple routes
2481void ModuloScheduleExpanderMVE::mergeRegUsesAfterPipeline(Register OrigReg,
2482 Register NewReg) {
2483 SmallVector<MachineOperand *> UsesAfterLoop;
2484 SmallVector<MachineInstr *> LoopPhis;
2485 for (MachineRegisterInfo::use_iterator I = MRI.use_begin(RegNo: OrigReg),
2486 E = MRI.use_end();
2487 I != E; ++I) {
2488 MachineOperand &O = *I;
2489 if (O.getParent()->getParent() != OrigKernel &&
2490 O.getParent()->getParent() != Prolog &&
2491 O.getParent()->getParent() != NewKernel &&
2492 O.getParent()->getParent() != Epilog)
2493 UsesAfterLoop.push_back(Elt: &O);
2494 if (O.getParent()->getParent() == OrigKernel && O.getParent()->isPHI())
2495 LoopPhis.push_back(Elt: O.getParent());
2496 }
2497
2498 // Merge the route that only execute the pipelined loop (when there are no
2499 // remaining iterations) with the route that execute the original loop.
2500 if (!UsesAfterLoop.empty()) {
2501 Register PhiReg = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigReg));
2502 MachineInstr *NewPhi =
2503 BuildMI(BB&: *NewExit, I: NewExit->getFirstNonPHI(), MIMD: DebugLoc(),
2504 MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: PhiReg)
2505 .addReg(RegNo: OrigReg)
2506 .addMBB(MBB: OrigKernel)
2507 .addReg(RegNo: NewReg)
2508 .addMBB(MBB: Epilog);
2509 LIS.InsertMachineInstrInMaps(MI&: *NewPhi);
2510
2511 for (MachineOperand *MO : UsesAfterLoop)
2512 MO->setReg(PhiReg);
2513
2514 // The interval of OrigReg is invalid and should be recalculated when
2515 // LiveInterval::getInterval() is called.
2516 if (LIS.hasInterval(Reg: OrigReg))
2517 LIS.removeInterval(Reg: OrigReg);
2518 }
2519
2520 // Merge routes from the pipelined loop and the bypassed route before the
2521 // original loop
2522 if (!LoopPhis.empty()) {
2523 for (MachineInstr *Phi : LoopPhis) {
2524 Register InitReg, LoopReg;
2525 getPhiRegs(Phi&: *Phi, Loop: OrigKernel, InitVal&: InitReg, LoopVal&: LoopReg);
2526 Register NewInit = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: InitReg));
2527 MachineInstr *NewPhi =
2528 BuildMI(BB&: *NewPreheader, I: NewPreheader->getFirstNonPHI(),
2529 MIMD: Phi->getDebugLoc(), MCID: TII->get(Opcode: TargetOpcode::PHI), DestReg: NewInit)
2530 .addReg(RegNo: InitReg)
2531 .addMBB(MBB: Check)
2532 .addReg(RegNo: NewReg)
2533 .addMBB(MBB: Epilog);
2534 LIS.InsertMachineInstrInMaps(MI&: *NewPhi);
2535 replacePhiSrc(Phi&: *Phi, OrigReg: InitReg, NewReg: NewInit, NewMBB: NewPreheader);
2536 }
2537 }
2538}
2539
2540void ModuloScheduleExpanderMVE::generateProlog(
2541 SmallVectorImpl<ValueMapTy> &PrologVRMap) {
2542 PrologVRMap.clear();
2543 PrologVRMap.resize(N: Schedule.getNumStages() - 1);
2544 DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;
2545 for (int PrologNum = 0; PrologNum < Schedule.getNumStages() - 1;
2546 ++PrologNum) {
2547 for (MachineInstr *MI : Schedule.getInstructions()) {
2548 if (MI->isPHI())
2549 continue;
2550 int StageNum = Schedule.getStage(MI);
2551 if (StageNum > PrologNum)
2552 continue;
2553 MachineInstr *NewMI = cloneInstr(OldMI: MI);
2554 updateInstrDef(NewMI, VRMap&: PrologVRMap[PrologNum], LastDef: false);
2555 NewMIMap[NewMI] = {PrologNum, StageNum};
2556 Prolog->push_back(MI: NewMI);
2557 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
2558 }
2559 }
2560
2561 for (auto I : NewMIMap) {
2562 MachineInstr *MI = I.first;
2563 int PrologNum = I.second.first;
2564 int StageNum = I.second.second;
2565 updateInstrUse(MI, StageNum, PhaseNum: PrologNum, CurVRMap&: PrologVRMap, PrevVRMap: nullptr);
2566 }
2567
2568 LLVM_DEBUG({
2569 dbgs() << "prolog:\n";
2570 Prolog->dump();
2571 });
2572}
2573
2574void ModuloScheduleExpanderMVE::generateKernel(
2575 SmallVectorImpl<ValueMapTy> &PrologVRMap,
2576 SmallVectorImpl<ValueMapTy> &KernelVRMap, InstrMapTy &LastStage0Insts) {
2577 KernelVRMap.clear();
2578 KernelVRMap.resize(N: NumUnroll);
2579 SmallVector<ValueMapTy> PhiVRMap;
2580 PhiVRMap.resize(N: NumUnroll);
2581 DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;
2582 for (int UnrollNum = 0; UnrollNum < NumUnroll; ++UnrollNum) {
2583 for (MachineInstr *MI : Schedule.getInstructions()) {
2584 if (MI->isPHI())
2585 continue;
2586 int StageNum = Schedule.getStage(MI);
2587 MachineInstr *NewMI = cloneInstr(OldMI: MI);
2588 if (UnrollNum == NumUnroll - 1)
2589 LastStage0Insts[MI] = NewMI;
2590 updateInstrDef(NewMI, VRMap&: KernelVRMap[UnrollNum],
2591 LastDef: (UnrollNum == NumUnroll - 1 && StageNum == 0));
2592 generatePhi(OrigMI: MI, UnrollNum, PrologVRMap, KernelVRMap, PhiVRMap);
2593 NewMIMap[NewMI] = {UnrollNum, StageNum};
2594 NewKernel->push_back(MI: NewMI);
2595 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
2596 }
2597 }
2598
2599 for (auto I : NewMIMap) {
2600 MachineInstr *MI = I.first;
2601 int UnrollNum = I.second.first;
2602 int StageNum = I.second.second;
2603 updateInstrUse(MI, StageNum, PhaseNum: UnrollNum, CurVRMap&: KernelVRMap, PrevVRMap: &PhiVRMap);
2604 }
2605
2606 // If remaining trip count is greater than NumUnroll-1, loop continues
2607 insertCondBranch(MBB&: *NewKernel, RequiredTC: NumUnroll - 1, LastStage0Insts, GreaterThan&: *NewKernel,
2608 Otherwise&: *Epilog);
2609
2610 LLVM_DEBUG({
2611 dbgs() << "kernel:\n";
2612 NewKernel->dump();
2613 });
2614}
2615
2616void ModuloScheduleExpanderMVE::generateEpilog(
2617 SmallVectorImpl<ValueMapTy> &KernelVRMap,
2618 SmallVectorImpl<ValueMapTy> &EpilogVRMap, InstrMapTy &LastStage0Insts) {
2619 EpilogVRMap.clear();
2620 EpilogVRMap.resize(N: Schedule.getNumStages() - 1);
2621 DenseMap<MachineInstr *, std::pair<int, int>> NewMIMap;
2622 for (int EpilogNum = 0; EpilogNum < Schedule.getNumStages() - 1;
2623 ++EpilogNum) {
2624 for (MachineInstr *MI : Schedule.getInstructions()) {
2625 if (MI->isPHI())
2626 continue;
2627 int StageNum = Schedule.getStage(MI);
2628 if (StageNum <= EpilogNum)
2629 continue;
2630 MachineInstr *NewMI = cloneInstr(OldMI: MI);
2631 updateInstrDef(NewMI, VRMap&: EpilogVRMap[EpilogNum], LastDef: StageNum - 1 == EpilogNum);
2632 NewMIMap[NewMI] = {EpilogNum, StageNum};
2633 Epilog->push_back(MI: NewMI);
2634 LIS.InsertMachineInstrInMaps(MI&: *NewMI);
2635 }
2636 }
2637
2638 for (auto I : NewMIMap) {
2639 MachineInstr *MI = I.first;
2640 int EpilogNum = I.second.first;
2641 int StageNum = I.second.second;
2642 updateInstrUse(MI, StageNum, PhaseNum: EpilogNum, CurVRMap&: EpilogVRMap, PrevVRMap: &KernelVRMap);
2643 }
2644
2645 // If there are remaining iterations, they are executed in the original loop.
2646 // Instructions related to loop control, such as loop counter comparison,
2647 // are indicated by shouldIgnoreForPipelining() and are assumed to be placed
2648 // in stage 0. Thus, the map is for the last one in the kernel.
2649 insertCondBranch(MBB&: *Epilog, RequiredTC: 0, LastStage0Insts, GreaterThan&: *NewPreheader, Otherwise&: *NewExit);
2650
2651 LLVM_DEBUG({
2652 dbgs() << "epilog:\n";
2653 Epilog->dump();
2654 });
2655}
2656
2657/// Calculate the number of unroll required and set it to NumUnroll
2658void ModuloScheduleExpanderMVE::calcNumUnroll() {
2659 DenseMap<MachineInstr *, unsigned> Inst2Idx;
2660 NumUnroll = 1;
2661 for (unsigned I = 0; I < Schedule.getInstructions().size(); ++I)
2662 Inst2Idx[Schedule.getInstructions()[I]] = I;
2663
2664 for (MachineInstr *MI : Schedule.getInstructions()) {
2665 if (MI->isPHI())
2666 continue;
2667 int StageNum = Schedule.getStage(MI);
2668 for (const MachineOperand &MO : MI->uses()) {
2669 if (!MO.isReg() || !MO.getReg().isVirtual())
2670 continue;
2671 MachineInstr *DefMI = MRI.getVRegDef(Reg: MO.getReg());
2672 if (DefMI->getParent() != OrigKernel)
2673 continue;
2674
2675 int NumUnrollLocal = 1;
2676 if (DefMI->isPHI()) {
2677 ++NumUnrollLocal;
2678 // canApply() guarantees that DefMI is not phi and is an instruction in
2679 // the loop
2680 DefMI = MRI.getVRegDef(Reg: getLoopPhiReg(Phi&: *DefMI, LoopBB: OrigKernel));
2681 }
2682 NumUnrollLocal += StageNum - Schedule.getStage(MI: DefMI);
2683 if (Inst2Idx[MI] <= Inst2Idx[DefMI])
2684 --NumUnrollLocal;
2685 NumUnroll = std::max(a: NumUnroll, b: NumUnrollLocal);
2686 }
2687 }
2688 LLVM_DEBUG(dbgs() << "NumUnroll: " << NumUnroll << "\n");
2689}
2690
2691/// Create new virtual registers for definitions of NewMI and update NewMI.
2692/// If the definitions are referenced after the pipelined loop, phis are
2693/// created to merge with other routes.
2694void ModuloScheduleExpanderMVE::updateInstrDef(MachineInstr *NewMI,
2695 ValueMapTy &VRMap,
2696 bool LastDef) {
2697 for (MachineOperand &MO : NewMI->all_defs()) {
2698 if (!MO.getReg().isVirtual())
2699 continue;
2700 Register Reg = MO.getReg();
2701 const TargetRegisterClass *RC = MRI.getRegClass(Reg);
2702 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
2703 MO.setReg(NewReg);
2704 VRMap[Reg] = NewReg;
2705 if (LastDef)
2706 mergeRegUsesAfterPipeline(OrigReg: Reg, NewReg);
2707 }
2708}
2709
2710void ModuloScheduleExpanderMVE::expand() {
2711 OrigKernel = Schedule.getLoop()->getTopBlock();
2712 OrigPreheader = Schedule.getLoop()->getLoopPreheader();
2713 OrigExit = Schedule.getLoop()->getExitBlock();
2714
2715 LLVM_DEBUG(Schedule.dump());
2716
2717 generatePipelinedLoop();
2718}
2719
2720/// Check if ModuloScheduleExpanderMVE can be applied to L
2721bool ModuloScheduleExpanderMVE::canApply(MachineLoop &L) {
2722 if (!L.getExitBlock()) {
2723 LLVM_DEBUG(dbgs() << "Can not apply MVE expander: No single exit block.\n");
2724 return false;
2725 }
2726
2727 MachineBasicBlock *BB = L.getTopBlock();
2728 MachineRegisterInfo &MRI = BB->getParent()->getRegInfo();
2729
2730 // Put some constraints on the operands of the phis to simplify the
2731 // transformation
2732 DenseSet<Register> UsedByPhi;
2733 for (MachineInstr &MI : BB->phis()) {
2734 // Registers defined by phis must be used only inside the loop and be never
2735 // used by phis.
2736 for (MachineOperand &MO : MI.defs())
2737 if (MO.isReg())
2738 for (MachineInstr &Ref : MRI.use_instructions(Reg: MO.getReg()))
2739 if (Ref.getParent() != BB || Ref.isPHI()) {
2740 LLVM_DEBUG(dbgs() << "Can not apply MVE expander: A phi result is "
2741 "referenced outside of the loop or by phi.\n");
2742 return false;
2743 }
2744
2745 // A source register from the loop block must be defined inside the loop.
2746 // A register defined inside the loop must be referenced by only one phi at
2747 // most.
2748 Register InitVal, LoopVal;
2749 getPhiRegs(Phi&: MI, Loop: MI.getParent(), InitVal, LoopVal);
2750 if (!Register(LoopVal).isVirtual() || MRI.getDefBlock(Reg: LoopVal) != BB) {
2751 LLVM_DEBUG(
2752 dbgs() << "Can not apply MVE expander: A phi source value coming "
2753 "from the loop is not defined in the loop.\n");
2754 return false;
2755 }
2756 if (UsedByPhi.count(V: LoopVal)) {
2757 LLVM_DEBUG(dbgs() << "Can not apply MVE expander: A value defined in the "
2758 "loop is referenced by two or more phis.\n");
2759 return false;
2760 }
2761 UsedByPhi.insert(V: LoopVal);
2762 }
2763
2764 return true;
2765}
2766
2767//===----------------------------------------------------------------------===//
2768// ModuloScheduleTestPass implementation
2769//===----------------------------------------------------------------------===//
2770// This pass constructs a ModuloSchedule from its module and runs
2771// ModuloScheduleExpander.
2772//
2773// The module is expected to contain a single-block analyzable loop.
2774// The total order of instructions is taken from the loop as-is.
2775// Instructions are expected to be annotated with a PostInstrSymbol.
2776// This PostInstrSymbol must have the following format:
2777// "Stage=%d Cycle=%d".
2778//===----------------------------------------------------------------------===//
2779
2780namespace {
2781class ModuloScheduleTest : public MachineFunctionPass {
2782public:
2783 static char ID;
2784
2785 ModuloScheduleTest() : MachineFunctionPass(ID) {}
2786
2787 bool runOnMachineFunction(MachineFunction &MF) override;
2788 void runOnLoop(MachineFunction &MF, MachineLoop &L);
2789
2790 void getAnalysisUsage(AnalysisUsage &AU) const override {
2791 AU.addRequired<MachineLoopInfoWrapperPass>();
2792 AU.addRequired<LiveIntervalsWrapperPass>();
2793 MachineFunctionPass::getAnalysisUsage(AU);
2794 }
2795};
2796} // namespace
2797
2798char ModuloScheduleTest::ID = 0;
2799
2800INITIALIZE_PASS_BEGIN(ModuloScheduleTest, "modulo-schedule-test",
2801 "Modulo Schedule test pass", false, false)
2802INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
2803INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
2804INITIALIZE_PASS_END(ModuloScheduleTest, "modulo-schedule-test",
2805 "Modulo Schedule test pass", false, false)
2806
2807bool ModuloScheduleTest::runOnMachineFunction(MachineFunction &MF) {
2808 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
2809 for (auto *L : MLI) {
2810 if (L->getTopBlock() != L->getBottomBlock())
2811 continue;
2812 runOnLoop(MF, L&: *L);
2813 return false;
2814 }
2815 return false;
2816}
2817
2818static void parseSymbolString(StringRef S, int &Cycle, int &Stage) {
2819 std::pair<StringRef, StringRef> StageAndCycle = getToken(Source: S, Delimiters: "_");
2820 std::pair<StringRef, StringRef> StageTokenAndValue =
2821 getToken(Source: StageAndCycle.first, Delimiters: "-");
2822 std::pair<StringRef, StringRef> CycleTokenAndValue =
2823 getToken(Source: StageAndCycle.second, Delimiters: "-");
2824 if (StageTokenAndValue.first != "Stage" ||
2825 CycleTokenAndValue.first != "_Cycle") {
2826 llvm_unreachable(
2827 "Bad post-instr symbol syntax: see comment in ModuloScheduleTest");
2828 return;
2829 }
2830
2831 StageTokenAndValue.second.drop_front().getAsInteger(Radix: 10, Result&: Stage);
2832 CycleTokenAndValue.second.drop_front().getAsInteger(Radix: 10, Result&: Cycle);
2833
2834 dbgs() << " Stage=" << Stage << ", Cycle=" << Cycle << "\n";
2835}
2836
2837void ModuloScheduleTest::runOnLoop(MachineFunction &MF, MachineLoop &L) {
2838 LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
2839 MachineBasicBlock *BB = L.getTopBlock();
2840 dbgs() << "--- ModuloScheduleTest running on BB#" << BB->getNumber() << "\n";
2841
2842 DenseMap<MachineInstr *, int> Cycle, Stage;
2843 std::vector<MachineInstr *> Instrs;
2844 for (MachineInstr &MI : *BB) {
2845 if (MI.isTerminator())
2846 continue;
2847 Instrs.push_back(x: &MI);
2848 if (MCSymbol *Sym = MI.getPostInstrSymbol()) {
2849 dbgs() << "Parsing post-instr symbol for " << MI;
2850 parseSymbolString(S: Sym->getName(), Cycle&: Cycle[&MI], Stage&: Stage[&MI]);
2851 }
2852 }
2853
2854 ModuloSchedule MS(MF, &L, std::move(Instrs), std::move(Cycle),
2855 std::move(Stage));
2856 ModuloScheduleExpander MSE(
2857 MF, MS, LIS, /*InstrChanges=*/ModuloScheduleExpander::InstrChangesTy());
2858 MSE.expand();
2859 MSE.cleanup();
2860}
2861
2862//===----------------------------------------------------------------------===//
2863// ModuloScheduleTestAnnotater implementation
2864//===----------------------------------------------------------------------===//
2865
2866void ModuloScheduleTestAnnotater::annotate() {
2867 for (MachineInstr *MI : S.getInstructions()) {
2868 SmallVector<char, 16> SV;
2869 raw_svector_ostream OS(SV);
2870 OS << "Stage-" << S.getStage(MI) << "_Cycle-" << S.getCycle(MI);
2871 MCSymbol *Sym = MF.getContext().getOrCreateSymbol(Name: OS.str());
2872 MI->setPostInstrSymbol(MF, Symbol: Sym);
2873 }
2874}
2875