109467b48Spatrick //===- ModuloSchedule.cpp - Software pipeline schedule expansion ----------===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick
909467b48Spatrick #include "llvm/CodeGen/ModuloSchedule.h"
1009467b48Spatrick #include "llvm/ADT/StringExtras.h"
11097a140dSpatrick #include "llvm/Analysis/MemoryLocation.h"
1209467b48Spatrick #include "llvm/CodeGen/LiveIntervals.h"
1309467b48Spatrick #include "llvm/CodeGen/MachineInstrBuilder.h"
14*d415bd75Srobert #include "llvm/CodeGen/MachineLoopInfo.h"
1509467b48Spatrick #include "llvm/CodeGen/MachineRegisterInfo.h"
1609467b48Spatrick #include "llvm/InitializePasses.h"
1709467b48Spatrick #include "llvm/MC/MCContext.h"
1809467b48Spatrick #include "llvm/Support/Debug.h"
1909467b48Spatrick #include "llvm/Support/ErrorHandling.h"
2009467b48Spatrick #include "llvm/Support/raw_ostream.h"
2109467b48Spatrick
2209467b48Spatrick #define DEBUG_TYPE "pipeliner"
2309467b48Spatrick using namespace llvm;
2409467b48Spatrick
print(raw_ostream & OS)2509467b48Spatrick void ModuloSchedule::print(raw_ostream &OS) {
2609467b48Spatrick for (MachineInstr *MI : ScheduledInstrs)
2709467b48Spatrick OS << "[stage " << getStage(MI) << " @" << getCycle(MI) << "c] " << *MI;
2809467b48Spatrick }
2909467b48Spatrick
3009467b48Spatrick //===----------------------------------------------------------------------===//
3109467b48Spatrick // ModuloScheduleExpander implementation
3209467b48Spatrick //===----------------------------------------------------------------------===//
3309467b48Spatrick
3409467b48Spatrick /// Return the register values for the operands of a Phi instruction.
3509467b48Spatrick /// This function assume the instruction is a Phi.
getPhiRegs(MachineInstr & Phi,MachineBasicBlock * Loop,unsigned & InitVal,unsigned & LoopVal)3609467b48Spatrick static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
3709467b48Spatrick unsigned &InitVal, unsigned &LoopVal) {
3809467b48Spatrick assert(Phi.isPHI() && "Expecting a Phi.");
3909467b48Spatrick
4009467b48Spatrick InitVal = 0;
4109467b48Spatrick LoopVal = 0;
4209467b48Spatrick for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
4309467b48Spatrick if (Phi.getOperand(i + 1).getMBB() != Loop)
4409467b48Spatrick InitVal = Phi.getOperand(i).getReg();
4509467b48Spatrick else
4609467b48Spatrick LoopVal = Phi.getOperand(i).getReg();
4709467b48Spatrick
4809467b48Spatrick assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure.");
4909467b48Spatrick }
5009467b48Spatrick
5109467b48Spatrick /// Return the Phi register value that comes from the incoming block.
getInitPhiReg(MachineInstr & Phi,MachineBasicBlock * LoopBB)5209467b48Spatrick static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
5309467b48Spatrick for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
5409467b48Spatrick if (Phi.getOperand(i + 1).getMBB() != LoopBB)
5509467b48Spatrick return Phi.getOperand(i).getReg();
5609467b48Spatrick return 0;
5709467b48Spatrick }
5809467b48Spatrick
5909467b48Spatrick /// Return the Phi register value that comes the loop block.
getLoopPhiReg(MachineInstr & Phi,MachineBasicBlock * LoopBB)6009467b48Spatrick static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
6109467b48Spatrick for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
6209467b48Spatrick if (Phi.getOperand(i + 1).getMBB() == LoopBB)
6309467b48Spatrick return Phi.getOperand(i).getReg();
6409467b48Spatrick return 0;
6509467b48Spatrick }
6609467b48Spatrick
expand()6709467b48Spatrick void ModuloScheduleExpander::expand() {
6809467b48Spatrick BB = Schedule.getLoop()->getTopBlock();
6909467b48Spatrick Preheader = *BB->pred_begin();
7009467b48Spatrick if (Preheader == BB)
7109467b48Spatrick Preheader = *std::next(BB->pred_begin());
7209467b48Spatrick
7309467b48Spatrick // Iterate over the definitions in each instruction, and compute the
7409467b48Spatrick // stage difference for each use. Keep the maximum value.
7509467b48Spatrick for (MachineInstr *MI : Schedule.getInstructions()) {
7609467b48Spatrick int DefStage = Schedule.getStage(MI);
77*d415bd75Srobert for (const MachineOperand &Op : MI->operands()) {
7809467b48Spatrick if (!Op.isReg() || !Op.isDef())
7909467b48Spatrick continue;
8009467b48Spatrick
8109467b48Spatrick Register Reg = Op.getReg();
8209467b48Spatrick unsigned MaxDiff = 0;
8309467b48Spatrick bool PhiIsSwapped = false;
84*d415bd75Srobert for (MachineOperand &UseOp : MRI.use_operands(Reg)) {
8509467b48Spatrick MachineInstr *UseMI = UseOp.getParent();
8609467b48Spatrick int UseStage = Schedule.getStage(UseMI);
8709467b48Spatrick unsigned Diff = 0;
8809467b48Spatrick if (UseStage != -1 && UseStage >= DefStage)
8909467b48Spatrick Diff = UseStage - DefStage;
9009467b48Spatrick if (MI->isPHI()) {
9109467b48Spatrick if (isLoopCarried(*MI))
9209467b48Spatrick ++Diff;
9309467b48Spatrick else
9409467b48Spatrick PhiIsSwapped = true;
9509467b48Spatrick }
9609467b48Spatrick MaxDiff = std::max(Diff, MaxDiff);
9709467b48Spatrick }
9809467b48Spatrick RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped);
9909467b48Spatrick }
10009467b48Spatrick }
10109467b48Spatrick
10209467b48Spatrick generatePipelinedLoop();
10309467b48Spatrick }
10409467b48Spatrick
generatePipelinedLoop()10509467b48Spatrick void ModuloScheduleExpander::generatePipelinedLoop() {
10609467b48Spatrick LoopInfo = TII->analyzeLoopForPipelining(BB);
10709467b48Spatrick assert(LoopInfo && "Must be able to analyze loop!");
10809467b48Spatrick
10909467b48Spatrick // Create a new basic block for the kernel and add it to the CFG.
11009467b48Spatrick MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
11109467b48Spatrick
11209467b48Spatrick unsigned MaxStageCount = Schedule.getNumStages() - 1;
11309467b48Spatrick
11409467b48Spatrick // Remember the registers that are used in different stages. The index is
11509467b48Spatrick // the iteration, or stage, that the instruction is scheduled in. This is
11609467b48Spatrick // a map between register names in the original block and the names created
11709467b48Spatrick // in each stage of the pipelined loop.
11809467b48Spatrick ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2];
119*d415bd75Srobert
120*d415bd75Srobert // The renaming destination by Phis for the registers across stages.
121*d415bd75Srobert // This map is updated during Phis generation to point to the most recent
122*d415bd75Srobert // renaming destination.
123*d415bd75Srobert ValueMapTy *VRMapPhi = new ValueMapTy[(MaxStageCount + 1) * 2];
124*d415bd75Srobert
12509467b48Spatrick InstrMapTy InstrMap;
12609467b48Spatrick
12709467b48Spatrick SmallVector<MachineBasicBlock *, 4> PrologBBs;
12809467b48Spatrick
12909467b48Spatrick // Generate the prolog instructions that set up the pipeline.
13009467b48Spatrick generateProlog(MaxStageCount, KernelBB, VRMap, PrologBBs);
13109467b48Spatrick MF.insert(BB->getIterator(), KernelBB);
13209467b48Spatrick
13309467b48Spatrick // Rearrange the instructions to generate the new, pipelined loop,
13409467b48Spatrick // and update register names as needed.
13509467b48Spatrick for (MachineInstr *CI : Schedule.getInstructions()) {
13609467b48Spatrick if (CI->isPHI())
13709467b48Spatrick continue;
13809467b48Spatrick unsigned StageNum = Schedule.getStage(CI);
13909467b48Spatrick MachineInstr *NewMI = cloneInstr(CI, MaxStageCount, StageNum);
14009467b48Spatrick updateInstruction(NewMI, false, MaxStageCount, StageNum, VRMap);
14109467b48Spatrick KernelBB->push_back(NewMI);
14209467b48Spatrick InstrMap[NewMI] = CI;
14309467b48Spatrick }
14409467b48Spatrick
14509467b48Spatrick // Copy any terminator instructions to the new kernel, and update
14609467b48Spatrick // names as needed.
147*d415bd75Srobert for (MachineInstr &MI : BB->terminators()) {
148*d415bd75Srobert MachineInstr *NewMI = MF.CloneMachineInstr(&MI);
14909467b48Spatrick updateInstruction(NewMI, false, MaxStageCount, 0, VRMap);
15009467b48Spatrick KernelBB->push_back(NewMI);
151*d415bd75Srobert InstrMap[NewMI] = &MI;
15209467b48Spatrick }
15309467b48Spatrick
15409467b48Spatrick NewKernel = KernelBB;
15509467b48Spatrick KernelBB->transferSuccessors(BB);
15609467b48Spatrick KernelBB->replaceSuccessor(BB, KernelBB);
15709467b48Spatrick
15809467b48Spatrick generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap,
15909467b48Spatrick InstrMap, MaxStageCount, MaxStageCount, false);
160*d415bd75Srobert generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap, VRMapPhi,
161*d415bd75Srobert InstrMap, MaxStageCount, MaxStageCount, false);
16209467b48Spatrick
16309467b48Spatrick LLVM_DEBUG(dbgs() << "New block\n"; KernelBB->dump(););
16409467b48Spatrick
16509467b48Spatrick SmallVector<MachineBasicBlock *, 4> EpilogBBs;
16609467b48Spatrick // Generate the epilog instructions to complete the pipeline.
167*d415bd75Srobert generateEpilog(MaxStageCount, KernelBB, BB, VRMap, VRMapPhi, EpilogBBs,
168*d415bd75Srobert PrologBBs);
16909467b48Spatrick
17009467b48Spatrick // We need this step because the register allocation doesn't handle some
17109467b48Spatrick // situations well, so we insert copies to help out.
17209467b48Spatrick splitLifetimes(KernelBB, EpilogBBs);
17309467b48Spatrick
17409467b48Spatrick // Remove dead instructions due to loop induction variables.
17509467b48Spatrick removeDeadInstructions(KernelBB, EpilogBBs);
17609467b48Spatrick
17709467b48Spatrick // Add branches between prolog and epilog blocks.
17809467b48Spatrick addBranches(*Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap);
17909467b48Spatrick
18009467b48Spatrick delete[] VRMap;
181*d415bd75Srobert delete[] VRMapPhi;
18209467b48Spatrick }
18309467b48Spatrick
cleanup()18409467b48Spatrick void ModuloScheduleExpander::cleanup() {
18509467b48Spatrick // Remove the original loop since it's no longer referenced.
18609467b48Spatrick for (auto &I : *BB)
18709467b48Spatrick LIS.RemoveMachineInstrFromMaps(I);
18809467b48Spatrick BB->clear();
18909467b48Spatrick BB->eraseFromParent();
19009467b48Spatrick }
19109467b48Spatrick
19209467b48Spatrick /// Generate the pipeline prolog code.
generateProlog(unsigned LastStage,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,MBBVectorTy & PrologBBs)19309467b48Spatrick void ModuloScheduleExpander::generateProlog(unsigned LastStage,
19409467b48Spatrick MachineBasicBlock *KernelBB,
19509467b48Spatrick ValueMapTy *VRMap,
19609467b48Spatrick MBBVectorTy &PrologBBs) {
19709467b48Spatrick MachineBasicBlock *PredBB = Preheader;
19809467b48Spatrick InstrMapTy InstrMap;
19909467b48Spatrick
20009467b48Spatrick // Generate a basic block for each stage, not including the last stage,
20109467b48Spatrick // which will be generated in the kernel. Each basic block may contain
20209467b48Spatrick // instructions from multiple stages/iterations.
20309467b48Spatrick for (unsigned i = 0; i < LastStage; ++i) {
20409467b48Spatrick // Create and insert the prolog basic block prior to the original loop
20509467b48Spatrick // basic block. The original loop is removed later.
20609467b48Spatrick MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
20709467b48Spatrick PrologBBs.push_back(NewBB);
20809467b48Spatrick MF.insert(BB->getIterator(), NewBB);
20909467b48Spatrick NewBB->transferSuccessors(PredBB);
21009467b48Spatrick PredBB->addSuccessor(NewBB);
21109467b48Spatrick PredBB = NewBB;
21209467b48Spatrick
21309467b48Spatrick // Generate instructions for each appropriate stage. Process instructions
21409467b48Spatrick // in original program order.
21509467b48Spatrick for (int StageNum = i; StageNum >= 0; --StageNum) {
21609467b48Spatrick for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
21709467b48Spatrick BBE = BB->getFirstTerminator();
21809467b48Spatrick BBI != BBE; ++BBI) {
21909467b48Spatrick if (Schedule.getStage(&*BBI) == StageNum) {
22009467b48Spatrick if (BBI->isPHI())
22109467b48Spatrick continue;
22209467b48Spatrick MachineInstr *NewMI =
22309467b48Spatrick cloneAndChangeInstr(&*BBI, i, (unsigned)StageNum);
22409467b48Spatrick updateInstruction(NewMI, false, i, (unsigned)StageNum, VRMap);
22509467b48Spatrick NewBB->push_back(NewMI);
22609467b48Spatrick InstrMap[NewMI] = &*BBI;
22709467b48Spatrick }
22809467b48Spatrick }
22909467b48Spatrick }
23009467b48Spatrick rewritePhiValues(NewBB, i, VRMap, InstrMap);
23109467b48Spatrick LLVM_DEBUG({
23209467b48Spatrick dbgs() << "prolog:\n";
23309467b48Spatrick NewBB->dump();
23409467b48Spatrick });
23509467b48Spatrick }
23609467b48Spatrick
23709467b48Spatrick PredBB->replaceSuccessor(BB, KernelBB);
23809467b48Spatrick
23909467b48Spatrick // Check if we need to remove the branch from the preheader to the original
24009467b48Spatrick // loop, and replace it with a branch to the new loop.
24109467b48Spatrick unsigned numBranches = TII->removeBranch(*Preheader);
24209467b48Spatrick if (numBranches) {
24309467b48Spatrick SmallVector<MachineOperand, 0> Cond;
24409467b48Spatrick TII->insertBranch(*Preheader, PrologBBs[0], nullptr, Cond, DebugLoc());
24509467b48Spatrick }
24609467b48Spatrick }
24709467b48Spatrick
24809467b48Spatrick /// Generate the pipeline epilog code. The epilog code finishes the iterations
24909467b48Spatrick /// that were started in either the prolog or the kernel. We create a basic
25009467b48Spatrick /// block for each stage that needs to complete.
generateEpilog(unsigned LastStage,MachineBasicBlock * KernelBB,MachineBasicBlock * OrigBB,ValueMapTy * VRMap,ValueMapTy * VRMapPhi,MBBVectorTy & EpilogBBs,MBBVectorTy & PrologBBs)251*d415bd75Srobert void ModuloScheduleExpander::generateEpilog(
252*d415bd75Srobert unsigned LastStage, MachineBasicBlock *KernelBB, MachineBasicBlock *OrigBB,
253*d415bd75Srobert ValueMapTy *VRMap, ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,
25409467b48Spatrick MBBVectorTy &PrologBBs) {
25509467b48Spatrick // We need to change the branch from the kernel to the first epilog block, so
25609467b48Spatrick // this call to analyze branch uses the kernel rather than the original BB.
25709467b48Spatrick MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
25809467b48Spatrick SmallVector<MachineOperand, 4> Cond;
25909467b48Spatrick bool checkBranch = TII->analyzeBranch(*KernelBB, TBB, FBB, Cond);
26009467b48Spatrick assert(!checkBranch && "generateEpilog must be able to analyze the branch");
26109467b48Spatrick if (checkBranch)
26209467b48Spatrick return;
26309467b48Spatrick
26409467b48Spatrick MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin();
26509467b48Spatrick if (*LoopExitI == KernelBB)
26609467b48Spatrick ++LoopExitI;
26709467b48Spatrick assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor");
26809467b48Spatrick MachineBasicBlock *LoopExitBB = *LoopExitI;
26909467b48Spatrick
27009467b48Spatrick MachineBasicBlock *PredBB = KernelBB;
27109467b48Spatrick MachineBasicBlock *EpilogStart = LoopExitBB;
27209467b48Spatrick InstrMapTy InstrMap;
27309467b48Spatrick
27409467b48Spatrick // Generate a basic block for each stage, not including the last stage,
27509467b48Spatrick // which was generated for the kernel. Each basic block may contain
27609467b48Spatrick // instructions from multiple stages/iterations.
27709467b48Spatrick int EpilogStage = LastStage + 1;
27809467b48Spatrick for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {
27909467b48Spatrick MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock();
28009467b48Spatrick EpilogBBs.push_back(NewBB);
28109467b48Spatrick MF.insert(BB->getIterator(), NewBB);
28209467b48Spatrick
28309467b48Spatrick PredBB->replaceSuccessor(LoopExitBB, NewBB);
28409467b48Spatrick NewBB->addSuccessor(LoopExitBB);
28509467b48Spatrick
28609467b48Spatrick if (EpilogStart == LoopExitBB)
28709467b48Spatrick EpilogStart = NewBB;
28809467b48Spatrick
28909467b48Spatrick // Add instructions to the epilog depending on the current block.
29009467b48Spatrick // Process instructions in original program order.
29109467b48Spatrick for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) {
29209467b48Spatrick for (auto &BBI : *BB) {
29309467b48Spatrick if (BBI.isPHI())
29409467b48Spatrick continue;
29509467b48Spatrick MachineInstr *In = &BBI;
29609467b48Spatrick if ((unsigned)Schedule.getStage(In) == StageNum) {
29709467b48Spatrick // Instructions with memoperands in the epilog are updated with
29809467b48Spatrick // conservative values.
29909467b48Spatrick MachineInstr *NewMI = cloneInstr(In, UINT_MAX, 0);
30009467b48Spatrick updateInstruction(NewMI, i == 1, EpilogStage, 0, VRMap);
30109467b48Spatrick NewBB->push_back(NewMI);
30209467b48Spatrick InstrMap[NewMI] = In;
30309467b48Spatrick }
30409467b48Spatrick }
30509467b48Spatrick }
30609467b48Spatrick generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap,
30709467b48Spatrick InstrMap, LastStage, EpilogStage, i == 1);
308*d415bd75Srobert generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap, VRMapPhi,
309*d415bd75Srobert InstrMap, LastStage, EpilogStage, i == 1);
31009467b48Spatrick PredBB = NewBB;
31109467b48Spatrick
31209467b48Spatrick LLVM_DEBUG({
31309467b48Spatrick dbgs() << "epilog:\n";
31409467b48Spatrick NewBB->dump();
31509467b48Spatrick });
31609467b48Spatrick }
31709467b48Spatrick
31809467b48Spatrick // Fix any Phi nodes in the loop exit block.
31909467b48Spatrick LoopExitBB->replacePhiUsesWith(BB, PredBB);
32009467b48Spatrick
32109467b48Spatrick // Create a branch to the new epilog from the kernel.
32209467b48Spatrick // Remove the original branch and add a new branch to the epilog.
32309467b48Spatrick TII->removeBranch(*KernelBB);
324*d415bd75Srobert assert((OrigBB == TBB || OrigBB == FBB) &&
325*d415bd75Srobert "Unable to determine looping branch direction");
326*d415bd75Srobert if (OrigBB != TBB)
327*d415bd75Srobert TII->insertBranch(*KernelBB, EpilogStart, KernelBB, Cond, DebugLoc());
328*d415bd75Srobert else
32909467b48Spatrick TII->insertBranch(*KernelBB, KernelBB, EpilogStart, Cond, DebugLoc());
33009467b48Spatrick // Add a branch to the loop exit.
33109467b48Spatrick if (EpilogBBs.size() > 0) {
33209467b48Spatrick MachineBasicBlock *LastEpilogBB = EpilogBBs.back();
33309467b48Spatrick SmallVector<MachineOperand, 4> Cond1;
33409467b48Spatrick TII->insertBranch(*LastEpilogBB, LoopExitBB, nullptr, Cond1, DebugLoc());
33509467b48Spatrick }
33609467b48Spatrick }
33709467b48Spatrick
33809467b48Spatrick /// Replace all uses of FromReg that appear outside the specified
33909467b48Spatrick /// basic block with ToReg.
replaceRegUsesAfterLoop(unsigned FromReg,unsigned ToReg,MachineBasicBlock * MBB,MachineRegisterInfo & MRI,LiveIntervals & LIS)34009467b48Spatrick static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg,
34109467b48Spatrick MachineBasicBlock *MBB,
34209467b48Spatrick MachineRegisterInfo &MRI,
34309467b48Spatrick LiveIntervals &LIS) {
344*d415bd75Srobert for (MachineOperand &O :
345*d415bd75Srobert llvm::make_early_inc_range(MRI.use_operands(FromReg)))
34609467b48Spatrick if (O.getParent()->getParent() != MBB)
34709467b48Spatrick O.setReg(ToReg);
34809467b48Spatrick if (!LIS.hasInterval(ToReg))
34909467b48Spatrick LIS.createEmptyInterval(ToReg);
35009467b48Spatrick }
35109467b48Spatrick
35209467b48Spatrick /// Return true if the register has a use that occurs outside the
35309467b48Spatrick /// specified loop.
hasUseAfterLoop(unsigned Reg,MachineBasicBlock * BB,MachineRegisterInfo & MRI)35409467b48Spatrick static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB,
35509467b48Spatrick MachineRegisterInfo &MRI) {
356*d415bd75Srobert for (const MachineOperand &MO : MRI.use_operands(Reg))
357*d415bd75Srobert if (MO.getParent()->getParent() != BB)
35809467b48Spatrick return true;
35909467b48Spatrick return false;
36009467b48Spatrick }
36109467b48Spatrick
36209467b48Spatrick /// Generate Phis for the specific block in the generated pipelined code.
36309467b48Spatrick /// This function looks at the Phis from the original code to guide the
36409467b48Spatrick /// creation of new Phis.
generateExistingPhis(MachineBasicBlock * NewBB,MachineBasicBlock * BB1,MachineBasicBlock * BB2,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,InstrMapTy & InstrMap,unsigned LastStageNum,unsigned CurStageNum,bool IsLast)36509467b48Spatrick void ModuloScheduleExpander::generateExistingPhis(
36609467b48Spatrick MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
36709467b48Spatrick MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap,
36809467b48Spatrick unsigned LastStageNum, unsigned CurStageNum, bool IsLast) {
36909467b48Spatrick // Compute the stage number for the initial value of the Phi, which
37009467b48Spatrick // comes from the prolog. The prolog to use depends on to which kernel/
37109467b48Spatrick // epilog that we're adding the Phi.
37209467b48Spatrick unsigned PrologStage = 0;
37309467b48Spatrick unsigned PrevStage = 0;
37409467b48Spatrick bool InKernel = (LastStageNum == CurStageNum);
37509467b48Spatrick if (InKernel) {
37609467b48Spatrick PrologStage = LastStageNum - 1;
37709467b48Spatrick PrevStage = CurStageNum;
37809467b48Spatrick } else {
37909467b48Spatrick PrologStage = LastStageNum - (CurStageNum - LastStageNum);
38009467b48Spatrick PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;
38109467b48Spatrick }
38209467b48Spatrick
38309467b48Spatrick for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
38409467b48Spatrick BBE = BB->getFirstNonPHI();
38509467b48Spatrick BBI != BBE; ++BBI) {
38609467b48Spatrick Register Def = BBI->getOperand(0).getReg();
38709467b48Spatrick
38809467b48Spatrick unsigned InitVal = 0;
38909467b48Spatrick unsigned LoopVal = 0;
39009467b48Spatrick getPhiRegs(*BBI, BB, InitVal, LoopVal);
39109467b48Spatrick
39209467b48Spatrick unsigned PhiOp1 = 0;
39309467b48Spatrick // The Phi value from the loop body typically is defined in the loop, but
39409467b48Spatrick // not always. So, we need to check if the value is defined in the loop.
39509467b48Spatrick unsigned PhiOp2 = LoopVal;
39609467b48Spatrick if (VRMap[LastStageNum].count(LoopVal))
39709467b48Spatrick PhiOp2 = VRMap[LastStageNum][LoopVal];
39809467b48Spatrick
39909467b48Spatrick int StageScheduled = Schedule.getStage(&*BBI);
40009467b48Spatrick int LoopValStage = Schedule.getStage(MRI.getVRegDef(LoopVal));
40109467b48Spatrick unsigned NumStages = getStagesForReg(Def, CurStageNum);
40209467b48Spatrick if (NumStages == 0) {
40309467b48Spatrick // We don't need to generate a Phi anymore, but we need to rename any uses
40409467b48Spatrick // of the Phi value.
40509467b48Spatrick unsigned NewReg = VRMap[PrevStage][LoopVal];
40609467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, 0, &*BBI, Def,
40709467b48Spatrick InitVal, NewReg);
40809467b48Spatrick if (VRMap[CurStageNum].count(LoopVal))
40909467b48Spatrick VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal];
41009467b48Spatrick }
41109467b48Spatrick // Adjust the number of Phis needed depending on the number of prologs left,
41209467b48Spatrick // and the distance from where the Phi is first scheduled. The number of
41309467b48Spatrick // Phis cannot exceed the number of prolog stages. Each stage can
41409467b48Spatrick // potentially define two values.
41509467b48Spatrick unsigned MaxPhis = PrologStage + 2;
41609467b48Spatrick if (!InKernel && (int)PrologStage <= LoopValStage)
41709467b48Spatrick MaxPhis = std::max((int)MaxPhis - (int)LoopValStage, 1);
41809467b48Spatrick unsigned NumPhis = std::min(NumStages, MaxPhis);
41909467b48Spatrick
42009467b48Spatrick unsigned NewReg = 0;
42109467b48Spatrick unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;
42209467b48Spatrick // In the epilog, we may need to look back one stage to get the correct
423097a140dSpatrick // Phi name, because the epilog and prolog blocks execute the same stage.
42409467b48Spatrick // The correct name is from the previous block only when the Phi has
42509467b48Spatrick // been completely scheduled prior to the epilog, and Phi value is not
42609467b48Spatrick // needed in multiple stages.
42709467b48Spatrick int StageDiff = 0;
42809467b48Spatrick if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&
42909467b48Spatrick NumPhis == 1)
43009467b48Spatrick StageDiff = 1;
43109467b48Spatrick // Adjust the computations below when the phi and the loop definition
43209467b48Spatrick // are scheduled in different stages.
43309467b48Spatrick if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)
43409467b48Spatrick StageDiff = StageScheduled - LoopValStage;
43509467b48Spatrick for (unsigned np = 0; np < NumPhis; ++np) {
43609467b48Spatrick // If the Phi hasn't been scheduled, then use the initial Phi operand
43709467b48Spatrick // value. Otherwise, use the scheduled version of the instruction. This
43809467b48Spatrick // is a little complicated when a Phi references another Phi.
43909467b48Spatrick if (np > PrologStage || StageScheduled >= (int)LastStageNum)
44009467b48Spatrick PhiOp1 = InitVal;
44109467b48Spatrick // Check if the Phi has already been scheduled in a prolog stage.
44209467b48Spatrick else if (PrologStage >= AccessStage + StageDiff + np &&
44309467b48Spatrick VRMap[PrologStage - StageDiff - np].count(LoopVal) != 0)
44409467b48Spatrick PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];
44509467b48Spatrick // Check if the Phi has already been scheduled, but the loop instruction
44609467b48Spatrick // is either another Phi, or doesn't occur in the loop.
44709467b48Spatrick else if (PrologStage >= AccessStage + StageDiff + np) {
44809467b48Spatrick // If the Phi references another Phi, we need to examine the other
44909467b48Spatrick // Phi to get the correct value.
45009467b48Spatrick PhiOp1 = LoopVal;
45109467b48Spatrick MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1);
45209467b48Spatrick int Indirects = 1;
45309467b48Spatrick while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) {
45409467b48Spatrick int PhiStage = Schedule.getStage(InstOp1);
45509467b48Spatrick if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects)
45609467b48Spatrick PhiOp1 = getInitPhiReg(*InstOp1, BB);
45709467b48Spatrick else
45809467b48Spatrick PhiOp1 = getLoopPhiReg(*InstOp1, BB);
45909467b48Spatrick InstOp1 = MRI.getVRegDef(PhiOp1);
46009467b48Spatrick int PhiOpStage = Schedule.getStage(InstOp1);
46109467b48Spatrick int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);
46209467b48Spatrick if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np &&
46309467b48Spatrick VRMap[PrologStage - StageAdj - Indirects - np].count(PhiOp1)) {
46409467b48Spatrick PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1];
46509467b48Spatrick break;
46609467b48Spatrick }
46709467b48Spatrick ++Indirects;
46809467b48Spatrick }
46909467b48Spatrick } else
47009467b48Spatrick PhiOp1 = InitVal;
47109467b48Spatrick // If this references a generated Phi in the kernel, get the Phi operand
47209467b48Spatrick // from the incoming block.
47309467b48Spatrick if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1))
47409467b48Spatrick if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB)
47509467b48Spatrick PhiOp1 = getInitPhiReg(*InstOp1, KernelBB);
47609467b48Spatrick
47709467b48Spatrick MachineInstr *PhiInst = MRI.getVRegDef(LoopVal);
47809467b48Spatrick bool LoopDefIsPhi = PhiInst && PhiInst->isPHI();
47909467b48Spatrick // In the epilog, a map lookup is needed to get the value from the kernel,
48009467b48Spatrick // or previous epilog block. How is does this depends on if the
48109467b48Spatrick // instruction is scheduled in the previous block.
48209467b48Spatrick if (!InKernel) {
48309467b48Spatrick int StageDiffAdj = 0;
48409467b48Spatrick if (LoopValStage != -1 && StageScheduled > LoopValStage)
48509467b48Spatrick StageDiffAdj = StageScheduled - LoopValStage;
48609467b48Spatrick // Use the loop value defined in the kernel, unless the kernel
48709467b48Spatrick // contains the last definition of the Phi.
48809467b48Spatrick if (np == 0 && PrevStage == LastStageNum &&
48909467b48Spatrick (StageScheduled != 0 || LoopValStage != 0) &&
49009467b48Spatrick VRMap[PrevStage - StageDiffAdj].count(LoopVal))
49109467b48Spatrick PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal];
49209467b48Spatrick // Use the value defined by the Phi. We add one because we switch
49309467b48Spatrick // from looking at the loop value to the Phi definition.
49409467b48Spatrick else if (np > 0 && PrevStage == LastStageNum &&
49509467b48Spatrick VRMap[PrevStage - np + 1].count(Def))
49609467b48Spatrick PhiOp2 = VRMap[PrevStage - np + 1][Def];
49709467b48Spatrick // Use the loop value defined in the kernel.
49809467b48Spatrick else if (static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&
49909467b48Spatrick VRMap[PrevStage - StageDiffAdj - np].count(LoopVal))
50009467b48Spatrick PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal];
50109467b48Spatrick // Use the value defined by the Phi, unless we're generating the first
50209467b48Spatrick // epilog and the Phi refers to a Phi in a different stage.
50309467b48Spatrick else if (VRMap[PrevStage - np].count(Def) &&
50409467b48Spatrick (!LoopDefIsPhi || (PrevStage != LastStageNum) ||
50509467b48Spatrick (LoopValStage == StageScheduled)))
50609467b48Spatrick PhiOp2 = VRMap[PrevStage - np][Def];
50709467b48Spatrick }
50809467b48Spatrick
50909467b48Spatrick // Check if we can reuse an existing Phi. This occurs when a Phi
51009467b48Spatrick // references another Phi, and the other Phi is scheduled in an
51109467b48Spatrick // earlier stage. We can try to reuse an existing Phi up until the last
51209467b48Spatrick // stage of the current Phi.
51309467b48Spatrick if (LoopDefIsPhi) {
51409467b48Spatrick if (static_cast<int>(PrologStage - np) >= StageScheduled) {
51509467b48Spatrick int LVNumStages = getStagesForPhi(LoopVal);
51609467b48Spatrick int StageDiff = (StageScheduled - LoopValStage);
51709467b48Spatrick LVNumStages -= StageDiff;
51809467b48Spatrick // Make sure the loop value Phi has been processed already.
51909467b48Spatrick if (LVNumStages > (int)np && VRMap[CurStageNum].count(LoopVal)) {
52009467b48Spatrick NewReg = PhiOp2;
52109467b48Spatrick unsigned ReuseStage = CurStageNum;
52209467b48Spatrick if (isLoopCarried(*PhiInst))
52309467b48Spatrick ReuseStage -= LVNumStages;
52409467b48Spatrick // Check if the Phi to reuse has been generated yet. If not, then
52509467b48Spatrick // there is nothing to reuse.
52609467b48Spatrick if (VRMap[ReuseStage - np].count(LoopVal)) {
52709467b48Spatrick NewReg = VRMap[ReuseStage - np][LoopVal];
52809467b48Spatrick
52909467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
53009467b48Spatrick Def, NewReg);
53109467b48Spatrick // Update the map with the new Phi name.
53209467b48Spatrick VRMap[CurStageNum - np][Def] = NewReg;
53309467b48Spatrick PhiOp2 = NewReg;
53409467b48Spatrick if (VRMap[LastStageNum - np - 1].count(LoopVal))
53509467b48Spatrick PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];
53609467b48Spatrick
53709467b48Spatrick if (IsLast && np == NumPhis - 1)
53809467b48Spatrick replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
53909467b48Spatrick continue;
54009467b48Spatrick }
54109467b48Spatrick }
54209467b48Spatrick }
54309467b48Spatrick if (InKernel && StageDiff > 0 &&
54409467b48Spatrick VRMap[CurStageNum - StageDiff - np].count(LoopVal))
54509467b48Spatrick PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];
54609467b48Spatrick }
54709467b48Spatrick
54809467b48Spatrick const TargetRegisterClass *RC = MRI.getRegClass(Def);
54909467b48Spatrick NewReg = MRI.createVirtualRegister(RC);
55009467b48Spatrick
55109467b48Spatrick MachineInstrBuilder NewPhi =
55209467b48Spatrick BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(),
55309467b48Spatrick TII->get(TargetOpcode::PHI), NewReg);
55409467b48Spatrick NewPhi.addReg(PhiOp1).addMBB(BB1);
55509467b48Spatrick NewPhi.addReg(PhiOp2).addMBB(BB2);
55609467b48Spatrick if (np == 0)
55709467b48Spatrick InstrMap[NewPhi] = &*BBI;
55809467b48Spatrick
55909467b48Spatrick // We define the Phis after creating the new pipelined code, so
56009467b48Spatrick // we need to rename the Phi values in scheduled instructions.
56109467b48Spatrick
56209467b48Spatrick unsigned PrevReg = 0;
56309467b48Spatrick if (InKernel && VRMap[PrevStage - np].count(LoopVal))
56409467b48Spatrick PrevReg = VRMap[PrevStage - np][LoopVal];
56509467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,
56609467b48Spatrick NewReg, PrevReg);
56709467b48Spatrick // If the Phi has been scheduled, use the new name for rewriting.
56809467b48Spatrick if (VRMap[CurStageNum - np].count(Def)) {
56909467b48Spatrick unsigned R = VRMap[CurStageNum - np][Def];
57009467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, R,
57109467b48Spatrick NewReg);
57209467b48Spatrick }
57309467b48Spatrick
57409467b48Spatrick // Check if we need to rename any uses that occurs after the loop. The
57509467b48Spatrick // register to replace depends on whether the Phi is scheduled in the
57609467b48Spatrick // epilog.
57709467b48Spatrick if (IsLast && np == NumPhis - 1)
57809467b48Spatrick replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
57909467b48Spatrick
58009467b48Spatrick // In the kernel, a dependent Phi uses the value from this Phi.
58109467b48Spatrick if (InKernel)
58209467b48Spatrick PhiOp2 = NewReg;
58309467b48Spatrick
58409467b48Spatrick // Update the map with the new Phi name.
58509467b48Spatrick VRMap[CurStageNum - np][Def] = NewReg;
58609467b48Spatrick }
58709467b48Spatrick
58809467b48Spatrick while (NumPhis++ < NumStages) {
58909467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, NumPhis, &*BBI, Def,
59009467b48Spatrick NewReg, 0);
59109467b48Spatrick }
59209467b48Spatrick
59309467b48Spatrick // Check if we need to rename a Phi that has been eliminated due to
59409467b48Spatrick // scheduling.
59509467b48Spatrick if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal))
59609467b48Spatrick replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS);
59709467b48Spatrick }
59809467b48Spatrick }
59909467b48Spatrick
60009467b48Spatrick /// Generate Phis for the specified block in the generated pipelined code.
60109467b48Spatrick /// These are new Phis needed because the definition is scheduled after the
60209467b48Spatrick /// use in the pipelined sequence.
generatePhis(MachineBasicBlock * NewBB,MachineBasicBlock * BB1,MachineBasicBlock * BB2,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,ValueMapTy * VRMapPhi,InstrMapTy & InstrMap,unsigned LastStageNum,unsigned CurStageNum,bool IsLast)60309467b48Spatrick void ModuloScheduleExpander::generatePhis(
60409467b48Spatrick MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
605*d415bd75Srobert MachineBasicBlock *KernelBB, ValueMapTy *VRMap, ValueMapTy *VRMapPhi,
606*d415bd75Srobert InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum,
607*d415bd75Srobert bool IsLast) {
60809467b48Spatrick // Compute the stage number that contains the initial Phi value, and
60909467b48Spatrick // the Phi from the previous stage.
61009467b48Spatrick unsigned PrologStage = 0;
61109467b48Spatrick unsigned PrevStage = 0;
61209467b48Spatrick unsigned StageDiff = CurStageNum - LastStageNum;
61309467b48Spatrick bool InKernel = (StageDiff == 0);
61409467b48Spatrick if (InKernel) {
61509467b48Spatrick PrologStage = LastStageNum - 1;
61609467b48Spatrick PrevStage = CurStageNum;
61709467b48Spatrick } else {
61809467b48Spatrick PrologStage = LastStageNum - StageDiff;
61909467b48Spatrick PrevStage = LastStageNum + StageDiff - 1;
62009467b48Spatrick }
62109467b48Spatrick
62209467b48Spatrick for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(),
62309467b48Spatrick BBE = BB->instr_end();
62409467b48Spatrick BBI != BBE; ++BBI) {
62509467b48Spatrick for (unsigned i = 0, e = BBI->getNumOperands(); i != e; ++i) {
62609467b48Spatrick MachineOperand &MO = BBI->getOperand(i);
627*d415bd75Srobert if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
62809467b48Spatrick continue;
62909467b48Spatrick
63009467b48Spatrick int StageScheduled = Schedule.getStage(&*BBI);
63109467b48Spatrick assert(StageScheduled != -1 && "Expecting scheduled instruction.");
63209467b48Spatrick Register Def = MO.getReg();
63309467b48Spatrick unsigned NumPhis = getStagesForReg(Def, CurStageNum);
63409467b48Spatrick // An instruction scheduled in stage 0 and is used after the loop
63509467b48Spatrick // requires a phi in the epilog for the last definition from either
63609467b48Spatrick // the kernel or prolog.
63709467b48Spatrick if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&
63809467b48Spatrick hasUseAfterLoop(Def, BB, MRI))
63909467b48Spatrick NumPhis = 1;
64009467b48Spatrick if (!InKernel && (unsigned)StageScheduled > PrologStage)
64109467b48Spatrick continue;
64209467b48Spatrick
643*d415bd75Srobert unsigned PhiOp2;
644*d415bd75Srobert if (InKernel) {
645*d415bd75Srobert PhiOp2 = VRMap[PrevStage][Def];
64609467b48Spatrick if (MachineInstr *InstOp2 = MRI.getVRegDef(PhiOp2))
64709467b48Spatrick if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)
64809467b48Spatrick PhiOp2 = getLoopPhiReg(*InstOp2, BB2);
649*d415bd75Srobert }
65009467b48Spatrick // The number of Phis can't exceed the number of prolog stages. The
65109467b48Spatrick // prolog stage number is zero based.
65209467b48Spatrick if (NumPhis > PrologStage + 1 - StageScheduled)
65309467b48Spatrick NumPhis = PrologStage + 1 - StageScheduled;
65409467b48Spatrick for (unsigned np = 0; np < NumPhis; ++np) {
655*d415bd75Srobert // Example for
656*d415bd75Srobert // Org:
657*d415bd75Srobert // %Org = ... (Scheduled at Stage#0, NumPhi = 2)
658*d415bd75Srobert //
659*d415bd75Srobert // Prolog0 (Stage0):
660*d415bd75Srobert // %Clone0 = ...
661*d415bd75Srobert // Prolog1 (Stage1):
662*d415bd75Srobert // %Clone1 = ...
663*d415bd75Srobert // Kernel (Stage2):
664*d415bd75Srobert // %Phi0 = Phi %Clone1, Prolog1, %Clone2, Kernel
665*d415bd75Srobert // %Phi1 = Phi %Clone0, Prolog1, %Phi0, Kernel
666*d415bd75Srobert // %Clone2 = ...
667*d415bd75Srobert // Epilog0 (Stage3):
668*d415bd75Srobert // %Phi2 = Phi %Clone1, Prolog1, %Clone2, Kernel
669*d415bd75Srobert // %Phi3 = Phi %Clone0, Prolog1, %Phi0, Kernel
670*d415bd75Srobert // Epilog1 (Stage4):
671*d415bd75Srobert // %Phi4 = Phi %Clone0, Prolog0, %Phi2, Epilog0
672*d415bd75Srobert //
673*d415bd75Srobert // VRMap = {0: %Clone0, 1: %Clone1, 2: %Clone2}
674*d415bd75Srobert // VRMapPhi (after Kernel) = {0: %Phi1, 1: %Phi0}
675*d415bd75Srobert // VRMapPhi (after Epilog0) = {0: %Phi3, 1: %Phi2}
676*d415bd75Srobert
67709467b48Spatrick unsigned PhiOp1 = VRMap[PrologStage][Def];
67809467b48Spatrick if (np <= PrologStage)
67909467b48Spatrick PhiOp1 = VRMap[PrologStage - np][Def];
680*d415bd75Srobert if (!InKernel) {
681*d415bd75Srobert if (PrevStage == LastStageNum && np == 0)
682*d415bd75Srobert PhiOp2 = VRMap[LastStageNum][Def];
683*d415bd75Srobert else
684*d415bd75Srobert PhiOp2 = VRMapPhi[PrevStage - np][Def];
68509467b48Spatrick }
68609467b48Spatrick
68709467b48Spatrick const TargetRegisterClass *RC = MRI.getRegClass(Def);
68809467b48Spatrick Register NewReg = MRI.createVirtualRegister(RC);
68909467b48Spatrick
69009467b48Spatrick MachineInstrBuilder NewPhi =
69109467b48Spatrick BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(),
69209467b48Spatrick TII->get(TargetOpcode::PHI), NewReg);
69309467b48Spatrick NewPhi.addReg(PhiOp1).addMBB(BB1);
69409467b48Spatrick NewPhi.addReg(PhiOp2).addMBB(BB2);
69509467b48Spatrick if (np == 0)
69609467b48Spatrick InstrMap[NewPhi] = &*BBI;
69709467b48Spatrick
69809467b48Spatrick // Rewrite uses and update the map. The actions depend upon whether
69909467b48Spatrick // we generating code for the kernel or epilog blocks.
70009467b48Spatrick if (InKernel) {
70109467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp1,
70209467b48Spatrick NewReg);
70309467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp2,
70409467b48Spatrick NewReg);
70509467b48Spatrick
70609467b48Spatrick PhiOp2 = NewReg;
707*d415bd75Srobert VRMapPhi[PrevStage - np - 1][Def] = NewReg;
70809467b48Spatrick } else {
709*d415bd75Srobert VRMapPhi[CurStageNum - np][Def] = NewReg;
71009467b48Spatrick if (np == NumPhis - 1)
71109467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,
71209467b48Spatrick NewReg);
71309467b48Spatrick }
71409467b48Spatrick if (IsLast && np == NumPhis - 1)
71509467b48Spatrick replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
71609467b48Spatrick }
71709467b48Spatrick }
71809467b48Spatrick }
71909467b48Spatrick }
72009467b48Spatrick
72109467b48Spatrick /// Remove instructions that generate values with no uses.
72209467b48Spatrick /// Typically, these are induction variable operations that generate values
72309467b48Spatrick /// used in the loop itself. A dead instruction has a definition with
72409467b48Spatrick /// no uses, or uses that occur in the original loop only.
removeDeadInstructions(MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs)72509467b48Spatrick void ModuloScheduleExpander::removeDeadInstructions(MachineBasicBlock *KernelBB,
72609467b48Spatrick MBBVectorTy &EpilogBBs) {
72709467b48Spatrick // For each epilog block, check that the value defined by each instruction
72809467b48Spatrick // is used. If not, delete it.
729*d415bd75Srobert for (MachineBasicBlock *MBB : llvm::reverse(EpilogBBs))
730*d415bd75Srobert for (MachineBasicBlock::reverse_instr_iterator MI = MBB->instr_rbegin(),
731*d415bd75Srobert ME = MBB->instr_rend();
73209467b48Spatrick MI != ME;) {
73309467b48Spatrick // From DeadMachineInstructionElem. Don't delete inline assembly.
73409467b48Spatrick if (MI->isInlineAsm()) {
73509467b48Spatrick ++MI;
73609467b48Spatrick continue;
73709467b48Spatrick }
73809467b48Spatrick bool SawStore = false;
73909467b48Spatrick // Check if it's safe to remove the instruction due to side effects.
74009467b48Spatrick // We can, and want to, remove Phis here.
74109467b48Spatrick if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI()) {
74209467b48Spatrick ++MI;
74309467b48Spatrick continue;
74409467b48Spatrick }
74509467b48Spatrick bool used = true;
746*d415bd75Srobert for (const MachineOperand &MO : MI->operands()) {
747*d415bd75Srobert if (!MO.isReg() || !MO.isDef())
74809467b48Spatrick continue;
749*d415bd75Srobert Register reg = MO.getReg();
75009467b48Spatrick // Assume physical registers are used, unless they are marked dead.
751*d415bd75Srobert if (reg.isPhysical()) {
752*d415bd75Srobert used = !MO.isDead();
75309467b48Spatrick if (used)
75409467b48Spatrick break;
75509467b48Spatrick continue;
75609467b48Spatrick }
75709467b48Spatrick unsigned realUses = 0;
758*d415bd75Srobert for (const MachineOperand &U : MRI.use_operands(reg)) {
75909467b48Spatrick // Check if there are any uses that occur only in the original
76009467b48Spatrick // loop. If so, that's not a real use.
761*d415bd75Srobert if (U.getParent()->getParent() != BB) {
76209467b48Spatrick realUses++;
76309467b48Spatrick used = true;
76409467b48Spatrick break;
76509467b48Spatrick }
76609467b48Spatrick }
76709467b48Spatrick if (realUses > 0)
76809467b48Spatrick break;
76909467b48Spatrick used = false;
77009467b48Spatrick }
77109467b48Spatrick if (!used) {
77209467b48Spatrick LIS.RemoveMachineInstrFromMaps(*MI);
77309467b48Spatrick MI++->eraseFromParent();
77409467b48Spatrick continue;
77509467b48Spatrick }
77609467b48Spatrick ++MI;
77709467b48Spatrick }
77809467b48Spatrick // In the kernel block, check if we can remove a Phi that generates a value
77909467b48Spatrick // used in an instruction removed in the epilog block.
780*d415bd75Srobert for (MachineInstr &MI : llvm::make_early_inc_range(KernelBB->phis())) {
781*d415bd75Srobert Register reg = MI.getOperand(0).getReg();
78209467b48Spatrick if (MRI.use_begin(reg) == MRI.use_end()) {
783*d415bd75Srobert LIS.RemoveMachineInstrFromMaps(MI);
784*d415bd75Srobert MI.eraseFromParent();
78509467b48Spatrick }
78609467b48Spatrick }
78709467b48Spatrick }
78809467b48Spatrick
78909467b48Spatrick /// For loop carried definitions, we split the lifetime of a virtual register
79009467b48Spatrick /// that has uses past the definition in the next iteration. A copy with a new
79109467b48Spatrick /// virtual register is inserted before the definition, which helps with
79209467b48Spatrick /// generating a better register assignment.
79309467b48Spatrick ///
79409467b48Spatrick /// v1 = phi(a, v2) v1 = phi(a, v2)
79509467b48Spatrick /// v2 = phi(b, v3) v2 = phi(b, v3)
79609467b48Spatrick /// v3 = .. v4 = copy v1
79709467b48Spatrick /// .. = V1 v3 = ..
79809467b48Spatrick /// .. = v4
splitLifetimes(MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs)79909467b48Spatrick void ModuloScheduleExpander::splitLifetimes(MachineBasicBlock *KernelBB,
80009467b48Spatrick MBBVectorTy &EpilogBBs) {
80109467b48Spatrick const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
80209467b48Spatrick for (auto &PHI : KernelBB->phis()) {
80309467b48Spatrick Register Def = PHI.getOperand(0).getReg();
80409467b48Spatrick // Check for any Phi definition that used as an operand of another Phi
80509467b48Spatrick // in the same block.
80609467b48Spatrick for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(Def),
80709467b48Spatrick E = MRI.use_instr_end();
80809467b48Spatrick I != E; ++I) {
80909467b48Spatrick if (I->isPHI() && I->getParent() == KernelBB) {
81009467b48Spatrick // Get the loop carried definition.
81109467b48Spatrick unsigned LCDef = getLoopPhiReg(PHI, KernelBB);
81209467b48Spatrick if (!LCDef)
81309467b48Spatrick continue;
81409467b48Spatrick MachineInstr *MI = MRI.getVRegDef(LCDef);
81509467b48Spatrick if (!MI || MI->getParent() != KernelBB || MI->isPHI())
81609467b48Spatrick continue;
81709467b48Spatrick // Search through the rest of the block looking for uses of the Phi
81809467b48Spatrick // definition. If one occurs, then split the lifetime.
81909467b48Spatrick unsigned SplitReg = 0;
82009467b48Spatrick for (auto &BBJ : make_range(MachineBasicBlock::instr_iterator(MI),
82109467b48Spatrick KernelBB->instr_end()))
82209467b48Spatrick if (BBJ.readsRegister(Def)) {
82309467b48Spatrick // We split the lifetime when we find the first use.
82409467b48Spatrick if (SplitReg == 0) {
82509467b48Spatrick SplitReg = MRI.createVirtualRegister(MRI.getRegClass(Def));
82609467b48Spatrick BuildMI(*KernelBB, MI, MI->getDebugLoc(),
82709467b48Spatrick TII->get(TargetOpcode::COPY), SplitReg)
82809467b48Spatrick .addReg(Def);
82909467b48Spatrick }
83009467b48Spatrick BBJ.substituteRegister(Def, SplitReg, 0, *TRI);
83109467b48Spatrick }
83209467b48Spatrick if (!SplitReg)
83309467b48Spatrick continue;
83409467b48Spatrick // Search through each of the epilog blocks for any uses to be renamed.
83509467b48Spatrick for (auto &Epilog : EpilogBBs)
83609467b48Spatrick for (auto &I : *Epilog)
83709467b48Spatrick if (I.readsRegister(Def))
83809467b48Spatrick I.substituteRegister(Def, SplitReg, 0, *TRI);
83909467b48Spatrick break;
84009467b48Spatrick }
84109467b48Spatrick }
84209467b48Spatrick }
84309467b48Spatrick }
84409467b48Spatrick
84509467b48Spatrick /// Remove the incoming block from the Phis in a basic block.
removePhis(MachineBasicBlock * BB,MachineBasicBlock * Incoming)84609467b48Spatrick static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming) {
84709467b48Spatrick for (MachineInstr &MI : *BB) {
84809467b48Spatrick if (!MI.isPHI())
84909467b48Spatrick break;
85009467b48Spatrick for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2)
85109467b48Spatrick if (MI.getOperand(i + 1).getMBB() == Incoming) {
852*d415bd75Srobert MI.removeOperand(i + 1);
853*d415bd75Srobert MI.removeOperand(i);
85409467b48Spatrick break;
85509467b48Spatrick }
85609467b48Spatrick }
85709467b48Spatrick }
85809467b48Spatrick
85909467b48Spatrick /// Create branches from each prolog basic block to the appropriate epilog
86009467b48Spatrick /// block. These edges are needed if the loop ends before reaching the
86109467b48Spatrick /// kernel.
addBranches(MachineBasicBlock & PreheaderBB,MBBVectorTy & PrologBBs,MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs,ValueMapTy * VRMap)86209467b48Spatrick void ModuloScheduleExpander::addBranches(MachineBasicBlock &PreheaderBB,
86309467b48Spatrick MBBVectorTy &PrologBBs,
86409467b48Spatrick MachineBasicBlock *KernelBB,
86509467b48Spatrick MBBVectorTy &EpilogBBs,
86609467b48Spatrick ValueMapTy *VRMap) {
86709467b48Spatrick assert(PrologBBs.size() == EpilogBBs.size() && "Prolog/Epilog mismatch");
86809467b48Spatrick MachineBasicBlock *LastPro = KernelBB;
86909467b48Spatrick MachineBasicBlock *LastEpi = KernelBB;
87009467b48Spatrick
87109467b48Spatrick // Start from the blocks connected to the kernel and work "out"
87209467b48Spatrick // to the first prolog and the last epilog blocks.
87309467b48Spatrick SmallVector<MachineInstr *, 4> PrevInsts;
87409467b48Spatrick unsigned MaxIter = PrologBBs.size() - 1;
87509467b48Spatrick for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) {
87609467b48Spatrick // Add branches to the prolog that go to the corresponding
87709467b48Spatrick // epilog, and the fall-thru prolog/kernel block.
87809467b48Spatrick MachineBasicBlock *Prolog = PrologBBs[j];
87909467b48Spatrick MachineBasicBlock *Epilog = EpilogBBs[i];
88009467b48Spatrick
88109467b48Spatrick SmallVector<MachineOperand, 4> Cond;
882*d415bd75Srobert std::optional<bool> StaticallyGreater =
88309467b48Spatrick LoopInfo->createTripCountGreaterCondition(j + 1, *Prolog, Cond);
88409467b48Spatrick unsigned numAdded = 0;
885*d415bd75Srobert if (!StaticallyGreater) {
88609467b48Spatrick Prolog->addSuccessor(Epilog);
88709467b48Spatrick numAdded = TII->insertBranch(*Prolog, Epilog, LastPro, Cond, DebugLoc());
88809467b48Spatrick } else if (*StaticallyGreater == false) {
88909467b48Spatrick Prolog->addSuccessor(Epilog);
89009467b48Spatrick Prolog->removeSuccessor(LastPro);
89109467b48Spatrick LastEpi->removeSuccessor(Epilog);
89209467b48Spatrick numAdded = TII->insertBranch(*Prolog, Epilog, nullptr, Cond, DebugLoc());
89309467b48Spatrick removePhis(Epilog, LastEpi);
89409467b48Spatrick // Remove the blocks that are no longer referenced.
89509467b48Spatrick if (LastPro != LastEpi) {
89609467b48Spatrick LastEpi->clear();
89709467b48Spatrick LastEpi->eraseFromParent();
89809467b48Spatrick }
89909467b48Spatrick if (LastPro == KernelBB) {
90009467b48Spatrick LoopInfo->disposed();
90109467b48Spatrick NewKernel = nullptr;
90209467b48Spatrick }
90309467b48Spatrick LastPro->clear();
90409467b48Spatrick LastPro->eraseFromParent();
90509467b48Spatrick } else {
90609467b48Spatrick numAdded = TII->insertBranch(*Prolog, LastPro, nullptr, Cond, DebugLoc());
90709467b48Spatrick removePhis(Epilog, Prolog);
90809467b48Spatrick }
90909467b48Spatrick LastPro = Prolog;
91009467b48Spatrick LastEpi = Epilog;
91109467b48Spatrick for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(),
91209467b48Spatrick E = Prolog->instr_rend();
91309467b48Spatrick I != E && numAdded > 0; ++I, --numAdded)
91409467b48Spatrick updateInstruction(&*I, false, j, 0, VRMap);
91509467b48Spatrick }
91609467b48Spatrick
91709467b48Spatrick if (NewKernel) {
91809467b48Spatrick LoopInfo->setPreheader(PrologBBs[MaxIter]);
91909467b48Spatrick LoopInfo->adjustTripCount(-(MaxIter + 1));
92009467b48Spatrick }
92109467b48Spatrick }
92209467b48Spatrick
92309467b48Spatrick /// Return true if we can compute the amount the instruction changes
92409467b48Spatrick /// during each iteration. Set Delta to the amount of the change.
computeDelta(MachineInstr & MI,unsigned & Delta)92509467b48Spatrick bool ModuloScheduleExpander::computeDelta(MachineInstr &MI, unsigned &Delta) {
92609467b48Spatrick const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
92709467b48Spatrick const MachineOperand *BaseOp;
92809467b48Spatrick int64_t Offset;
929097a140dSpatrick bool OffsetIsScalable;
930097a140dSpatrick if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
931097a140dSpatrick return false;
932097a140dSpatrick
933097a140dSpatrick // FIXME: This algorithm assumes instructions have fixed-size offsets.
934097a140dSpatrick if (OffsetIsScalable)
93509467b48Spatrick return false;
93609467b48Spatrick
93709467b48Spatrick if (!BaseOp->isReg())
93809467b48Spatrick return false;
93909467b48Spatrick
94009467b48Spatrick Register BaseReg = BaseOp->getReg();
94109467b48Spatrick
94209467b48Spatrick MachineRegisterInfo &MRI = MF.getRegInfo();
94309467b48Spatrick // Check if there is a Phi. If so, get the definition in the loop.
94409467b48Spatrick MachineInstr *BaseDef = MRI.getVRegDef(BaseReg);
94509467b48Spatrick if (BaseDef && BaseDef->isPHI()) {
94609467b48Spatrick BaseReg = getLoopPhiReg(*BaseDef, MI.getParent());
94709467b48Spatrick BaseDef = MRI.getVRegDef(BaseReg);
94809467b48Spatrick }
94909467b48Spatrick if (!BaseDef)
95009467b48Spatrick return false;
95109467b48Spatrick
95209467b48Spatrick int D = 0;
95309467b48Spatrick if (!TII->getIncrementValue(*BaseDef, D) && D >= 0)
95409467b48Spatrick return false;
95509467b48Spatrick
95609467b48Spatrick Delta = D;
95709467b48Spatrick return true;
95809467b48Spatrick }
95909467b48Spatrick
96009467b48Spatrick /// Update the memory operand with a new offset when the pipeliner
96109467b48Spatrick /// generates a new copy of the instruction that refers to a
96209467b48Spatrick /// different memory location.
updateMemOperands(MachineInstr & NewMI,MachineInstr & OldMI,unsigned Num)96309467b48Spatrick void ModuloScheduleExpander::updateMemOperands(MachineInstr &NewMI,
96409467b48Spatrick MachineInstr &OldMI,
96509467b48Spatrick unsigned Num) {
96609467b48Spatrick if (Num == 0)
96709467b48Spatrick return;
96809467b48Spatrick // If the instruction has memory operands, then adjust the offset
96909467b48Spatrick // when the instruction appears in different stages.
97009467b48Spatrick if (NewMI.memoperands_empty())
97109467b48Spatrick return;
97209467b48Spatrick SmallVector<MachineMemOperand *, 2> NewMMOs;
97309467b48Spatrick for (MachineMemOperand *MMO : NewMI.memoperands()) {
97409467b48Spatrick // TODO: Figure out whether isAtomic is really necessary (see D57601).
97509467b48Spatrick if (MMO->isVolatile() || MMO->isAtomic() ||
97609467b48Spatrick (MMO->isInvariant() && MMO->isDereferenceable()) ||
97709467b48Spatrick (!MMO->getValue())) {
97809467b48Spatrick NewMMOs.push_back(MMO);
97909467b48Spatrick continue;
98009467b48Spatrick }
98109467b48Spatrick unsigned Delta;
98209467b48Spatrick if (Num != UINT_MAX && computeDelta(OldMI, Delta)) {
98309467b48Spatrick int64_t AdjOffset = Delta * Num;
98409467b48Spatrick NewMMOs.push_back(
98509467b48Spatrick MF.getMachineMemOperand(MMO, AdjOffset, MMO->getSize()));
98609467b48Spatrick } else {
98709467b48Spatrick NewMMOs.push_back(
98809467b48Spatrick MF.getMachineMemOperand(MMO, 0, MemoryLocation::UnknownSize));
98909467b48Spatrick }
99009467b48Spatrick }
99109467b48Spatrick NewMI.setMemRefs(MF, NewMMOs);
99209467b48Spatrick }
99309467b48Spatrick
99409467b48Spatrick /// Clone the instruction for the new pipelined loop and update the
99509467b48Spatrick /// memory operands, if needed.
cloneInstr(MachineInstr * OldMI,unsigned CurStageNum,unsigned InstStageNum)99609467b48Spatrick MachineInstr *ModuloScheduleExpander::cloneInstr(MachineInstr *OldMI,
99709467b48Spatrick unsigned CurStageNum,
99809467b48Spatrick unsigned InstStageNum) {
99909467b48Spatrick MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);
100009467b48Spatrick updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
100109467b48Spatrick return NewMI;
100209467b48Spatrick }
100309467b48Spatrick
100409467b48Spatrick /// Clone the instruction for the new pipelined loop. If needed, this
100509467b48Spatrick /// function updates the instruction using the values saved in the
100609467b48Spatrick /// InstrChanges structure.
cloneAndChangeInstr(MachineInstr * OldMI,unsigned CurStageNum,unsigned InstStageNum)100709467b48Spatrick MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
100809467b48Spatrick MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum) {
100909467b48Spatrick MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);
101009467b48Spatrick auto It = InstrChanges.find(OldMI);
101109467b48Spatrick if (It != InstrChanges.end()) {
101209467b48Spatrick std::pair<unsigned, int64_t> RegAndOffset = It->second;
101309467b48Spatrick unsigned BasePos, OffsetPos;
101409467b48Spatrick if (!TII->getBaseAndOffsetPosition(*OldMI, BasePos, OffsetPos))
101509467b48Spatrick return nullptr;
101609467b48Spatrick int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm();
101709467b48Spatrick MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first);
101809467b48Spatrick if (Schedule.getStage(LoopDef) > (signed)InstStageNum)
101909467b48Spatrick NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
102009467b48Spatrick NewMI->getOperand(OffsetPos).setImm(NewOffset);
102109467b48Spatrick }
102209467b48Spatrick updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
102309467b48Spatrick return NewMI;
102409467b48Spatrick }
102509467b48Spatrick
102609467b48Spatrick /// Update the machine instruction with new virtual registers. This
1027*d415bd75Srobert /// function may change the definitions and/or uses.
updateInstruction(MachineInstr * NewMI,bool LastDef,unsigned CurStageNum,unsigned InstrStageNum,ValueMapTy * VRMap)102809467b48Spatrick void ModuloScheduleExpander::updateInstruction(MachineInstr *NewMI,
102909467b48Spatrick bool LastDef,
103009467b48Spatrick unsigned CurStageNum,
103109467b48Spatrick unsigned InstrStageNum,
103209467b48Spatrick ValueMapTy *VRMap) {
1033*d415bd75Srobert for (MachineOperand &MO : NewMI->operands()) {
1034*d415bd75Srobert if (!MO.isReg() || !MO.getReg().isVirtual())
103509467b48Spatrick continue;
103609467b48Spatrick Register reg = MO.getReg();
103709467b48Spatrick if (MO.isDef()) {
103809467b48Spatrick // Create a new virtual register for the definition.
103909467b48Spatrick const TargetRegisterClass *RC = MRI.getRegClass(reg);
104009467b48Spatrick Register NewReg = MRI.createVirtualRegister(RC);
104109467b48Spatrick MO.setReg(NewReg);
104209467b48Spatrick VRMap[CurStageNum][reg] = NewReg;
104309467b48Spatrick if (LastDef)
104409467b48Spatrick replaceRegUsesAfterLoop(reg, NewReg, BB, MRI, LIS);
104509467b48Spatrick } else if (MO.isUse()) {
104609467b48Spatrick MachineInstr *Def = MRI.getVRegDef(reg);
104709467b48Spatrick // Compute the stage that contains the last definition for instruction.
104809467b48Spatrick int DefStageNum = Schedule.getStage(Def);
104909467b48Spatrick unsigned StageNum = CurStageNum;
105009467b48Spatrick if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) {
105109467b48Spatrick // Compute the difference in stages between the defintion and the use.
105209467b48Spatrick unsigned StageDiff = (InstrStageNum - DefStageNum);
105309467b48Spatrick // Make an adjustment to get the last definition.
105409467b48Spatrick StageNum -= StageDiff;
105509467b48Spatrick }
105609467b48Spatrick if (VRMap[StageNum].count(reg))
105709467b48Spatrick MO.setReg(VRMap[StageNum][reg]);
105809467b48Spatrick }
105909467b48Spatrick }
106009467b48Spatrick }
106109467b48Spatrick
106209467b48Spatrick /// Return the instruction in the loop that defines the register.
106309467b48Spatrick /// If the definition is a Phi, then follow the Phi operand to
106409467b48Spatrick /// the instruction in the loop.
findDefInLoop(unsigned Reg)106509467b48Spatrick MachineInstr *ModuloScheduleExpander::findDefInLoop(unsigned Reg) {
106609467b48Spatrick SmallPtrSet<MachineInstr *, 8> Visited;
106709467b48Spatrick MachineInstr *Def = MRI.getVRegDef(Reg);
106809467b48Spatrick while (Def->isPHI()) {
106909467b48Spatrick if (!Visited.insert(Def).second)
107009467b48Spatrick break;
107109467b48Spatrick for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
107209467b48Spatrick if (Def->getOperand(i + 1).getMBB() == BB) {
107309467b48Spatrick Def = MRI.getVRegDef(Def->getOperand(i).getReg());
107409467b48Spatrick break;
107509467b48Spatrick }
107609467b48Spatrick }
107709467b48Spatrick return Def;
107809467b48Spatrick }
107909467b48Spatrick
108009467b48Spatrick /// Return the new name for the value from the previous stage.
getPrevMapVal(unsigned StageNum,unsigned PhiStage,unsigned LoopVal,unsigned LoopStage,ValueMapTy * VRMap,MachineBasicBlock * BB)108109467b48Spatrick unsigned ModuloScheduleExpander::getPrevMapVal(
108209467b48Spatrick unsigned StageNum, unsigned PhiStage, unsigned LoopVal, unsigned LoopStage,
108309467b48Spatrick ValueMapTy *VRMap, MachineBasicBlock *BB) {
108409467b48Spatrick unsigned PrevVal = 0;
108509467b48Spatrick if (StageNum > PhiStage) {
108609467b48Spatrick MachineInstr *LoopInst = MRI.getVRegDef(LoopVal);
108709467b48Spatrick if (PhiStage == LoopStage && VRMap[StageNum - 1].count(LoopVal))
108809467b48Spatrick // The name is defined in the previous stage.
108909467b48Spatrick PrevVal = VRMap[StageNum - 1][LoopVal];
109009467b48Spatrick else if (VRMap[StageNum].count(LoopVal))
109109467b48Spatrick // The previous name is defined in the current stage when the instruction
109209467b48Spatrick // order is swapped.
109309467b48Spatrick PrevVal = VRMap[StageNum][LoopVal];
109409467b48Spatrick else if (!LoopInst->isPHI() || LoopInst->getParent() != BB)
109509467b48Spatrick // The loop value hasn't yet been scheduled.
109609467b48Spatrick PrevVal = LoopVal;
109709467b48Spatrick else if (StageNum == PhiStage + 1)
109809467b48Spatrick // The loop value is another phi, which has not been scheduled.
109909467b48Spatrick PrevVal = getInitPhiReg(*LoopInst, BB);
110009467b48Spatrick else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB)
110109467b48Spatrick // The loop value is another phi, which has been scheduled.
110209467b48Spatrick PrevVal =
110309467b48Spatrick getPrevMapVal(StageNum - 1, PhiStage, getLoopPhiReg(*LoopInst, BB),
110409467b48Spatrick LoopStage, VRMap, BB);
110509467b48Spatrick }
110609467b48Spatrick return PrevVal;
110709467b48Spatrick }
110809467b48Spatrick
110909467b48Spatrick /// Rewrite the Phi values in the specified block to use the mappings
111009467b48Spatrick /// from the initial operand. Once the Phi is scheduled, we switch
111109467b48Spatrick /// to using the loop value instead of the Phi value, so those names
111209467b48Spatrick /// do not need to be rewritten.
rewritePhiValues(MachineBasicBlock * NewBB,unsigned StageNum,ValueMapTy * VRMap,InstrMapTy & InstrMap)111309467b48Spatrick void ModuloScheduleExpander::rewritePhiValues(MachineBasicBlock *NewBB,
111409467b48Spatrick unsigned StageNum,
111509467b48Spatrick ValueMapTy *VRMap,
111609467b48Spatrick InstrMapTy &InstrMap) {
111709467b48Spatrick for (auto &PHI : BB->phis()) {
111809467b48Spatrick unsigned InitVal = 0;
111909467b48Spatrick unsigned LoopVal = 0;
112009467b48Spatrick getPhiRegs(PHI, BB, InitVal, LoopVal);
112109467b48Spatrick Register PhiDef = PHI.getOperand(0).getReg();
112209467b48Spatrick
112309467b48Spatrick unsigned PhiStage = (unsigned)Schedule.getStage(MRI.getVRegDef(PhiDef));
112409467b48Spatrick unsigned LoopStage = (unsigned)Schedule.getStage(MRI.getVRegDef(LoopVal));
112509467b48Spatrick unsigned NumPhis = getStagesForPhi(PhiDef);
112609467b48Spatrick if (NumPhis > StageNum)
112709467b48Spatrick NumPhis = StageNum;
112809467b48Spatrick for (unsigned np = 0; np <= NumPhis; ++np) {
112909467b48Spatrick unsigned NewVal =
113009467b48Spatrick getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
113109467b48Spatrick if (!NewVal)
113209467b48Spatrick NewVal = InitVal;
113309467b48Spatrick rewriteScheduledInstr(NewBB, InstrMap, StageNum - np, np, &PHI, PhiDef,
113409467b48Spatrick NewVal);
113509467b48Spatrick }
113609467b48Spatrick }
113709467b48Spatrick }
113809467b48Spatrick
113909467b48Spatrick /// Rewrite a previously scheduled instruction to use the register value
114009467b48Spatrick /// from the new instruction. Make sure the instruction occurs in the
114109467b48Spatrick /// 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)114209467b48Spatrick void ModuloScheduleExpander::rewriteScheduledInstr(
114309467b48Spatrick MachineBasicBlock *BB, InstrMapTy &InstrMap, unsigned CurStageNum,
114409467b48Spatrick unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, unsigned NewReg,
114509467b48Spatrick unsigned PrevReg) {
114609467b48Spatrick bool InProlog = (CurStageNum < (unsigned)Schedule.getNumStages() - 1);
114709467b48Spatrick int StagePhi = Schedule.getStage(Phi) + PhiNum;
114809467b48Spatrick // Rewrite uses that have been scheduled already to use the new
114909467b48Spatrick // Phi register.
1150*d415bd75Srobert for (MachineOperand &UseOp :
1151*d415bd75Srobert llvm::make_early_inc_range(MRI.use_operands(OldReg))) {
115209467b48Spatrick MachineInstr *UseMI = UseOp.getParent();
115309467b48Spatrick if (UseMI->getParent() != BB)
115409467b48Spatrick continue;
115509467b48Spatrick if (UseMI->isPHI()) {
115609467b48Spatrick if (!Phi->isPHI() && UseMI->getOperand(0).getReg() == NewReg)
115709467b48Spatrick continue;
115809467b48Spatrick if (getLoopPhiReg(*UseMI, BB) != OldReg)
115909467b48Spatrick continue;
116009467b48Spatrick }
116109467b48Spatrick InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI);
116209467b48Spatrick assert(OrigInstr != InstrMap.end() && "Instruction not scheduled.");
116309467b48Spatrick MachineInstr *OrigMI = OrigInstr->second;
116409467b48Spatrick int StageSched = Schedule.getStage(OrigMI);
116509467b48Spatrick int CycleSched = Schedule.getCycle(OrigMI);
116609467b48Spatrick unsigned ReplaceReg = 0;
116709467b48Spatrick // This is the stage for the scheduled instruction.
116809467b48Spatrick if (StagePhi == StageSched && Phi->isPHI()) {
116909467b48Spatrick int CyclePhi = Schedule.getCycle(Phi);
117009467b48Spatrick if (PrevReg && InProlog)
117109467b48Spatrick ReplaceReg = PrevReg;
117209467b48Spatrick else if (PrevReg && !isLoopCarried(*Phi) &&
117309467b48Spatrick (CyclePhi <= CycleSched || OrigMI->isPHI()))
117409467b48Spatrick ReplaceReg = PrevReg;
117509467b48Spatrick else
117609467b48Spatrick ReplaceReg = NewReg;
117709467b48Spatrick }
117809467b48Spatrick // The scheduled instruction occurs before the scheduled Phi, and the
117909467b48Spatrick // Phi is not loop carried.
118009467b48Spatrick if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(*Phi))
118109467b48Spatrick ReplaceReg = NewReg;
118209467b48Spatrick if (StagePhi > StageSched && Phi->isPHI())
118309467b48Spatrick ReplaceReg = NewReg;
118409467b48Spatrick if (!InProlog && !Phi->isPHI() && StagePhi < StageSched)
118509467b48Spatrick ReplaceReg = NewReg;
118609467b48Spatrick if (ReplaceReg) {
1187*d415bd75Srobert const TargetRegisterClass *NRC =
118809467b48Spatrick MRI.constrainRegClass(ReplaceReg, MRI.getRegClass(OldReg));
1189*d415bd75Srobert if (NRC)
119009467b48Spatrick UseOp.setReg(ReplaceReg);
1191*d415bd75Srobert else {
1192*d415bd75Srobert Register SplitReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
1193*d415bd75Srobert BuildMI(*BB, UseMI, UseMI->getDebugLoc(), TII->get(TargetOpcode::COPY),
1194*d415bd75Srobert SplitReg)
1195*d415bd75Srobert .addReg(ReplaceReg);
1196*d415bd75Srobert UseOp.setReg(SplitReg);
1197*d415bd75Srobert }
119809467b48Spatrick }
119909467b48Spatrick }
120009467b48Spatrick }
120109467b48Spatrick
isLoopCarried(MachineInstr & Phi)120209467b48Spatrick bool ModuloScheduleExpander::isLoopCarried(MachineInstr &Phi) {
120309467b48Spatrick if (!Phi.isPHI())
120409467b48Spatrick return false;
120509467b48Spatrick int DefCycle = Schedule.getCycle(&Phi);
120609467b48Spatrick int DefStage = Schedule.getStage(&Phi);
120709467b48Spatrick
120809467b48Spatrick unsigned InitVal = 0;
120909467b48Spatrick unsigned LoopVal = 0;
121009467b48Spatrick getPhiRegs(Phi, Phi.getParent(), InitVal, LoopVal);
121109467b48Spatrick MachineInstr *Use = MRI.getVRegDef(LoopVal);
121209467b48Spatrick if (!Use || Use->isPHI())
121309467b48Spatrick return true;
121409467b48Spatrick int LoopCycle = Schedule.getCycle(Use);
121509467b48Spatrick int LoopStage = Schedule.getStage(Use);
121609467b48Spatrick return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
121709467b48Spatrick }
121809467b48Spatrick
121909467b48Spatrick //===----------------------------------------------------------------------===//
122009467b48Spatrick // PeelingModuloScheduleExpander implementation
122109467b48Spatrick //===----------------------------------------------------------------------===//
122209467b48Spatrick // This is a reimplementation of ModuloScheduleExpander that works by creating
122309467b48Spatrick // a fully correct steady-state kernel and peeling off the prolog and epilogs.
122409467b48Spatrick //===----------------------------------------------------------------------===//
122509467b48Spatrick
122609467b48Spatrick namespace {
122709467b48Spatrick // Remove any dead phis in MBB. Dead phis either have only one block as input
122809467b48Spatrick // (in which case they are the identity) or have no uses.
EliminateDeadPhis(MachineBasicBlock * MBB,MachineRegisterInfo & MRI,LiveIntervals * LIS,bool KeepSingleSrcPhi=false)122909467b48Spatrick void EliminateDeadPhis(MachineBasicBlock *MBB, MachineRegisterInfo &MRI,
123009467b48Spatrick LiveIntervals *LIS, bool KeepSingleSrcPhi = false) {
123109467b48Spatrick bool Changed = true;
123209467b48Spatrick while (Changed) {
123309467b48Spatrick Changed = false;
1234*d415bd75Srobert for (MachineInstr &MI : llvm::make_early_inc_range(MBB->phis())) {
123509467b48Spatrick assert(MI.isPHI());
123609467b48Spatrick if (MRI.use_empty(MI.getOperand(0).getReg())) {
123709467b48Spatrick if (LIS)
123809467b48Spatrick LIS->RemoveMachineInstrFromMaps(MI);
123909467b48Spatrick MI.eraseFromParent();
124009467b48Spatrick Changed = true;
124109467b48Spatrick } else if (!KeepSingleSrcPhi && MI.getNumExplicitOperands() == 3) {
1242*d415bd75Srobert const TargetRegisterClass *ConstrainRegClass =
124309467b48Spatrick MRI.constrainRegClass(MI.getOperand(1).getReg(),
124409467b48Spatrick MRI.getRegClass(MI.getOperand(0).getReg()));
1245*d415bd75Srobert assert(ConstrainRegClass &&
1246*d415bd75Srobert "Expected a valid constrained register class!");
1247*d415bd75Srobert (void)ConstrainRegClass;
124809467b48Spatrick MRI.replaceRegWith(MI.getOperand(0).getReg(),
124909467b48Spatrick MI.getOperand(1).getReg());
125009467b48Spatrick if (LIS)
125109467b48Spatrick LIS->RemoveMachineInstrFromMaps(MI);
125209467b48Spatrick MI.eraseFromParent();
125309467b48Spatrick Changed = true;
125409467b48Spatrick }
125509467b48Spatrick }
125609467b48Spatrick }
125709467b48Spatrick }
125809467b48Spatrick
125909467b48Spatrick /// Rewrites the kernel block in-place to adhere to the given schedule.
126009467b48Spatrick /// KernelRewriter holds all of the state required to perform the rewriting.
126109467b48Spatrick class KernelRewriter {
126209467b48Spatrick ModuloSchedule &S;
126309467b48Spatrick MachineBasicBlock *BB;
126409467b48Spatrick MachineBasicBlock *PreheaderBB, *ExitBB;
126509467b48Spatrick MachineRegisterInfo &MRI;
126609467b48Spatrick const TargetInstrInfo *TII;
126709467b48Spatrick LiveIntervals *LIS;
126809467b48Spatrick
126909467b48Spatrick // Map from register class to canonical undef register for that class.
127009467b48Spatrick DenseMap<const TargetRegisterClass *, Register> Undefs;
127109467b48Spatrick // Map from <LoopReg, InitReg> to phi register for all created phis. Note that
127209467b48Spatrick // this map is only used when InitReg is non-undef.
127309467b48Spatrick DenseMap<std::pair<unsigned, unsigned>, Register> Phis;
127409467b48Spatrick // Map from LoopReg to phi register where the InitReg is undef.
127509467b48Spatrick DenseMap<Register, Register> UndefPhis;
127609467b48Spatrick
127709467b48Spatrick // Reg is used by MI. Return the new register MI should use to adhere to the
127809467b48Spatrick // schedule. Insert phis as necessary.
127909467b48Spatrick Register remapUse(Register Reg, MachineInstr &MI);
128009467b48Spatrick // Insert a phi that carries LoopReg from the loop body and InitReg otherwise.
128109467b48Spatrick // If InitReg is not given it is chosen arbitrarily. It will either be undef
128209467b48Spatrick // or will be chosen so as to share another phi.
1283*d415bd75Srobert Register phi(Register LoopReg, std::optional<Register> InitReg = {},
128409467b48Spatrick const TargetRegisterClass *RC = nullptr);
128509467b48Spatrick // Create an undef register of the given register class.
128609467b48Spatrick Register undef(const TargetRegisterClass *RC);
128709467b48Spatrick
128809467b48Spatrick public:
128973471bf0Spatrick KernelRewriter(MachineLoop &L, ModuloSchedule &S, MachineBasicBlock *LoopBB,
129009467b48Spatrick LiveIntervals *LIS = nullptr);
129109467b48Spatrick void rewrite();
129209467b48Spatrick };
129309467b48Spatrick } // namespace
129409467b48Spatrick
KernelRewriter(MachineLoop & L,ModuloSchedule & S,MachineBasicBlock * LoopBB,LiveIntervals * LIS)129509467b48Spatrick KernelRewriter::KernelRewriter(MachineLoop &L, ModuloSchedule &S,
129673471bf0Spatrick MachineBasicBlock *LoopBB, LiveIntervals *LIS)
129773471bf0Spatrick : S(S), BB(LoopBB), PreheaderBB(L.getLoopPreheader()),
129809467b48Spatrick ExitBB(L.getExitBlock()), MRI(BB->getParent()->getRegInfo()),
129909467b48Spatrick TII(BB->getParent()->getSubtarget().getInstrInfo()), LIS(LIS) {
130009467b48Spatrick PreheaderBB = *BB->pred_begin();
130109467b48Spatrick if (PreheaderBB == BB)
130209467b48Spatrick PreheaderBB = *std::next(BB->pred_begin());
130309467b48Spatrick }
130409467b48Spatrick
rewrite()130509467b48Spatrick void KernelRewriter::rewrite() {
130609467b48Spatrick // Rearrange the loop to be in schedule order. Note that the schedule may
130709467b48Spatrick // contain instructions that are not owned by the loop block (InstrChanges and
130809467b48Spatrick // friends), so we gracefully handle unowned instructions and delete any
130909467b48Spatrick // instructions that weren't in the schedule.
131009467b48Spatrick auto InsertPt = BB->getFirstTerminator();
131109467b48Spatrick MachineInstr *FirstMI = nullptr;
131209467b48Spatrick for (MachineInstr *MI : S.getInstructions()) {
131309467b48Spatrick if (MI->isPHI())
131409467b48Spatrick continue;
131509467b48Spatrick if (MI->getParent())
131609467b48Spatrick MI->removeFromParent();
131709467b48Spatrick BB->insert(InsertPt, MI);
131809467b48Spatrick if (!FirstMI)
131909467b48Spatrick FirstMI = MI;
132009467b48Spatrick }
132109467b48Spatrick assert(FirstMI && "Failed to find first MI in schedule");
132209467b48Spatrick
132309467b48Spatrick // At this point all of the scheduled instructions are between FirstMI
132409467b48Spatrick // and the end of the block. Kill from the first non-phi to FirstMI.
132509467b48Spatrick for (auto I = BB->getFirstNonPHI(); I != FirstMI->getIterator();) {
132609467b48Spatrick if (LIS)
132709467b48Spatrick LIS->RemoveMachineInstrFromMaps(*I);
132809467b48Spatrick (I++)->eraseFromParent();
132909467b48Spatrick }
133009467b48Spatrick
133109467b48Spatrick // Now remap every instruction in the loop.
133209467b48Spatrick for (MachineInstr &MI : *BB) {
133309467b48Spatrick if (MI.isPHI() || MI.isTerminator())
133409467b48Spatrick continue;
133509467b48Spatrick for (MachineOperand &MO : MI.uses()) {
133609467b48Spatrick if (!MO.isReg() || MO.getReg().isPhysical() || MO.isImplicit())
133709467b48Spatrick continue;
133809467b48Spatrick Register Reg = remapUse(MO.getReg(), MI);
133909467b48Spatrick MO.setReg(Reg);
134009467b48Spatrick }
134109467b48Spatrick }
134209467b48Spatrick EliminateDeadPhis(BB, MRI, LIS);
134309467b48Spatrick
134409467b48Spatrick // Ensure a phi exists for all instructions that are either referenced by
134509467b48Spatrick // an illegal phi or by an instruction outside the loop. This allows us to
134609467b48Spatrick // treat remaps of these values the same as "normal" values that come from
134709467b48Spatrick // loop-carried phis.
134809467b48Spatrick for (auto MI = BB->getFirstNonPHI(); MI != BB->end(); ++MI) {
134909467b48Spatrick if (MI->isPHI()) {
135009467b48Spatrick Register R = MI->getOperand(0).getReg();
135109467b48Spatrick phi(R);
135209467b48Spatrick continue;
135309467b48Spatrick }
135409467b48Spatrick
135509467b48Spatrick for (MachineOperand &Def : MI->defs()) {
135609467b48Spatrick for (MachineInstr &MI : MRI.use_instructions(Def.getReg())) {
135709467b48Spatrick if (MI.getParent() != BB) {
135809467b48Spatrick phi(Def.getReg());
135909467b48Spatrick break;
136009467b48Spatrick }
136109467b48Spatrick }
136209467b48Spatrick }
136309467b48Spatrick }
136409467b48Spatrick }
136509467b48Spatrick
remapUse(Register Reg,MachineInstr & MI)136609467b48Spatrick Register KernelRewriter::remapUse(Register Reg, MachineInstr &MI) {
136709467b48Spatrick MachineInstr *Producer = MRI.getUniqueVRegDef(Reg);
136809467b48Spatrick if (!Producer)
136909467b48Spatrick return Reg;
137009467b48Spatrick
137109467b48Spatrick int ConsumerStage = S.getStage(&MI);
137209467b48Spatrick if (!Producer->isPHI()) {
137309467b48Spatrick // Non-phi producers are simple to remap. Insert as many phis as the
137409467b48Spatrick // difference between the consumer and producer stages.
137509467b48Spatrick if (Producer->getParent() != BB)
137609467b48Spatrick // Producer was not inside the loop. Use the register as-is.
137709467b48Spatrick return Reg;
137809467b48Spatrick int ProducerStage = S.getStage(Producer);
137909467b48Spatrick assert(ConsumerStage != -1 &&
138009467b48Spatrick "In-loop consumer should always be scheduled!");
138109467b48Spatrick assert(ConsumerStage >= ProducerStage);
138209467b48Spatrick unsigned StageDiff = ConsumerStage - ProducerStage;
138309467b48Spatrick
138409467b48Spatrick for (unsigned I = 0; I < StageDiff; ++I)
138509467b48Spatrick Reg = phi(Reg);
138609467b48Spatrick return Reg;
138709467b48Spatrick }
138809467b48Spatrick
138909467b48Spatrick // First, dive through the phi chain to find the defaults for the generated
139009467b48Spatrick // phis.
1391*d415bd75Srobert SmallVector<std::optional<Register>, 4> Defaults;
139209467b48Spatrick Register LoopReg = Reg;
139309467b48Spatrick auto LoopProducer = Producer;
139409467b48Spatrick while (LoopProducer->isPHI() && LoopProducer->getParent() == BB) {
139509467b48Spatrick LoopReg = getLoopPhiReg(*LoopProducer, BB);
139609467b48Spatrick Defaults.emplace_back(getInitPhiReg(*LoopProducer, BB));
139709467b48Spatrick LoopProducer = MRI.getUniqueVRegDef(LoopReg);
139809467b48Spatrick assert(LoopProducer);
139909467b48Spatrick }
140009467b48Spatrick int LoopProducerStage = S.getStage(LoopProducer);
140109467b48Spatrick
1402*d415bd75Srobert std::optional<Register> IllegalPhiDefault;
140309467b48Spatrick
140409467b48Spatrick if (LoopProducerStage == -1) {
140509467b48Spatrick // Do nothing.
140609467b48Spatrick } else if (LoopProducerStage > ConsumerStage) {
140709467b48Spatrick // This schedule is only representable if ProducerStage == ConsumerStage+1.
140809467b48Spatrick // In addition, Consumer's cycle must be scheduled after Producer in the
140909467b48Spatrick // rescheduled loop. This is enforced by the pipeliner's ASAP and ALAP
141009467b48Spatrick // functions.
141109467b48Spatrick #ifndef NDEBUG // Silence unused variables in non-asserts mode.
141209467b48Spatrick int LoopProducerCycle = S.getCycle(LoopProducer);
141309467b48Spatrick int ConsumerCycle = S.getCycle(&MI);
141409467b48Spatrick #endif
141509467b48Spatrick assert(LoopProducerCycle <= ConsumerCycle);
141609467b48Spatrick assert(LoopProducerStage == ConsumerStage + 1);
141709467b48Spatrick // Peel off the first phi from Defaults and insert a phi between producer
141809467b48Spatrick // and consumer. This phi will not be at the front of the block so we
141909467b48Spatrick // consider it illegal. It will only exist during the rewrite process; it
142009467b48Spatrick // needs to exist while we peel off prologs because these could take the
142109467b48Spatrick // default value. After that we can replace all uses with the loop producer
142209467b48Spatrick // value.
142309467b48Spatrick IllegalPhiDefault = Defaults.front();
142409467b48Spatrick Defaults.erase(Defaults.begin());
142509467b48Spatrick } else {
142609467b48Spatrick assert(ConsumerStage >= LoopProducerStage);
142709467b48Spatrick int StageDiff = ConsumerStage - LoopProducerStage;
142809467b48Spatrick if (StageDiff > 0) {
142909467b48Spatrick LLVM_DEBUG(dbgs() << " -- padding defaults array from " << Defaults.size()
143009467b48Spatrick << " to " << (Defaults.size() + StageDiff) << "\n");
143109467b48Spatrick // If we need more phis than we have defaults for, pad out with undefs for
143209467b48Spatrick // the earliest phis, which are at the end of the defaults chain (the
143309467b48Spatrick // chain is in reverse order).
1434*d415bd75Srobert Defaults.resize(Defaults.size() + StageDiff,
1435*d415bd75Srobert Defaults.empty() ? std::optional<Register>()
143609467b48Spatrick : Defaults.back());
143709467b48Spatrick }
143809467b48Spatrick }
143909467b48Spatrick
144009467b48Spatrick // Now we know the number of stages to jump back, insert the phi chain.
144109467b48Spatrick auto DefaultI = Defaults.rbegin();
144209467b48Spatrick while (DefaultI != Defaults.rend())
144309467b48Spatrick LoopReg = phi(LoopReg, *DefaultI++, MRI.getRegClass(Reg));
144409467b48Spatrick
1445*d415bd75Srobert if (IllegalPhiDefault) {
144609467b48Spatrick // The consumer optionally consumes LoopProducer in the same iteration
144709467b48Spatrick // (because the producer is scheduled at an earlier cycle than the consumer)
144809467b48Spatrick // or the initial value. To facilitate this we create an illegal block here
144909467b48Spatrick // by embedding a phi in the middle of the block. We will fix this up
145009467b48Spatrick // immediately prior to pruning.
145109467b48Spatrick auto RC = MRI.getRegClass(Reg);
145209467b48Spatrick Register R = MRI.createVirtualRegister(RC);
1453097a140dSpatrick MachineInstr *IllegalPhi =
145409467b48Spatrick BuildMI(*BB, MI, DebugLoc(), TII->get(TargetOpcode::PHI), R)
1455*d415bd75Srobert .addReg(*IllegalPhiDefault)
145609467b48Spatrick .addMBB(PreheaderBB) // Block choice is arbitrary and has no effect.
145709467b48Spatrick .addReg(LoopReg)
145809467b48Spatrick .addMBB(BB); // Block choice is arbitrary and has no effect.
1459097a140dSpatrick // Illegal phi should belong to the producer stage so that it can be
1460097a140dSpatrick // filtered correctly during peeling.
1461097a140dSpatrick S.setStage(IllegalPhi, LoopProducerStage);
146209467b48Spatrick return R;
146309467b48Spatrick }
146409467b48Spatrick
146509467b48Spatrick return LoopReg;
146609467b48Spatrick }
146709467b48Spatrick
phi(Register LoopReg,std::optional<Register> InitReg,const TargetRegisterClass * RC)1468*d415bd75Srobert Register KernelRewriter::phi(Register LoopReg, std::optional<Register> InitReg,
146909467b48Spatrick const TargetRegisterClass *RC) {
147009467b48Spatrick // If the init register is not undef, try and find an existing phi.
1471*d415bd75Srobert if (InitReg) {
1472*d415bd75Srobert auto I = Phis.find({LoopReg, *InitReg});
147309467b48Spatrick if (I != Phis.end())
147409467b48Spatrick return I->second;
147509467b48Spatrick } else {
147609467b48Spatrick for (auto &KV : Phis) {
147709467b48Spatrick if (KV.first.first == LoopReg)
147809467b48Spatrick return KV.second;
147909467b48Spatrick }
148009467b48Spatrick }
148109467b48Spatrick
148209467b48Spatrick // InitReg is either undef or no existing phi takes InitReg as input. Try and
148309467b48Spatrick // find a phi that takes undef as input.
148409467b48Spatrick auto I = UndefPhis.find(LoopReg);
148509467b48Spatrick if (I != UndefPhis.end()) {
148609467b48Spatrick Register R = I->second;
1487*d415bd75Srobert if (!InitReg)
148809467b48Spatrick // Found a phi taking undef as input, and this input is undef so return
148909467b48Spatrick // without any more changes.
149009467b48Spatrick return R;
149109467b48Spatrick // Found a phi taking undef as input, so rewrite it to take InitReg.
149209467b48Spatrick MachineInstr *MI = MRI.getVRegDef(R);
1493*d415bd75Srobert MI->getOperand(1).setReg(*InitReg);
1494*d415bd75Srobert Phis.insert({{LoopReg, *InitReg}, R});
1495*d415bd75Srobert const TargetRegisterClass *ConstrainRegClass =
1496*d415bd75Srobert MRI.constrainRegClass(R, MRI.getRegClass(*InitReg));
1497*d415bd75Srobert assert(ConstrainRegClass && "Expected a valid constrained register class!");
1498*d415bd75Srobert (void)ConstrainRegClass;
149909467b48Spatrick UndefPhis.erase(I);
150009467b48Spatrick return R;
150109467b48Spatrick }
150209467b48Spatrick
150309467b48Spatrick // Failed to find any existing phi to reuse, so create a new one.
150409467b48Spatrick if (!RC)
150509467b48Spatrick RC = MRI.getRegClass(LoopReg);
150609467b48Spatrick Register R = MRI.createVirtualRegister(RC);
1507*d415bd75Srobert if (InitReg) {
1508*d415bd75Srobert const TargetRegisterClass *ConstrainRegClass =
150909467b48Spatrick MRI.constrainRegClass(R, MRI.getRegClass(*InitReg));
1510*d415bd75Srobert assert(ConstrainRegClass && "Expected a valid constrained register class!");
1511*d415bd75Srobert (void)ConstrainRegClass;
1512*d415bd75Srobert }
151309467b48Spatrick BuildMI(*BB, BB->getFirstNonPHI(), DebugLoc(), TII->get(TargetOpcode::PHI), R)
1514*d415bd75Srobert .addReg(InitReg ? *InitReg : undef(RC))
151509467b48Spatrick .addMBB(PreheaderBB)
151609467b48Spatrick .addReg(LoopReg)
151709467b48Spatrick .addMBB(BB);
1518*d415bd75Srobert if (!InitReg)
151909467b48Spatrick UndefPhis[LoopReg] = R;
152009467b48Spatrick else
152109467b48Spatrick Phis[{LoopReg, *InitReg}] = R;
152209467b48Spatrick return R;
152309467b48Spatrick }
152409467b48Spatrick
undef(const TargetRegisterClass * RC)152509467b48Spatrick Register KernelRewriter::undef(const TargetRegisterClass *RC) {
152609467b48Spatrick Register &R = Undefs[RC];
152709467b48Spatrick if (R == 0) {
152809467b48Spatrick // Create an IMPLICIT_DEF that defines this register if we need it.
152909467b48Spatrick // All uses of this should be removed by the time we have finished unrolling
153009467b48Spatrick // prologs and epilogs.
153109467b48Spatrick R = MRI.createVirtualRegister(RC);
153209467b48Spatrick auto *InsertBB = &PreheaderBB->getParent()->front();
153309467b48Spatrick BuildMI(*InsertBB, InsertBB->getFirstTerminator(), DebugLoc(),
153409467b48Spatrick TII->get(TargetOpcode::IMPLICIT_DEF), R);
153509467b48Spatrick }
153609467b48Spatrick return R;
153709467b48Spatrick }
153809467b48Spatrick
153909467b48Spatrick namespace {
154009467b48Spatrick /// Describes an operand in the kernel of a pipelined loop. Characteristics of
154109467b48Spatrick /// the operand are discovered, such as how many in-loop PHIs it has to jump
154209467b48Spatrick /// through and defaults for these phis.
154309467b48Spatrick class KernelOperandInfo {
154409467b48Spatrick MachineBasicBlock *BB;
154509467b48Spatrick MachineRegisterInfo &MRI;
154609467b48Spatrick SmallVector<Register, 4> PhiDefaults;
154709467b48Spatrick MachineOperand *Source;
154809467b48Spatrick MachineOperand *Target;
154909467b48Spatrick
155009467b48Spatrick public:
KernelOperandInfo(MachineOperand * MO,MachineRegisterInfo & MRI,const SmallPtrSetImpl<MachineInstr * > & IllegalPhis)155109467b48Spatrick KernelOperandInfo(MachineOperand *MO, MachineRegisterInfo &MRI,
155209467b48Spatrick const SmallPtrSetImpl<MachineInstr *> &IllegalPhis)
155309467b48Spatrick : MRI(MRI) {
155409467b48Spatrick Source = MO;
155509467b48Spatrick BB = MO->getParent()->getParent();
155609467b48Spatrick while (isRegInLoop(MO)) {
155709467b48Spatrick MachineInstr *MI = MRI.getVRegDef(MO->getReg());
155809467b48Spatrick if (MI->isFullCopy()) {
155909467b48Spatrick MO = &MI->getOperand(1);
156009467b48Spatrick continue;
156109467b48Spatrick }
156209467b48Spatrick if (!MI->isPHI())
156309467b48Spatrick break;
156409467b48Spatrick // If this is an illegal phi, don't count it in distance.
156509467b48Spatrick if (IllegalPhis.count(MI)) {
156609467b48Spatrick MO = &MI->getOperand(3);
156709467b48Spatrick continue;
156809467b48Spatrick }
156909467b48Spatrick
157009467b48Spatrick Register Default = getInitPhiReg(*MI, BB);
157109467b48Spatrick MO = MI->getOperand(2).getMBB() == BB ? &MI->getOperand(1)
157209467b48Spatrick : &MI->getOperand(3);
157309467b48Spatrick PhiDefaults.push_back(Default);
157409467b48Spatrick }
157509467b48Spatrick Target = MO;
157609467b48Spatrick }
157709467b48Spatrick
operator ==(const KernelOperandInfo & Other) const157809467b48Spatrick bool operator==(const KernelOperandInfo &Other) const {
157909467b48Spatrick return PhiDefaults.size() == Other.PhiDefaults.size();
158009467b48Spatrick }
158109467b48Spatrick
print(raw_ostream & OS) const158209467b48Spatrick void print(raw_ostream &OS) const {
158309467b48Spatrick OS << "use of " << *Source << ": distance(" << PhiDefaults.size() << ") in "
158409467b48Spatrick << *Source->getParent();
158509467b48Spatrick }
158609467b48Spatrick
158709467b48Spatrick private:
isRegInLoop(MachineOperand * MO)158809467b48Spatrick bool isRegInLoop(MachineOperand *MO) {
158909467b48Spatrick return MO->isReg() && MO->getReg().isVirtual() &&
159009467b48Spatrick MRI.getVRegDef(MO->getReg())->getParent() == BB;
159109467b48Spatrick }
159209467b48Spatrick };
159309467b48Spatrick } // namespace
159409467b48Spatrick
159509467b48Spatrick MachineBasicBlock *
peelKernel(LoopPeelDirection LPD)159609467b48Spatrick PeelingModuloScheduleExpander::peelKernel(LoopPeelDirection LPD) {
159709467b48Spatrick MachineBasicBlock *NewBB = PeelSingleBlockLoop(LPD, BB, MRI, TII);
159809467b48Spatrick if (LPD == LPD_Front)
159909467b48Spatrick PeeledFront.push_back(NewBB);
160009467b48Spatrick else
160109467b48Spatrick PeeledBack.push_front(NewBB);
160209467b48Spatrick for (auto I = BB->begin(), NI = NewBB->begin(); !I->isTerminator();
160309467b48Spatrick ++I, ++NI) {
160409467b48Spatrick CanonicalMIs[&*I] = &*I;
160509467b48Spatrick CanonicalMIs[&*NI] = &*I;
160609467b48Spatrick BlockMIs[{NewBB, &*I}] = &*NI;
160709467b48Spatrick BlockMIs[{BB, &*I}] = &*I;
160809467b48Spatrick }
160909467b48Spatrick return NewBB;
161009467b48Spatrick }
161109467b48Spatrick
filterInstructions(MachineBasicBlock * MB,int MinStage)161209467b48Spatrick void PeelingModuloScheduleExpander::filterInstructions(MachineBasicBlock *MB,
161309467b48Spatrick int MinStage) {
161409467b48Spatrick for (auto I = MB->getFirstInstrTerminator()->getReverseIterator();
161509467b48Spatrick I != std::next(MB->getFirstNonPHI()->getReverseIterator());) {
161609467b48Spatrick MachineInstr *MI = &*I++;
161709467b48Spatrick int Stage = getStage(MI);
161809467b48Spatrick if (Stage == -1 || Stage >= MinStage)
161909467b48Spatrick continue;
162009467b48Spatrick
162109467b48Spatrick for (MachineOperand &DefMO : MI->defs()) {
162209467b48Spatrick SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
162309467b48Spatrick for (MachineInstr &UseMI : MRI.use_instructions(DefMO.getReg())) {
162409467b48Spatrick // Only PHIs can use values from this block by construction.
162509467b48Spatrick // Match with the equivalent PHI in B.
162609467b48Spatrick assert(UseMI.isPHI());
162709467b48Spatrick Register Reg = getEquivalentRegisterIn(UseMI.getOperand(0).getReg(),
162809467b48Spatrick MI->getParent());
162909467b48Spatrick Subs.emplace_back(&UseMI, Reg);
163009467b48Spatrick }
163109467b48Spatrick for (auto &Sub : Subs)
163209467b48Spatrick Sub.first->substituteRegister(DefMO.getReg(), Sub.second, /*SubIdx=*/0,
163309467b48Spatrick *MRI.getTargetRegisterInfo());
163409467b48Spatrick }
163509467b48Spatrick if (LIS)
163609467b48Spatrick LIS->RemoveMachineInstrFromMaps(*MI);
163709467b48Spatrick MI->eraseFromParent();
163809467b48Spatrick }
163909467b48Spatrick }
164009467b48Spatrick
moveStageBetweenBlocks(MachineBasicBlock * DestBB,MachineBasicBlock * SourceBB,unsigned Stage)164109467b48Spatrick void PeelingModuloScheduleExpander::moveStageBetweenBlocks(
164209467b48Spatrick MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage) {
164309467b48Spatrick auto InsertPt = DestBB->getFirstNonPHI();
164409467b48Spatrick DenseMap<Register, Register> Remaps;
1645*d415bd75Srobert for (MachineInstr &MI : llvm::make_early_inc_range(
1646*d415bd75Srobert llvm::make_range(SourceBB->getFirstNonPHI(), SourceBB->end()))) {
1647*d415bd75Srobert if (MI.isPHI()) {
164809467b48Spatrick // This is an illegal PHI. If we move any instructions using an illegal
1649097a140dSpatrick // PHI, we need to create a legal Phi.
1650*d415bd75Srobert if (getStage(&MI) != Stage) {
1651097a140dSpatrick // The legal Phi is not necessary if the illegal phi's stage
1652097a140dSpatrick // is being moved.
1653*d415bd75Srobert Register PhiR = MI.getOperand(0).getReg();
165409467b48Spatrick auto RC = MRI.getRegClass(PhiR);
165509467b48Spatrick Register NR = MRI.createVirtualRegister(RC);
1656097a140dSpatrick MachineInstr *NI = BuildMI(*DestBB, DestBB->getFirstNonPHI(),
1657097a140dSpatrick DebugLoc(), TII->get(TargetOpcode::PHI), NR)
165809467b48Spatrick .addReg(PhiR)
165909467b48Spatrick .addMBB(SourceBB);
1660*d415bd75Srobert BlockMIs[{DestBB, CanonicalMIs[&MI]}] = NI;
1661*d415bd75Srobert CanonicalMIs[NI] = CanonicalMIs[&MI];
166209467b48Spatrick Remaps[PhiR] = NR;
1663097a140dSpatrick }
166409467b48Spatrick }
1665*d415bd75Srobert if (getStage(&MI) != Stage)
166609467b48Spatrick continue;
1667*d415bd75Srobert MI.removeFromParent();
1668*d415bd75Srobert DestBB->insert(InsertPt, &MI);
1669*d415bd75Srobert auto *KernelMI = CanonicalMIs[&MI];
1670*d415bd75Srobert BlockMIs[{DestBB, KernelMI}] = &MI;
167109467b48Spatrick BlockMIs.erase({SourceBB, KernelMI});
167209467b48Spatrick }
167309467b48Spatrick SmallVector<MachineInstr *, 4> PhiToDelete;
167409467b48Spatrick for (MachineInstr &MI : DestBB->phis()) {
167509467b48Spatrick assert(MI.getNumOperands() == 3);
167609467b48Spatrick MachineInstr *Def = MRI.getVRegDef(MI.getOperand(1).getReg());
167709467b48Spatrick // If the instruction referenced by the phi is moved inside the block
167809467b48Spatrick // we don't need the phi anymore.
167909467b48Spatrick if (getStage(Def) == Stage) {
168009467b48Spatrick Register PhiReg = MI.getOperand(0).getReg();
1681097a140dSpatrick assert(Def->findRegisterDefOperandIdx(MI.getOperand(1).getReg()) != -1);
1682097a140dSpatrick MRI.replaceRegWith(MI.getOperand(0).getReg(), MI.getOperand(1).getReg());
168309467b48Spatrick MI.getOperand(0).setReg(PhiReg);
168409467b48Spatrick PhiToDelete.push_back(&MI);
168509467b48Spatrick }
168609467b48Spatrick }
168709467b48Spatrick for (auto *P : PhiToDelete)
168809467b48Spatrick P->eraseFromParent();
168909467b48Spatrick InsertPt = DestBB->getFirstNonPHI();
169009467b48Spatrick // Helper to clone Phi instructions into the destination block. We clone Phi
169109467b48Spatrick // greedily to avoid combinatorial explosion of Phi instructions.
169209467b48Spatrick auto clonePhi = [&](MachineInstr *Phi) {
169309467b48Spatrick MachineInstr *NewMI = MF.CloneMachineInstr(Phi);
169409467b48Spatrick DestBB->insert(InsertPt, NewMI);
169509467b48Spatrick Register OrigR = Phi->getOperand(0).getReg();
169609467b48Spatrick Register R = MRI.createVirtualRegister(MRI.getRegClass(OrigR));
169709467b48Spatrick NewMI->getOperand(0).setReg(R);
169809467b48Spatrick NewMI->getOperand(1).setReg(OrigR);
169909467b48Spatrick NewMI->getOperand(2).setMBB(*DestBB->pred_begin());
170009467b48Spatrick Remaps[OrigR] = R;
170109467b48Spatrick CanonicalMIs[NewMI] = CanonicalMIs[Phi];
170209467b48Spatrick BlockMIs[{DestBB, CanonicalMIs[Phi]}] = NewMI;
170309467b48Spatrick PhiNodeLoopIteration[NewMI] = PhiNodeLoopIteration[Phi];
170409467b48Spatrick return R;
170509467b48Spatrick };
170609467b48Spatrick for (auto I = DestBB->getFirstNonPHI(); I != DestBB->end(); ++I) {
170709467b48Spatrick for (MachineOperand &MO : I->uses()) {
170809467b48Spatrick if (!MO.isReg())
170909467b48Spatrick continue;
171009467b48Spatrick if (Remaps.count(MO.getReg()))
171109467b48Spatrick MO.setReg(Remaps[MO.getReg()]);
171209467b48Spatrick else {
171309467b48Spatrick // If we are using a phi from the source block we need to add a new phi
171409467b48Spatrick // pointing to the old one.
171509467b48Spatrick MachineInstr *Use = MRI.getUniqueVRegDef(MO.getReg());
171609467b48Spatrick if (Use && Use->isPHI() && Use->getParent() == SourceBB) {
171709467b48Spatrick Register R = clonePhi(Use);
171809467b48Spatrick MO.setReg(R);
171909467b48Spatrick }
172009467b48Spatrick }
172109467b48Spatrick }
172209467b48Spatrick }
172309467b48Spatrick }
172409467b48Spatrick
172509467b48Spatrick Register
getPhiCanonicalReg(MachineInstr * CanonicalPhi,MachineInstr * Phi)172609467b48Spatrick PeelingModuloScheduleExpander::getPhiCanonicalReg(MachineInstr *CanonicalPhi,
172709467b48Spatrick MachineInstr *Phi) {
172809467b48Spatrick unsigned distance = PhiNodeLoopIteration[Phi];
172909467b48Spatrick MachineInstr *CanonicalUse = CanonicalPhi;
1730097a140dSpatrick Register CanonicalUseReg = CanonicalUse->getOperand(0).getReg();
173109467b48Spatrick for (unsigned I = 0; I < distance; ++I) {
173209467b48Spatrick assert(CanonicalUse->isPHI());
173309467b48Spatrick assert(CanonicalUse->getNumOperands() == 5);
173409467b48Spatrick unsigned LoopRegIdx = 3, InitRegIdx = 1;
173509467b48Spatrick if (CanonicalUse->getOperand(2).getMBB() == CanonicalUse->getParent())
173609467b48Spatrick std::swap(LoopRegIdx, InitRegIdx);
1737097a140dSpatrick CanonicalUseReg = CanonicalUse->getOperand(LoopRegIdx).getReg();
1738097a140dSpatrick CanonicalUse = MRI.getVRegDef(CanonicalUseReg);
173909467b48Spatrick }
1740097a140dSpatrick return CanonicalUseReg;
174109467b48Spatrick }
174209467b48Spatrick
peelPrologAndEpilogs()174309467b48Spatrick void PeelingModuloScheduleExpander::peelPrologAndEpilogs() {
174409467b48Spatrick BitVector LS(Schedule.getNumStages(), true);
174509467b48Spatrick BitVector AS(Schedule.getNumStages(), true);
174609467b48Spatrick LiveStages[BB] = LS;
174709467b48Spatrick AvailableStages[BB] = AS;
174809467b48Spatrick
174909467b48Spatrick // Peel out the prologs.
175009467b48Spatrick LS.reset();
175109467b48Spatrick for (int I = 0; I < Schedule.getNumStages() - 1; ++I) {
1752*d415bd75Srobert LS[I] = true;
175309467b48Spatrick Prologs.push_back(peelKernel(LPD_Front));
175409467b48Spatrick LiveStages[Prologs.back()] = LS;
175509467b48Spatrick AvailableStages[Prologs.back()] = LS;
175609467b48Spatrick }
175709467b48Spatrick
175809467b48Spatrick // Create a block that will end up as the new loop exiting block (dominated by
175909467b48Spatrick // all prologs and epilogs). It will only contain PHIs, in the same order as
176009467b48Spatrick // BB's PHIs. This gives us a poor-man's LCSSA with the inductive property
176109467b48Spatrick // that the exiting block is a (sub) clone of BB. This in turn gives us the
176209467b48Spatrick // property that any value deffed in BB but used outside of BB is used by a
176309467b48Spatrick // PHI in the exiting block.
176409467b48Spatrick MachineBasicBlock *ExitingBB = CreateLCSSAExitingBlock();
176509467b48Spatrick EliminateDeadPhis(ExitingBB, MRI, LIS, /*KeepSingleSrcPhi=*/true);
176609467b48Spatrick // Push out the epilogs, again in reverse order.
176709467b48Spatrick // We can't assume anything about the minumum loop trip count at this point,
176809467b48Spatrick // so emit a fairly complex epilog.
176909467b48Spatrick
177009467b48Spatrick // We first peel number of stages minus one epilogue. Then we remove dead
177109467b48Spatrick // stages and reorder instructions based on their stage. If we have 3 stages
177209467b48Spatrick // we generate first:
177309467b48Spatrick // E0[3, 2, 1]
177409467b48Spatrick // E1[3', 2']
177509467b48Spatrick // E2[3'']
177609467b48Spatrick // And then we move instructions based on their stages to have:
177709467b48Spatrick // E0[3]
177809467b48Spatrick // E1[2, 3']
177909467b48Spatrick // E2[1, 2', 3'']
178009467b48Spatrick // The transformation is legal because we only move instructions past
178109467b48Spatrick // instructions of a previous loop iteration.
178209467b48Spatrick for (int I = 1; I <= Schedule.getNumStages() - 1; ++I) {
178309467b48Spatrick Epilogs.push_back(peelKernel(LPD_Back));
178409467b48Spatrick MachineBasicBlock *B = Epilogs.back();
178509467b48Spatrick filterInstructions(B, Schedule.getNumStages() - I);
178609467b48Spatrick // Keep track at which iteration each phi belongs to. We need it to know
178709467b48Spatrick // what version of the variable to use during prologue/epilogue stitching.
178809467b48Spatrick EliminateDeadPhis(B, MRI, LIS, /*KeepSingleSrcPhi=*/true);
1789*d415bd75Srobert for (MachineInstr &Phi : B->phis())
1790*d415bd75Srobert PhiNodeLoopIteration[&Phi] = Schedule.getNumStages() - I;
179109467b48Spatrick }
179209467b48Spatrick for (size_t I = 0; I < Epilogs.size(); I++) {
179309467b48Spatrick LS.reset();
179409467b48Spatrick for (size_t J = I; J < Epilogs.size(); J++) {
179509467b48Spatrick int Iteration = J;
179609467b48Spatrick unsigned Stage = Schedule.getNumStages() - 1 + I - J;
179709467b48Spatrick // Move stage one block at a time so that Phi nodes are updated correctly.
179809467b48Spatrick for (size_t K = Iteration; K > I; K--)
179909467b48Spatrick moveStageBetweenBlocks(Epilogs[K - 1], Epilogs[K], Stage);
1800*d415bd75Srobert LS[Stage] = true;
180109467b48Spatrick }
180209467b48Spatrick LiveStages[Epilogs[I]] = LS;
180309467b48Spatrick AvailableStages[Epilogs[I]] = AS;
180409467b48Spatrick }
180509467b48Spatrick
180609467b48Spatrick // Now we've defined all the prolog and epilog blocks as a fallthrough
180709467b48Spatrick // sequence, add the edges that will be followed if the loop trip count is
180809467b48Spatrick // lower than the number of stages (connecting prologs directly with epilogs).
180909467b48Spatrick auto PI = Prologs.begin();
181009467b48Spatrick auto EI = Epilogs.begin();
181109467b48Spatrick assert(Prologs.size() == Epilogs.size());
181209467b48Spatrick for (; PI != Prologs.end(); ++PI, ++EI) {
181309467b48Spatrick MachineBasicBlock *Pred = *(*EI)->pred_begin();
181409467b48Spatrick (*PI)->addSuccessor(*EI);
181509467b48Spatrick for (MachineInstr &MI : (*EI)->phis()) {
181609467b48Spatrick Register Reg = MI.getOperand(1).getReg();
181709467b48Spatrick MachineInstr *Use = MRI.getUniqueVRegDef(Reg);
181809467b48Spatrick if (Use && Use->getParent() == Pred) {
181909467b48Spatrick MachineInstr *CanonicalUse = CanonicalMIs[Use];
182009467b48Spatrick if (CanonicalUse->isPHI()) {
182109467b48Spatrick // If the use comes from a phi we need to skip as many phi as the
182209467b48Spatrick // distance between the epilogue and the kernel. Trace through the phi
182309467b48Spatrick // chain to find the right value.
182409467b48Spatrick Reg = getPhiCanonicalReg(CanonicalUse, Use);
182509467b48Spatrick }
182609467b48Spatrick Reg = getEquivalentRegisterIn(Reg, *PI);
182709467b48Spatrick }
182809467b48Spatrick MI.addOperand(MachineOperand::CreateReg(Reg, /*isDef=*/false));
182909467b48Spatrick MI.addOperand(MachineOperand::CreateMBB(*PI));
183009467b48Spatrick }
183109467b48Spatrick }
183209467b48Spatrick
183309467b48Spatrick // Create a list of all blocks in order.
183409467b48Spatrick SmallVector<MachineBasicBlock *, 8> Blocks;
183509467b48Spatrick llvm::copy(PeeledFront, std::back_inserter(Blocks));
183609467b48Spatrick Blocks.push_back(BB);
183709467b48Spatrick llvm::copy(PeeledBack, std::back_inserter(Blocks));
183809467b48Spatrick
183909467b48Spatrick // Iterate in reverse order over all instructions, remapping as we go.
184009467b48Spatrick for (MachineBasicBlock *B : reverse(Blocks)) {
1841*d415bd75Srobert for (auto I = B->instr_rbegin();
184209467b48Spatrick I != std::next(B->getFirstNonPHI()->getReverseIterator());) {
1843*d415bd75Srobert MachineBasicBlock::reverse_instr_iterator MI = I++;
1844*d415bd75Srobert rewriteUsesOf(&*MI);
184509467b48Spatrick }
184609467b48Spatrick }
184709467b48Spatrick for (auto *MI : IllegalPhisToDelete) {
184809467b48Spatrick if (LIS)
184909467b48Spatrick LIS->RemoveMachineInstrFromMaps(*MI);
185009467b48Spatrick MI->eraseFromParent();
185109467b48Spatrick }
185209467b48Spatrick IllegalPhisToDelete.clear();
185309467b48Spatrick
185409467b48Spatrick // Now all remapping has been done, we're free to optimize the generated code.
185509467b48Spatrick for (MachineBasicBlock *B : reverse(Blocks))
185609467b48Spatrick EliminateDeadPhis(B, MRI, LIS);
185709467b48Spatrick EliminateDeadPhis(ExitingBB, MRI, LIS);
185809467b48Spatrick }
185909467b48Spatrick
CreateLCSSAExitingBlock()186009467b48Spatrick MachineBasicBlock *PeelingModuloScheduleExpander::CreateLCSSAExitingBlock() {
186109467b48Spatrick MachineFunction &MF = *BB->getParent();
186209467b48Spatrick MachineBasicBlock *Exit = *BB->succ_begin();
186309467b48Spatrick if (Exit == BB)
186409467b48Spatrick Exit = *std::next(BB->succ_begin());
186509467b48Spatrick
186609467b48Spatrick MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
186709467b48Spatrick MF.insert(std::next(BB->getIterator()), NewBB);
186809467b48Spatrick
186909467b48Spatrick // Clone all phis in BB into NewBB and rewrite.
187009467b48Spatrick for (MachineInstr &MI : BB->phis()) {
187109467b48Spatrick auto RC = MRI.getRegClass(MI.getOperand(0).getReg());
187209467b48Spatrick Register OldR = MI.getOperand(3).getReg();
187309467b48Spatrick Register R = MRI.createVirtualRegister(RC);
187409467b48Spatrick SmallVector<MachineInstr *, 4> Uses;
187509467b48Spatrick for (MachineInstr &Use : MRI.use_instructions(OldR))
187609467b48Spatrick if (Use.getParent() != BB)
187709467b48Spatrick Uses.push_back(&Use);
187809467b48Spatrick for (MachineInstr *Use : Uses)
187909467b48Spatrick Use->substituteRegister(OldR, R, /*SubIdx=*/0,
188009467b48Spatrick *MRI.getTargetRegisterInfo());
188109467b48Spatrick MachineInstr *NI = BuildMI(NewBB, DebugLoc(), TII->get(TargetOpcode::PHI), R)
188209467b48Spatrick .addReg(OldR)
188309467b48Spatrick .addMBB(BB);
188409467b48Spatrick BlockMIs[{NewBB, &MI}] = NI;
188509467b48Spatrick CanonicalMIs[NI] = &MI;
188609467b48Spatrick }
188709467b48Spatrick BB->replaceSuccessor(Exit, NewBB);
188809467b48Spatrick Exit->replacePhiUsesWith(BB, NewBB);
188909467b48Spatrick NewBB->addSuccessor(Exit);
189009467b48Spatrick
189109467b48Spatrick MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
189209467b48Spatrick SmallVector<MachineOperand, 4> Cond;
189309467b48Spatrick bool CanAnalyzeBr = !TII->analyzeBranch(*BB, TBB, FBB, Cond);
189409467b48Spatrick (void)CanAnalyzeBr;
189509467b48Spatrick assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
189609467b48Spatrick TII->removeBranch(*BB);
189709467b48Spatrick TII->insertBranch(*BB, TBB == Exit ? NewBB : TBB, FBB == Exit ? NewBB : FBB,
189809467b48Spatrick Cond, DebugLoc());
189909467b48Spatrick TII->insertUnconditionalBranch(*NewBB, Exit, DebugLoc());
190009467b48Spatrick return NewBB;
190109467b48Spatrick }
190209467b48Spatrick
190309467b48Spatrick Register
getEquivalentRegisterIn(Register Reg,MachineBasicBlock * BB)190409467b48Spatrick PeelingModuloScheduleExpander::getEquivalentRegisterIn(Register Reg,
190509467b48Spatrick MachineBasicBlock *BB) {
190609467b48Spatrick MachineInstr *MI = MRI.getUniqueVRegDef(Reg);
190709467b48Spatrick unsigned OpIdx = MI->findRegisterDefOperandIdx(Reg);
190809467b48Spatrick return BlockMIs[{BB, CanonicalMIs[MI]}]->getOperand(OpIdx).getReg();
190909467b48Spatrick }
191009467b48Spatrick
rewriteUsesOf(MachineInstr * MI)191109467b48Spatrick void PeelingModuloScheduleExpander::rewriteUsesOf(MachineInstr *MI) {
191209467b48Spatrick if (MI->isPHI()) {
191309467b48Spatrick // This is an illegal PHI. The loop-carried (desired) value is operand 3,
191409467b48Spatrick // and it is produced by this block.
191509467b48Spatrick Register PhiR = MI->getOperand(0).getReg();
191609467b48Spatrick Register R = MI->getOperand(3).getReg();
191709467b48Spatrick int RMIStage = getStage(MRI.getUniqueVRegDef(R));
191809467b48Spatrick if (RMIStage != -1 && !AvailableStages[MI->getParent()].test(RMIStage))
191909467b48Spatrick R = MI->getOperand(1).getReg();
192009467b48Spatrick MRI.setRegClass(R, MRI.getRegClass(PhiR));
192109467b48Spatrick MRI.replaceRegWith(PhiR, R);
192209467b48Spatrick // Postpone deleting the Phi as it may be referenced by BlockMIs and used
192309467b48Spatrick // later to figure out how to remap registers.
192409467b48Spatrick MI->getOperand(0).setReg(PhiR);
192509467b48Spatrick IllegalPhisToDelete.push_back(MI);
192609467b48Spatrick return;
192709467b48Spatrick }
192809467b48Spatrick
192909467b48Spatrick int Stage = getStage(MI);
193009467b48Spatrick if (Stage == -1 || LiveStages.count(MI->getParent()) == 0 ||
193109467b48Spatrick LiveStages[MI->getParent()].test(Stage))
193209467b48Spatrick // Instruction is live, no rewriting to do.
193309467b48Spatrick return;
193409467b48Spatrick
193509467b48Spatrick for (MachineOperand &DefMO : MI->defs()) {
193609467b48Spatrick SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
193709467b48Spatrick for (MachineInstr &UseMI : MRI.use_instructions(DefMO.getReg())) {
193809467b48Spatrick // Only PHIs can use values from this block by construction.
193909467b48Spatrick // Match with the equivalent PHI in B.
194009467b48Spatrick assert(UseMI.isPHI());
194109467b48Spatrick Register Reg = getEquivalentRegisterIn(UseMI.getOperand(0).getReg(),
194209467b48Spatrick MI->getParent());
194309467b48Spatrick Subs.emplace_back(&UseMI, Reg);
194409467b48Spatrick }
194509467b48Spatrick for (auto &Sub : Subs)
194609467b48Spatrick Sub.first->substituteRegister(DefMO.getReg(), Sub.second, /*SubIdx=*/0,
194709467b48Spatrick *MRI.getTargetRegisterInfo());
194809467b48Spatrick }
194909467b48Spatrick if (LIS)
195009467b48Spatrick LIS->RemoveMachineInstrFromMaps(*MI);
195109467b48Spatrick MI->eraseFromParent();
195209467b48Spatrick }
195309467b48Spatrick
fixupBranches()195409467b48Spatrick void PeelingModuloScheduleExpander::fixupBranches() {
195509467b48Spatrick // Work outwards from the kernel.
195609467b48Spatrick bool KernelDisposed = false;
195709467b48Spatrick int TC = Schedule.getNumStages() - 1;
195809467b48Spatrick for (auto PI = Prologs.rbegin(), EI = Epilogs.rbegin(); PI != Prologs.rend();
195909467b48Spatrick ++PI, ++EI, --TC) {
196009467b48Spatrick MachineBasicBlock *Prolog = *PI;
196109467b48Spatrick MachineBasicBlock *Fallthrough = *Prolog->succ_begin();
196209467b48Spatrick MachineBasicBlock *Epilog = *EI;
196309467b48Spatrick SmallVector<MachineOperand, 4> Cond;
196409467b48Spatrick TII->removeBranch(*Prolog);
1965*d415bd75Srobert std::optional<bool> StaticallyGreater =
1966097a140dSpatrick LoopInfo->createTripCountGreaterCondition(TC, *Prolog, Cond);
1967*d415bd75Srobert if (!StaticallyGreater) {
196809467b48Spatrick LLVM_DEBUG(dbgs() << "Dynamic: TC > " << TC << "\n");
196909467b48Spatrick // Dynamically branch based on Cond.
197009467b48Spatrick TII->insertBranch(*Prolog, Epilog, Fallthrough, Cond, DebugLoc());
197109467b48Spatrick } else if (*StaticallyGreater == false) {
197209467b48Spatrick LLVM_DEBUG(dbgs() << "Static-false: TC > " << TC << "\n");
197309467b48Spatrick // Prolog never falls through; branch to epilog and orphan interior
197409467b48Spatrick // blocks. Leave it to unreachable-block-elim to clean up.
197509467b48Spatrick Prolog->removeSuccessor(Fallthrough);
197609467b48Spatrick for (MachineInstr &P : Fallthrough->phis()) {
1977*d415bd75Srobert P.removeOperand(2);
1978*d415bd75Srobert P.removeOperand(1);
197909467b48Spatrick }
198009467b48Spatrick TII->insertUnconditionalBranch(*Prolog, Epilog, DebugLoc());
198109467b48Spatrick KernelDisposed = true;
198209467b48Spatrick } else {
198309467b48Spatrick LLVM_DEBUG(dbgs() << "Static-true: TC > " << TC << "\n");
198409467b48Spatrick // Prolog always falls through; remove incoming values in epilog.
198509467b48Spatrick Prolog->removeSuccessor(Epilog);
198609467b48Spatrick for (MachineInstr &P : Epilog->phis()) {
1987*d415bd75Srobert P.removeOperand(4);
1988*d415bd75Srobert P.removeOperand(3);
198909467b48Spatrick }
199009467b48Spatrick }
199109467b48Spatrick }
199209467b48Spatrick
199309467b48Spatrick if (!KernelDisposed) {
1994097a140dSpatrick LoopInfo->adjustTripCount(-(Schedule.getNumStages() - 1));
1995097a140dSpatrick LoopInfo->setPreheader(Prologs.back());
199609467b48Spatrick } else {
1997097a140dSpatrick LoopInfo->disposed();
199809467b48Spatrick }
199909467b48Spatrick }
200009467b48Spatrick
rewriteKernel()200109467b48Spatrick void PeelingModuloScheduleExpander::rewriteKernel() {
200273471bf0Spatrick KernelRewriter KR(*Schedule.getLoop(), Schedule, BB);
200309467b48Spatrick KR.rewrite();
200409467b48Spatrick }
200509467b48Spatrick
expand()200609467b48Spatrick void PeelingModuloScheduleExpander::expand() {
200709467b48Spatrick BB = Schedule.getLoop()->getTopBlock();
200809467b48Spatrick Preheader = Schedule.getLoop()->getLoopPreheader();
200909467b48Spatrick LLVM_DEBUG(Schedule.dump());
2010097a140dSpatrick LoopInfo = TII->analyzeLoopForPipelining(BB);
2011097a140dSpatrick assert(LoopInfo);
201209467b48Spatrick
201309467b48Spatrick rewriteKernel();
201409467b48Spatrick peelPrologAndEpilogs();
201509467b48Spatrick fixupBranches();
201609467b48Spatrick }
201709467b48Spatrick
validateAgainstModuloScheduleExpander()201809467b48Spatrick void PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander() {
201909467b48Spatrick BB = Schedule.getLoop()->getTopBlock();
202009467b48Spatrick Preheader = Schedule.getLoop()->getLoopPreheader();
202109467b48Spatrick
202209467b48Spatrick // Dump the schedule before we invalidate and remap all its instructions.
202309467b48Spatrick // Stash it in a string so we can print it if we found an error.
202409467b48Spatrick std::string ScheduleDump;
202509467b48Spatrick raw_string_ostream OS(ScheduleDump);
202609467b48Spatrick Schedule.print(OS);
202709467b48Spatrick OS.flush();
202809467b48Spatrick
202909467b48Spatrick // First, run the normal ModuleScheduleExpander. We don't support any
203009467b48Spatrick // InstrChanges.
203109467b48Spatrick assert(LIS && "Requires LiveIntervals!");
203209467b48Spatrick ModuloScheduleExpander MSE(MF, Schedule, *LIS,
203309467b48Spatrick ModuloScheduleExpander::InstrChangesTy());
203409467b48Spatrick MSE.expand();
203509467b48Spatrick MachineBasicBlock *ExpandedKernel = MSE.getRewrittenKernel();
203609467b48Spatrick if (!ExpandedKernel) {
203709467b48Spatrick // The expander optimized away the kernel. We can't do any useful checking.
203809467b48Spatrick MSE.cleanup();
203909467b48Spatrick return;
204009467b48Spatrick }
204109467b48Spatrick // Before running the KernelRewriter, re-add BB into the CFG.
204209467b48Spatrick Preheader->addSuccessor(BB);
204309467b48Spatrick
204409467b48Spatrick // Now run the new expansion algorithm.
204573471bf0Spatrick KernelRewriter KR(*Schedule.getLoop(), Schedule, BB);
204609467b48Spatrick KR.rewrite();
204709467b48Spatrick peelPrologAndEpilogs();
204809467b48Spatrick
204909467b48Spatrick // Collect all illegal phis that the new algorithm created. We'll give these
205009467b48Spatrick // to KernelOperandInfo.
205109467b48Spatrick SmallPtrSet<MachineInstr *, 4> IllegalPhis;
205209467b48Spatrick for (auto NI = BB->getFirstNonPHI(); NI != BB->end(); ++NI) {
205309467b48Spatrick if (NI->isPHI())
205409467b48Spatrick IllegalPhis.insert(&*NI);
205509467b48Spatrick }
205609467b48Spatrick
205709467b48Spatrick // Co-iterate across both kernels. We expect them to be identical apart from
205809467b48Spatrick // phis and full COPYs (we look through both).
205909467b48Spatrick SmallVector<std::pair<KernelOperandInfo, KernelOperandInfo>, 8> KOIs;
206009467b48Spatrick auto OI = ExpandedKernel->begin();
206109467b48Spatrick auto NI = BB->begin();
206209467b48Spatrick for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {
206309467b48Spatrick while (OI->isPHI() || OI->isFullCopy())
206409467b48Spatrick ++OI;
206509467b48Spatrick while (NI->isPHI() || NI->isFullCopy())
206609467b48Spatrick ++NI;
206709467b48Spatrick assert(OI->getOpcode() == NI->getOpcode() && "Opcodes don't match?!");
206809467b48Spatrick // Analyze every operand separately.
206909467b48Spatrick for (auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();
207009467b48Spatrick OOpI != OI->operands_end(); ++OOpI, ++NOpI)
207109467b48Spatrick KOIs.emplace_back(KernelOperandInfo(&*OOpI, MRI, IllegalPhis),
207209467b48Spatrick KernelOperandInfo(&*NOpI, MRI, IllegalPhis));
207309467b48Spatrick }
207409467b48Spatrick
207509467b48Spatrick bool Failed = false;
207609467b48Spatrick for (auto &OldAndNew : KOIs) {
207709467b48Spatrick if (OldAndNew.first == OldAndNew.second)
207809467b48Spatrick continue;
207909467b48Spatrick Failed = true;
208009467b48Spatrick errs() << "Modulo kernel validation error: [\n";
208109467b48Spatrick errs() << " [golden] ";
208209467b48Spatrick OldAndNew.first.print(errs());
208309467b48Spatrick errs() << " ";
208409467b48Spatrick OldAndNew.second.print(errs());
208509467b48Spatrick errs() << "]\n";
208609467b48Spatrick }
208709467b48Spatrick
208809467b48Spatrick if (Failed) {
208909467b48Spatrick errs() << "Golden reference kernel:\n";
209009467b48Spatrick ExpandedKernel->print(errs());
209109467b48Spatrick errs() << "New kernel:\n";
209209467b48Spatrick BB->print(errs());
209309467b48Spatrick errs() << ScheduleDump;
209409467b48Spatrick report_fatal_error(
209509467b48Spatrick "Modulo kernel validation (-pipeliner-experimental-cg) failed");
209609467b48Spatrick }
209709467b48Spatrick
209809467b48Spatrick // Cleanup by removing BB from the CFG again as the original
209909467b48Spatrick // ModuloScheduleExpander intended.
210009467b48Spatrick Preheader->removeSuccessor(BB);
210109467b48Spatrick MSE.cleanup();
210209467b48Spatrick }
210309467b48Spatrick
210409467b48Spatrick //===----------------------------------------------------------------------===//
210509467b48Spatrick // ModuloScheduleTestPass implementation
210609467b48Spatrick //===----------------------------------------------------------------------===//
210709467b48Spatrick // This pass constructs a ModuloSchedule from its module and runs
210809467b48Spatrick // ModuloScheduleExpander.
210909467b48Spatrick //
211009467b48Spatrick // The module is expected to contain a single-block analyzable loop.
211109467b48Spatrick // The total order of instructions is taken from the loop as-is.
211209467b48Spatrick // Instructions are expected to be annotated with a PostInstrSymbol.
211309467b48Spatrick // This PostInstrSymbol must have the following format:
211409467b48Spatrick // "Stage=%d Cycle=%d".
211509467b48Spatrick //===----------------------------------------------------------------------===//
211609467b48Spatrick
211709467b48Spatrick namespace {
211809467b48Spatrick class ModuloScheduleTest : public MachineFunctionPass {
211909467b48Spatrick public:
212009467b48Spatrick static char ID;
212109467b48Spatrick
ModuloScheduleTest()212209467b48Spatrick ModuloScheduleTest() : MachineFunctionPass(ID) {
212309467b48Spatrick initializeModuloScheduleTestPass(*PassRegistry::getPassRegistry());
212409467b48Spatrick }
212509467b48Spatrick
212609467b48Spatrick bool runOnMachineFunction(MachineFunction &MF) override;
212709467b48Spatrick void runOnLoop(MachineFunction &MF, MachineLoop &L);
212809467b48Spatrick
getAnalysisUsage(AnalysisUsage & AU) const212909467b48Spatrick void getAnalysisUsage(AnalysisUsage &AU) const override {
213009467b48Spatrick AU.addRequired<MachineLoopInfo>();
213109467b48Spatrick AU.addRequired<LiveIntervals>();
213209467b48Spatrick MachineFunctionPass::getAnalysisUsage(AU);
213309467b48Spatrick }
213409467b48Spatrick };
213509467b48Spatrick } // namespace
213609467b48Spatrick
213709467b48Spatrick char ModuloScheduleTest::ID = 0;
213809467b48Spatrick
213909467b48Spatrick INITIALIZE_PASS_BEGIN(ModuloScheduleTest, "modulo-schedule-test",
214009467b48Spatrick "Modulo Schedule test pass", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)214109467b48Spatrick INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
214209467b48Spatrick INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
214309467b48Spatrick INITIALIZE_PASS_END(ModuloScheduleTest, "modulo-schedule-test",
214409467b48Spatrick "Modulo Schedule test pass", false, false)
214509467b48Spatrick
214609467b48Spatrick bool ModuloScheduleTest::runOnMachineFunction(MachineFunction &MF) {
214709467b48Spatrick MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
214809467b48Spatrick for (auto *L : MLI) {
214909467b48Spatrick if (L->getTopBlock() != L->getBottomBlock())
215009467b48Spatrick continue;
215109467b48Spatrick runOnLoop(MF, *L);
215209467b48Spatrick return false;
215309467b48Spatrick }
215409467b48Spatrick return false;
215509467b48Spatrick }
215609467b48Spatrick
parseSymbolString(StringRef S,int & Cycle,int & Stage)215709467b48Spatrick static void parseSymbolString(StringRef S, int &Cycle, int &Stage) {
215809467b48Spatrick std::pair<StringRef, StringRef> StageAndCycle = getToken(S, "_");
215909467b48Spatrick std::pair<StringRef, StringRef> StageTokenAndValue =
216009467b48Spatrick getToken(StageAndCycle.first, "-");
216109467b48Spatrick std::pair<StringRef, StringRef> CycleTokenAndValue =
216209467b48Spatrick getToken(StageAndCycle.second, "-");
216309467b48Spatrick if (StageTokenAndValue.first != "Stage" ||
216409467b48Spatrick CycleTokenAndValue.first != "_Cycle") {
216509467b48Spatrick llvm_unreachable(
216609467b48Spatrick "Bad post-instr symbol syntax: see comment in ModuloScheduleTest");
216709467b48Spatrick return;
216809467b48Spatrick }
216909467b48Spatrick
217009467b48Spatrick StageTokenAndValue.second.drop_front().getAsInteger(10, Stage);
217109467b48Spatrick CycleTokenAndValue.second.drop_front().getAsInteger(10, Cycle);
217209467b48Spatrick
217309467b48Spatrick dbgs() << " Stage=" << Stage << ", Cycle=" << Cycle << "\n";
217409467b48Spatrick }
217509467b48Spatrick
runOnLoop(MachineFunction & MF,MachineLoop & L)217609467b48Spatrick void ModuloScheduleTest::runOnLoop(MachineFunction &MF, MachineLoop &L) {
217709467b48Spatrick LiveIntervals &LIS = getAnalysis<LiveIntervals>();
217809467b48Spatrick MachineBasicBlock *BB = L.getTopBlock();
217909467b48Spatrick dbgs() << "--- ModuloScheduleTest running on BB#" << BB->getNumber() << "\n";
218009467b48Spatrick
218109467b48Spatrick DenseMap<MachineInstr *, int> Cycle, Stage;
218209467b48Spatrick std::vector<MachineInstr *> Instrs;
218309467b48Spatrick for (MachineInstr &MI : *BB) {
218409467b48Spatrick if (MI.isTerminator())
218509467b48Spatrick continue;
218609467b48Spatrick Instrs.push_back(&MI);
218709467b48Spatrick if (MCSymbol *Sym = MI.getPostInstrSymbol()) {
218809467b48Spatrick dbgs() << "Parsing post-instr symbol for " << MI;
218909467b48Spatrick parseSymbolString(Sym->getName(), Cycle[&MI], Stage[&MI]);
219009467b48Spatrick }
219109467b48Spatrick }
219209467b48Spatrick
219309467b48Spatrick ModuloSchedule MS(MF, &L, std::move(Instrs), std::move(Cycle),
219409467b48Spatrick std::move(Stage));
219509467b48Spatrick ModuloScheduleExpander MSE(
219609467b48Spatrick MF, MS, LIS, /*InstrChanges=*/ModuloScheduleExpander::InstrChangesTy());
219709467b48Spatrick MSE.expand();
219809467b48Spatrick MSE.cleanup();
219909467b48Spatrick }
220009467b48Spatrick
220109467b48Spatrick //===----------------------------------------------------------------------===//
220209467b48Spatrick // ModuloScheduleTestAnnotater implementation
220309467b48Spatrick //===----------------------------------------------------------------------===//
220409467b48Spatrick
annotate()220509467b48Spatrick void ModuloScheduleTestAnnotater::annotate() {
220609467b48Spatrick for (MachineInstr *MI : S.getInstructions()) {
220709467b48Spatrick SmallVector<char, 16> SV;
220809467b48Spatrick raw_svector_ostream OS(SV);
220909467b48Spatrick OS << "Stage-" << S.getStage(MI) << "_Cycle-" << S.getCycle(MI);
221009467b48Spatrick MCSymbol *Sym = MF.getContext().getOrCreateSymbol(OS.str());
221109467b48Spatrick MI->setPostInstrSymbol(MF, Sym);
221209467b48Spatrick }
221309467b48Spatrick }
2214