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/CodeGen/LiveIntervals.h"
12 #include "llvm/CodeGen/MachineInstrBuilder.h"
13 #include "llvm/CodeGen/MachineLoopUtils.h"
14 #include "llvm/CodeGen/MachineRegisterInfo.h"
15 #include "llvm/CodeGen/TargetInstrInfo.h"
16 #include "llvm/InitializePasses.h"
17 #include "llvm/MC/MCContext.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/ErrorHandling.h"
20 #include "llvm/Support/raw_ostream.h"
21
22 #define DEBUG_TYPE "pipeliner"
23 using namespace llvm;
24
print(raw_ostream & OS)25 void ModuloSchedule::print(raw_ostream &OS) {
26 for (MachineInstr *MI : ScheduledInstrs)
27 OS << "[stage " << getStage(MI) << " @" << getCycle(MI) << "c] " << *MI;
28 }
29
30 //===----------------------------------------------------------------------===//
31 // ModuloScheduleExpander implementation
32 //===----------------------------------------------------------------------===//
33
34 /// Return the register values for the operands of a Phi instruction.
35 /// This function assume the instruction is a Phi.
getPhiRegs(MachineInstr & Phi,MachineBasicBlock * Loop,unsigned & InitVal,unsigned & LoopVal)36 static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
37 unsigned &InitVal, unsigned &LoopVal) {
38 assert(Phi.isPHI() && "Expecting a Phi.");
39
40 InitVal = 0;
41 LoopVal = 0;
42 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
43 if (Phi.getOperand(i + 1).getMBB() != Loop)
44 InitVal = Phi.getOperand(i).getReg();
45 else
46 LoopVal = Phi.getOperand(i).getReg();
47
48 assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure.");
49 }
50
51 /// Return the Phi register value that comes from the incoming block.
getInitPhiReg(MachineInstr & Phi,MachineBasicBlock * LoopBB)52 static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
53 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
54 if (Phi.getOperand(i + 1).getMBB() != LoopBB)
55 return Phi.getOperand(i).getReg();
56 return 0;
57 }
58
59 /// Return the Phi register value that comes the loop block.
getLoopPhiReg(MachineInstr & Phi,MachineBasicBlock * LoopBB)60 static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
61 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
62 if (Phi.getOperand(i + 1).getMBB() == LoopBB)
63 return Phi.getOperand(i).getReg();
64 return 0;
65 }
66
expand()67 void ModuloScheduleExpander::expand() {
68 BB = Schedule.getLoop()->getTopBlock();
69 Preheader = *BB->pred_begin();
70 if (Preheader == BB)
71 Preheader = *std::next(BB->pred_begin());
72
73 // Iterate over the definitions in each instruction, and compute the
74 // stage difference for each use. Keep the maximum value.
75 for (MachineInstr *MI : Schedule.getInstructions()) {
76 int DefStage = Schedule.getStage(MI);
77 for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
78 MachineOperand &Op = MI->getOperand(i);
79 if (!Op.isReg() || !Op.isDef())
80 continue;
81
82 Register Reg = Op.getReg();
83 unsigned MaxDiff = 0;
84 bool PhiIsSwapped = false;
85 for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(Reg),
86 EI = MRI.use_end();
87 UI != EI; ++UI) {
88 MachineOperand &UseOp = *UI;
89 MachineInstr *UseMI = UseOp.getParent();
90 int UseStage = Schedule.getStage(UseMI);
91 unsigned Diff = 0;
92 if (UseStage != -1 && UseStage >= DefStage)
93 Diff = UseStage - DefStage;
94 if (MI->isPHI()) {
95 if (isLoopCarried(*MI))
96 ++Diff;
97 else
98 PhiIsSwapped = true;
99 }
100 MaxDiff = std::max(Diff, MaxDiff);
101 }
102 RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped);
103 }
104 }
105
106 generatePipelinedLoop();
107 }
108
generatePipelinedLoop()109 void ModuloScheduleExpander::generatePipelinedLoop() {
110 LoopInfo = TII->analyzeLoopForPipelining(BB);
111 assert(LoopInfo && "Must be able to analyze loop!");
112
113 // Create a new basic block for the kernel and add it to the CFG.
114 MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
115
116 unsigned MaxStageCount = Schedule.getNumStages() - 1;
117
118 // Remember the registers that are used in different stages. The index is
119 // the iteration, or stage, that the instruction is scheduled in. This is
120 // a map between register names in the original block and the names created
121 // in each stage of the pipelined loop.
122 ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2];
123 InstrMapTy InstrMap;
124
125 SmallVector<MachineBasicBlock *, 4> PrologBBs;
126
127 // Generate the prolog instructions that set up the pipeline.
128 generateProlog(MaxStageCount, KernelBB, VRMap, PrologBBs);
129 MF.insert(BB->getIterator(), KernelBB);
130
131 // Rearrange the instructions to generate the new, pipelined loop,
132 // and update register names as needed.
133 for (MachineInstr *CI : Schedule.getInstructions()) {
134 if (CI->isPHI())
135 continue;
136 unsigned StageNum = Schedule.getStage(CI);
137 MachineInstr *NewMI = cloneInstr(CI, MaxStageCount, StageNum);
138 updateInstruction(NewMI, false, MaxStageCount, StageNum, VRMap);
139 KernelBB->push_back(NewMI);
140 InstrMap[NewMI] = CI;
141 }
142
143 // Copy any terminator instructions to the new kernel, and update
144 // names as needed.
145 for (MachineBasicBlock::iterator I = BB->getFirstTerminator(),
146 E = BB->instr_end();
147 I != E; ++I) {
148 MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
149 updateInstruction(NewMI, false, MaxStageCount, 0, VRMap);
150 KernelBB->push_back(NewMI);
151 InstrMap[NewMI] = &*I;
152 }
153
154 NewKernel = KernelBB;
155 KernelBB->transferSuccessors(BB);
156 KernelBB->replaceSuccessor(BB, KernelBB);
157
158 generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap,
159 InstrMap, MaxStageCount, MaxStageCount, false);
160 generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap, InstrMap,
161 MaxStageCount, MaxStageCount, false);
162
163 LLVM_DEBUG(dbgs() << "New block\n"; KernelBB->dump(););
164
165 SmallVector<MachineBasicBlock *, 4> EpilogBBs;
166 // Generate the epilog instructions to complete the pipeline.
167 generateEpilog(MaxStageCount, KernelBB, VRMap, EpilogBBs, PrologBBs);
168
169 // We need this step because the register allocation doesn't handle some
170 // situations well, so we insert copies to help out.
171 splitLifetimes(KernelBB, EpilogBBs);
172
173 // Remove dead instructions due to loop induction variables.
174 removeDeadInstructions(KernelBB, EpilogBBs);
175
176 // Add branches between prolog and epilog blocks.
177 addBranches(*Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap);
178
179 delete[] VRMap;
180 }
181
cleanup()182 void ModuloScheduleExpander::cleanup() {
183 // Remove the original loop since it's no longer referenced.
184 for (auto &I : *BB)
185 LIS.RemoveMachineInstrFromMaps(I);
186 BB->clear();
187 BB->eraseFromParent();
188 }
189
190 /// Generate the pipeline prolog code.
generateProlog(unsigned LastStage,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,MBBVectorTy & PrologBBs)191 void ModuloScheduleExpander::generateProlog(unsigned LastStage,
192 MachineBasicBlock *KernelBB,
193 ValueMapTy *VRMap,
194 MBBVectorTy &PrologBBs) {
195 MachineBasicBlock *PredBB = Preheader;
196 InstrMapTy InstrMap;
197
198 // Generate a basic block for each stage, not including the last stage,
199 // which will be generated in the kernel. Each basic block may contain
200 // instructions from multiple stages/iterations.
201 for (unsigned i = 0; i < LastStage; ++i) {
202 // Create and insert the prolog basic block prior to the original loop
203 // basic block. The original loop is removed later.
204 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
205 PrologBBs.push_back(NewBB);
206 MF.insert(BB->getIterator(), NewBB);
207 NewBB->transferSuccessors(PredBB);
208 PredBB->addSuccessor(NewBB);
209 PredBB = NewBB;
210
211 // Generate instructions for each appropriate stage. Process instructions
212 // in original program order.
213 for (int StageNum = i; StageNum >= 0; --StageNum) {
214 for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
215 BBE = BB->getFirstTerminator();
216 BBI != BBE; ++BBI) {
217 if (Schedule.getStage(&*BBI) == StageNum) {
218 if (BBI->isPHI())
219 continue;
220 MachineInstr *NewMI =
221 cloneAndChangeInstr(&*BBI, i, (unsigned)StageNum);
222 updateInstruction(NewMI, false, i, (unsigned)StageNum, VRMap);
223 NewBB->push_back(NewMI);
224 InstrMap[NewMI] = &*BBI;
225 }
226 }
227 }
228 rewritePhiValues(NewBB, i, VRMap, InstrMap);
229 LLVM_DEBUG({
230 dbgs() << "prolog:\n";
231 NewBB->dump();
232 });
233 }
234
235 PredBB->replaceSuccessor(BB, KernelBB);
236
237 // Check if we need to remove the branch from the preheader to the original
238 // loop, and replace it with a branch to the new loop.
239 unsigned numBranches = TII->removeBranch(*Preheader);
240 if (numBranches) {
241 SmallVector<MachineOperand, 0> Cond;
242 TII->insertBranch(*Preheader, PrologBBs[0], nullptr, Cond, DebugLoc());
243 }
244 }
245
246 /// Generate the pipeline epilog code. The epilog code finishes the iterations
247 /// that were started in either the prolog or the kernel. We create a basic
248 /// block for each stage that needs to complete.
generateEpilog(unsigned LastStage,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,MBBVectorTy & EpilogBBs,MBBVectorTy & PrologBBs)249 void ModuloScheduleExpander::generateEpilog(unsigned LastStage,
250 MachineBasicBlock *KernelBB,
251 ValueMapTy *VRMap,
252 MBBVectorTy &EpilogBBs,
253 MBBVectorTy &PrologBBs) {
254 // We need to change the branch from the kernel to the first epilog block, so
255 // this call to analyze branch uses the kernel rather than the original BB.
256 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
257 SmallVector<MachineOperand, 4> Cond;
258 bool checkBranch = TII->analyzeBranch(*KernelBB, TBB, FBB, Cond);
259 assert(!checkBranch && "generateEpilog must be able to analyze the branch");
260 if (checkBranch)
261 return;
262
263 MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin();
264 if (*LoopExitI == KernelBB)
265 ++LoopExitI;
266 assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor");
267 MachineBasicBlock *LoopExitBB = *LoopExitI;
268
269 MachineBasicBlock *PredBB = KernelBB;
270 MachineBasicBlock *EpilogStart = LoopExitBB;
271 InstrMapTy InstrMap;
272
273 // Generate a basic block for each stage, not including the last stage,
274 // which was generated for the kernel. Each basic block may contain
275 // instructions from multiple stages/iterations.
276 int EpilogStage = LastStage + 1;
277 for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {
278 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock();
279 EpilogBBs.push_back(NewBB);
280 MF.insert(BB->getIterator(), NewBB);
281
282 PredBB->replaceSuccessor(LoopExitBB, NewBB);
283 NewBB->addSuccessor(LoopExitBB);
284
285 if (EpilogStart == LoopExitBB)
286 EpilogStart = NewBB;
287
288 // Add instructions to the epilog depending on the current block.
289 // Process instructions in original program order.
290 for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) {
291 for (auto &BBI : *BB) {
292 if (BBI.isPHI())
293 continue;
294 MachineInstr *In = &BBI;
295 if ((unsigned)Schedule.getStage(In) == StageNum) {
296 // Instructions with memoperands in the epilog are updated with
297 // conservative values.
298 MachineInstr *NewMI = cloneInstr(In, UINT_MAX, 0);
299 updateInstruction(NewMI, i == 1, EpilogStage, 0, VRMap);
300 NewBB->push_back(NewMI);
301 InstrMap[NewMI] = In;
302 }
303 }
304 }
305 generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap,
306 InstrMap, LastStage, EpilogStage, i == 1);
307 generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap, InstrMap,
308 LastStage, EpilogStage, i == 1);
309 PredBB = NewBB;
310
311 LLVM_DEBUG({
312 dbgs() << "epilog:\n";
313 NewBB->dump();
314 });
315 }
316
317 // Fix any Phi nodes in the loop exit block.
318 LoopExitBB->replacePhiUsesWith(BB, PredBB);
319
320 // Create a branch to the new epilog from the kernel.
321 // Remove the original branch and add a new branch to the epilog.
322 TII->removeBranch(*KernelBB);
323 TII->insertBranch(*KernelBB, KernelBB, EpilogStart, Cond, DebugLoc());
324 // Add a branch to the loop exit.
325 if (EpilogBBs.size() > 0) {
326 MachineBasicBlock *LastEpilogBB = EpilogBBs.back();
327 SmallVector<MachineOperand, 4> Cond1;
328 TII->insertBranch(*LastEpilogBB, LoopExitBB, nullptr, Cond1, DebugLoc());
329 }
330 }
331
332 /// Replace all uses of FromReg that appear outside the specified
333 /// basic block with ToReg.
replaceRegUsesAfterLoop(unsigned FromReg,unsigned ToReg,MachineBasicBlock * MBB,MachineRegisterInfo & MRI,LiveIntervals & LIS)334 static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg,
335 MachineBasicBlock *MBB,
336 MachineRegisterInfo &MRI,
337 LiveIntervals &LIS) {
338 for (MachineRegisterInfo::use_iterator I = MRI.use_begin(FromReg),
339 E = MRI.use_end();
340 I != E;) {
341 MachineOperand &O = *I;
342 ++I;
343 if (O.getParent()->getParent() != MBB)
344 O.setReg(ToReg);
345 }
346 if (!LIS.hasInterval(ToReg))
347 LIS.createEmptyInterval(ToReg);
348 }
349
350 /// Return true if the register has a use that occurs outside the
351 /// specified loop.
hasUseAfterLoop(unsigned Reg,MachineBasicBlock * BB,MachineRegisterInfo & MRI)352 static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB,
353 MachineRegisterInfo &MRI) {
354 for (MachineRegisterInfo::use_iterator I = MRI.use_begin(Reg),
355 E = MRI.use_end();
356 I != E; ++I)
357 if (I->getParent()->getParent() != BB)
358 return true;
359 return false;
360 }
361
362 /// Generate Phis for the specific block in the generated pipelined code.
363 /// This function looks at the Phis from the original code to guide the
364 /// creation of new Phis.
generateExistingPhis(MachineBasicBlock * NewBB,MachineBasicBlock * BB1,MachineBasicBlock * BB2,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,InstrMapTy & InstrMap,unsigned LastStageNum,unsigned CurStageNum,bool IsLast)365 void ModuloScheduleExpander::generateExistingPhis(
366 MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
367 MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap,
368 unsigned LastStageNum, unsigned CurStageNum, bool IsLast) {
369 // Compute the stage number for the initial value of the Phi, which
370 // comes from the prolog. The prolog to use depends on to which kernel/
371 // epilog that we're adding the Phi.
372 unsigned PrologStage = 0;
373 unsigned PrevStage = 0;
374 bool InKernel = (LastStageNum == CurStageNum);
375 if (InKernel) {
376 PrologStage = LastStageNum - 1;
377 PrevStage = CurStageNum;
378 } else {
379 PrologStage = LastStageNum - (CurStageNum - LastStageNum);
380 PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;
381 }
382
383 for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
384 BBE = BB->getFirstNonPHI();
385 BBI != BBE; ++BBI) {
386 Register Def = BBI->getOperand(0).getReg();
387
388 unsigned InitVal = 0;
389 unsigned LoopVal = 0;
390 getPhiRegs(*BBI, BB, InitVal, LoopVal);
391
392 unsigned PhiOp1 = 0;
393 // The Phi value from the loop body typically is defined in the loop, but
394 // not always. So, we need to check if the value is defined in the loop.
395 unsigned PhiOp2 = LoopVal;
396 if (VRMap[LastStageNum].count(LoopVal))
397 PhiOp2 = VRMap[LastStageNum][LoopVal];
398
399 int StageScheduled = Schedule.getStage(&*BBI);
400 int LoopValStage = Schedule.getStage(MRI.getVRegDef(LoopVal));
401 unsigned NumStages = getStagesForReg(Def, CurStageNum);
402 if (NumStages == 0) {
403 // We don't need to generate a Phi anymore, but we need to rename any uses
404 // of the Phi value.
405 unsigned NewReg = VRMap[PrevStage][LoopVal];
406 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, 0, &*BBI, Def,
407 InitVal, NewReg);
408 if (VRMap[CurStageNum].count(LoopVal))
409 VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal];
410 }
411 // Adjust the number of Phis needed depending on the number of prologs left,
412 // and the distance from where the Phi is first scheduled. The number of
413 // Phis cannot exceed the number of prolog stages. Each stage can
414 // potentially define two values.
415 unsigned MaxPhis = PrologStage + 2;
416 if (!InKernel && (int)PrologStage <= LoopValStage)
417 MaxPhis = std::max((int)MaxPhis - (int)LoopValStage, 1);
418 unsigned NumPhis = std::min(NumStages, MaxPhis);
419
420 unsigned NewReg = 0;
421 unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;
422 // In the epilog, we may need to look back one stage to get the correct
423 // Phi name because the epilog and prolog blocks execute the same stage.
424 // The correct name is from the previous block only when the Phi has
425 // been completely scheduled prior to the epilog, and Phi value is not
426 // needed in multiple stages.
427 int StageDiff = 0;
428 if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&
429 NumPhis == 1)
430 StageDiff = 1;
431 // Adjust the computations below when the phi and the loop definition
432 // are scheduled in different stages.
433 if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)
434 StageDiff = StageScheduled - LoopValStage;
435 for (unsigned np = 0; np < NumPhis; ++np) {
436 // If the Phi hasn't been scheduled, then use the initial Phi operand
437 // value. Otherwise, use the scheduled version of the instruction. This
438 // is a little complicated when a Phi references another Phi.
439 if (np > PrologStage || StageScheduled >= (int)LastStageNum)
440 PhiOp1 = InitVal;
441 // Check if the Phi has already been scheduled in a prolog stage.
442 else if (PrologStage >= AccessStage + StageDiff + np &&
443 VRMap[PrologStage - StageDiff - np].count(LoopVal) != 0)
444 PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];
445 // Check if the Phi has already been scheduled, but the loop instruction
446 // is either another Phi, or doesn't occur in the loop.
447 else if (PrologStage >= AccessStage + StageDiff + np) {
448 // If the Phi references another Phi, we need to examine the other
449 // Phi to get the correct value.
450 PhiOp1 = LoopVal;
451 MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1);
452 int Indirects = 1;
453 while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) {
454 int PhiStage = Schedule.getStage(InstOp1);
455 if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects)
456 PhiOp1 = getInitPhiReg(*InstOp1, BB);
457 else
458 PhiOp1 = getLoopPhiReg(*InstOp1, BB);
459 InstOp1 = MRI.getVRegDef(PhiOp1);
460 int PhiOpStage = Schedule.getStage(InstOp1);
461 int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);
462 if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np &&
463 VRMap[PrologStage - StageAdj - Indirects - np].count(PhiOp1)) {
464 PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1];
465 break;
466 }
467 ++Indirects;
468 }
469 } else
470 PhiOp1 = InitVal;
471 // If this references a generated Phi in the kernel, get the Phi operand
472 // from the incoming block.
473 if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1))
474 if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB)
475 PhiOp1 = getInitPhiReg(*InstOp1, KernelBB);
476
477 MachineInstr *PhiInst = MRI.getVRegDef(LoopVal);
478 bool LoopDefIsPhi = PhiInst && PhiInst->isPHI();
479 // In the epilog, a map lookup is needed to get the value from the kernel,
480 // or previous epilog block. How is does this depends on if the
481 // instruction is scheduled in the previous block.
482 if (!InKernel) {
483 int StageDiffAdj = 0;
484 if (LoopValStage != -1 && StageScheduled > LoopValStage)
485 StageDiffAdj = StageScheduled - LoopValStage;
486 // Use the loop value defined in the kernel, unless the kernel
487 // contains the last definition of the Phi.
488 if (np == 0 && PrevStage == LastStageNum &&
489 (StageScheduled != 0 || LoopValStage != 0) &&
490 VRMap[PrevStage - StageDiffAdj].count(LoopVal))
491 PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal];
492 // Use the value defined by the Phi. We add one because we switch
493 // from looking at the loop value to the Phi definition.
494 else if (np > 0 && PrevStage == LastStageNum &&
495 VRMap[PrevStage - np + 1].count(Def))
496 PhiOp2 = VRMap[PrevStage - np + 1][Def];
497 // Use the loop value defined in the kernel.
498 else if (static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&
499 VRMap[PrevStage - StageDiffAdj - np].count(LoopVal))
500 PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal];
501 // Use the value defined by the Phi, unless we're generating the first
502 // epilog and the Phi refers to a Phi in a different stage.
503 else if (VRMap[PrevStage - np].count(Def) &&
504 (!LoopDefIsPhi || (PrevStage != LastStageNum) ||
505 (LoopValStage == StageScheduled)))
506 PhiOp2 = VRMap[PrevStage - np][Def];
507 }
508
509 // Check if we can reuse an existing Phi. This occurs when a Phi
510 // references another Phi, and the other Phi is scheduled in an
511 // earlier stage. We can try to reuse an existing Phi up until the last
512 // stage of the current Phi.
513 if (LoopDefIsPhi) {
514 if (static_cast<int>(PrologStage - np) >= StageScheduled) {
515 int LVNumStages = getStagesForPhi(LoopVal);
516 int StageDiff = (StageScheduled - LoopValStage);
517 LVNumStages -= StageDiff;
518 // Make sure the loop value Phi has been processed already.
519 if (LVNumStages > (int)np && VRMap[CurStageNum].count(LoopVal)) {
520 NewReg = PhiOp2;
521 unsigned ReuseStage = CurStageNum;
522 if (isLoopCarried(*PhiInst))
523 ReuseStage -= LVNumStages;
524 // Check if the Phi to reuse has been generated yet. If not, then
525 // there is nothing to reuse.
526 if (VRMap[ReuseStage - np].count(LoopVal)) {
527 NewReg = VRMap[ReuseStage - np][LoopVal];
528
529 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
530 Def, NewReg);
531 // Update the map with the new Phi name.
532 VRMap[CurStageNum - np][Def] = NewReg;
533 PhiOp2 = NewReg;
534 if (VRMap[LastStageNum - np - 1].count(LoopVal))
535 PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];
536
537 if (IsLast && np == NumPhis - 1)
538 replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
539 continue;
540 }
541 }
542 }
543 if (InKernel && StageDiff > 0 &&
544 VRMap[CurStageNum - StageDiff - np].count(LoopVal))
545 PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];
546 }
547
548 const TargetRegisterClass *RC = MRI.getRegClass(Def);
549 NewReg = MRI.createVirtualRegister(RC);
550
551 MachineInstrBuilder NewPhi =
552 BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(),
553 TII->get(TargetOpcode::PHI), NewReg);
554 NewPhi.addReg(PhiOp1).addMBB(BB1);
555 NewPhi.addReg(PhiOp2).addMBB(BB2);
556 if (np == 0)
557 InstrMap[NewPhi] = &*BBI;
558
559 // We define the Phis after creating the new pipelined code, so
560 // we need to rename the Phi values in scheduled instructions.
561
562 unsigned PrevReg = 0;
563 if (InKernel && VRMap[PrevStage - np].count(LoopVal))
564 PrevReg = VRMap[PrevStage - np][LoopVal];
565 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,
566 NewReg, PrevReg);
567 // If the Phi has been scheduled, use the new name for rewriting.
568 if (VRMap[CurStageNum - np].count(Def)) {
569 unsigned R = VRMap[CurStageNum - np][Def];
570 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, R,
571 NewReg);
572 }
573
574 // Check if we need to rename any uses that occurs after the loop. The
575 // register to replace depends on whether the Phi is scheduled in the
576 // epilog.
577 if (IsLast && np == NumPhis - 1)
578 replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
579
580 // In the kernel, a dependent Phi uses the value from this Phi.
581 if (InKernel)
582 PhiOp2 = NewReg;
583
584 // Update the map with the new Phi name.
585 VRMap[CurStageNum - np][Def] = NewReg;
586 }
587
588 while (NumPhis++ < NumStages) {
589 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, NumPhis, &*BBI, Def,
590 NewReg, 0);
591 }
592
593 // Check if we need to rename a Phi that has been eliminated due to
594 // scheduling.
595 if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal))
596 replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS);
597 }
598 }
599
600 /// Generate Phis for the specified block in the generated pipelined code.
601 /// These are new Phis needed because the definition is scheduled after the
602 /// use in the pipelined sequence.
generatePhis(MachineBasicBlock * NewBB,MachineBasicBlock * BB1,MachineBasicBlock * BB2,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,InstrMapTy & InstrMap,unsigned LastStageNum,unsigned CurStageNum,bool IsLast)603 void ModuloScheduleExpander::generatePhis(
604 MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
605 MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap,
606 unsigned LastStageNum, unsigned CurStageNum, bool IsLast) {
607 // Compute the stage number that contains the initial Phi value, and
608 // the Phi from the previous stage.
609 unsigned PrologStage = 0;
610 unsigned PrevStage = 0;
611 unsigned StageDiff = CurStageNum - LastStageNum;
612 bool InKernel = (StageDiff == 0);
613 if (InKernel) {
614 PrologStage = LastStageNum - 1;
615 PrevStage = CurStageNum;
616 } else {
617 PrologStage = LastStageNum - StageDiff;
618 PrevStage = LastStageNum + StageDiff - 1;
619 }
620
621 for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(),
622 BBE = BB->instr_end();
623 BBI != BBE; ++BBI) {
624 for (unsigned i = 0, e = BBI->getNumOperands(); i != e; ++i) {
625 MachineOperand &MO = BBI->getOperand(i);
626 if (!MO.isReg() || !MO.isDef() ||
627 !Register::isVirtualRegister(MO.getReg()))
628 continue;
629
630 int StageScheduled = Schedule.getStage(&*BBI);
631 assert(StageScheduled != -1 && "Expecting scheduled instruction.");
632 Register Def = MO.getReg();
633 unsigned NumPhis = getStagesForReg(Def, CurStageNum);
634 // An instruction scheduled in stage 0 and is used after the loop
635 // requires a phi in the epilog for the last definition from either
636 // the kernel or prolog.
637 if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&
638 hasUseAfterLoop(Def, BB, MRI))
639 NumPhis = 1;
640 if (!InKernel && (unsigned)StageScheduled > PrologStage)
641 continue;
642
643 unsigned PhiOp2 = VRMap[PrevStage][Def];
644 if (MachineInstr *InstOp2 = MRI.getVRegDef(PhiOp2))
645 if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)
646 PhiOp2 = getLoopPhiReg(*InstOp2, BB2);
647 // The number of Phis can't exceed the number of prolog stages. The
648 // prolog stage number is zero based.
649 if (NumPhis > PrologStage + 1 - StageScheduled)
650 NumPhis = PrologStage + 1 - StageScheduled;
651 for (unsigned np = 0; np < NumPhis; ++np) {
652 unsigned PhiOp1 = VRMap[PrologStage][Def];
653 if (np <= PrologStage)
654 PhiOp1 = VRMap[PrologStage - np][Def];
655 if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) {
656 if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB)
657 PhiOp1 = getInitPhiReg(*InstOp1, KernelBB);
658 if (InstOp1->isPHI() && InstOp1->getParent() == NewBB)
659 PhiOp1 = getInitPhiReg(*InstOp1, NewBB);
660 }
661 if (!InKernel)
662 PhiOp2 = VRMap[PrevStage - np][Def];
663
664 const TargetRegisterClass *RC = MRI.getRegClass(Def);
665 Register NewReg = MRI.createVirtualRegister(RC);
666
667 MachineInstrBuilder NewPhi =
668 BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(),
669 TII->get(TargetOpcode::PHI), NewReg);
670 NewPhi.addReg(PhiOp1).addMBB(BB1);
671 NewPhi.addReg(PhiOp2).addMBB(BB2);
672 if (np == 0)
673 InstrMap[NewPhi] = &*BBI;
674
675 // Rewrite uses and update the map. The actions depend upon whether
676 // we generating code for the kernel or epilog blocks.
677 if (InKernel) {
678 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp1,
679 NewReg);
680 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp2,
681 NewReg);
682
683 PhiOp2 = NewReg;
684 VRMap[PrevStage - np - 1][Def] = NewReg;
685 } else {
686 VRMap[CurStageNum - np][Def] = NewReg;
687 if (np == NumPhis - 1)
688 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,
689 NewReg);
690 }
691 if (IsLast && np == NumPhis - 1)
692 replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
693 }
694 }
695 }
696 }
697
698 /// Remove instructions that generate values with no uses.
699 /// Typically, these are induction variable operations that generate values
700 /// used in the loop itself. A dead instruction has a definition with
701 /// no uses, or uses that occur in the original loop only.
removeDeadInstructions(MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs)702 void ModuloScheduleExpander::removeDeadInstructions(MachineBasicBlock *KernelBB,
703 MBBVectorTy &EpilogBBs) {
704 // For each epilog block, check that the value defined by each instruction
705 // is used. If not, delete it.
706 for (MBBVectorTy::reverse_iterator MBB = EpilogBBs.rbegin(),
707 MBE = EpilogBBs.rend();
708 MBB != MBE; ++MBB)
709 for (MachineBasicBlock::reverse_instr_iterator MI = (*MBB)->instr_rbegin(),
710 ME = (*MBB)->instr_rend();
711 MI != ME;) {
712 // From DeadMachineInstructionElem. Don't delete inline assembly.
713 if (MI->isInlineAsm()) {
714 ++MI;
715 continue;
716 }
717 bool SawStore = false;
718 // Check if it's safe to remove the instruction due to side effects.
719 // We can, and want to, remove Phis here.
720 if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI()) {
721 ++MI;
722 continue;
723 }
724 bool used = true;
725 for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
726 MOE = MI->operands_end();
727 MOI != MOE; ++MOI) {
728 if (!MOI->isReg() || !MOI->isDef())
729 continue;
730 Register reg = MOI->getReg();
731 // Assume physical registers are used, unless they are marked dead.
732 if (Register::isPhysicalRegister(reg)) {
733 used = !MOI->isDead();
734 if (used)
735 break;
736 continue;
737 }
738 unsigned realUses = 0;
739 for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(reg),
740 EI = MRI.use_end();
741 UI != EI; ++UI) {
742 // Check if there are any uses that occur only in the original
743 // loop. If so, that's not a real use.
744 if (UI->getParent()->getParent() != BB) {
745 realUses++;
746 used = true;
747 break;
748 }
749 }
750 if (realUses > 0)
751 break;
752 used = false;
753 }
754 if (!used) {
755 LIS.RemoveMachineInstrFromMaps(*MI);
756 MI++->eraseFromParent();
757 continue;
758 }
759 ++MI;
760 }
761 // In the kernel block, check if we can remove a Phi that generates a value
762 // used in an instruction removed in the epilog block.
763 for (MachineBasicBlock::iterator BBI = KernelBB->instr_begin(),
764 BBE = KernelBB->getFirstNonPHI();
765 BBI != BBE;) {
766 MachineInstr *MI = &*BBI;
767 ++BBI;
768 Register reg = MI->getOperand(0).getReg();
769 if (MRI.use_begin(reg) == MRI.use_end()) {
770 LIS.RemoveMachineInstrFromMaps(*MI);
771 MI->eraseFromParent();
772 }
773 }
774 }
775
776 /// For loop carried definitions, we split the lifetime of a virtual register
777 /// that has uses past the definition in the next iteration. A copy with a new
778 /// virtual register is inserted before the definition, which helps with
779 /// generating a better register assignment.
780 ///
781 /// v1 = phi(a, v2) v1 = phi(a, v2)
782 /// v2 = phi(b, v3) v2 = phi(b, v3)
783 /// v3 = .. v4 = copy v1
784 /// .. = V1 v3 = ..
785 /// .. = v4
splitLifetimes(MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs)786 void ModuloScheduleExpander::splitLifetimes(MachineBasicBlock *KernelBB,
787 MBBVectorTy &EpilogBBs) {
788 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
789 for (auto &PHI : KernelBB->phis()) {
790 Register Def = PHI.getOperand(0).getReg();
791 // Check for any Phi definition that used as an operand of another Phi
792 // in the same block.
793 for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(Def),
794 E = MRI.use_instr_end();
795 I != E; ++I) {
796 if (I->isPHI() && I->getParent() == KernelBB) {
797 // Get the loop carried definition.
798 unsigned LCDef = getLoopPhiReg(PHI, KernelBB);
799 if (!LCDef)
800 continue;
801 MachineInstr *MI = MRI.getVRegDef(LCDef);
802 if (!MI || MI->getParent() != KernelBB || MI->isPHI())
803 continue;
804 // Search through the rest of the block looking for uses of the Phi
805 // definition. If one occurs, then split the lifetime.
806 unsigned SplitReg = 0;
807 for (auto &BBJ : make_range(MachineBasicBlock::instr_iterator(MI),
808 KernelBB->instr_end()))
809 if (BBJ.readsRegister(Def)) {
810 // We split the lifetime when we find the first use.
811 if (SplitReg == 0) {
812 SplitReg = MRI.createVirtualRegister(MRI.getRegClass(Def));
813 BuildMI(*KernelBB, MI, MI->getDebugLoc(),
814 TII->get(TargetOpcode::COPY), SplitReg)
815 .addReg(Def);
816 }
817 BBJ.substituteRegister(Def, SplitReg, 0, *TRI);
818 }
819 if (!SplitReg)
820 continue;
821 // Search through each of the epilog blocks for any uses to be renamed.
822 for (auto &Epilog : EpilogBBs)
823 for (auto &I : *Epilog)
824 if (I.readsRegister(Def))
825 I.substituteRegister(Def, SplitReg, 0, *TRI);
826 break;
827 }
828 }
829 }
830 }
831
832 /// Remove the incoming block from the Phis in a basic block.
removePhis(MachineBasicBlock * BB,MachineBasicBlock * Incoming)833 static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming) {
834 for (MachineInstr &MI : *BB) {
835 if (!MI.isPHI())
836 break;
837 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2)
838 if (MI.getOperand(i + 1).getMBB() == Incoming) {
839 MI.RemoveOperand(i + 1);
840 MI.RemoveOperand(i);
841 break;
842 }
843 }
844 }
845
846 /// Create branches from each prolog basic block to the appropriate epilog
847 /// block. These edges are needed if the loop ends before reaching the
848 /// kernel.
addBranches(MachineBasicBlock & PreheaderBB,MBBVectorTy & PrologBBs,MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs,ValueMapTy * VRMap)849 void ModuloScheduleExpander::addBranches(MachineBasicBlock &PreheaderBB,
850 MBBVectorTy &PrologBBs,
851 MachineBasicBlock *KernelBB,
852 MBBVectorTy &EpilogBBs,
853 ValueMapTy *VRMap) {
854 assert(PrologBBs.size() == EpilogBBs.size() && "Prolog/Epilog mismatch");
855 MachineBasicBlock *LastPro = KernelBB;
856 MachineBasicBlock *LastEpi = KernelBB;
857
858 // Start from the blocks connected to the kernel and work "out"
859 // to the first prolog and the last epilog blocks.
860 SmallVector<MachineInstr *, 4> PrevInsts;
861 unsigned MaxIter = PrologBBs.size() - 1;
862 for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) {
863 // Add branches to the prolog that go to the corresponding
864 // epilog, and the fall-thru prolog/kernel block.
865 MachineBasicBlock *Prolog = PrologBBs[j];
866 MachineBasicBlock *Epilog = EpilogBBs[i];
867
868 SmallVector<MachineOperand, 4> Cond;
869 Optional<bool> StaticallyGreater =
870 LoopInfo->createTripCountGreaterCondition(j + 1, *Prolog, Cond);
871 unsigned numAdded = 0;
872 if (!StaticallyGreater.hasValue()) {
873 Prolog->addSuccessor(Epilog);
874 numAdded = TII->insertBranch(*Prolog, Epilog, LastPro, Cond, DebugLoc());
875 } else if (*StaticallyGreater == false) {
876 Prolog->addSuccessor(Epilog);
877 Prolog->removeSuccessor(LastPro);
878 LastEpi->removeSuccessor(Epilog);
879 numAdded = TII->insertBranch(*Prolog, Epilog, nullptr, Cond, DebugLoc());
880 removePhis(Epilog, LastEpi);
881 // Remove the blocks that are no longer referenced.
882 if (LastPro != LastEpi) {
883 LastEpi->clear();
884 LastEpi->eraseFromParent();
885 }
886 if (LastPro == KernelBB) {
887 LoopInfo->disposed();
888 NewKernel = nullptr;
889 }
890 LastPro->clear();
891 LastPro->eraseFromParent();
892 } else {
893 numAdded = TII->insertBranch(*Prolog, LastPro, nullptr, Cond, DebugLoc());
894 removePhis(Epilog, Prolog);
895 }
896 LastPro = Prolog;
897 LastEpi = Epilog;
898 for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(),
899 E = Prolog->instr_rend();
900 I != E && numAdded > 0; ++I, --numAdded)
901 updateInstruction(&*I, false, j, 0, VRMap);
902 }
903
904 if (NewKernel) {
905 LoopInfo->setPreheader(PrologBBs[MaxIter]);
906 LoopInfo->adjustTripCount(-(MaxIter + 1));
907 }
908 }
909
910 /// Return true if we can compute the amount the instruction changes
911 /// during each iteration. Set Delta to the amount of the change.
computeDelta(MachineInstr & MI,unsigned & Delta)912 bool ModuloScheduleExpander::computeDelta(MachineInstr &MI, unsigned &Delta) {
913 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
914 const MachineOperand *BaseOp;
915 int64_t Offset;
916 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI))
917 return false;
918
919 if (!BaseOp->isReg())
920 return false;
921
922 Register BaseReg = BaseOp->getReg();
923
924 MachineRegisterInfo &MRI = MF.getRegInfo();
925 // Check if there is a Phi. If so, get the definition in the loop.
926 MachineInstr *BaseDef = MRI.getVRegDef(BaseReg);
927 if (BaseDef && BaseDef->isPHI()) {
928 BaseReg = getLoopPhiReg(*BaseDef, MI.getParent());
929 BaseDef = MRI.getVRegDef(BaseReg);
930 }
931 if (!BaseDef)
932 return false;
933
934 int D = 0;
935 if (!TII->getIncrementValue(*BaseDef, D) && D >= 0)
936 return false;
937
938 Delta = D;
939 return true;
940 }
941
942 /// Update the memory operand with a new offset when the pipeliner
943 /// generates a new copy of the instruction that refers to a
944 /// different memory location.
updateMemOperands(MachineInstr & NewMI,MachineInstr & OldMI,unsigned Num)945 void ModuloScheduleExpander::updateMemOperands(MachineInstr &NewMI,
946 MachineInstr &OldMI,
947 unsigned Num) {
948 if (Num == 0)
949 return;
950 // If the instruction has memory operands, then adjust the offset
951 // when the instruction appears in different stages.
952 if (NewMI.memoperands_empty())
953 return;
954 SmallVector<MachineMemOperand *, 2> NewMMOs;
955 for (MachineMemOperand *MMO : NewMI.memoperands()) {
956 // TODO: Figure out whether isAtomic is really necessary (see D57601).
957 if (MMO->isVolatile() || MMO->isAtomic() ||
958 (MMO->isInvariant() && MMO->isDereferenceable()) ||
959 (!MMO->getValue())) {
960 NewMMOs.push_back(MMO);
961 continue;
962 }
963 unsigned Delta;
964 if (Num != UINT_MAX && computeDelta(OldMI, Delta)) {
965 int64_t AdjOffset = Delta * Num;
966 NewMMOs.push_back(
967 MF.getMachineMemOperand(MMO, AdjOffset, MMO->getSize()));
968 } else {
969 NewMMOs.push_back(
970 MF.getMachineMemOperand(MMO, 0, MemoryLocation::UnknownSize));
971 }
972 }
973 NewMI.setMemRefs(MF, NewMMOs);
974 }
975
976 /// Clone the instruction for the new pipelined loop and update the
977 /// memory operands, if needed.
cloneInstr(MachineInstr * OldMI,unsigned CurStageNum,unsigned InstStageNum)978 MachineInstr *ModuloScheduleExpander::cloneInstr(MachineInstr *OldMI,
979 unsigned CurStageNum,
980 unsigned InstStageNum) {
981 MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);
982 // Check for tied operands in inline asm instructions. This should be handled
983 // elsewhere, but I'm not sure of the best solution.
984 if (OldMI->isInlineAsm())
985 for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
986 const auto &MO = OldMI->getOperand(i);
987 if (MO.isReg() && MO.isUse())
988 break;
989 unsigned UseIdx;
990 if (OldMI->isRegTiedToUseOperand(i, &UseIdx))
991 NewMI->tieOperands(i, UseIdx);
992 }
993 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
994 return NewMI;
995 }
996
997 /// Clone the instruction for the new pipelined loop. If needed, this
998 /// function updates the instruction using the values saved in the
999 /// InstrChanges structure.
cloneAndChangeInstr(MachineInstr * OldMI,unsigned CurStageNum,unsigned InstStageNum)1000 MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
1001 MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum) {
1002 MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);
1003 auto It = InstrChanges.find(OldMI);
1004 if (It != InstrChanges.end()) {
1005 std::pair<unsigned, int64_t> RegAndOffset = It->second;
1006 unsigned BasePos, OffsetPos;
1007 if (!TII->getBaseAndOffsetPosition(*OldMI, BasePos, OffsetPos))
1008 return nullptr;
1009 int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm();
1010 MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first);
1011 if (Schedule.getStage(LoopDef) > (signed)InstStageNum)
1012 NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
1013 NewMI->getOperand(OffsetPos).setImm(NewOffset);
1014 }
1015 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
1016 return NewMI;
1017 }
1018
1019 /// Update the machine instruction with new virtual registers. This
1020 /// function may change the defintions and/or uses.
updateInstruction(MachineInstr * NewMI,bool LastDef,unsigned CurStageNum,unsigned InstrStageNum,ValueMapTy * VRMap)1021 void ModuloScheduleExpander::updateInstruction(MachineInstr *NewMI,
1022 bool LastDef,
1023 unsigned CurStageNum,
1024 unsigned InstrStageNum,
1025 ValueMapTy *VRMap) {
1026 for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
1027 MachineOperand &MO = NewMI->getOperand(i);
1028 if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg()))
1029 continue;
1030 Register reg = MO.getReg();
1031 if (MO.isDef()) {
1032 // Create a new virtual register for the definition.
1033 const TargetRegisterClass *RC = MRI.getRegClass(reg);
1034 Register NewReg = MRI.createVirtualRegister(RC);
1035 MO.setReg(NewReg);
1036 VRMap[CurStageNum][reg] = NewReg;
1037 if (LastDef)
1038 replaceRegUsesAfterLoop(reg, NewReg, BB, MRI, LIS);
1039 } else if (MO.isUse()) {
1040 MachineInstr *Def = MRI.getVRegDef(reg);
1041 // Compute the stage that contains the last definition for instruction.
1042 int DefStageNum = Schedule.getStage(Def);
1043 unsigned StageNum = CurStageNum;
1044 if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) {
1045 // Compute the difference in stages between the defintion and the use.
1046 unsigned StageDiff = (InstrStageNum - DefStageNum);
1047 // Make an adjustment to get the last definition.
1048 StageNum -= StageDiff;
1049 }
1050 if (VRMap[StageNum].count(reg))
1051 MO.setReg(VRMap[StageNum][reg]);
1052 }
1053 }
1054 }
1055
1056 /// Return the instruction in the loop that defines the register.
1057 /// If the definition is a Phi, then follow the Phi operand to
1058 /// the instruction in the loop.
findDefInLoop(unsigned Reg)1059 MachineInstr *ModuloScheduleExpander::findDefInLoop(unsigned Reg) {
1060 SmallPtrSet<MachineInstr *, 8> Visited;
1061 MachineInstr *Def = MRI.getVRegDef(Reg);
1062 while (Def->isPHI()) {
1063 if (!Visited.insert(Def).second)
1064 break;
1065 for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
1066 if (Def->getOperand(i + 1).getMBB() == BB) {
1067 Def = MRI.getVRegDef(Def->getOperand(i).getReg());
1068 break;
1069 }
1070 }
1071 return Def;
1072 }
1073
1074 /// Return the new name for the value from the previous stage.
getPrevMapVal(unsigned StageNum,unsigned PhiStage,unsigned LoopVal,unsigned LoopStage,ValueMapTy * VRMap,MachineBasicBlock * BB)1075 unsigned ModuloScheduleExpander::getPrevMapVal(
1076 unsigned StageNum, unsigned PhiStage, unsigned LoopVal, unsigned LoopStage,
1077 ValueMapTy *VRMap, MachineBasicBlock *BB) {
1078 unsigned PrevVal = 0;
1079 if (StageNum > PhiStage) {
1080 MachineInstr *LoopInst = MRI.getVRegDef(LoopVal);
1081 if (PhiStage == LoopStage && VRMap[StageNum - 1].count(LoopVal))
1082 // The name is defined in the previous stage.
1083 PrevVal = VRMap[StageNum - 1][LoopVal];
1084 else if (VRMap[StageNum].count(LoopVal))
1085 // The previous name is defined in the current stage when the instruction
1086 // order is swapped.
1087 PrevVal = VRMap[StageNum][LoopVal];
1088 else if (!LoopInst->isPHI() || LoopInst->getParent() != BB)
1089 // The loop value hasn't yet been scheduled.
1090 PrevVal = LoopVal;
1091 else if (StageNum == PhiStage + 1)
1092 // The loop value is another phi, which has not been scheduled.
1093 PrevVal = getInitPhiReg(*LoopInst, BB);
1094 else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB)
1095 // The loop value is another phi, which has been scheduled.
1096 PrevVal =
1097 getPrevMapVal(StageNum - 1, PhiStage, getLoopPhiReg(*LoopInst, BB),
1098 LoopStage, VRMap, BB);
1099 }
1100 return PrevVal;
1101 }
1102
1103 /// Rewrite the Phi values in the specified block to use the mappings
1104 /// from the initial operand. Once the Phi is scheduled, we switch
1105 /// to using the loop value instead of the Phi value, so those names
1106 /// do not need to be rewritten.
rewritePhiValues(MachineBasicBlock * NewBB,unsigned StageNum,ValueMapTy * VRMap,InstrMapTy & InstrMap)1107 void ModuloScheduleExpander::rewritePhiValues(MachineBasicBlock *NewBB,
1108 unsigned StageNum,
1109 ValueMapTy *VRMap,
1110 InstrMapTy &InstrMap) {
1111 for (auto &PHI : BB->phis()) {
1112 unsigned InitVal = 0;
1113 unsigned LoopVal = 0;
1114 getPhiRegs(PHI, BB, InitVal, LoopVal);
1115 Register PhiDef = PHI.getOperand(0).getReg();
1116
1117 unsigned PhiStage = (unsigned)Schedule.getStage(MRI.getVRegDef(PhiDef));
1118 unsigned LoopStage = (unsigned)Schedule.getStage(MRI.getVRegDef(LoopVal));
1119 unsigned NumPhis = getStagesForPhi(PhiDef);
1120 if (NumPhis > StageNum)
1121 NumPhis = StageNum;
1122 for (unsigned np = 0; np <= NumPhis; ++np) {
1123 unsigned NewVal =
1124 getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
1125 if (!NewVal)
1126 NewVal = InitVal;
1127 rewriteScheduledInstr(NewBB, InstrMap, StageNum - np, np, &PHI, PhiDef,
1128 NewVal);
1129 }
1130 }
1131 }
1132
1133 /// Rewrite a previously scheduled instruction to use the register value
1134 /// from the new instruction. Make sure the instruction occurs in the
1135 /// basic block, and we don't change the uses in the new instruction.
rewriteScheduledInstr(MachineBasicBlock * BB,InstrMapTy & InstrMap,unsigned CurStageNum,unsigned PhiNum,MachineInstr * Phi,unsigned OldReg,unsigned NewReg,unsigned PrevReg)1136 void ModuloScheduleExpander::rewriteScheduledInstr(
1137 MachineBasicBlock *BB, InstrMapTy &InstrMap, unsigned CurStageNum,
1138 unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, unsigned NewReg,
1139 unsigned PrevReg) {
1140 bool InProlog = (CurStageNum < (unsigned)Schedule.getNumStages() - 1);
1141 int StagePhi = Schedule.getStage(Phi) + PhiNum;
1142 // Rewrite uses that have been scheduled already to use the new
1143 // Phi register.
1144 for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(OldReg),
1145 EI = MRI.use_end();
1146 UI != EI;) {
1147 MachineOperand &UseOp = *UI;
1148 MachineInstr *UseMI = UseOp.getParent();
1149 ++UI;
1150 if (UseMI->getParent() != BB)
1151 continue;
1152 if (UseMI->isPHI()) {
1153 if (!Phi->isPHI() && UseMI->getOperand(0).getReg() == NewReg)
1154 continue;
1155 if (getLoopPhiReg(*UseMI, BB) != OldReg)
1156 continue;
1157 }
1158 InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI);
1159 assert(OrigInstr != InstrMap.end() && "Instruction not scheduled.");
1160 MachineInstr *OrigMI = OrigInstr->second;
1161 int StageSched = Schedule.getStage(OrigMI);
1162 int CycleSched = Schedule.getCycle(OrigMI);
1163 unsigned ReplaceReg = 0;
1164 // This is the stage for the scheduled instruction.
1165 if (StagePhi == StageSched && Phi->isPHI()) {
1166 int CyclePhi = Schedule.getCycle(Phi);
1167 if (PrevReg && InProlog)
1168 ReplaceReg = PrevReg;
1169 else if (PrevReg && !isLoopCarried(*Phi) &&
1170 (CyclePhi <= CycleSched || OrigMI->isPHI()))
1171 ReplaceReg = PrevReg;
1172 else
1173 ReplaceReg = NewReg;
1174 }
1175 // The scheduled instruction occurs before the scheduled Phi, and the
1176 // Phi is not loop carried.
1177 if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(*Phi))
1178 ReplaceReg = NewReg;
1179 if (StagePhi > StageSched && Phi->isPHI())
1180 ReplaceReg = NewReg;
1181 if (!InProlog && !Phi->isPHI() && StagePhi < StageSched)
1182 ReplaceReg = NewReg;
1183 if (ReplaceReg) {
1184 MRI.constrainRegClass(ReplaceReg, MRI.getRegClass(OldReg));
1185 UseOp.setReg(ReplaceReg);
1186 }
1187 }
1188 }
1189
isLoopCarried(MachineInstr & Phi)1190 bool ModuloScheduleExpander::isLoopCarried(MachineInstr &Phi) {
1191 if (!Phi.isPHI())
1192 return false;
1193 int DefCycle = Schedule.getCycle(&Phi);
1194 int DefStage = Schedule.getStage(&Phi);
1195
1196 unsigned InitVal = 0;
1197 unsigned LoopVal = 0;
1198 getPhiRegs(Phi, Phi.getParent(), InitVal, LoopVal);
1199 MachineInstr *Use = MRI.getVRegDef(LoopVal);
1200 if (!Use || Use->isPHI())
1201 return true;
1202 int LoopCycle = Schedule.getCycle(Use);
1203 int LoopStage = Schedule.getStage(Use);
1204 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
1205 }
1206
1207 //===----------------------------------------------------------------------===//
1208 // PeelingModuloScheduleExpander implementation
1209 //===----------------------------------------------------------------------===//
1210 // This is a reimplementation of ModuloScheduleExpander that works by creating
1211 // a fully correct steady-state kernel and peeling off the prolog and epilogs.
1212 //===----------------------------------------------------------------------===//
1213
1214 namespace {
1215 // Remove any dead phis in MBB. Dead phis either have only one block as input
1216 // (in which case they are the identity) or have no uses.
EliminateDeadPhis(MachineBasicBlock * MBB,MachineRegisterInfo & MRI,LiveIntervals * LIS,bool KeepSingleSrcPhi=false)1217 void EliminateDeadPhis(MachineBasicBlock *MBB, MachineRegisterInfo &MRI,
1218 LiveIntervals *LIS, bool KeepSingleSrcPhi = false) {
1219 bool Changed = true;
1220 while (Changed) {
1221 Changed = false;
1222 for (auto I = MBB->begin(); I != MBB->getFirstNonPHI();) {
1223 MachineInstr &MI = *I++;
1224 assert(MI.isPHI());
1225 if (MRI.use_empty(MI.getOperand(0).getReg())) {
1226 if (LIS)
1227 LIS->RemoveMachineInstrFromMaps(MI);
1228 MI.eraseFromParent();
1229 Changed = true;
1230 } else if (!KeepSingleSrcPhi && MI.getNumExplicitOperands() == 3) {
1231 MRI.constrainRegClass(MI.getOperand(1).getReg(),
1232 MRI.getRegClass(MI.getOperand(0).getReg()));
1233 MRI.replaceRegWith(MI.getOperand(0).getReg(),
1234 MI.getOperand(1).getReg());
1235 if (LIS)
1236 LIS->RemoveMachineInstrFromMaps(MI);
1237 MI.eraseFromParent();
1238 Changed = true;
1239 }
1240 }
1241 }
1242 }
1243
1244 /// Rewrites the kernel block in-place to adhere to the given schedule.
1245 /// KernelRewriter holds all of the state required to perform the rewriting.
1246 class KernelRewriter {
1247 ModuloSchedule &S;
1248 MachineBasicBlock *BB;
1249 MachineBasicBlock *PreheaderBB, *ExitBB;
1250 MachineRegisterInfo &MRI;
1251 const TargetInstrInfo *TII;
1252 LiveIntervals *LIS;
1253
1254 // Map from register class to canonical undef register for that class.
1255 DenseMap<const TargetRegisterClass *, Register> Undefs;
1256 // Map from <LoopReg, InitReg> to phi register for all created phis. Note that
1257 // this map is only used when InitReg is non-undef.
1258 DenseMap<std::pair<unsigned, unsigned>, Register> Phis;
1259 // Map from LoopReg to phi register where the InitReg is undef.
1260 DenseMap<Register, Register> UndefPhis;
1261
1262 // Reg is used by MI. Return the new register MI should use to adhere to the
1263 // schedule. Insert phis as necessary.
1264 Register remapUse(Register Reg, MachineInstr &MI);
1265 // Insert a phi that carries LoopReg from the loop body and InitReg otherwise.
1266 // If InitReg is not given it is chosen arbitrarily. It will either be undef
1267 // or will be chosen so as to share another phi.
1268 Register phi(Register LoopReg, Optional<Register> InitReg = {},
1269 const TargetRegisterClass *RC = nullptr);
1270 // Create an undef register of the given register class.
1271 Register undef(const TargetRegisterClass *RC);
1272
1273 public:
1274 KernelRewriter(MachineLoop &L, ModuloSchedule &S,
1275 LiveIntervals *LIS = nullptr);
1276 void rewrite();
1277 };
1278 } // namespace
1279
KernelRewriter(MachineLoop & L,ModuloSchedule & S,LiveIntervals * LIS)1280 KernelRewriter::KernelRewriter(MachineLoop &L, ModuloSchedule &S,
1281 LiveIntervals *LIS)
1282 : S(S), BB(L.getTopBlock()), PreheaderBB(L.getLoopPreheader()),
1283 ExitBB(L.getExitBlock()), MRI(BB->getParent()->getRegInfo()),
1284 TII(BB->getParent()->getSubtarget().getInstrInfo()), LIS(LIS) {
1285 PreheaderBB = *BB->pred_begin();
1286 if (PreheaderBB == BB)
1287 PreheaderBB = *std::next(BB->pred_begin());
1288 }
1289
rewrite()1290 void KernelRewriter::rewrite() {
1291 // Rearrange the loop to be in schedule order. Note that the schedule may
1292 // contain instructions that are not owned by the loop block (InstrChanges and
1293 // friends), so we gracefully handle unowned instructions and delete any
1294 // instructions that weren't in the schedule.
1295 auto InsertPt = BB->getFirstTerminator();
1296 MachineInstr *FirstMI = nullptr;
1297 for (MachineInstr *MI : S.getInstructions()) {
1298 if (MI->isPHI())
1299 continue;
1300 if (MI->getParent())
1301 MI->removeFromParent();
1302 BB->insert(InsertPt, MI);
1303 if (!FirstMI)
1304 FirstMI = MI;
1305 }
1306 assert(FirstMI && "Failed to find first MI in schedule");
1307
1308 // At this point all of the scheduled instructions are between FirstMI
1309 // and the end of the block. Kill from the first non-phi to FirstMI.
1310 for (auto I = BB->getFirstNonPHI(); I != FirstMI->getIterator();) {
1311 if (LIS)
1312 LIS->RemoveMachineInstrFromMaps(*I);
1313 (I++)->eraseFromParent();
1314 }
1315
1316 // Now remap every instruction in the loop.
1317 for (MachineInstr &MI : *BB) {
1318 if (MI.isPHI() || MI.isTerminator())
1319 continue;
1320 for (MachineOperand &MO : MI.uses()) {
1321 if (!MO.isReg() || MO.getReg().isPhysical() || MO.isImplicit())
1322 continue;
1323 Register Reg = remapUse(MO.getReg(), MI);
1324 MO.setReg(Reg);
1325 }
1326 }
1327 EliminateDeadPhis(BB, MRI, LIS);
1328
1329 // Ensure a phi exists for all instructions that are either referenced by
1330 // an illegal phi or by an instruction outside the loop. This allows us to
1331 // treat remaps of these values the same as "normal" values that come from
1332 // loop-carried phis.
1333 for (auto MI = BB->getFirstNonPHI(); MI != BB->end(); ++MI) {
1334 if (MI->isPHI()) {
1335 Register R = MI->getOperand(0).getReg();
1336 phi(R);
1337 continue;
1338 }
1339
1340 for (MachineOperand &Def : MI->defs()) {
1341 for (MachineInstr &MI : MRI.use_instructions(Def.getReg())) {
1342 if (MI.getParent() != BB) {
1343 phi(Def.getReg());
1344 break;
1345 }
1346 }
1347 }
1348 }
1349 }
1350
remapUse(Register Reg,MachineInstr & MI)1351 Register KernelRewriter::remapUse(Register Reg, MachineInstr &MI) {
1352 MachineInstr *Producer = MRI.getUniqueVRegDef(Reg);
1353 if (!Producer)
1354 return Reg;
1355
1356 int ConsumerStage = S.getStage(&MI);
1357 if (!Producer->isPHI()) {
1358 // Non-phi producers are simple to remap. Insert as many phis as the
1359 // difference between the consumer and producer stages.
1360 if (Producer->getParent() != BB)
1361 // Producer was not inside the loop. Use the register as-is.
1362 return Reg;
1363 int ProducerStage = S.getStage(Producer);
1364 assert(ConsumerStage != -1 &&
1365 "In-loop consumer should always be scheduled!");
1366 assert(ConsumerStage >= ProducerStage);
1367 unsigned StageDiff = ConsumerStage - ProducerStage;
1368
1369 for (unsigned I = 0; I < StageDiff; ++I)
1370 Reg = phi(Reg);
1371 return Reg;
1372 }
1373
1374 // First, dive through the phi chain to find the defaults for the generated
1375 // phis.
1376 SmallVector<Optional<Register>, 4> Defaults;
1377 Register LoopReg = Reg;
1378 auto LoopProducer = Producer;
1379 while (LoopProducer->isPHI() && LoopProducer->getParent() == BB) {
1380 LoopReg = getLoopPhiReg(*LoopProducer, BB);
1381 Defaults.emplace_back(getInitPhiReg(*LoopProducer, BB));
1382 LoopProducer = MRI.getUniqueVRegDef(LoopReg);
1383 assert(LoopProducer);
1384 }
1385 int LoopProducerStage = S.getStage(LoopProducer);
1386
1387 Optional<Register> IllegalPhiDefault;
1388
1389 if (LoopProducerStage == -1) {
1390 // Do nothing.
1391 } else if (LoopProducerStage > ConsumerStage) {
1392 // This schedule is only representable if ProducerStage == ConsumerStage+1.
1393 // In addition, Consumer's cycle must be scheduled after Producer in the
1394 // rescheduled loop. This is enforced by the pipeliner's ASAP and ALAP
1395 // functions.
1396 #ifndef NDEBUG // Silence unused variables in non-asserts mode.
1397 int LoopProducerCycle = S.getCycle(LoopProducer);
1398 int ConsumerCycle = S.getCycle(&MI);
1399 #endif
1400 assert(LoopProducerCycle <= ConsumerCycle);
1401 assert(LoopProducerStage == ConsumerStage + 1);
1402 // Peel off the first phi from Defaults and insert a phi between producer
1403 // and consumer. This phi will not be at the front of the block so we
1404 // consider it illegal. It will only exist during the rewrite process; it
1405 // needs to exist while we peel off prologs because these could take the
1406 // default value. After that we can replace all uses with the loop producer
1407 // value.
1408 IllegalPhiDefault = Defaults.front();
1409 Defaults.erase(Defaults.begin());
1410 } else {
1411 assert(ConsumerStage >= LoopProducerStage);
1412 int StageDiff = ConsumerStage - LoopProducerStage;
1413 if (StageDiff > 0) {
1414 LLVM_DEBUG(dbgs() << " -- padding defaults array from " << Defaults.size()
1415 << " to " << (Defaults.size() + StageDiff) << "\n");
1416 // If we need more phis than we have defaults for, pad out with undefs for
1417 // the earliest phis, which are at the end of the defaults chain (the
1418 // chain is in reverse order).
1419 Defaults.resize(Defaults.size() + StageDiff, Defaults.empty()
1420 ? Optional<Register>()
1421 : Defaults.back());
1422 }
1423 }
1424
1425 // Now we know the number of stages to jump back, insert the phi chain.
1426 auto DefaultI = Defaults.rbegin();
1427 while (DefaultI != Defaults.rend())
1428 LoopReg = phi(LoopReg, *DefaultI++, MRI.getRegClass(Reg));
1429
1430 if (IllegalPhiDefault.hasValue()) {
1431 // The consumer optionally consumes LoopProducer in the same iteration
1432 // (because the producer is scheduled at an earlier cycle than the consumer)
1433 // or the initial value. To facilitate this we create an illegal block here
1434 // by embedding a phi in the middle of the block. We will fix this up
1435 // immediately prior to pruning.
1436 auto RC = MRI.getRegClass(Reg);
1437 Register R = MRI.createVirtualRegister(RC);
1438 BuildMI(*BB, MI, DebugLoc(), TII->get(TargetOpcode::PHI), R)
1439 .addReg(IllegalPhiDefault.getValue())
1440 .addMBB(PreheaderBB) // Block choice is arbitrary and has no effect.
1441 .addReg(LoopReg)
1442 .addMBB(BB); // Block choice is arbitrary and has no effect.
1443 return R;
1444 }
1445
1446 return LoopReg;
1447 }
1448
phi(Register LoopReg,Optional<Register> InitReg,const TargetRegisterClass * RC)1449 Register KernelRewriter::phi(Register LoopReg, Optional<Register> InitReg,
1450 const TargetRegisterClass *RC) {
1451 // If the init register is not undef, try and find an existing phi.
1452 if (InitReg.hasValue()) {
1453 auto I = Phis.find({LoopReg, InitReg.getValue()});
1454 if (I != Phis.end())
1455 return I->second;
1456 } else {
1457 for (auto &KV : Phis) {
1458 if (KV.first.first == LoopReg)
1459 return KV.second;
1460 }
1461 }
1462
1463 // InitReg is either undef or no existing phi takes InitReg as input. Try and
1464 // find a phi that takes undef as input.
1465 auto I = UndefPhis.find(LoopReg);
1466 if (I != UndefPhis.end()) {
1467 Register R = I->second;
1468 if (!InitReg.hasValue())
1469 // Found a phi taking undef as input, and this input is undef so return
1470 // without any more changes.
1471 return R;
1472 // Found a phi taking undef as input, so rewrite it to take InitReg.
1473 MachineInstr *MI = MRI.getVRegDef(R);
1474 MI->getOperand(1).setReg(InitReg.getValue());
1475 Phis.insert({{LoopReg, InitReg.getValue()}, R});
1476 MRI.constrainRegClass(R, MRI.getRegClass(InitReg.getValue()));
1477 UndefPhis.erase(I);
1478 return R;
1479 }
1480
1481 // Failed to find any existing phi to reuse, so create a new one.
1482 if (!RC)
1483 RC = MRI.getRegClass(LoopReg);
1484 Register R = MRI.createVirtualRegister(RC);
1485 if (InitReg.hasValue())
1486 MRI.constrainRegClass(R, MRI.getRegClass(*InitReg));
1487 BuildMI(*BB, BB->getFirstNonPHI(), DebugLoc(), TII->get(TargetOpcode::PHI), R)
1488 .addReg(InitReg.hasValue() ? *InitReg : undef(RC))
1489 .addMBB(PreheaderBB)
1490 .addReg(LoopReg)
1491 .addMBB(BB);
1492 if (!InitReg.hasValue())
1493 UndefPhis[LoopReg] = R;
1494 else
1495 Phis[{LoopReg, *InitReg}] = R;
1496 return R;
1497 }
1498
undef(const TargetRegisterClass * RC)1499 Register KernelRewriter::undef(const TargetRegisterClass *RC) {
1500 Register &R = Undefs[RC];
1501 if (R == 0) {
1502 // Create an IMPLICIT_DEF that defines this register if we need it.
1503 // All uses of this should be removed by the time we have finished unrolling
1504 // prologs and epilogs.
1505 R = MRI.createVirtualRegister(RC);
1506 auto *InsertBB = &PreheaderBB->getParent()->front();
1507 BuildMI(*InsertBB, InsertBB->getFirstTerminator(), DebugLoc(),
1508 TII->get(TargetOpcode::IMPLICIT_DEF), R);
1509 }
1510 return R;
1511 }
1512
1513 namespace {
1514 /// Describes an operand in the kernel of a pipelined loop. Characteristics of
1515 /// the operand are discovered, such as how many in-loop PHIs it has to jump
1516 /// through and defaults for these phis.
1517 class KernelOperandInfo {
1518 MachineBasicBlock *BB;
1519 MachineRegisterInfo &MRI;
1520 SmallVector<Register, 4> PhiDefaults;
1521 MachineOperand *Source;
1522 MachineOperand *Target;
1523
1524 public:
KernelOperandInfo(MachineOperand * MO,MachineRegisterInfo & MRI,const SmallPtrSetImpl<MachineInstr * > & IllegalPhis)1525 KernelOperandInfo(MachineOperand *MO, MachineRegisterInfo &MRI,
1526 const SmallPtrSetImpl<MachineInstr *> &IllegalPhis)
1527 : MRI(MRI) {
1528 Source = MO;
1529 BB = MO->getParent()->getParent();
1530 while (isRegInLoop(MO)) {
1531 MachineInstr *MI = MRI.getVRegDef(MO->getReg());
1532 if (MI->isFullCopy()) {
1533 MO = &MI->getOperand(1);
1534 continue;
1535 }
1536 if (!MI->isPHI())
1537 break;
1538 // If this is an illegal phi, don't count it in distance.
1539 if (IllegalPhis.count(MI)) {
1540 MO = &MI->getOperand(3);
1541 continue;
1542 }
1543
1544 Register Default = getInitPhiReg(*MI, BB);
1545 MO = MI->getOperand(2).getMBB() == BB ? &MI->getOperand(1)
1546 : &MI->getOperand(3);
1547 PhiDefaults.push_back(Default);
1548 }
1549 Target = MO;
1550 }
1551
operator ==(const KernelOperandInfo & Other) const1552 bool operator==(const KernelOperandInfo &Other) const {
1553 return PhiDefaults.size() == Other.PhiDefaults.size();
1554 }
1555
print(raw_ostream & OS) const1556 void print(raw_ostream &OS) const {
1557 OS << "use of " << *Source << ": distance(" << PhiDefaults.size() << ") in "
1558 << *Source->getParent();
1559 }
1560
1561 private:
isRegInLoop(MachineOperand * MO)1562 bool isRegInLoop(MachineOperand *MO) {
1563 return MO->isReg() && MO->getReg().isVirtual() &&
1564 MRI.getVRegDef(MO->getReg())->getParent() == BB;
1565 }
1566 };
1567 } // namespace
1568
1569 MachineBasicBlock *
peelKernel(LoopPeelDirection LPD)1570 PeelingModuloScheduleExpander::peelKernel(LoopPeelDirection LPD) {
1571 MachineBasicBlock *NewBB = PeelSingleBlockLoop(LPD, BB, MRI, TII);
1572 if (LPD == LPD_Front)
1573 PeeledFront.push_back(NewBB);
1574 else
1575 PeeledBack.push_front(NewBB);
1576 for (auto I = BB->begin(), NI = NewBB->begin(); !I->isTerminator();
1577 ++I, ++NI) {
1578 CanonicalMIs[&*I] = &*I;
1579 CanonicalMIs[&*NI] = &*I;
1580 BlockMIs[{NewBB, &*I}] = &*NI;
1581 BlockMIs[{BB, &*I}] = &*I;
1582 }
1583 return NewBB;
1584 }
1585
filterInstructions(MachineBasicBlock * MB,int MinStage)1586 void PeelingModuloScheduleExpander::filterInstructions(MachineBasicBlock *MB,
1587 int MinStage) {
1588 for (auto I = MB->getFirstInstrTerminator()->getReverseIterator();
1589 I != std::next(MB->getFirstNonPHI()->getReverseIterator());) {
1590 MachineInstr *MI = &*I++;
1591 int Stage = getStage(MI);
1592 if (Stage == -1 || Stage >= MinStage)
1593 continue;
1594
1595 for (MachineOperand &DefMO : MI->defs()) {
1596 SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
1597 for (MachineInstr &UseMI : MRI.use_instructions(DefMO.getReg())) {
1598 // Only PHIs can use values from this block by construction.
1599 // Match with the equivalent PHI in B.
1600 assert(UseMI.isPHI());
1601 Register Reg = getEquivalentRegisterIn(UseMI.getOperand(0).getReg(),
1602 MI->getParent());
1603 Subs.emplace_back(&UseMI, Reg);
1604 }
1605 for (auto &Sub : Subs)
1606 Sub.first->substituteRegister(DefMO.getReg(), Sub.second, /*SubIdx=*/0,
1607 *MRI.getTargetRegisterInfo());
1608 }
1609 if (LIS)
1610 LIS->RemoveMachineInstrFromMaps(*MI);
1611 MI->eraseFromParent();
1612 }
1613 }
1614
moveStageBetweenBlocks(MachineBasicBlock * DestBB,MachineBasicBlock * SourceBB,unsigned Stage)1615 void PeelingModuloScheduleExpander::moveStageBetweenBlocks(
1616 MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage) {
1617 auto InsertPt = DestBB->getFirstNonPHI();
1618 DenseMap<Register, Register> Remaps;
1619 for (auto I = SourceBB->getFirstNonPHI(); I != SourceBB->end();) {
1620 MachineInstr *MI = &*I++;
1621 if (MI->isPHI()) {
1622 // This is an illegal PHI. If we move any instructions using an illegal
1623 // PHI, we need to create a legal Phi
1624 Register PhiR = MI->getOperand(0).getReg();
1625 auto RC = MRI.getRegClass(PhiR);
1626 Register NR = MRI.createVirtualRegister(RC);
1627 MachineInstr *NI = BuildMI(*DestBB, DestBB->getFirstNonPHI(), DebugLoc(),
1628 TII->get(TargetOpcode::PHI), NR)
1629 .addReg(PhiR)
1630 .addMBB(SourceBB);
1631 BlockMIs[{DestBB, CanonicalMIs[MI]}] = NI;
1632 CanonicalMIs[NI] = CanonicalMIs[MI];
1633 Remaps[PhiR] = NR;
1634 continue;
1635 }
1636 if (getStage(MI) != Stage)
1637 continue;
1638 MI->removeFromParent();
1639 DestBB->insert(InsertPt, MI);
1640 auto *KernelMI = CanonicalMIs[MI];
1641 BlockMIs[{DestBB, KernelMI}] = MI;
1642 BlockMIs.erase({SourceBB, KernelMI});
1643 }
1644 SmallVector<MachineInstr *, 4> PhiToDelete;
1645 for (MachineInstr &MI : DestBB->phis()) {
1646 assert(MI.getNumOperands() == 3);
1647 MachineInstr *Def = MRI.getVRegDef(MI.getOperand(1).getReg());
1648 // If the instruction referenced by the phi is moved inside the block
1649 // we don't need the phi anymore.
1650 if (getStage(Def) == Stage) {
1651 Register PhiReg = MI.getOperand(0).getReg();
1652 MRI.replaceRegWith(MI.getOperand(0).getReg(),
1653 Def->getOperand(0).getReg());
1654 MI.getOperand(0).setReg(PhiReg);
1655 PhiToDelete.push_back(&MI);
1656 }
1657 }
1658 for (auto *P : PhiToDelete)
1659 P->eraseFromParent();
1660 InsertPt = DestBB->getFirstNonPHI();
1661 // Helper to clone Phi instructions into the destination block. We clone Phi
1662 // greedily to avoid combinatorial explosion of Phi instructions.
1663 auto clonePhi = [&](MachineInstr *Phi) {
1664 MachineInstr *NewMI = MF.CloneMachineInstr(Phi);
1665 DestBB->insert(InsertPt, NewMI);
1666 Register OrigR = Phi->getOperand(0).getReg();
1667 Register R = MRI.createVirtualRegister(MRI.getRegClass(OrigR));
1668 NewMI->getOperand(0).setReg(R);
1669 NewMI->getOperand(1).setReg(OrigR);
1670 NewMI->getOperand(2).setMBB(*DestBB->pred_begin());
1671 Remaps[OrigR] = R;
1672 CanonicalMIs[NewMI] = CanonicalMIs[Phi];
1673 BlockMIs[{DestBB, CanonicalMIs[Phi]}] = NewMI;
1674 PhiNodeLoopIteration[NewMI] = PhiNodeLoopIteration[Phi];
1675 return R;
1676 };
1677 for (auto I = DestBB->getFirstNonPHI(); I != DestBB->end(); ++I) {
1678 for (MachineOperand &MO : I->uses()) {
1679 if (!MO.isReg())
1680 continue;
1681 if (Remaps.count(MO.getReg()))
1682 MO.setReg(Remaps[MO.getReg()]);
1683 else {
1684 // If we are using a phi from the source block we need to add a new phi
1685 // pointing to the old one.
1686 MachineInstr *Use = MRI.getUniqueVRegDef(MO.getReg());
1687 if (Use && Use->isPHI() && Use->getParent() == SourceBB) {
1688 Register R = clonePhi(Use);
1689 MO.setReg(R);
1690 }
1691 }
1692 }
1693 }
1694 }
1695
1696 Register
getPhiCanonicalReg(MachineInstr * CanonicalPhi,MachineInstr * Phi)1697 PeelingModuloScheduleExpander::getPhiCanonicalReg(MachineInstr *CanonicalPhi,
1698 MachineInstr *Phi) {
1699 unsigned distance = PhiNodeLoopIteration[Phi];
1700 MachineInstr *CanonicalUse = CanonicalPhi;
1701 for (unsigned I = 0; I < distance; ++I) {
1702 assert(CanonicalUse->isPHI());
1703 assert(CanonicalUse->getNumOperands() == 5);
1704 unsigned LoopRegIdx = 3, InitRegIdx = 1;
1705 if (CanonicalUse->getOperand(2).getMBB() == CanonicalUse->getParent())
1706 std::swap(LoopRegIdx, InitRegIdx);
1707 CanonicalUse =
1708 MRI.getVRegDef(CanonicalUse->getOperand(LoopRegIdx).getReg());
1709 }
1710 return CanonicalUse->getOperand(0).getReg();
1711 }
1712
peelPrologAndEpilogs()1713 void PeelingModuloScheduleExpander::peelPrologAndEpilogs() {
1714 BitVector LS(Schedule.getNumStages(), true);
1715 BitVector AS(Schedule.getNumStages(), true);
1716 LiveStages[BB] = LS;
1717 AvailableStages[BB] = AS;
1718
1719 // Peel out the prologs.
1720 LS.reset();
1721 for (int I = 0; I < Schedule.getNumStages() - 1; ++I) {
1722 LS[I] = 1;
1723 Prologs.push_back(peelKernel(LPD_Front));
1724 LiveStages[Prologs.back()] = LS;
1725 AvailableStages[Prologs.back()] = LS;
1726 }
1727
1728 // Create a block that will end up as the new loop exiting block (dominated by
1729 // all prologs and epilogs). It will only contain PHIs, in the same order as
1730 // BB's PHIs. This gives us a poor-man's LCSSA with the inductive property
1731 // that the exiting block is a (sub) clone of BB. This in turn gives us the
1732 // property that any value deffed in BB but used outside of BB is used by a
1733 // PHI in the exiting block.
1734 MachineBasicBlock *ExitingBB = CreateLCSSAExitingBlock();
1735 EliminateDeadPhis(ExitingBB, MRI, LIS, /*KeepSingleSrcPhi=*/true);
1736 // Push out the epilogs, again in reverse order.
1737 // We can't assume anything about the minumum loop trip count at this point,
1738 // so emit a fairly complex epilog.
1739
1740 // We first peel number of stages minus one epilogue. Then we remove dead
1741 // stages and reorder instructions based on their stage. If we have 3 stages
1742 // we generate first:
1743 // E0[3, 2, 1]
1744 // E1[3', 2']
1745 // E2[3'']
1746 // And then we move instructions based on their stages to have:
1747 // E0[3]
1748 // E1[2, 3']
1749 // E2[1, 2', 3'']
1750 // The transformation is legal because we only move instructions past
1751 // instructions of a previous loop iteration.
1752 for (int I = 1; I <= Schedule.getNumStages() - 1; ++I) {
1753 Epilogs.push_back(peelKernel(LPD_Back));
1754 MachineBasicBlock *B = Epilogs.back();
1755 filterInstructions(B, Schedule.getNumStages() - I);
1756 // Keep track at which iteration each phi belongs to. We need it to know
1757 // what version of the variable to use during prologue/epilogue stitching.
1758 EliminateDeadPhis(B, MRI, LIS, /*KeepSingleSrcPhi=*/true);
1759 for (auto Phi = B->begin(), IE = B->getFirstNonPHI(); Phi != IE; ++Phi)
1760 PhiNodeLoopIteration[&*Phi] = Schedule.getNumStages() - I;
1761 }
1762 for (size_t I = 0; I < Epilogs.size(); I++) {
1763 LS.reset();
1764 for (size_t J = I; J < Epilogs.size(); J++) {
1765 int Iteration = J;
1766 unsigned Stage = Schedule.getNumStages() - 1 + I - J;
1767 // Move stage one block at a time so that Phi nodes are updated correctly.
1768 for (size_t K = Iteration; K > I; K--)
1769 moveStageBetweenBlocks(Epilogs[K - 1], Epilogs[K], Stage);
1770 LS[Stage] = 1;
1771 }
1772 LiveStages[Epilogs[I]] = LS;
1773 AvailableStages[Epilogs[I]] = AS;
1774 }
1775
1776 // Now we've defined all the prolog and epilog blocks as a fallthrough
1777 // sequence, add the edges that will be followed if the loop trip count is
1778 // lower than the number of stages (connecting prologs directly with epilogs).
1779 auto PI = Prologs.begin();
1780 auto EI = Epilogs.begin();
1781 assert(Prologs.size() == Epilogs.size());
1782 for (; PI != Prologs.end(); ++PI, ++EI) {
1783 MachineBasicBlock *Pred = *(*EI)->pred_begin();
1784 (*PI)->addSuccessor(*EI);
1785 for (MachineInstr &MI : (*EI)->phis()) {
1786 Register Reg = MI.getOperand(1).getReg();
1787 MachineInstr *Use = MRI.getUniqueVRegDef(Reg);
1788 if (Use && Use->getParent() == Pred) {
1789 MachineInstr *CanonicalUse = CanonicalMIs[Use];
1790 if (CanonicalUse->isPHI()) {
1791 // If the use comes from a phi we need to skip as many phi as the
1792 // distance between the epilogue and the kernel. Trace through the phi
1793 // chain to find the right value.
1794 Reg = getPhiCanonicalReg(CanonicalUse, Use);
1795 }
1796 Reg = getEquivalentRegisterIn(Reg, *PI);
1797 }
1798 MI.addOperand(MachineOperand::CreateReg(Reg, /*isDef=*/false));
1799 MI.addOperand(MachineOperand::CreateMBB(*PI));
1800 }
1801 }
1802
1803 // Create a list of all blocks in order.
1804 SmallVector<MachineBasicBlock *, 8> Blocks;
1805 llvm::copy(PeeledFront, std::back_inserter(Blocks));
1806 Blocks.push_back(BB);
1807 llvm::copy(PeeledBack, std::back_inserter(Blocks));
1808
1809 // Iterate in reverse order over all instructions, remapping as we go.
1810 for (MachineBasicBlock *B : reverse(Blocks)) {
1811 for (auto I = B->getFirstInstrTerminator()->getReverseIterator();
1812 I != std::next(B->getFirstNonPHI()->getReverseIterator());) {
1813 MachineInstr *MI = &*I++;
1814 rewriteUsesOf(MI);
1815 }
1816 }
1817 for (auto *MI : IllegalPhisToDelete) {
1818 if (LIS)
1819 LIS->RemoveMachineInstrFromMaps(*MI);
1820 MI->eraseFromParent();
1821 }
1822 IllegalPhisToDelete.clear();
1823
1824 // Now all remapping has been done, we're free to optimize the generated code.
1825 for (MachineBasicBlock *B : reverse(Blocks))
1826 EliminateDeadPhis(B, MRI, LIS);
1827 EliminateDeadPhis(ExitingBB, MRI, LIS);
1828 }
1829
CreateLCSSAExitingBlock()1830 MachineBasicBlock *PeelingModuloScheduleExpander::CreateLCSSAExitingBlock() {
1831 MachineFunction &MF = *BB->getParent();
1832 MachineBasicBlock *Exit = *BB->succ_begin();
1833 if (Exit == BB)
1834 Exit = *std::next(BB->succ_begin());
1835
1836 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
1837 MF.insert(std::next(BB->getIterator()), NewBB);
1838
1839 // Clone all phis in BB into NewBB and rewrite.
1840 for (MachineInstr &MI : BB->phis()) {
1841 auto RC = MRI.getRegClass(MI.getOperand(0).getReg());
1842 Register OldR = MI.getOperand(3).getReg();
1843 Register R = MRI.createVirtualRegister(RC);
1844 SmallVector<MachineInstr *, 4> Uses;
1845 for (MachineInstr &Use : MRI.use_instructions(OldR))
1846 if (Use.getParent() != BB)
1847 Uses.push_back(&Use);
1848 for (MachineInstr *Use : Uses)
1849 Use->substituteRegister(OldR, R, /*SubIdx=*/0,
1850 *MRI.getTargetRegisterInfo());
1851 MachineInstr *NI = BuildMI(NewBB, DebugLoc(), TII->get(TargetOpcode::PHI), R)
1852 .addReg(OldR)
1853 .addMBB(BB);
1854 BlockMIs[{NewBB, &MI}] = NI;
1855 CanonicalMIs[NI] = &MI;
1856 }
1857 BB->replaceSuccessor(Exit, NewBB);
1858 Exit->replacePhiUsesWith(BB, NewBB);
1859 NewBB->addSuccessor(Exit);
1860
1861 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1862 SmallVector<MachineOperand, 4> Cond;
1863 bool CanAnalyzeBr = !TII->analyzeBranch(*BB, TBB, FBB, Cond);
1864 (void)CanAnalyzeBr;
1865 assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
1866 TII->removeBranch(*BB);
1867 TII->insertBranch(*BB, TBB == Exit ? NewBB : TBB, FBB == Exit ? NewBB : FBB,
1868 Cond, DebugLoc());
1869 TII->insertUnconditionalBranch(*NewBB, Exit, DebugLoc());
1870 return NewBB;
1871 }
1872
1873 Register
getEquivalentRegisterIn(Register Reg,MachineBasicBlock * BB)1874 PeelingModuloScheduleExpander::getEquivalentRegisterIn(Register Reg,
1875 MachineBasicBlock *BB) {
1876 MachineInstr *MI = MRI.getUniqueVRegDef(Reg);
1877 unsigned OpIdx = MI->findRegisterDefOperandIdx(Reg);
1878 return BlockMIs[{BB, CanonicalMIs[MI]}]->getOperand(OpIdx).getReg();
1879 }
1880
rewriteUsesOf(MachineInstr * MI)1881 void PeelingModuloScheduleExpander::rewriteUsesOf(MachineInstr *MI) {
1882 if (MI->isPHI()) {
1883 // This is an illegal PHI. The loop-carried (desired) value is operand 3,
1884 // and it is produced by this block.
1885 Register PhiR = MI->getOperand(0).getReg();
1886 Register R = MI->getOperand(3).getReg();
1887 int RMIStage = getStage(MRI.getUniqueVRegDef(R));
1888 if (RMIStage != -1 && !AvailableStages[MI->getParent()].test(RMIStage))
1889 R = MI->getOperand(1).getReg();
1890 MRI.setRegClass(R, MRI.getRegClass(PhiR));
1891 MRI.replaceRegWith(PhiR, R);
1892 // Postpone deleting the Phi as it may be referenced by BlockMIs and used
1893 // later to figure out how to remap registers.
1894 MI->getOperand(0).setReg(PhiR);
1895 IllegalPhisToDelete.push_back(MI);
1896 return;
1897 }
1898
1899 int Stage = getStage(MI);
1900 if (Stage == -1 || LiveStages.count(MI->getParent()) == 0 ||
1901 LiveStages[MI->getParent()].test(Stage))
1902 // Instruction is live, no rewriting to do.
1903 return;
1904
1905 for (MachineOperand &DefMO : MI->defs()) {
1906 SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
1907 for (MachineInstr &UseMI : MRI.use_instructions(DefMO.getReg())) {
1908 // Only PHIs can use values from this block by construction.
1909 // Match with the equivalent PHI in B.
1910 assert(UseMI.isPHI());
1911 Register Reg = getEquivalentRegisterIn(UseMI.getOperand(0).getReg(),
1912 MI->getParent());
1913 Subs.emplace_back(&UseMI, Reg);
1914 }
1915 for (auto &Sub : Subs)
1916 Sub.first->substituteRegister(DefMO.getReg(), Sub.second, /*SubIdx=*/0,
1917 *MRI.getTargetRegisterInfo());
1918 }
1919 if (LIS)
1920 LIS->RemoveMachineInstrFromMaps(*MI);
1921 MI->eraseFromParent();
1922 }
1923
fixupBranches()1924 void PeelingModuloScheduleExpander::fixupBranches() {
1925 // Work outwards from the kernel.
1926 bool KernelDisposed = false;
1927 int TC = Schedule.getNumStages() - 1;
1928 for (auto PI = Prologs.rbegin(), EI = Epilogs.rbegin(); PI != Prologs.rend();
1929 ++PI, ++EI, --TC) {
1930 MachineBasicBlock *Prolog = *PI;
1931 MachineBasicBlock *Fallthrough = *Prolog->succ_begin();
1932 MachineBasicBlock *Epilog = *EI;
1933 SmallVector<MachineOperand, 4> Cond;
1934 TII->removeBranch(*Prolog);
1935 Optional<bool> StaticallyGreater =
1936 Info->createTripCountGreaterCondition(TC, *Prolog, Cond);
1937 if (!StaticallyGreater.hasValue()) {
1938 LLVM_DEBUG(dbgs() << "Dynamic: TC > " << TC << "\n");
1939 // Dynamically branch based on Cond.
1940 TII->insertBranch(*Prolog, Epilog, Fallthrough, Cond, DebugLoc());
1941 } else if (*StaticallyGreater == false) {
1942 LLVM_DEBUG(dbgs() << "Static-false: TC > " << TC << "\n");
1943 // Prolog never falls through; branch to epilog and orphan interior
1944 // blocks. Leave it to unreachable-block-elim to clean up.
1945 Prolog->removeSuccessor(Fallthrough);
1946 for (MachineInstr &P : Fallthrough->phis()) {
1947 P.RemoveOperand(2);
1948 P.RemoveOperand(1);
1949 }
1950 TII->insertUnconditionalBranch(*Prolog, Epilog, DebugLoc());
1951 KernelDisposed = true;
1952 } else {
1953 LLVM_DEBUG(dbgs() << "Static-true: TC > " << TC << "\n");
1954 // Prolog always falls through; remove incoming values in epilog.
1955 Prolog->removeSuccessor(Epilog);
1956 for (MachineInstr &P : Epilog->phis()) {
1957 P.RemoveOperand(4);
1958 P.RemoveOperand(3);
1959 }
1960 }
1961 }
1962
1963 if (!KernelDisposed) {
1964 Info->adjustTripCount(-(Schedule.getNumStages() - 1));
1965 Info->setPreheader(Prologs.back());
1966 } else {
1967 Info->disposed();
1968 }
1969 }
1970
rewriteKernel()1971 void PeelingModuloScheduleExpander::rewriteKernel() {
1972 KernelRewriter KR(*Schedule.getLoop(), Schedule);
1973 KR.rewrite();
1974 }
1975
expand()1976 void PeelingModuloScheduleExpander::expand() {
1977 BB = Schedule.getLoop()->getTopBlock();
1978 Preheader = Schedule.getLoop()->getLoopPreheader();
1979 LLVM_DEBUG(Schedule.dump());
1980 Info = TII->analyzeLoopForPipelining(BB);
1981 assert(Info);
1982
1983 rewriteKernel();
1984 peelPrologAndEpilogs();
1985 fixupBranches();
1986 }
1987
validateAgainstModuloScheduleExpander()1988 void PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander() {
1989 BB = Schedule.getLoop()->getTopBlock();
1990 Preheader = Schedule.getLoop()->getLoopPreheader();
1991
1992 // Dump the schedule before we invalidate and remap all its instructions.
1993 // Stash it in a string so we can print it if we found an error.
1994 std::string ScheduleDump;
1995 raw_string_ostream OS(ScheduleDump);
1996 Schedule.print(OS);
1997 OS.flush();
1998
1999 // First, run the normal ModuleScheduleExpander. We don't support any
2000 // InstrChanges.
2001 assert(LIS && "Requires LiveIntervals!");
2002 ModuloScheduleExpander MSE(MF, Schedule, *LIS,
2003 ModuloScheduleExpander::InstrChangesTy());
2004 MSE.expand();
2005 MachineBasicBlock *ExpandedKernel = MSE.getRewrittenKernel();
2006 if (!ExpandedKernel) {
2007 // The expander optimized away the kernel. We can't do any useful checking.
2008 MSE.cleanup();
2009 return;
2010 }
2011 // Before running the KernelRewriter, re-add BB into the CFG.
2012 Preheader->addSuccessor(BB);
2013
2014 // Now run the new expansion algorithm.
2015 KernelRewriter KR(*Schedule.getLoop(), Schedule);
2016 KR.rewrite();
2017 peelPrologAndEpilogs();
2018
2019 // Collect all illegal phis that the new algorithm created. We'll give these
2020 // to KernelOperandInfo.
2021 SmallPtrSet<MachineInstr *, 4> IllegalPhis;
2022 for (auto NI = BB->getFirstNonPHI(); NI != BB->end(); ++NI) {
2023 if (NI->isPHI())
2024 IllegalPhis.insert(&*NI);
2025 }
2026
2027 // Co-iterate across both kernels. We expect them to be identical apart from
2028 // phis and full COPYs (we look through both).
2029 SmallVector<std::pair<KernelOperandInfo, KernelOperandInfo>, 8> KOIs;
2030 auto OI = ExpandedKernel->begin();
2031 auto NI = BB->begin();
2032 for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {
2033 while (OI->isPHI() || OI->isFullCopy())
2034 ++OI;
2035 while (NI->isPHI() || NI->isFullCopy())
2036 ++NI;
2037 assert(OI->getOpcode() == NI->getOpcode() && "Opcodes don't match?!");
2038 // Analyze every operand separately.
2039 for (auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();
2040 OOpI != OI->operands_end(); ++OOpI, ++NOpI)
2041 KOIs.emplace_back(KernelOperandInfo(&*OOpI, MRI, IllegalPhis),
2042 KernelOperandInfo(&*NOpI, MRI, IllegalPhis));
2043 }
2044
2045 bool Failed = false;
2046 for (auto &OldAndNew : KOIs) {
2047 if (OldAndNew.first == OldAndNew.second)
2048 continue;
2049 Failed = true;
2050 errs() << "Modulo kernel validation error: [\n";
2051 errs() << " [golden] ";
2052 OldAndNew.first.print(errs());
2053 errs() << " ";
2054 OldAndNew.second.print(errs());
2055 errs() << "]\n";
2056 }
2057
2058 if (Failed) {
2059 errs() << "Golden reference kernel:\n";
2060 ExpandedKernel->print(errs());
2061 errs() << "New kernel:\n";
2062 BB->print(errs());
2063 errs() << ScheduleDump;
2064 report_fatal_error(
2065 "Modulo kernel validation (-pipeliner-experimental-cg) failed");
2066 }
2067
2068 // Cleanup by removing BB from the CFG again as the original
2069 // ModuloScheduleExpander intended.
2070 Preheader->removeSuccessor(BB);
2071 MSE.cleanup();
2072 }
2073
2074 //===----------------------------------------------------------------------===//
2075 // ModuloScheduleTestPass implementation
2076 //===----------------------------------------------------------------------===//
2077 // This pass constructs a ModuloSchedule from its module and runs
2078 // ModuloScheduleExpander.
2079 //
2080 // The module is expected to contain a single-block analyzable loop.
2081 // The total order of instructions is taken from the loop as-is.
2082 // Instructions are expected to be annotated with a PostInstrSymbol.
2083 // This PostInstrSymbol must have the following format:
2084 // "Stage=%d Cycle=%d".
2085 //===----------------------------------------------------------------------===//
2086
2087 namespace {
2088 class ModuloScheduleTest : public MachineFunctionPass {
2089 public:
2090 static char ID;
2091
ModuloScheduleTest()2092 ModuloScheduleTest() : MachineFunctionPass(ID) {
2093 initializeModuloScheduleTestPass(*PassRegistry::getPassRegistry());
2094 }
2095
2096 bool runOnMachineFunction(MachineFunction &MF) override;
2097 void runOnLoop(MachineFunction &MF, MachineLoop &L);
2098
getAnalysisUsage(AnalysisUsage & AU) const2099 void getAnalysisUsage(AnalysisUsage &AU) const override {
2100 AU.addRequired<MachineLoopInfo>();
2101 AU.addRequired<LiveIntervals>();
2102 MachineFunctionPass::getAnalysisUsage(AU);
2103 }
2104 };
2105 } // namespace
2106
2107 char ModuloScheduleTest::ID = 0;
2108
2109 INITIALIZE_PASS_BEGIN(ModuloScheduleTest, "modulo-schedule-test",
2110 "Modulo Schedule test pass", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)2111 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
2112 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
2113 INITIALIZE_PASS_END(ModuloScheduleTest, "modulo-schedule-test",
2114 "Modulo Schedule test pass", false, false)
2115
2116 bool ModuloScheduleTest::runOnMachineFunction(MachineFunction &MF) {
2117 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
2118 for (auto *L : MLI) {
2119 if (L->getTopBlock() != L->getBottomBlock())
2120 continue;
2121 runOnLoop(MF, *L);
2122 return false;
2123 }
2124 return false;
2125 }
2126
parseSymbolString(StringRef S,int & Cycle,int & Stage)2127 static void parseSymbolString(StringRef S, int &Cycle, int &Stage) {
2128 std::pair<StringRef, StringRef> StageAndCycle = getToken(S, "_");
2129 std::pair<StringRef, StringRef> StageTokenAndValue =
2130 getToken(StageAndCycle.first, "-");
2131 std::pair<StringRef, StringRef> CycleTokenAndValue =
2132 getToken(StageAndCycle.second, "-");
2133 if (StageTokenAndValue.first != "Stage" ||
2134 CycleTokenAndValue.first != "_Cycle") {
2135 llvm_unreachable(
2136 "Bad post-instr symbol syntax: see comment in ModuloScheduleTest");
2137 return;
2138 }
2139
2140 StageTokenAndValue.second.drop_front().getAsInteger(10, Stage);
2141 CycleTokenAndValue.second.drop_front().getAsInteger(10, Cycle);
2142
2143 dbgs() << " Stage=" << Stage << ", Cycle=" << Cycle << "\n";
2144 }
2145
runOnLoop(MachineFunction & MF,MachineLoop & L)2146 void ModuloScheduleTest::runOnLoop(MachineFunction &MF, MachineLoop &L) {
2147 LiveIntervals &LIS = getAnalysis<LiveIntervals>();
2148 MachineBasicBlock *BB = L.getTopBlock();
2149 dbgs() << "--- ModuloScheduleTest running on BB#" << BB->getNumber() << "\n";
2150
2151 DenseMap<MachineInstr *, int> Cycle, Stage;
2152 std::vector<MachineInstr *> Instrs;
2153 for (MachineInstr &MI : *BB) {
2154 if (MI.isTerminator())
2155 continue;
2156 Instrs.push_back(&MI);
2157 if (MCSymbol *Sym = MI.getPostInstrSymbol()) {
2158 dbgs() << "Parsing post-instr symbol for " << MI;
2159 parseSymbolString(Sym->getName(), Cycle[&MI], Stage[&MI]);
2160 }
2161 }
2162
2163 ModuloSchedule MS(MF, &L, std::move(Instrs), std::move(Cycle),
2164 std::move(Stage));
2165 ModuloScheduleExpander MSE(
2166 MF, MS, LIS, /*InstrChanges=*/ModuloScheduleExpander::InstrChangesTy());
2167 MSE.expand();
2168 MSE.cleanup();
2169 }
2170
2171 //===----------------------------------------------------------------------===//
2172 // ModuloScheduleTestAnnotater implementation
2173 //===----------------------------------------------------------------------===//
2174
annotate()2175 void ModuloScheduleTestAnnotater::annotate() {
2176 for (MachineInstr *MI : S.getInstructions()) {
2177 SmallVector<char, 16> SV;
2178 raw_svector_ostream OS(SV);
2179 OS << "Stage-" << S.getStage(MI) << "_Cycle-" << S.getCycle(MI);
2180 MCSymbol *Sym = MF.getContext().getOrCreateSymbol(OS.str());
2181 MI->setPostInstrSymbol(MF, Sym);
2182 }
2183 }
2184