18bcb0991SDimitry Andric //===- ModuloSchedule.cpp - Software pipeline schedule expansion ----------===//
28bcb0991SDimitry Andric //
38bcb0991SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
48bcb0991SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
58bcb0991SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
68bcb0991SDimitry Andric //
78bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
88bcb0991SDimitry Andric
98bcb0991SDimitry Andric #include "llvm/CodeGen/ModuloSchedule.h"
108bcb0991SDimitry Andric #include "llvm/ADT/StringExtras.h"
115ffd83dbSDimitry Andric #include "llvm/Analysis/MemoryLocation.h"
128bcb0991SDimitry Andric #include "llvm/CodeGen/LiveIntervals.h"
138bcb0991SDimitry Andric #include "llvm/CodeGen/MachineInstrBuilder.h"
1481ad6265SDimitry Andric #include "llvm/CodeGen/MachineLoopInfo.h"
158bcb0991SDimitry Andric #include "llvm/CodeGen/MachineRegisterInfo.h"
16480093f4SDimitry Andric #include "llvm/InitializePasses.h"
178bcb0991SDimitry Andric #include "llvm/MC/MCContext.h"
188bcb0991SDimitry Andric #include "llvm/Support/Debug.h"
198bcb0991SDimitry Andric #include "llvm/Support/ErrorHandling.h"
208bcb0991SDimitry Andric #include "llvm/Support/raw_ostream.h"
218bcb0991SDimitry Andric
228bcb0991SDimitry Andric #define DEBUG_TYPE "pipeliner"
238bcb0991SDimitry Andric using namespace llvm;
248bcb0991SDimitry Andric
print(raw_ostream & OS)258bcb0991SDimitry Andric void ModuloSchedule::print(raw_ostream &OS) {
268bcb0991SDimitry Andric for (MachineInstr *MI : ScheduledInstrs)
278bcb0991SDimitry Andric OS << "[stage " << getStage(MI) << " @" << getCycle(MI) << "c] " << *MI;
288bcb0991SDimitry Andric }
298bcb0991SDimitry Andric
308bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
318bcb0991SDimitry Andric // ModuloScheduleExpander implementation
328bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
338bcb0991SDimitry Andric
348bcb0991SDimitry Andric /// Return the register values for the operands of a Phi instruction.
358bcb0991SDimitry Andric /// This function assume the instruction is a Phi.
getPhiRegs(MachineInstr & Phi,MachineBasicBlock * Loop,unsigned & InitVal,unsigned & LoopVal)368bcb0991SDimitry Andric static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
378bcb0991SDimitry Andric unsigned &InitVal, unsigned &LoopVal) {
388bcb0991SDimitry Andric assert(Phi.isPHI() && "Expecting a Phi.");
398bcb0991SDimitry Andric
408bcb0991SDimitry Andric InitVal = 0;
418bcb0991SDimitry Andric LoopVal = 0;
428bcb0991SDimitry Andric for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
438bcb0991SDimitry Andric if (Phi.getOperand(i + 1).getMBB() != Loop)
448bcb0991SDimitry Andric InitVal = Phi.getOperand(i).getReg();
458bcb0991SDimitry Andric else
468bcb0991SDimitry Andric LoopVal = Phi.getOperand(i).getReg();
478bcb0991SDimitry Andric
488bcb0991SDimitry Andric assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure.");
498bcb0991SDimitry Andric }
508bcb0991SDimitry Andric
518bcb0991SDimitry Andric /// Return the Phi register value that comes from the incoming block.
getInitPhiReg(MachineInstr & Phi,MachineBasicBlock * LoopBB)528bcb0991SDimitry Andric static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
538bcb0991SDimitry Andric for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
548bcb0991SDimitry Andric if (Phi.getOperand(i + 1).getMBB() != LoopBB)
558bcb0991SDimitry Andric return Phi.getOperand(i).getReg();
568bcb0991SDimitry Andric return 0;
578bcb0991SDimitry Andric }
588bcb0991SDimitry Andric
598bcb0991SDimitry Andric /// Return the Phi register value that comes the loop block.
getLoopPhiReg(MachineInstr & Phi,MachineBasicBlock * LoopBB)608bcb0991SDimitry Andric static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
618bcb0991SDimitry Andric for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
628bcb0991SDimitry Andric if (Phi.getOperand(i + 1).getMBB() == LoopBB)
638bcb0991SDimitry Andric return Phi.getOperand(i).getReg();
648bcb0991SDimitry Andric return 0;
658bcb0991SDimitry Andric }
668bcb0991SDimitry Andric
expand()678bcb0991SDimitry Andric void ModuloScheduleExpander::expand() {
688bcb0991SDimitry Andric BB = Schedule.getLoop()->getTopBlock();
698bcb0991SDimitry Andric Preheader = *BB->pred_begin();
708bcb0991SDimitry Andric if (Preheader == BB)
718bcb0991SDimitry Andric Preheader = *std::next(BB->pred_begin());
728bcb0991SDimitry Andric
738bcb0991SDimitry Andric // Iterate over the definitions in each instruction, and compute the
748bcb0991SDimitry Andric // stage difference for each use. Keep the maximum value.
758bcb0991SDimitry Andric for (MachineInstr *MI : Schedule.getInstructions()) {
768bcb0991SDimitry Andric int DefStage = Schedule.getStage(MI);
77*06c3fb27SDimitry Andric for (const MachineOperand &Op : MI->all_defs()) {
788bcb0991SDimitry Andric Register Reg = Op.getReg();
798bcb0991SDimitry Andric unsigned MaxDiff = 0;
808bcb0991SDimitry Andric bool PhiIsSwapped = false;
81349cc55cSDimitry Andric for (MachineOperand &UseOp : MRI.use_operands(Reg)) {
828bcb0991SDimitry Andric MachineInstr *UseMI = UseOp.getParent();
838bcb0991SDimitry Andric int UseStage = Schedule.getStage(UseMI);
848bcb0991SDimitry Andric unsigned Diff = 0;
858bcb0991SDimitry Andric if (UseStage != -1 && UseStage >= DefStage)
868bcb0991SDimitry Andric Diff = UseStage - DefStage;
878bcb0991SDimitry Andric if (MI->isPHI()) {
888bcb0991SDimitry Andric if (isLoopCarried(*MI))
898bcb0991SDimitry Andric ++Diff;
908bcb0991SDimitry Andric else
918bcb0991SDimitry Andric PhiIsSwapped = true;
928bcb0991SDimitry Andric }
938bcb0991SDimitry Andric MaxDiff = std::max(Diff, MaxDiff);
948bcb0991SDimitry Andric }
958bcb0991SDimitry Andric RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped);
968bcb0991SDimitry Andric }
978bcb0991SDimitry Andric }
988bcb0991SDimitry Andric
998bcb0991SDimitry Andric generatePipelinedLoop();
1008bcb0991SDimitry Andric }
1018bcb0991SDimitry Andric
generatePipelinedLoop()1028bcb0991SDimitry Andric void ModuloScheduleExpander::generatePipelinedLoop() {
1038bcb0991SDimitry Andric LoopInfo = TII->analyzeLoopForPipelining(BB);
1048bcb0991SDimitry Andric assert(LoopInfo && "Must be able to analyze loop!");
1058bcb0991SDimitry Andric
1068bcb0991SDimitry Andric // Create a new basic block for the kernel and add it to the CFG.
1078bcb0991SDimitry Andric MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
1088bcb0991SDimitry Andric
1098bcb0991SDimitry Andric unsigned MaxStageCount = Schedule.getNumStages() - 1;
1108bcb0991SDimitry Andric
1118bcb0991SDimitry Andric // Remember the registers that are used in different stages. The index is
1128bcb0991SDimitry Andric // the iteration, or stage, that the instruction is scheduled in. This is
1138bcb0991SDimitry Andric // a map between register names in the original block and the names created
1148bcb0991SDimitry Andric // in each stage of the pipelined loop.
1158bcb0991SDimitry Andric ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2];
116bdd1243dSDimitry Andric
117bdd1243dSDimitry Andric // The renaming destination by Phis for the registers across stages.
118bdd1243dSDimitry Andric // This map is updated during Phis generation to point to the most recent
119bdd1243dSDimitry Andric // renaming destination.
120bdd1243dSDimitry Andric ValueMapTy *VRMapPhi = new ValueMapTy[(MaxStageCount + 1) * 2];
121bdd1243dSDimitry Andric
1228bcb0991SDimitry Andric InstrMapTy InstrMap;
1238bcb0991SDimitry Andric
1248bcb0991SDimitry Andric SmallVector<MachineBasicBlock *, 4> PrologBBs;
1258bcb0991SDimitry Andric
1268bcb0991SDimitry Andric // Generate the prolog instructions that set up the pipeline.
1278bcb0991SDimitry Andric generateProlog(MaxStageCount, KernelBB, VRMap, PrologBBs);
1288bcb0991SDimitry Andric MF.insert(BB->getIterator(), KernelBB);
1298bcb0991SDimitry Andric
1308bcb0991SDimitry Andric // Rearrange the instructions to generate the new, pipelined loop,
1318bcb0991SDimitry Andric // and update register names as needed.
1328bcb0991SDimitry Andric for (MachineInstr *CI : Schedule.getInstructions()) {
1338bcb0991SDimitry Andric if (CI->isPHI())
1348bcb0991SDimitry Andric continue;
1358bcb0991SDimitry Andric unsigned StageNum = Schedule.getStage(CI);
1368bcb0991SDimitry Andric MachineInstr *NewMI = cloneInstr(CI, MaxStageCount, StageNum);
1378bcb0991SDimitry Andric updateInstruction(NewMI, false, MaxStageCount, StageNum, VRMap);
1388bcb0991SDimitry Andric KernelBB->push_back(NewMI);
1398bcb0991SDimitry Andric InstrMap[NewMI] = CI;
1408bcb0991SDimitry Andric }
1418bcb0991SDimitry Andric
1428bcb0991SDimitry Andric // Copy any terminator instructions to the new kernel, and update
1438bcb0991SDimitry Andric // names as needed.
144349cc55cSDimitry Andric for (MachineInstr &MI : BB->terminators()) {
145349cc55cSDimitry Andric MachineInstr *NewMI = MF.CloneMachineInstr(&MI);
1468bcb0991SDimitry Andric updateInstruction(NewMI, false, MaxStageCount, 0, VRMap);
1478bcb0991SDimitry Andric KernelBB->push_back(NewMI);
148349cc55cSDimitry Andric InstrMap[NewMI] = &MI;
1498bcb0991SDimitry Andric }
1508bcb0991SDimitry Andric
1518bcb0991SDimitry Andric NewKernel = KernelBB;
1528bcb0991SDimitry Andric KernelBB->transferSuccessors(BB);
1538bcb0991SDimitry Andric KernelBB->replaceSuccessor(BB, KernelBB);
1548bcb0991SDimitry Andric
1558bcb0991SDimitry Andric generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap,
1568bcb0991SDimitry Andric InstrMap, MaxStageCount, MaxStageCount, false);
157bdd1243dSDimitry Andric generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap, VRMapPhi,
158bdd1243dSDimitry Andric InstrMap, MaxStageCount, MaxStageCount, false);
1598bcb0991SDimitry Andric
1608bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << "New block\n"; KernelBB->dump(););
1618bcb0991SDimitry Andric
1628bcb0991SDimitry Andric SmallVector<MachineBasicBlock *, 4> EpilogBBs;
1638bcb0991SDimitry Andric // Generate the epilog instructions to complete the pipeline.
164bdd1243dSDimitry Andric generateEpilog(MaxStageCount, KernelBB, BB, VRMap, VRMapPhi, EpilogBBs,
165bdd1243dSDimitry Andric PrologBBs);
1668bcb0991SDimitry Andric
1678bcb0991SDimitry Andric // We need this step because the register allocation doesn't handle some
1688bcb0991SDimitry Andric // situations well, so we insert copies to help out.
1698bcb0991SDimitry Andric splitLifetimes(KernelBB, EpilogBBs);
1708bcb0991SDimitry Andric
1718bcb0991SDimitry Andric // Remove dead instructions due to loop induction variables.
1728bcb0991SDimitry Andric removeDeadInstructions(KernelBB, EpilogBBs);
1738bcb0991SDimitry Andric
1748bcb0991SDimitry Andric // Add branches between prolog and epilog blocks.
1758bcb0991SDimitry Andric addBranches(*Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap);
1768bcb0991SDimitry Andric
1778bcb0991SDimitry Andric delete[] VRMap;
178bdd1243dSDimitry Andric delete[] VRMapPhi;
1798bcb0991SDimitry Andric }
1808bcb0991SDimitry Andric
cleanup()1818bcb0991SDimitry Andric void ModuloScheduleExpander::cleanup() {
1828bcb0991SDimitry Andric // Remove the original loop since it's no longer referenced.
1838bcb0991SDimitry Andric for (auto &I : *BB)
1848bcb0991SDimitry Andric LIS.RemoveMachineInstrFromMaps(I);
1858bcb0991SDimitry Andric BB->clear();
1868bcb0991SDimitry Andric BB->eraseFromParent();
1878bcb0991SDimitry Andric }
1888bcb0991SDimitry Andric
1898bcb0991SDimitry Andric /// Generate the pipeline prolog code.
generateProlog(unsigned LastStage,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,MBBVectorTy & PrologBBs)1908bcb0991SDimitry Andric void ModuloScheduleExpander::generateProlog(unsigned LastStage,
1918bcb0991SDimitry Andric MachineBasicBlock *KernelBB,
1928bcb0991SDimitry Andric ValueMapTy *VRMap,
1938bcb0991SDimitry Andric MBBVectorTy &PrologBBs) {
1948bcb0991SDimitry Andric MachineBasicBlock *PredBB = Preheader;
1958bcb0991SDimitry Andric InstrMapTy InstrMap;
1968bcb0991SDimitry Andric
1978bcb0991SDimitry Andric // Generate a basic block for each stage, not including the last stage,
1988bcb0991SDimitry Andric // which will be generated in the kernel. Each basic block may contain
1998bcb0991SDimitry Andric // instructions from multiple stages/iterations.
2008bcb0991SDimitry Andric for (unsigned i = 0; i < LastStage; ++i) {
2018bcb0991SDimitry Andric // Create and insert the prolog basic block prior to the original loop
2028bcb0991SDimitry Andric // basic block. The original loop is removed later.
2038bcb0991SDimitry Andric MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
2048bcb0991SDimitry Andric PrologBBs.push_back(NewBB);
2058bcb0991SDimitry Andric MF.insert(BB->getIterator(), NewBB);
2068bcb0991SDimitry Andric NewBB->transferSuccessors(PredBB);
2078bcb0991SDimitry Andric PredBB->addSuccessor(NewBB);
2088bcb0991SDimitry Andric PredBB = NewBB;
2098bcb0991SDimitry Andric
2108bcb0991SDimitry Andric // Generate instructions for each appropriate stage. Process instructions
2118bcb0991SDimitry Andric // in original program order.
2128bcb0991SDimitry Andric for (int StageNum = i; StageNum >= 0; --StageNum) {
2138bcb0991SDimitry Andric for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
2148bcb0991SDimitry Andric BBE = BB->getFirstTerminator();
2158bcb0991SDimitry Andric BBI != BBE; ++BBI) {
2168bcb0991SDimitry Andric if (Schedule.getStage(&*BBI) == StageNum) {
2178bcb0991SDimitry Andric if (BBI->isPHI())
2188bcb0991SDimitry Andric continue;
2198bcb0991SDimitry Andric MachineInstr *NewMI =
2208bcb0991SDimitry Andric cloneAndChangeInstr(&*BBI, i, (unsigned)StageNum);
2218bcb0991SDimitry Andric updateInstruction(NewMI, false, i, (unsigned)StageNum, VRMap);
2228bcb0991SDimitry Andric NewBB->push_back(NewMI);
2238bcb0991SDimitry Andric InstrMap[NewMI] = &*BBI;
2248bcb0991SDimitry Andric }
2258bcb0991SDimitry Andric }
2268bcb0991SDimitry Andric }
2278bcb0991SDimitry Andric rewritePhiValues(NewBB, i, VRMap, InstrMap);
2288bcb0991SDimitry Andric LLVM_DEBUG({
2298bcb0991SDimitry Andric dbgs() << "prolog:\n";
2308bcb0991SDimitry Andric NewBB->dump();
2318bcb0991SDimitry Andric });
2328bcb0991SDimitry Andric }
2338bcb0991SDimitry Andric
2348bcb0991SDimitry Andric PredBB->replaceSuccessor(BB, KernelBB);
2358bcb0991SDimitry Andric
2368bcb0991SDimitry Andric // Check if we need to remove the branch from the preheader to the original
2378bcb0991SDimitry Andric // loop, and replace it with a branch to the new loop.
2388bcb0991SDimitry Andric unsigned numBranches = TII->removeBranch(*Preheader);
2398bcb0991SDimitry Andric if (numBranches) {
2408bcb0991SDimitry Andric SmallVector<MachineOperand, 0> Cond;
2418bcb0991SDimitry Andric TII->insertBranch(*Preheader, PrologBBs[0], nullptr, Cond, DebugLoc());
2428bcb0991SDimitry Andric }
2438bcb0991SDimitry Andric }
2448bcb0991SDimitry Andric
2458bcb0991SDimitry Andric /// Generate the pipeline epilog code. The epilog code finishes the iterations
2468bcb0991SDimitry Andric /// that were started in either the prolog or the kernel. We create a basic
2478bcb0991SDimitry Andric /// block for each stage that needs to complete.
generateEpilog(unsigned LastStage,MachineBasicBlock * KernelBB,MachineBasicBlock * OrigBB,ValueMapTy * VRMap,ValueMapTy * VRMapPhi,MBBVectorTy & EpilogBBs,MBBVectorTy & PrologBBs)24881ad6265SDimitry Andric void ModuloScheduleExpander::generateEpilog(
24981ad6265SDimitry Andric unsigned LastStage, MachineBasicBlock *KernelBB, MachineBasicBlock *OrigBB,
250bdd1243dSDimitry Andric ValueMapTy *VRMap, ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,
251bdd1243dSDimitry Andric MBBVectorTy &PrologBBs) {
2528bcb0991SDimitry Andric // We need to change the branch from the kernel to the first epilog block, so
2538bcb0991SDimitry Andric // this call to analyze branch uses the kernel rather than the original BB.
2548bcb0991SDimitry Andric MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
2558bcb0991SDimitry Andric SmallVector<MachineOperand, 4> Cond;
2568bcb0991SDimitry Andric bool checkBranch = TII->analyzeBranch(*KernelBB, TBB, FBB, Cond);
2578bcb0991SDimitry Andric assert(!checkBranch && "generateEpilog must be able to analyze the branch");
2588bcb0991SDimitry Andric if (checkBranch)
2598bcb0991SDimitry Andric return;
2608bcb0991SDimitry Andric
2618bcb0991SDimitry Andric MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin();
2628bcb0991SDimitry Andric if (*LoopExitI == KernelBB)
2638bcb0991SDimitry Andric ++LoopExitI;
2648bcb0991SDimitry Andric assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor");
2658bcb0991SDimitry Andric MachineBasicBlock *LoopExitBB = *LoopExitI;
2668bcb0991SDimitry Andric
2678bcb0991SDimitry Andric MachineBasicBlock *PredBB = KernelBB;
2688bcb0991SDimitry Andric MachineBasicBlock *EpilogStart = LoopExitBB;
2698bcb0991SDimitry Andric InstrMapTy InstrMap;
2708bcb0991SDimitry Andric
2718bcb0991SDimitry Andric // Generate a basic block for each stage, not including the last stage,
2728bcb0991SDimitry Andric // which was generated for the kernel. Each basic block may contain
2738bcb0991SDimitry Andric // instructions from multiple stages/iterations.
2748bcb0991SDimitry Andric int EpilogStage = LastStage + 1;
2758bcb0991SDimitry Andric for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {
2768bcb0991SDimitry Andric MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock();
2778bcb0991SDimitry Andric EpilogBBs.push_back(NewBB);
2788bcb0991SDimitry Andric MF.insert(BB->getIterator(), NewBB);
2798bcb0991SDimitry Andric
2808bcb0991SDimitry Andric PredBB->replaceSuccessor(LoopExitBB, NewBB);
2818bcb0991SDimitry Andric NewBB->addSuccessor(LoopExitBB);
2828bcb0991SDimitry Andric
2838bcb0991SDimitry Andric if (EpilogStart == LoopExitBB)
2848bcb0991SDimitry Andric EpilogStart = NewBB;
2858bcb0991SDimitry Andric
2868bcb0991SDimitry Andric // Add instructions to the epilog depending on the current block.
2878bcb0991SDimitry Andric // Process instructions in original program order.
2888bcb0991SDimitry Andric for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) {
2898bcb0991SDimitry Andric for (auto &BBI : *BB) {
2908bcb0991SDimitry Andric if (BBI.isPHI())
2918bcb0991SDimitry Andric continue;
2928bcb0991SDimitry Andric MachineInstr *In = &BBI;
2938bcb0991SDimitry Andric if ((unsigned)Schedule.getStage(In) == StageNum) {
2948bcb0991SDimitry Andric // Instructions with memoperands in the epilog are updated with
2958bcb0991SDimitry Andric // conservative values.
2968bcb0991SDimitry Andric MachineInstr *NewMI = cloneInstr(In, UINT_MAX, 0);
2978bcb0991SDimitry Andric updateInstruction(NewMI, i == 1, EpilogStage, 0, VRMap);
2988bcb0991SDimitry Andric NewBB->push_back(NewMI);
2998bcb0991SDimitry Andric InstrMap[NewMI] = In;
3008bcb0991SDimitry Andric }
3018bcb0991SDimitry Andric }
3028bcb0991SDimitry Andric }
3038bcb0991SDimitry Andric generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap,
3048bcb0991SDimitry Andric InstrMap, LastStage, EpilogStage, i == 1);
305bdd1243dSDimitry Andric generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap, VRMapPhi,
306bdd1243dSDimitry Andric InstrMap, LastStage, EpilogStage, i == 1);
3078bcb0991SDimitry Andric PredBB = NewBB;
3088bcb0991SDimitry Andric
3098bcb0991SDimitry Andric LLVM_DEBUG({
3108bcb0991SDimitry Andric dbgs() << "epilog:\n";
3118bcb0991SDimitry Andric NewBB->dump();
3128bcb0991SDimitry Andric });
3138bcb0991SDimitry Andric }
3148bcb0991SDimitry Andric
3158bcb0991SDimitry Andric // Fix any Phi nodes in the loop exit block.
3168bcb0991SDimitry Andric LoopExitBB->replacePhiUsesWith(BB, PredBB);
3178bcb0991SDimitry Andric
3188bcb0991SDimitry Andric // Create a branch to the new epilog from the kernel.
3198bcb0991SDimitry Andric // Remove the original branch and add a new branch to the epilog.
3208bcb0991SDimitry Andric TII->removeBranch(*KernelBB);
32181ad6265SDimitry Andric assert((OrigBB == TBB || OrigBB == FBB) &&
32281ad6265SDimitry Andric "Unable to determine looping branch direction");
32381ad6265SDimitry Andric if (OrigBB != TBB)
32481ad6265SDimitry Andric TII->insertBranch(*KernelBB, EpilogStart, KernelBB, Cond, DebugLoc());
32581ad6265SDimitry Andric else
3268bcb0991SDimitry Andric TII->insertBranch(*KernelBB, KernelBB, EpilogStart, Cond, DebugLoc());
3278bcb0991SDimitry Andric // Add a branch to the loop exit.
3288bcb0991SDimitry Andric if (EpilogBBs.size() > 0) {
3298bcb0991SDimitry Andric MachineBasicBlock *LastEpilogBB = EpilogBBs.back();
3308bcb0991SDimitry Andric SmallVector<MachineOperand, 4> Cond1;
3318bcb0991SDimitry Andric TII->insertBranch(*LastEpilogBB, LoopExitBB, nullptr, Cond1, DebugLoc());
3328bcb0991SDimitry Andric }
3338bcb0991SDimitry Andric }
3348bcb0991SDimitry Andric
3358bcb0991SDimitry Andric /// Replace all uses of FromReg that appear outside the specified
3368bcb0991SDimitry Andric /// basic block with ToReg.
replaceRegUsesAfterLoop(unsigned FromReg,unsigned ToReg,MachineBasicBlock * MBB,MachineRegisterInfo & MRI,LiveIntervals & LIS)3378bcb0991SDimitry Andric static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg,
3388bcb0991SDimitry Andric MachineBasicBlock *MBB,
3398bcb0991SDimitry Andric MachineRegisterInfo &MRI,
3408bcb0991SDimitry Andric LiveIntervals &LIS) {
341349cc55cSDimitry Andric for (MachineOperand &O :
342349cc55cSDimitry Andric llvm::make_early_inc_range(MRI.use_operands(FromReg)))
3438bcb0991SDimitry Andric if (O.getParent()->getParent() != MBB)
3448bcb0991SDimitry Andric O.setReg(ToReg);
3458bcb0991SDimitry Andric if (!LIS.hasInterval(ToReg))
3468bcb0991SDimitry Andric LIS.createEmptyInterval(ToReg);
3478bcb0991SDimitry Andric }
3488bcb0991SDimitry Andric
3498bcb0991SDimitry Andric /// Return true if the register has a use that occurs outside the
3508bcb0991SDimitry Andric /// specified loop.
hasUseAfterLoop(unsigned Reg,MachineBasicBlock * BB,MachineRegisterInfo & MRI)3518bcb0991SDimitry Andric static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB,
3528bcb0991SDimitry Andric MachineRegisterInfo &MRI) {
353349cc55cSDimitry Andric for (const MachineOperand &MO : MRI.use_operands(Reg))
354349cc55cSDimitry Andric if (MO.getParent()->getParent() != BB)
3558bcb0991SDimitry Andric return true;
3568bcb0991SDimitry Andric return false;
3578bcb0991SDimitry Andric }
3588bcb0991SDimitry Andric
3598bcb0991SDimitry Andric /// Generate Phis for the specific block in the generated pipelined code.
3608bcb0991SDimitry Andric /// This function looks at the Phis from the original code to guide the
3618bcb0991SDimitry Andric /// creation of new Phis.
generateExistingPhis(MachineBasicBlock * NewBB,MachineBasicBlock * BB1,MachineBasicBlock * BB2,MachineBasicBlock * KernelBB,ValueMapTy * VRMap,InstrMapTy & InstrMap,unsigned LastStageNum,unsigned CurStageNum,bool IsLast)3628bcb0991SDimitry Andric void ModuloScheduleExpander::generateExistingPhis(
3638bcb0991SDimitry Andric MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
3648bcb0991SDimitry Andric MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap,
3658bcb0991SDimitry Andric unsigned LastStageNum, unsigned CurStageNum, bool IsLast) {
3668bcb0991SDimitry Andric // Compute the stage number for the initial value of the Phi, which
3678bcb0991SDimitry Andric // comes from the prolog. The prolog to use depends on to which kernel/
3688bcb0991SDimitry Andric // epilog that we're adding the Phi.
3698bcb0991SDimitry Andric unsigned PrologStage = 0;
3708bcb0991SDimitry Andric unsigned PrevStage = 0;
3718bcb0991SDimitry Andric bool InKernel = (LastStageNum == CurStageNum);
3728bcb0991SDimitry Andric if (InKernel) {
3738bcb0991SDimitry Andric PrologStage = LastStageNum - 1;
3748bcb0991SDimitry Andric PrevStage = CurStageNum;
3758bcb0991SDimitry Andric } else {
3768bcb0991SDimitry Andric PrologStage = LastStageNum - (CurStageNum - LastStageNum);
3778bcb0991SDimitry Andric PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;
3788bcb0991SDimitry Andric }
3798bcb0991SDimitry Andric
3808bcb0991SDimitry Andric for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
3818bcb0991SDimitry Andric BBE = BB->getFirstNonPHI();
3828bcb0991SDimitry Andric BBI != BBE; ++BBI) {
3838bcb0991SDimitry Andric Register Def = BBI->getOperand(0).getReg();
3848bcb0991SDimitry Andric
3858bcb0991SDimitry Andric unsigned InitVal = 0;
3868bcb0991SDimitry Andric unsigned LoopVal = 0;
3878bcb0991SDimitry Andric getPhiRegs(*BBI, BB, InitVal, LoopVal);
3888bcb0991SDimitry Andric
3898bcb0991SDimitry Andric unsigned PhiOp1 = 0;
3908bcb0991SDimitry Andric // The Phi value from the loop body typically is defined in the loop, but
3918bcb0991SDimitry Andric // not always. So, we need to check if the value is defined in the loop.
3928bcb0991SDimitry Andric unsigned PhiOp2 = LoopVal;
3938bcb0991SDimitry Andric if (VRMap[LastStageNum].count(LoopVal))
3948bcb0991SDimitry Andric PhiOp2 = VRMap[LastStageNum][LoopVal];
3958bcb0991SDimitry Andric
3968bcb0991SDimitry Andric int StageScheduled = Schedule.getStage(&*BBI);
3978bcb0991SDimitry Andric int LoopValStage = Schedule.getStage(MRI.getVRegDef(LoopVal));
3988bcb0991SDimitry Andric unsigned NumStages = getStagesForReg(Def, CurStageNum);
3998bcb0991SDimitry Andric if (NumStages == 0) {
4008bcb0991SDimitry Andric // We don't need to generate a Phi anymore, but we need to rename any uses
4018bcb0991SDimitry Andric // of the Phi value.
4028bcb0991SDimitry Andric unsigned NewReg = VRMap[PrevStage][LoopVal];
4038bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, 0, &*BBI, Def,
4048bcb0991SDimitry Andric InitVal, NewReg);
4058bcb0991SDimitry Andric if (VRMap[CurStageNum].count(LoopVal))
4068bcb0991SDimitry Andric VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal];
4078bcb0991SDimitry Andric }
4088bcb0991SDimitry Andric // Adjust the number of Phis needed depending on the number of prologs left,
4098bcb0991SDimitry Andric // and the distance from where the Phi is first scheduled. The number of
4108bcb0991SDimitry Andric // Phis cannot exceed the number of prolog stages. Each stage can
4118bcb0991SDimitry Andric // potentially define two values.
4128bcb0991SDimitry Andric unsigned MaxPhis = PrologStage + 2;
4138bcb0991SDimitry Andric if (!InKernel && (int)PrologStage <= LoopValStage)
4148bcb0991SDimitry Andric MaxPhis = std::max((int)MaxPhis - (int)LoopValStage, 1);
4158bcb0991SDimitry Andric unsigned NumPhis = std::min(NumStages, MaxPhis);
4168bcb0991SDimitry Andric
4178bcb0991SDimitry Andric unsigned NewReg = 0;
4188bcb0991SDimitry Andric unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;
4198bcb0991SDimitry Andric // In the epilog, we may need to look back one stage to get the correct
4205ffd83dbSDimitry Andric // Phi name, because the epilog and prolog blocks execute the same stage.
4218bcb0991SDimitry Andric // The correct name is from the previous block only when the Phi has
4228bcb0991SDimitry Andric // been completely scheduled prior to the epilog, and Phi value is not
4238bcb0991SDimitry Andric // needed in multiple stages.
4248bcb0991SDimitry Andric int StageDiff = 0;
4258bcb0991SDimitry Andric if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&
4268bcb0991SDimitry Andric NumPhis == 1)
4278bcb0991SDimitry Andric StageDiff = 1;
4288bcb0991SDimitry Andric // Adjust the computations below when the phi and the loop definition
4298bcb0991SDimitry Andric // are scheduled in different stages.
4308bcb0991SDimitry Andric if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)
4318bcb0991SDimitry Andric StageDiff = StageScheduled - LoopValStage;
4328bcb0991SDimitry Andric for (unsigned np = 0; np < NumPhis; ++np) {
4338bcb0991SDimitry Andric // If the Phi hasn't been scheduled, then use the initial Phi operand
4348bcb0991SDimitry Andric // value. Otherwise, use the scheduled version of the instruction. This
4358bcb0991SDimitry Andric // is a little complicated when a Phi references another Phi.
4368bcb0991SDimitry Andric if (np > PrologStage || StageScheduled >= (int)LastStageNum)
4378bcb0991SDimitry Andric PhiOp1 = InitVal;
4388bcb0991SDimitry Andric // Check if the Phi has already been scheduled in a prolog stage.
4398bcb0991SDimitry Andric else if (PrologStage >= AccessStage + StageDiff + np &&
4408bcb0991SDimitry Andric VRMap[PrologStage - StageDiff - np].count(LoopVal) != 0)
4418bcb0991SDimitry Andric PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];
4428bcb0991SDimitry Andric // Check if the Phi has already been scheduled, but the loop instruction
4438bcb0991SDimitry Andric // is either another Phi, or doesn't occur in the loop.
4448bcb0991SDimitry Andric else if (PrologStage >= AccessStage + StageDiff + np) {
4458bcb0991SDimitry Andric // If the Phi references another Phi, we need to examine the other
4468bcb0991SDimitry Andric // Phi to get the correct value.
4478bcb0991SDimitry Andric PhiOp1 = LoopVal;
4488bcb0991SDimitry Andric MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1);
4498bcb0991SDimitry Andric int Indirects = 1;
4508bcb0991SDimitry Andric while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) {
4518bcb0991SDimitry Andric int PhiStage = Schedule.getStage(InstOp1);
4528bcb0991SDimitry Andric if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects)
4538bcb0991SDimitry Andric PhiOp1 = getInitPhiReg(*InstOp1, BB);
4548bcb0991SDimitry Andric else
4558bcb0991SDimitry Andric PhiOp1 = getLoopPhiReg(*InstOp1, BB);
4568bcb0991SDimitry Andric InstOp1 = MRI.getVRegDef(PhiOp1);
4578bcb0991SDimitry Andric int PhiOpStage = Schedule.getStage(InstOp1);
4588bcb0991SDimitry Andric int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);
4598bcb0991SDimitry Andric if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np &&
4608bcb0991SDimitry Andric VRMap[PrologStage - StageAdj - Indirects - np].count(PhiOp1)) {
4618bcb0991SDimitry Andric PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1];
4628bcb0991SDimitry Andric break;
4638bcb0991SDimitry Andric }
4648bcb0991SDimitry Andric ++Indirects;
4658bcb0991SDimitry Andric }
4668bcb0991SDimitry Andric } else
4678bcb0991SDimitry Andric PhiOp1 = InitVal;
4688bcb0991SDimitry Andric // If this references a generated Phi in the kernel, get the Phi operand
4698bcb0991SDimitry Andric // from the incoming block.
4708bcb0991SDimitry Andric if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1))
4718bcb0991SDimitry Andric if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB)
4728bcb0991SDimitry Andric PhiOp1 = getInitPhiReg(*InstOp1, KernelBB);
4738bcb0991SDimitry Andric
4748bcb0991SDimitry Andric MachineInstr *PhiInst = MRI.getVRegDef(LoopVal);
4758bcb0991SDimitry Andric bool LoopDefIsPhi = PhiInst && PhiInst->isPHI();
4768bcb0991SDimitry Andric // In the epilog, a map lookup is needed to get the value from the kernel,
4778bcb0991SDimitry Andric // or previous epilog block. How is does this depends on if the
4788bcb0991SDimitry Andric // instruction is scheduled in the previous block.
4798bcb0991SDimitry Andric if (!InKernel) {
4808bcb0991SDimitry Andric int StageDiffAdj = 0;
4818bcb0991SDimitry Andric if (LoopValStage != -1 && StageScheduled > LoopValStage)
4828bcb0991SDimitry Andric StageDiffAdj = StageScheduled - LoopValStage;
4838bcb0991SDimitry Andric // Use the loop value defined in the kernel, unless the kernel
4848bcb0991SDimitry Andric // contains the last definition of the Phi.
4858bcb0991SDimitry Andric if (np == 0 && PrevStage == LastStageNum &&
4868bcb0991SDimitry Andric (StageScheduled != 0 || LoopValStage != 0) &&
4878bcb0991SDimitry Andric VRMap[PrevStage - StageDiffAdj].count(LoopVal))
4888bcb0991SDimitry Andric PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal];
4898bcb0991SDimitry Andric // Use the value defined by the Phi. We add one because we switch
4908bcb0991SDimitry Andric // from looking at the loop value to the Phi definition.
4918bcb0991SDimitry Andric else if (np > 0 && PrevStage == LastStageNum &&
4928bcb0991SDimitry Andric VRMap[PrevStage - np + 1].count(Def))
4938bcb0991SDimitry Andric PhiOp2 = VRMap[PrevStage - np + 1][Def];
4948bcb0991SDimitry Andric // Use the loop value defined in the kernel.
4958bcb0991SDimitry Andric else if (static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&
4968bcb0991SDimitry Andric VRMap[PrevStage - StageDiffAdj - np].count(LoopVal))
4978bcb0991SDimitry Andric PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal];
4988bcb0991SDimitry Andric // Use the value defined by the Phi, unless we're generating the first
4998bcb0991SDimitry Andric // epilog and the Phi refers to a Phi in a different stage.
5008bcb0991SDimitry Andric else if (VRMap[PrevStage - np].count(Def) &&
5018bcb0991SDimitry Andric (!LoopDefIsPhi || (PrevStage != LastStageNum) ||
5028bcb0991SDimitry Andric (LoopValStage == StageScheduled)))
5038bcb0991SDimitry Andric PhiOp2 = VRMap[PrevStage - np][Def];
5048bcb0991SDimitry Andric }
5058bcb0991SDimitry Andric
5068bcb0991SDimitry Andric // Check if we can reuse an existing Phi. This occurs when a Phi
5078bcb0991SDimitry Andric // references another Phi, and the other Phi is scheduled in an
5088bcb0991SDimitry Andric // earlier stage. We can try to reuse an existing Phi up until the last
5098bcb0991SDimitry Andric // stage of the current Phi.
5108bcb0991SDimitry Andric if (LoopDefIsPhi) {
5118bcb0991SDimitry Andric if (static_cast<int>(PrologStage - np) >= StageScheduled) {
5128bcb0991SDimitry Andric int LVNumStages = getStagesForPhi(LoopVal);
5138bcb0991SDimitry Andric int StageDiff = (StageScheduled - LoopValStage);
5148bcb0991SDimitry Andric LVNumStages -= StageDiff;
5158bcb0991SDimitry Andric // Make sure the loop value Phi has been processed already.
5168bcb0991SDimitry Andric if (LVNumStages > (int)np && VRMap[CurStageNum].count(LoopVal)) {
5178bcb0991SDimitry Andric NewReg = PhiOp2;
5188bcb0991SDimitry Andric unsigned ReuseStage = CurStageNum;
5198bcb0991SDimitry Andric if (isLoopCarried(*PhiInst))
5208bcb0991SDimitry Andric ReuseStage -= LVNumStages;
5218bcb0991SDimitry Andric // Check if the Phi to reuse has been generated yet. If not, then
5228bcb0991SDimitry Andric // there is nothing to reuse.
5238bcb0991SDimitry Andric if (VRMap[ReuseStage - np].count(LoopVal)) {
5248bcb0991SDimitry Andric NewReg = VRMap[ReuseStage - np][LoopVal];
5258bcb0991SDimitry Andric
5268bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
5278bcb0991SDimitry Andric Def, NewReg);
5288bcb0991SDimitry Andric // Update the map with the new Phi name.
5298bcb0991SDimitry Andric VRMap[CurStageNum - np][Def] = NewReg;
5308bcb0991SDimitry Andric PhiOp2 = NewReg;
5318bcb0991SDimitry Andric if (VRMap[LastStageNum - np - 1].count(LoopVal))
5328bcb0991SDimitry Andric PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];
5338bcb0991SDimitry Andric
5348bcb0991SDimitry Andric if (IsLast && np == NumPhis - 1)
5358bcb0991SDimitry Andric replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
5368bcb0991SDimitry Andric continue;
5378bcb0991SDimitry Andric }
5388bcb0991SDimitry Andric }
5398bcb0991SDimitry Andric }
5408bcb0991SDimitry Andric if (InKernel && StageDiff > 0 &&
5418bcb0991SDimitry Andric VRMap[CurStageNum - StageDiff - np].count(LoopVal))
5428bcb0991SDimitry Andric PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];
5438bcb0991SDimitry Andric }
5448bcb0991SDimitry Andric
5458bcb0991SDimitry Andric const TargetRegisterClass *RC = MRI.getRegClass(Def);
5468bcb0991SDimitry Andric NewReg = MRI.createVirtualRegister(RC);
5478bcb0991SDimitry Andric
5488bcb0991SDimitry Andric MachineInstrBuilder NewPhi =
5498bcb0991SDimitry Andric BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(),
5508bcb0991SDimitry Andric TII->get(TargetOpcode::PHI), NewReg);
5518bcb0991SDimitry Andric NewPhi.addReg(PhiOp1).addMBB(BB1);
5528bcb0991SDimitry Andric NewPhi.addReg(PhiOp2).addMBB(BB2);
5538bcb0991SDimitry Andric if (np == 0)
5548bcb0991SDimitry Andric InstrMap[NewPhi] = &*BBI;
5558bcb0991SDimitry Andric
5568bcb0991SDimitry Andric // We define the Phis after creating the new pipelined code, so
5578bcb0991SDimitry Andric // we need to rename the Phi values in scheduled instructions.
5588bcb0991SDimitry Andric
5598bcb0991SDimitry Andric unsigned PrevReg = 0;
5608bcb0991SDimitry Andric if (InKernel && VRMap[PrevStage - np].count(LoopVal))
5618bcb0991SDimitry Andric PrevReg = VRMap[PrevStage - np][LoopVal];
5628bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,
5638bcb0991SDimitry Andric NewReg, PrevReg);
5648bcb0991SDimitry Andric // If the Phi has been scheduled, use the new name for rewriting.
5658bcb0991SDimitry Andric if (VRMap[CurStageNum - np].count(Def)) {
5668bcb0991SDimitry Andric unsigned R = VRMap[CurStageNum - np][Def];
5678bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, R,
5688bcb0991SDimitry Andric NewReg);
5698bcb0991SDimitry Andric }
5708bcb0991SDimitry Andric
5718bcb0991SDimitry Andric // Check if we need to rename any uses that occurs after the loop. The
5728bcb0991SDimitry Andric // register to replace depends on whether the Phi is scheduled in the
5738bcb0991SDimitry Andric // epilog.
5748bcb0991SDimitry Andric if (IsLast && np == NumPhis - 1)
5758bcb0991SDimitry Andric replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
5768bcb0991SDimitry Andric
5778bcb0991SDimitry Andric // In the kernel, a dependent Phi uses the value from this Phi.
5788bcb0991SDimitry Andric if (InKernel)
5798bcb0991SDimitry Andric PhiOp2 = NewReg;
5808bcb0991SDimitry Andric
5818bcb0991SDimitry Andric // Update the map with the new Phi name.
5828bcb0991SDimitry Andric VRMap[CurStageNum - np][Def] = NewReg;
5838bcb0991SDimitry Andric }
5848bcb0991SDimitry Andric
5858bcb0991SDimitry Andric while (NumPhis++ < NumStages) {
5868bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, NumPhis, &*BBI, Def,
5878bcb0991SDimitry Andric NewReg, 0);
5888bcb0991SDimitry Andric }
5898bcb0991SDimitry Andric
5908bcb0991SDimitry Andric // Check if we need to rename a Phi that has been eliminated due to
5918bcb0991SDimitry Andric // scheduling.
5928bcb0991SDimitry Andric if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal))
5938bcb0991SDimitry Andric replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS);
5948bcb0991SDimitry Andric }
5958bcb0991SDimitry Andric }
5968bcb0991SDimitry Andric
5978bcb0991SDimitry Andric /// Generate Phis for the specified block in the generated pipelined code.
5988bcb0991SDimitry Andric /// These are new Phis needed because the definition is scheduled after the
5998bcb0991SDimitry Andric /// 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)6008bcb0991SDimitry Andric void ModuloScheduleExpander::generatePhis(
6018bcb0991SDimitry Andric MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
602bdd1243dSDimitry Andric MachineBasicBlock *KernelBB, ValueMapTy *VRMap, ValueMapTy *VRMapPhi,
603bdd1243dSDimitry Andric InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum,
604bdd1243dSDimitry Andric bool IsLast) {
6058bcb0991SDimitry Andric // Compute the stage number that contains the initial Phi value, and
6068bcb0991SDimitry Andric // the Phi from the previous stage.
6078bcb0991SDimitry Andric unsigned PrologStage = 0;
6088bcb0991SDimitry Andric unsigned PrevStage = 0;
6098bcb0991SDimitry Andric unsigned StageDiff = CurStageNum - LastStageNum;
6108bcb0991SDimitry Andric bool InKernel = (StageDiff == 0);
6118bcb0991SDimitry Andric if (InKernel) {
6128bcb0991SDimitry Andric PrologStage = LastStageNum - 1;
6138bcb0991SDimitry Andric PrevStage = CurStageNum;
6148bcb0991SDimitry Andric } else {
6158bcb0991SDimitry Andric PrologStage = LastStageNum - StageDiff;
6168bcb0991SDimitry Andric PrevStage = LastStageNum + StageDiff - 1;
6178bcb0991SDimitry Andric }
6188bcb0991SDimitry Andric
6198bcb0991SDimitry Andric for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(),
6208bcb0991SDimitry Andric BBE = BB->instr_end();
6218bcb0991SDimitry Andric BBI != BBE; ++BBI) {
6228bcb0991SDimitry Andric for (unsigned i = 0, e = BBI->getNumOperands(); i != e; ++i) {
6238bcb0991SDimitry Andric MachineOperand &MO = BBI->getOperand(i);
624bdd1243dSDimitry Andric if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
6258bcb0991SDimitry Andric continue;
6268bcb0991SDimitry Andric
6278bcb0991SDimitry Andric int StageScheduled = Schedule.getStage(&*BBI);
6288bcb0991SDimitry Andric assert(StageScheduled != -1 && "Expecting scheduled instruction.");
6298bcb0991SDimitry Andric Register Def = MO.getReg();
6308bcb0991SDimitry Andric unsigned NumPhis = getStagesForReg(Def, CurStageNum);
6318bcb0991SDimitry Andric // An instruction scheduled in stage 0 and is used after the loop
6328bcb0991SDimitry Andric // requires a phi in the epilog for the last definition from either
6338bcb0991SDimitry Andric // the kernel or prolog.
6348bcb0991SDimitry Andric if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&
6358bcb0991SDimitry Andric hasUseAfterLoop(Def, BB, MRI))
6368bcb0991SDimitry Andric NumPhis = 1;
6378bcb0991SDimitry Andric if (!InKernel && (unsigned)StageScheduled > PrologStage)
6388bcb0991SDimitry Andric continue;
6398bcb0991SDimitry Andric
640bdd1243dSDimitry Andric unsigned PhiOp2;
641bdd1243dSDimitry Andric if (InKernel) {
642bdd1243dSDimitry Andric PhiOp2 = VRMap[PrevStage][Def];
6438bcb0991SDimitry Andric if (MachineInstr *InstOp2 = MRI.getVRegDef(PhiOp2))
6448bcb0991SDimitry Andric if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)
6458bcb0991SDimitry Andric PhiOp2 = getLoopPhiReg(*InstOp2, BB2);
646bdd1243dSDimitry Andric }
6478bcb0991SDimitry Andric // The number of Phis can't exceed the number of prolog stages. The
6488bcb0991SDimitry Andric // prolog stage number is zero based.
6498bcb0991SDimitry Andric if (NumPhis > PrologStage + 1 - StageScheduled)
6508bcb0991SDimitry Andric NumPhis = PrologStage + 1 - StageScheduled;
6518bcb0991SDimitry Andric for (unsigned np = 0; np < NumPhis; ++np) {
652bdd1243dSDimitry Andric // Example for
653bdd1243dSDimitry Andric // Org:
654bdd1243dSDimitry Andric // %Org = ... (Scheduled at Stage#0, NumPhi = 2)
655bdd1243dSDimitry Andric //
656bdd1243dSDimitry Andric // Prolog0 (Stage0):
657bdd1243dSDimitry Andric // %Clone0 = ...
658bdd1243dSDimitry Andric // Prolog1 (Stage1):
659bdd1243dSDimitry Andric // %Clone1 = ...
660bdd1243dSDimitry Andric // Kernel (Stage2):
661bdd1243dSDimitry Andric // %Phi0 = Phi %Clone1, Prolog1, %Clone2, Kernel
662bdd1243dSDimitry Andric // %Phi1 = Phi %Clone0, Prolog1, %Phi0, Kernel
663bdd1243dSDimitry Andric // %Clone2 = ...
664bdd1243dSDimitry Andric // Epilog0 (Stage3):
665bdd1243dSDimitry Andric // %Phi2 = Phi %Clone1, Prolog1, %Clone2, Kernel
666bdd1243dSDimitry Andric // %Phi3 = Phi %Clone0, Prolog1, %Phi0, Kernel
667bdd1243dSDimitry Andric // Epilog1 (Stage4):
668bdd1243dSDimitry Andric // %Phi4 = Phi %Clone0, Prolog0, %Phi2, Epilog0
669bdd1243dSDimitry Andric //
670bdd1243dSDimitry Andric // VRMap = {0: %Clone0, 1: %Clone1, 2: %Clone2}
671bdd1243dSDimitry Andric // VRMapPhi (after Kernel) = {0: %Phi1, 1: %Phi0}
672bdd1243dSDimitry Andric // VRMapPhi (after Epilog0) = {0: %Phi3, 1: %Phi2}
673bdd1243dSDimitry Andric
6748bcb0991SDimitry Andric unsigned PhiOp1 = VRMap[PrologStage][Def];
6758bcb0991SDimitry Andric if (np <= PrologStage)
6768bcb0991SDimitry Andric PhiOp1 = VRMap[PrologStage - np][Def];
677bdd1243dSDimitry Andric if (!InKernel) {
678bdd1243dSDimitry Andric if (PrevStage == LastStageNum && np == 0)
679bdd1243dSDimitry Andric PhiOp2 = VRMap[LastStageNum][Def];
680bdd1243dSDimitry Andric else
681bdd1243dSDimitry Andric PhiOp2 = VRMapPhi[PrevStage - np][Def];
6828bcb0991SDimitry Andric }
6838bcb0991SDimitry Andric
6848bcb0991SDimitry Andric const TargetRegisterClass *RC = MRI.getRegClass(Def);
6858bcb0991SDimitry Andric Register NewReg = MRI.createVirtualRegister(RC);
6868bcb0991SDimitry Andric
6878bcb0991SDimitry Andric MachineInstrBuilder NewPhi =
6888bcb0991SDimitry Andric BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(),
6898bcb0991SDimitry Andric TII->get(TargetOpcode::PHI), NewReg);
6908bcb0991SDimitry Andric NewPhi.addReg(PhiOp1).addMBB(BB1);
6918bcb0991SDimitry Andric NewPhi.addReg(PhiOp2).addMBB(BB2);
6928bcb0991SDimitry Andric if (np == 0)
6938bcb0991SDimitry Andric InstrMap[NewPhi] = &*BBI;
6948bcb0991SDimitry Andric
6958bcb0991SDimitry Andric // Rewrite uses and update the map. The actions depend upon whether
6968bcb0991SDimitry Andric // we generating code for the kernel or epilog blocks.
6978bcb0991SDimitry Andric if (InKernel) {
6988bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp1,
6998bcb0991SDimitry Andric NewReg);
7008bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp2,
7018bcb0991SDimitry Andric NewReg);
7028bcb0991SDimitry Andric
7038bcb0991SDimitry Andric PhiOp2 = NewReg;
704bdd1243dSDimitry Andric VRMapPhi[PrevStage - np - 1][Def] = NewReg;
7058bcb0991SDimitry Andric } else {
706bdd1243dSDimitry Andric VRMapPhi[CurStageNum - np][Def] = NewReg;
7078bcb0991SDimitry Andric if (np == NumPhis - 1)
7088bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,
7098bcb0991SDimitry Andric NewReg);
7108bcb0991SDimitry Andric }
7118bcb0991SDimitry Andric if (IsLast && np == NumPhis - 1)
7128bcb0991SDimitry Andric replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
7138bcb0991SDimitry Andric }
7148bcb0991SDimitry Andric }
7158bcb0991SDimitry Andric }
7168bcb0991SDimitry Andric }
7178bcb0991SDimitry Andric
7188bcb0991SDimitry Andric /// Remove instructions that generate values with no uses.
7198bcb0991SDimitry Andric /// Typically, these are induction variable operations that generate values
7208bcb0991SDimitry Andric /// used in the loop itself. A dead instruction has a definition with
7218bcb0991SDimitry Andric /// no uses, or uses that occur in the original loop only.
removeDeadInstructions(MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs)7228bcb0991SDimitry Andric void ModuloScheduleExpander::removeDeadInstructions(MachineBasicBlock *KernelBB,
7238bcb0991SDimitry Andric MBBVectorTy &EpilogBBs) {
7248bcb0991SDimitry Andric // For each epilog block, check that the value defined by each instruction
7258bcb0991SDimitry Andric // is used. If not, delete it.
726349cc55cSDimitry Andric for (MachineBasicBlock *MBB : llvm::reverse(EpilogBBs))
727349cc55cSDimitry Andric for (MachineBasicBlock::reverse_instr_iterator MI = MBB->instr_rbegin(),
728349cc55cSDimitry Andric ME = MBB->instr_rend();
7298bcb0991SDimitry Andric MI != ME;) {
7308bcb0991SDimitry Andric // From DeadMachineInstructionElem. Don't delete inline assembly.
7318bcb0991SDimitry Andric if (MI->isInlineAsm()) {
7328bcb0991SDimitry Andric ++MI;
7338bcb0991SDimitry Andric continue;
7348bcb0991SDimitry Andric }
7358bcb0991SDimitry Andric bool SawStore = false;
7368bcb0991SDimitry Andric // Check if it's safe to remove the instruction due to side effects.
7378bcb0991SDimitry Andric // We can, and want to, remove Phis here.
7388bcb0991SDimitry Andric if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI()) {
7398bcb0991SDimitry Andric ++MI;
7408bcb0991SDimitry Andric continue;
7418bcb0991SDimitry Andric }
7428bcb0991SDimitry Andric bool used = true;
743*06c3fb27SDimitry Andric for (const MachineOperand &MO : MI->all_defs()) {
744349cc55cSDimitry Andric Register reg = MO.getReg();
7458bcb0991SDimitry Andric // Assume physical registers are used, unless they are marked dead.
746bdd1243dSDimitry Andric if (reg.isPhysical()) {
747349cc55cSDimitry Andric used = !MO.isDead();
7488bcb0991SDimitry Andric if (used)
7498bcb0991SDimitry Andric break;
7508bcb0991SDimitry Andric continue;
7518bcb0991SDimitry Andric }
7528bcb0991SDimitry Andric unsigned realUses = 0;
753349cc55cSDimitry Andric for (const MachineOperand &U : MRI.use_operands(reg)) {
7548bcb0991SDimitry Andric // Check if there are any uses that occur only in the original
7558bcb0991SDimitry Andric // loop. If so, that's not a real use.
756349cc55cSDimitry Andric if (U.getParent()->getParent() != BB) {
7578bcb0991SDimitry Andric realUses++;
7588bcb0991SDimitry Andric used = true;
7598bcb0991SDimitry Andric break;
7608bcb0991SDimitry Andric }
7618bcb0991SDimitry Andric }
7628bcb0991SDimitry Andric if (realUses > 0)
7638bcb0991SDimitry Andric break;
7648bcb0991SDimitry Andric used = false;
7658bcb0991SDimitry Andric }
7668bcb0991SDimitry Andric if (!used) {
7678bcb0991SDimitry Andric LIS.RemoveMachineInstrFromMaps(*MI);
7688bcb0991SDimitry Andric MI++->eraseFromParent();
7698bcb0991SDimitry Andric continue;
7708bcb0991SDimitry Andric }
7718bcb0991SDimitry Andric ++MI;
7728bcb0991SDimitry Andric }
7738bcb0991SDimitry Andric // In the kernel block, check if we can remove a Phi that generates a value
7748bcb0991SDimitry Andric // used in an instruction removed in the epilog block.
775349cc55cSDimitry Andric for (MachineInstr &MI : llvm::make_early_inc_range(KernelBB->phis())) {
776349cc55cSDimitry Andric Register reg = MI.getOperand(0).getReg();
7778bcb0991SDimitry Andric if (MRI.use_begin(reg) == MRI.use_end()) {
778349cc55cSDimitry Andric LIS.RemoveMachineInstrFromMaps(MI);
779349cc55cSDimitry Andric MI.eraseFromParent();
7808bcb0991SDimitry Andric }
7818bcb0991SDimitry Andric }
7828bcb0991SDimitry Andric }
7838bcb0991SDimitry Andric
7848bcb0991SDimitry Andric /// For loop carried definitions, we split the lifetime of a virtual register
7858bcb0991SDimitry Andric /// that has uses past the definition in the next iteration. A copy with a new
7868bcb0991SDimitry Andric /// virtual register is inserted before the definition, which helps with
7878bcb0991SDimitry Andric /// generating a better register assignment.
7888bcb0991SDimitry Andric ///
7898bcb0991SDimitry Andric /// v1 = phi(a, v2) v1 = phi(a, v2)
7908bcb0991SDimitry Andric /// v2 = phi(b, v3) v2 = phi(b, v3)
7918bcb0991SDimitry Andric /// v3 = .. v4 = copy v1
7928bcb0991SDimitry Andric /// .. = V1 v3 = ..
7938bcb0991SDimitry Andric /// .. = v4
splitLifetimes(MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs)7948bcb0991SDimitry Andric void ModuloScheduleExpander::splitLifetimes(MachineBasicBlock *KernelBB,
7958bcb0991SDimitry Andric MBBVectorTy &EpilogBBs) {
7968bcb0991SDimitry Andric const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
7978bcb0991SDimitry Andric for (auto &PHI : KernelBB->phis()) {
7988bcb0991SDimitry Andric Register Def = PHI.getOperand(0).getReg();
7998bcb0991SDimitry Andric // Check for any Phi definition that used as an operand of another Phi
8008bcb0991SDimitry Andric // in the same block.
8018bcb0991SDimitry Andric for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(Def),
8028bcb0991SDimitry Andric E = MRI.use_instr_end();
8038bcb0991SDimitry Andric I != E; ++I) {
8048bcb0991SDimitry Andric if (I->isPHI() && I->getParent() == KernelBB) {
8058bcb0991SDimitry Andric // Get the loop carried definition.
8068bcb0991SDimitry Andric unsigned LCDef = getLoopPhiReg(PHI, KernelBB);
8078bcb0991SDimitry Andric if (!LCDef)
8088bcb0991SDimitry Andric continue;
8098bcb0991SDimitry Andric MachineInstr *MI = MRI.getVRegDef(LCDef);
8108bcb0991SDimitry Andric if (!MI || MI->getParent() != KernelBB || MI->isPHI())
8118bcb0991SDimitry Andric continue;
8128bcb0991SDimitry Andric // Search through the rest of the block looking for uses of the Phi
8138bcb0991SDimitry Andric // definition. If one occurs, then split the lifetime.
8148bcb0991SDimitry Andric unsigned SplitReg = 0;
8158bcb0991SDimitry Andric for (auto &BBJ : make_range(MachineBasicBlock::instr_iterator(MI),
8168bcb0991SDimitry Andric KernelBB->instr_end()))
8178bcb0991SDimitry Andric if (BBJ.readsRegister(Def)) {
8188bcb0991SDimitry Andric // We split the lifetime when we find the first use.
8198bcb0991SDimitry Andric if (SplitReg == 0) {
8208bcb0991SDimitry Andric SplitReg = MRI.createVirtualRegister(MRI.getRegClass(Def));
8218bcb0991SDimitry Andric BuildMI(*KernelBB, MI, MI->getDebugLoc(),
8228bcb0991SDimitry Andric TII->get(TargetOpcode::COPY), SplitReg)
8238bcb0991SDimitry Andric .addReg(Def);
8248bcb0991SDimitry Andric }
8258bcb0991SDimitry Andric BBJ.substituteRegister(Def, SplitReg, 0, *TRI);
8268bcb0991SDimitry Andric }
8278bcb0991SDimitry Andric if (!SplitReg)
8288bcb0991SDimitry Andric continue;
8298bcb0991SDimitry Andric // Search through each of the epilog blocks for any uses to be renamed.
8308bcb0991SDimitry Andric for (auto &Epilog : EpilogBBs)
8318bcb0991SDimitry Andric for (auto &I : *Epilog)
8328bcb0991SDimitry Andric if (I.readsRegister(Def))
8338bcb0991SDimitry Andric I.substituteRegister(Def, SplitReg, 0, *TRI);
8348bcb0991SDimitry Andric break;
8358bcb0991SDimitry Andric }
8368bcb0991SDimitry Andric }
8378bcb0991SDimitry Andric }
8388bcb0991SDimitry Andric }
8398bcb0991SDimitry Andric
8408bcb0991SDimitry Andric /// Remove the incoming block from the Phis in a basic block.
removePhis(MachineBasicBlock * BB,MachineBasicBlock * Incoming)8418bcb0991SDimitry Andric static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming) {
8428bcb0991SDimitry Andric for (MachineInstr &MI : *BB) {
8438bcb0991SDimitry Andric if (!MI.isPHI())
8448bcb0991SDimitry Andric break;
8458bcb0991SDimitry Andric for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2)
8468bcb0991SDimitry Andric if (MI.getOperand(i + 1).getMBB() == Incoming) {
84781ad6265SDimitry Andric MI.removeOperand(i + 1);
84881ad6265SDimitry Andric MI.removeOperand(i);
8498bcb0991SDimitry Andric break;
8508bcb0991SDimitry Andric }
8518bcb0991SDimitry Andric }
8528bcb0991SDimitry Andric }
8538bcb0991SDimitry Andric
8548bcb0991SDimitry Andric /// Create branches from each prolog basic block to the appropriate epilog
8558bcb0991SDimitry Andric /// block. These edges are needed if the loop ends before reaching the
8568bcb0991SDimitry Andric /// kernel.
addBranches(MachineBasicBlock & PreheaderBB,MBBVectorTy & PrologBBs,MachineBasicBlock * KernelBB,MBBVectorTy & EpilogBBs,ValueMapTy * VRMap)8578bcb0991SDimitry Andric void ModuloScheduleExpander::addBranches(MachineBasicBlock &PreheaderBB,
8588bcb0991SDimitry Andric MBBVectorTy &PrologBBs,
8598bcb0991SDimitry Andric MachineBasicBlock *KernelBB,
8608bcb0991SDimitry Andric MBBVectorTy &EpilogBBs,
8618bcb0991SDimitry Andric ValueMapTy *VRMap) {
8628bcb0991SDimitry Andric assert(PrologBBs.size() == EpilogBBs.size() && "Prolog/Epilog mismatch");
8638bcb0991SDimitry Andric MachineBasicBlock *LastPro = KernelBB;
8648bcb0991SDimitry Andric MachineBasicBlock *LastEpi = KernelBB;
8658bcb0991SDimitry Andric
8668bcb0991SDimitry Andric // Start from the blocks connected to the kernel and work "out"
8678bcb0991SDimitry Andric // to the first prolog and the last epilog blocks.
8688bcb0991SDimitry Andric SmallVector<MachineInstr *, 4> PrevInsts;
8698bcb0991SDimitry Andric unsigned MaxIter = PrologBBs.size() - 1;
8708bcb0991SDimitry Andric for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) {
8718bcb0991SDimitry Andric // Add branches to the prolog that go to the corresponding
8728bcb0991SDimitry Andric // epilog, and the fall-thru prolog/kernel block.
8738bcb0991SDimitry Andric MachineBasicBlock *Prolog = PrologBBs[j];
8748bcb0991SDimitry Andric MachineBasicBlock *Epilog = EpilogBBs[i];
8758bcb0991SDimitry Andric
8768bcb0991SDimitry Andric SmallVector<MachineOperand, 4> Cond;
877bdd1243dSDimitry Andric std::optional<bool> StaticallyGreater =
8788bcb0991SDimitry Andric LoopInfo->createTripCountGreaterCondition(j + 1, *Prolog, Cond);
8798bcb0991SDimitry Andric unsigned numAdded = 0;
88081ad6265SDimitry Andric if (!StaticallyGreater) {
8818bcb0991SDimitry Andric Prolog->addSuccessor(Epilog);
8828bcb0991SDimitry Andric numAdded = TII->insertBranch(*Prolog, Epilog, LastPro, Cond, DebugLoc());
8838bcb0991SDimitry Andric } else if (*StaticallyGreater == false) {
8848bcb0991SDimitry Andric Prolog->addSuccessor(Epilog);
8858bcb0991SDimitry Andric Prolog->removeSuccessor(LastPro);
8868bcb0991SDimitry Andric LastEpi->removeSuccessor(Epilog);
8878bcb0991SDimitry Andric numAdded = TII->insertBranch(*Prolog, Epilog, nullptr, Cond, DebugLoc());
8888bcb0991SDimitry Andric removePhis(Epilog, LastEpi);
8898bcb0991SDimitry Andric // Remove the blocks that are no longer referenced.
8908bcb0991SDimitry Andric if (LastPro != LastEpi) {
8918bcb0991SDimitry Andric LastEpi->clear();
8928bcb0991SDimitry Andric LastEpi->eraseFromParent();
8938bcb0991SDimitry Andric }
8948bcb0991SDimitry Andric if (LastPro == KernelBB) {
8958bcb0991SDimitry Andric LoopInfo->disposed();
8968bcb0991SDimitry Andric NewKernel = nullptr;
8978bcb0991SDimitry Andric }
8988bcb0991SDimitry Andric LastPro->clear();
8998bcb0991SDimitry Andric LastPro->eraseFromParent();
9008bcb0991SDimitry Andric } else {
9018bcb0991SDimitry Andric numAdded = TII->insertBranch(*Prolog, LastPro, nullptr, Cond, DebugLoc());
9028bcb0991SDimitry Andric removePhis(Epilog, Prolog);
9038bcb0991SDimitry Andric }
9048bcb0991SDimitry Andric LastPro = Prolog;
9058bcb0991SDimitry Andric LastEpi = Epilog;
9068bcb0991SDimitry Andric for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(),
9078bcb0991SDimitry Andric E = Prolog->instr_rend();
9088bcb0991SDimitry Andric I != E && numAdded > 0; ++I, --numAdded)
9098bcb0991SDimitry Andric updateInstruction(&*I, false, j, 0, VRMap);
9108bcb0991SDimitry Andric }
9118bcb0991SDimitry Andric
9128bcb0991SDimitry Andric if (NewKernel) {
9138bcb0991SDimitry Andric LoopInfo->setPreheader(PrologBBs[MaxIter]);
9148bcb0991SDimitry Andric LoopInfo->adjustTripCount(-(MaxIter + 1));
9158bcb0991SDimitry Andric }
9168bcb0991SDimitry Andric }
9178bcb0991SDimitry Andric
9188bcb0991SDimitry Andric /// Return true if we can compute the amount the instruction changes
9198bcb0991SDimitry Andric /// during each iteration. Set Delta to the amount of the change.
computeDelta(MachineInstr & MI,unsigned & Delta)9208bcb0991SDimitry Andric bool ModuloScheduleExpander::computeDelta(MachineInstr &MI, unsigned &Delta) {
9218bcb0991SDimitry Andric const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
9228bcb0991SDimitry Andric const MachineOperand *BaseOp;
9238bcb0991SDimitry Andric int64_t Offset;
9245ffd83dbSDimitry Andric bool OffsetIsScalable;
9255ffd83dbSDimitry Andric if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
9265ffd83dbSDimitry Andric return false;
9275ffd83dbSDimitry Andric
9285ffd83dbSDimitry Andric // FIXME: This algorithm assumes instructions have fixed-size offsets.
9295ffd83dbSDimitry Andric if (OffsetIsScalable)
9308bcb0991SDimitry Andric return false;
9318bcb0991SDimitry Andric
9328bcb0991SDimitry Andric if (!BaseOp->isReg())
9338bcb0991SDimitry Andric return false;
9348bcb0991SDimitry Andric
9358bcb0991SDimitry Andric Register BaseReg = BaseOp->getReg();
9368bcb0991SDimitry Andric
9378bcb0991SDimitry Andric MachineRegisterInfo &MRI = MF.getRegInfo();
9388bcb0991SDimitry Andric // Check if there is a Phi. If so, get the definition in the loop.
9398bcb0991SDimitry Andric MachineInstr *BaseDef = MRI.getVRegDef(BaseReg);
9408bcb0991SDimitry Andric if (BaseDef && BaseDef->isPHI()) {
9418bcb0991SDimitry Andric BaseReg = getLoopPhiReg(*BaseDef, MI.getParent());
9428bcb0991SDimitry Andric BaseDef = MRI.getVRegDef(BaseReg);
9438bcb0991SDimitry Andric }
9448bcb0991SDimitry Andric if (!BaseDef)
9458bcb0991SDimitry Andric return false;
9468bcb0991SDimitry Andric
9478bcb0991SDimitry Andric int D = 0;
9488bcb0991SDimitry Andric if (!TII->getIncrementValue(*BaseDef, D) && D >= 0)
9498bcb0991SDimitry Andric return false;
9508bcb0991SDimitry Andric
9518bcb0991SDimitry Andric Delta = D;
9528bcb0991SDimitry Andric return true;
9538bcb0991SDimitry Andric }
9548bcb0991SDimitry Andric
9558bcb0991SDimitry Andric /// Update the memory operand with a new offset when the pipeliner
9568bcb0991SDimitry Andric /// generates a new copy of the instruction that refers to a
9578bcb0991SDimitry Andric /// different memory location.
updateMemOperands(MachineInstr & NewMI,MachineInstr & OldMI,unsigned Num)9588bcb0991SDimitry Andric void ModuloScheduleExpander::updateMemOperands(MachineInstr &NewMI,
9598bcb0991SDimitry Andric MachineInstr &OldMI,
9608bcb0991SDimitry Andric unsigned Num) {
9618bcb0991SDimitry Andric if (Num == 0)
9628bcb0991SDimitry Andric return;
9638bcb0991SDimitry Andric // If the instruction has memory operands, then adjust the offset
9648bcb0991SDimitry Andric // when the instruction appears in different stages.
9658bcb0991SDimitry Andric if (NewMI.memoperands_empty())
9668bcb0991SDimitry Andric return;
9678bcb0991SDimitry Andric SmallVector<MachineMemOperand *, 2> NewMMOs;
9688bcb0991SDimitry Andric for (MachineMemOperand *MMO : NewMI.memoperands()) {
9698bcb0991SDimitry Andric // TODO: Figure out whether isAtomic is really necessary (see D57601).
9708bcb0991SDimitry Andric if (MMO->isVolatile() || MMO->isAtomic() ||
9718bcb0991SDimitry Andric (MMO->isInvariant() && MMO->isDereferenceable()) ||
9728bcb0991SDimitry Andric (!MMO->getValue())) {
9738bcb0991SDimitry Andric NewMMOs.push_back(MMO);
9748bcb0991SDimitry Andric continue;
9758bcb0991SDimitry Andric }
9768bcb0991SDimitry Andric unsigned Delta;
9778bcb0991SDimitry Andric if (Num != UINT_MAX && computeDelta(OldMI, Delta)) {
9788bcb0991SDimitry Andric int64_t AdjOffset = Delta * Num;
9798bcb0991SDimitry Andric NewMMOs.push_back(
9808bcb0991SDimitry Andric MF.getMachineMemOperand(MMO, AdjOffset, MMO->getSize()));
9818bcb0991SDimitry Andric } else {
9828bcb0991SDimitry Andric NewMMOs.push_back(
9838bcb0991SDimitry Andric MF.getMachineMemOperand(MMO, 0, MemoryLocation::UnknownSize));
9848bcb0991SDimitry Andric }
9858bcb0991SDimitry Andric }
9868bcb0991SDimitry Andric NewMI.setMemRefs(MF, NewMMOs);
9878bcb0991SDimitry Andric }
9888bcb0991SDimitry Andric
9898bcb0991SDimitry Andric /// Clone the instruction for the new pipelined loop and update the
9908bcb0991SDimitry Andric /// memory operands, if needed.
cloneInstr(MachineInstr * OldMI,unsigned CurStageNum,unsigned InstStageNum)9918bcb0991SDimitry Andric MachineInstr *ModuloScheduleExpander::cloneInstr(MachineInstr *OldMI,
9928bcb0991SDimitry Andric unsigned CurStageNum,
9938bcb0991SDimitry Andric unsigned InstStageNum) {
9948bcb0991SDimitry Andric MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);
9958bcb0991SDimitry Andric updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
9968bcb0991SDimitry Andric return NewMI;
9978bcb0991SDimitry Andric }
9988bcb0991SDimitry Andric
9998bcb0991SDimitry Andric /// Clone the instruction for the new pipelined loop. If needed, this
10008bcb0991SDimitry Andric /// function updates the instruction using the values saved in the
10018bcb0991SDimitry Andric /// InstrChanges structure.
cloneAndChangeInstr(MachineInstr * OldMI,unsigned CurStageNum,unsigned InstStageNum)10028bcb0991SDimitry Andric MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
10038bcb0991SDimitry Andric MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum) {
10048bcb0991SDimitry Andric MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);
10058bcb0991SDimitry Andric auto It = InstrChanges.find(OldMI);
10068bcb0991SDimitry Andric if (It != InstrChanges.end()) {
10078bcb0991SDimitry Andric std::pair<unsigned, int64_t> RegAndOffset = It->second;
10088bcb0991SDimitry Andric unsigned BasePos, OffsetPos;
10098bcb0991SDimitry Andric if (!TII->getBaseAndOffsetPosition(*OldMI, BasePos, OffsetPos))
10108bcb0991SDimitry Andric return nullptr;
10118bcb0991SDimitry Andric int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm();
10128bcb0991SDimitry Andric MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first);
10138bcb0991SDimitry Andric if (Schedule.getStage(LoopDef) > (signed)InstStageNum)
10148bcb0991SDimitry Andric NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
10158bcb0991SDimitry Andric NewMI->getOperand(OffsetPos).setImm(NewOffset);
10168bcb0991SDimitry Andric }
10178bcb0991SDimitry Andric updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
10188bcb0991SDimitry Andric return NewMI;
10198bcb0991SDimitry Andric }
10208bcb0991SDimitry Andric
10218bcb0991SDimitry Andric /// Update the machine instruction with new virtual registers. This
102281ad6265SDimitry Andric /// function may change the definitions and/or uses.
updateInstruction(MachineInstr * NewMI,bool LastDef,unsigned CurStageNum,unsigned InstrStageNum,ValueMapTy * VRMap)10238bcb0991SDimitry Andric void ModuloScheduleExpander::updateInstruction(MachineInstr *NewMI,
10248bcb0991SDimitry Andric bool LastDef,
10258bcb0991SDimitry Andric unsigned CurStageNum,
10268bcb0991SDimitry Andric unsigned InstrStageNum,
10278bcb0991SDimitry Andric ValueMapTy *VRMap) {
10284824e7fdSDimitry Andric for (MachineOperand &MO : NewMI->operands()) {
1029bdd1243dSDimitry Andric if (!MO.isReg() || !MO.getReg().isVirtual())
10308bcb0991SDimitry Andric continue;
10318bcb0991SDimitry Andric Register reg = MO.getReg();
10328bcb0991SDimitry Andric if (MO.isDef()) {
10338bcb0991SDimitry Andric // Create a new virtual register for the definition.
10348bcb0991SDimitry Andric const TargetRegisterClass *RC = MRI.getRegClass(reg);
10358bcb0991SDimitry Andric Register NewReg = MRI.createVirtualRegister(RC);
10368bcb0991SDimitry Andric MO.setReg(NewReg);
10378bcb0991SDimitry Andric VRMap[CurStageNum][reg] = NewReg;
10388bcb0991SDimitry Andric if (LastDef)
10398bcb0991SDimitry Andric replaceRegUsesAfterLoop(reg, NewReg, BB, MRI, LIS);
10408bcb0991SDimitry Andric } else if (MO.isUse()) {
10418bcb0991SDimitry Andric MachineInstr *Def = MRI.getVRegDef(reg);
10428bcb0991SDimitry Andric // Compute the stage that contains the last definition for instruction.
10438bcb0991SDimitry Andric int DefStageNum = Schedule.getStage(Def);
10448bcb0991SDimitry Andric unsigned StageNum = CurStageNum;
10458bcb0991SDimitry Andric if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) {
10468bcb0991SDimitry Andric // Compute the difference in stages between the defintion and the use.
10478bcb0991SDimitry Andric unsigned StageDiff = (InstrStageNum - DefStageNum);
10488bcb0991SDimitry Andric // Make an adjustment to get the last definition.
10498bcb0991SDimitry Andric StageNum -= StageDiff;
10508bcb0991SDimitry Andric }
10518bcb0991SDimitry Andric if (VRMap[StageNum].count(reg))
10528bcb0991SDimitry Andric MO.setReg(VRMap[StageNum][reg]);
10538bcb0991SDimitry Andric }
10548bcb0991SDimitry Andric }
10558bcb0991SDimitry Andric }
10568bcb0991SDimitry Andric
10578bcb0991SDimitry Andric /// Return the instruction in the loop that defines the register.
10588bcb0991SDimitry Andric /// If the definition is a Phi, then follow the Phi operand to
10598bcb0991SDimitry Andric /// the instruction in the loop.
findDefInLoop(unsigned Reg)10608bcb0991SDimitry Andric MachineInstr *ModuloScheduleExpander::findDefInLoop(unsigned Reg) {
10618bcb0991SDimitry Andric SmallPtrSet<MachineInstr *, 8> Visited;
10628bcb0991SDimitry Andric MachineInstr *Def = MRI.getVRegDef(Reg);
10638bcb0991SDimitry Andric while (Def->isPHI()) {
10648bcb0991SDimitry Andric if (!Visited.insert(Def).second)
10658bcb0991SDimitry Andric break;
10668bcb0991SDimitry Andric for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
10678bcb0991SDimitry Andric if (Def->getOperand(i + 1).getMBB() == BB) {
10688bcb0991SDimitry Andric Def = MRI.getVRegDef(Def->getOperand(i).getReg());
10698bcb0991SDimitry Andric break;
10708bcb0991SDimitry Andric }
10718bcb0991SDimitry Andric }
10728bcb0991SDimitry Andric return Def;
10738bcb0991SDimitry Andric }
10748bcb0991SDimitry Andric
10758bcb0991SDimitry Andric /// Return the new name for the value from the previous stage.
getPrevMapVal(unsigned StageNum,unsigned PhiStage,unsigned LoopVal,unsigned LoopStage,ValueMapTy * VRMap,MachineBasicBlock * BB)10768bcb0991SDimitry Andric unsigned ModuloScheduleExpander::getPrevMapVal(
10778bcb0991SDimitry Andric unsigned StageNum, unsigned PhiStage, unsigned LoopVal, unsigned LoopStage,
10788bcb0991SDimitry Andric ValueMapTy *VRMap, MachineBasicBlock *BB) {
10798bcb0991SDimitry Andric unsigned PrevVal = 0;
10808bcb0991SDimitry Andric if (StageNum > PhiStage) {
10818bcb0991SDimitry Andric MachineInstr *LoopInst = MRI.getVRegDef(LoopVal);
10828bcb0991SDimitry Andric if (PhiStage == LoopStage && VRMap[StageNum - 1].count(LoopVal))
10838bcb0991SDimitry Andric // The name is defined in the previous stage.
10848bcb0991SDimitry Andric PrevVal = VRMap[StageNum - 1][LoopVal];
10858bcb0991SDimitry Andric else if (VRMap[StageNum].count(LoopVal))
10868bcb0991SDimitry Andric // The previous name is defined in the current stage when the instruction
10878bcb0991SDimitry Andric // order is swapped.
10888bcb0991SDimitry Andric PrevVal = VRMap[StageNum][LoopVal];
10898bcb0991SDimitry Andric else if (!LoopInst->isPHI() || LoopInst->getParent() != BB)
10908bcb0991SDimitry Andric // The loop value hasn't yet been scheduled.
10918bcb0991SDimitry Andric PrevVal = LoopVal;
10928bcb0991SDimitry Andric else if (StageNum == PhiStage + 1)
10938bcb0991SDimitry Andric // The loop value is another phi, which has not been scheduled.
10948bcb0991SDimitry Andric PrevVal = getInitPhiReg(*LoopInst, BB);
10958bcb0991SDimitry Andric else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB)
10968bcb0991SDimitry Andric // The loop value is another phi, which has been scheduled.
10978bcb0991SDimitry Andric PrevVal =
10988bcb0991SDimitry Andric getPrevMapVal(StageNum - 1, PhiStage, getLoopPhiReg(*LoopInst, BB),
10998bcb0991SDimitry Andric LoopStage, VRMap, BB);
11008bcb0991SDimitry Andric }
11018bcb0991SDimitry Andric return PrevVal;
11028bcb0991SDimitry Andric }
11038bcb0991SDimitry Andric
11048bcb0991SDimitry Andric /// Rewrite the Phi values in the specified block to use the mappings
11058bcb0991SDimitry Andric /// from the initial operand. Once the Phi is scheduled, we switch
11068bcb0991SDimitry Andric /// to using the loop value instead of the Phi value, so those names
11078bcb0991SDimitry Andric /// do not need to be rewritten.
rewritePhiValues(MachineBasicBlock * NewBB,unsigned StageNum,ValueMapTy * VRMap,InstrMapTy & InstrMap)11088bcb0991SDimitry Andric void ModuloScheduleExpander::rewritePhiValues(MachineBasicBlock *NewBB,
11098bcb0991SDimitry Andric unsigned StageNum,
11108bcb0991SDimitry Andric ValueMapTy *VRMap,
11118bcb0991SDimitry Andric InstrMapTy &InstrMap) {
11128bcb0991SDimitry Andric for (auto &PHI : BB->phis()) {
11138bcb0991SDimitry Andric unsigned InitVal = 0;
11148bcb0991SDimitry Andric unsigned LoopVal = 0;
11158bcb0991SDimitry Andric getPhiRegs(PHI, BB, InitVal, LoopVal);
11168bcb0991SDimitry Andric Register PhiDef = PHI.getOperand(0).getReg();
11178bcb0991SDimitry Andric
11188bcb0991SDimitry Andric unsigned PhiStage = (unsigned)Schedule.getStage(MRI.getVRegDef(PhiDef));
11198bcb0991SDimitry Andric unsigned LoopStage = (unsigned)Schedule.getStage(MRI.getVRegDef(LoopVal));
11208bcb0991SDimitry Andric unsigned NumPhis = getStagesForPhi(PhiDef);
11218bcb0991SDimitry Andric if (NumPhis > StageNum)
11228bcb0991SDimitry Andric NumPhis = StageNum;
11238bcb0991SDimitry Andric for (unsigned np = 0; np <= NumPhis; ++np) {
11248bcb0991SDimitry Andric unsigned NewVal =
11258bcb0991SDimitry Andric getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
11268bcb0991SDimitry Andric if (!NewVal)
11278bcb0991SDimitry Andric NewVal = InitVal;
11288bcb0991SDimitry Andric rewriteScheduledInstr(NewBB, InstrMap, StageNum - np, np, &PHI, PhiDef,
11298bcb0991SDimitry Andric NewVal);
11308bcb0991SDimitry Andric }
11318bcb0991SDimitry Andric }
11328bcb0991SDimitry Andric }
11338bcb0991SDimitry Andric
11348bcb0991SDimitry Andric /// Rewrite a previously scheduled instruction to use the register value
11358bcb0991SDimitry Andric /// from the new instruction. Make sure the instruction occurs in the
11368bcb0991SDimitry Andric /// 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)11378bcb0991SDimitry Andric void ModuloScheduleExpander::rewriteScheduledInstr(
11388bcb0991SDimitry Andric MachineBasicBlock *BB, InstrMapTy &InstrMap, unsigned CurStageNum,
11398bcb0991SDimitry Andric unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, unsigned NewReg,
11408bcb0991SDimitry Andric unsigned PrevReg) {
11418bcb0991SDimitry Andric bool InProlog = (CurStageNum < (unsigned)Schedule.getNumStages() - 1);
11428bcb0991SDimitry Andric int StagePhi = Schedule.getStage(Phi) + PhiNum;
11438bcb0991SDimitry Andric // Rewrite uses that have been scheduled already to use the new
11448bcb0991SDimitry Andric // Phi register.
1145349cc55cSDimitry Andric for (MachineOperand &UseOp :
1146349cc55cSDimitry Andric llvm::make_early_inc_range(MRI.use_operands(OldReg))) {
11478bcb0991SDimitry Andric MachineInstr *UseMI = UseOp.getParent();
11488bcb0991SDimitry Andric if (UseMI->getParent() != BB)
11498bcb0991SDimitry Andric continue;
11508bcb0991SDimitry Andric if (UseMI->isPHI()) {
11518bcb0991SDimitry Andric if (!Phi->isPHI() && UseMI->getOperand(0).getReg() == NewReg)
11528bcb0991SDimitry Andric continue;
11538bcb0991SDimitry Andric if (getLoopPhiReg(*UseMI, BB) != OldReg)
11548bcb0991SDimitry Andric continue;
11558bcb0991SDimitry Andric }
11568bcb0991SDimitry Andric InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI);
11578bcb0991SDimitry Andric assert(OrigInstr != InstrMap.end() && "Instruction not scheduled.");
11588bcb0991SDimitry Andric MachineInstr *OrigMI = OrigInstr->second;
11598bcb0991SDimitry Andric int StageSched = Schedule.getStage(OrigMI);
11608bcb0991SDimitry Andric int CycleSched = Schedule.getCycle(OrigMI);
11618bcb0991SDimitry Andric unsigned ReplaceReg = 0;
11628bcb0991SDimitry Andric // This is the stage for the scheduled instruction.
11638bcb0991SDimitry Andric if (StagePhi == StageSched && Phi->isPHI()) {
11648bcb0991SDimitry Andric int CyclePhi = Schedule.getCycle(Phi);
11658bcb0991SDimitry Andric if (PrevReg && InProlog)
11668bcb0991SDimitry Andric ReplaceReg = PrevReg;
11678bcb0991SDimitry Andric else if (PrevReg && !isLoopCarried(*Phi) &&
11688bcb0991SDimitry Andric (CyclePhi <= CycleSched || OrigMI->isPHI()))
11698bcb0991SDimitry Andric ReplaceReg = PrevReg;
11708bcb0991SDimitry Andric else
11718bcb0991SDimitry Andric ReplaceReg = NewReg;
11728bcb0991SDimitry Andric }
11738bcb0991SDimitry Andric // The scheduled instruction occurs before the scheduled Phi, and the
11748bcb0991SDimitry Andric // Phi is not loop carried.
11758bcb0991SDimitry Andric if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(*Phi))
11768bcb0991SDimitry Andric ReplaceReg = NewReg;
11778bcb0991SDimitry Andric if (StagePhi > StageSched && Phi->isPHI())
11788bcb0991SDimitry Andric ReplaceReg = NewReg;
11798bcb0991SDimitry Andric if (!InProlog && !Phi->isPHI() && StagePhi < StageSched)
11808bcb0991SDimitry Andric ReplaceReg = NewReg;
11818bcb0991SDimitry Andric if (ReplaceReg) {
118281ad6265SDimitry Andric const TargetRegisterClass *NRC =
11838bcb0991SDimitry Andric MRI.constrainRegClass(ReplaceReg, MRI.getRegClass(OldReg));
118481ad6265SDimitry Andric if (NRC)
11858bcb0991SDimitry Andric UseOp.setReg(ReplaceReg);
118681ad6265SDimitry Andric else {
118781ad6265SDimitry Andric Register SplitReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
118881ad6265SDimitry Andric BuildMI(*BB, UseMI, UseMI->getDebugLoc(), TII->get(TargetOpcode::COPY),
118981ad6265SDimitry Andric SplitReg)
119081ad6265SDimitry Andric .addReg(ReplaceReg);
119181ad6265SDimitry Andric UseOp.setReg(SplitReg);
119281ad6265SDimitry Andric }
11938bcb0991SDimitry Andric }
11948bcb0991SDimitry Andric }
11958bcb0991SDimitry Andric }
11968bcb0991SDimitry Andric
isLoopCarried(MachineInstr & Phi)11978bcb0991SDimitry Andric bool ModuloScheduleExpander::isLoopCarried(MachineInstr &Phi) {
11988bcb0991SDimitry Andric if (!Phi.isPHI())
11998bcb0991SDimitry Andric return false;
1200480093f4SDimitry Andric int DefCycle = Schedule.getCycle(&Phi);
12018bcb0991SDimitry Andric int DefStage = Schedule.getStage(&Phi);
12028bcb0991SDimitry Andric
12038bcb0991SDimitry Andric unsigned InitVal = 0;
12048bcb0991SDimitry Andric unsigned LoopVal = 0;
12058bcb0991SDimitry Andric getPhiRegs(Phi, Phi.getParent(), InitVal, LoopVal);
12068bcb0991SDimitry Andric MachineInstr *Use = MRI.getVRegDef(LoopVal);
12078bcb0991SDimitry Andric if (!Use || Use->isPHI())
12088bcb0991SDimitry Andric return true;
1209480093f4SDimitry Andric int LoopCycle = Schedule.getCycle(Use);
12108bcb0991SDimitry Andric int LoopStage = Schedule.getStage(Use);
12118bcb0991SDimitry Andric return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
12128bcb0991SDimitry Andric }
12138bcb0991SDimitry Andric
12148bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
12158bcb0991SDimitry Andric // PeelingModuloScheduleExpander implementation
12168bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
12178bcb0991SDimitry Andric // This is a reimplementation of ModuloScheduleExpander that works by creating
12188bcb0991SDimitry Andric // a fully correct steady-state kernel and peeling off the prolog and epilogs.
12198bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
12208bcb0991SDimitry Andric
12218bcb0991SDimitry Andric namespace {
12228bcb0991SDimitry Andric // Remove any dead phis in MBB. Dead phis either have only one block as input
12238bcb0991SDimitry Andric // (in which case they are the identity) or have no uses.
EliminateDeadPhis(MachineBasicBlock * MBB,MachineRegisterInfo & MRI,LiveIntervals * LIS,bool KeepSingleSrcPhi=false)12248bcb0991SDimitry Andric void EliminateDeadPhis(MachineBasicBlock *MBB, MachineRegisterInfo &MRI,
1225480093f4SDimitry Andric LiveIntervals *LIS, bool KeepSingleSrcPhi = false) {
12268bcb0991SDimitry Andric bool Changed = true;
12278bcb0991SDimitry Andric while (Changed) {
12288bcb0991SDimitry Andric Changed = false;
1229349cc55cSDimitry Andric for (MachineInstr &MI : llvm::make_early_inc_range(MBB->phis())) {
12308bcb0991SDimitry Andric assert(MI.isPHI());
12318bcb0991SDimitry Andric if (MRI.use_empty(MI.getOperand(0).getReg())) {
12328bcb0991SDimitry Andric if (LIS)
12338bcb0991SDimitry Andric LIS->RemoveMachineInstrFromMaps(MI);
12348bcb0991SDimitry Andric MI.eraseFromParent();
12358bcb0991SDimitry Andric Changed = true;
1236480093f4SDimitry Andric } else if (!KeepSingleSrcPhi && MI.getNumExplicitOperands() == 3) {
123781ad6265SDimitry Andric const TargetRegisterClass *ConstrainRegClass =
12388bcb0991SDimitry Andric MRI.constrainRegClass(MI.getOperand(1).getReg(),
12398bcb0991SDimitry Andric MRI.getRegClass(MI.getOperand(0).getReg()));
124081ad6265SDimitry Andric assert(ConstrainRegClass &&
124181ad6265SDimitry Andric "Expected a valid constrained register class!");
124281ad6265SDimitry Andric (void)ConstrainRegClass;
12438bcb0991SDimitry Andric MRI.replaceRegWith(MI.getOperand(0).getReg(),
12448bcb0991SDimitry Andric MI.getOperand(1).getReg());
12458bcb0991SDimitry Andric if (LIS)
12468bcb0991SDimitry Andric LIS->RemoveMachineInstrFromMaps(MI);
12478bcb0991SDimitry Andric MI.eraseFromParent();
12488bcb0991SDimitry Andric Changed = true;
12498bcb0991SDimitry Andric }
12508bcb0991SDimitry Andric }
12518bcb0991SDimitry Andric }
12528bcb0991SDimitry Andric }
12538bcb0991SDimitry Andric
12548bcb0991SDimitry Andric /// Rewrites the kernel block in-place to adhere to the given schedule.
12558bcb0991SDimitry Andric /// KernelRewriter holds all of the state required to perform the rewriting.
12568bcb0991SDimitry Andric class KernelRewriter {
12578bcb0991SDimitry Andric ModuloSchedule &S;
12588bcb0991SDimitry Andric MachineBasicBlock *BB;
12598bcb0991SDimitry Andric MachineBasicBlock *PreheaderBB, *ExitBB;
12608bcb0991SDimitry Andric MachineRegisterInfo &MRI;
12618bcb0991SDimitry Andric const TargetInstrInfo *TII;
12628bcb0991SDimitry Andric LiveIntervals *LIS;
12638bcb0991SDimitry Andric
12648bcb0991SDimitry Andric // Map from register class to canonical undef register for that class.
12658bcb0991SDimitry Andric DenseMap<const TargetRegisterClass *, Register> Undefs;
12668bcb0991SDimitry Andric // Map from <LoopReg, InitReg> to phi register for all created phis. Note that
12678bcb0991SDimitry Andric // this map is only used when InitReg is non-undef.
12688bcb0991SDimitry Andric DenseMap<std::pair<unsigned, unsigned>, Register> Phis;
12698bcb0991SDimitry Andric // Map from LoopReg to phi register where the InitReg is undef.
12708bcb0991SDimitry Andric DenseMap<Register, Register> UndefPhis;
12718bcb0991SDimitry Andric
12728bcb0991SDimitry Andric // Reg is used by MI. Return the new register MI should use to adhere to the
12738bcb0991SDimitry Andric // schedule. Insert phis as necessary.
12748bcb0991SDimitry Andric Register remapUse(Register Reg, MachineInstr &MI);
12758bcb0991SDimitry Andric // Insert a phi that carries LoopReg from the loop body and InitReg otherwise.
12768bcb0991SDimitry Andric // If InitReg is not given it is chosen arbitrarily. It will either be undef
12778bcb0991SDimitry Andric // or will be chosen so as to share another phi.
1278bdd1243dSDimitry Andric Register phi(Register LoopReg, std::optional<Register> InitReg = {},
12798bcb0991SDimitry Andric const TargetRegisterClass *RC = nullptr);
12808bcb0991SDimitry Andric // Create an undef register of the given register class.
12818bcb0991SDimitry Andric Register undef(const TargetRegisterClass *RC);
12828bcb0991SDimitry Andric
12838bcb0991SDimitry Andric public:
1284fe6060f1SDimitry Andric KernelRewriter(MachineLoop &L, ModuloSchedule &S, MachineBasicBlock *LoopBB,
12858bcb0991SDimitry Andric LiveIntervals *LIS = nullptr);
12868bcb0991SDimitry Andric void rewrite();
12878bcb0991SDimitry Andric };
12888bcb0991SDimitry Andric } // namespace
12898bcb0991SDimitry Andric
KernelRewriter(MachineLoop & L,ModuloSchedule & S,MachineBasicBlock * LoopBB,LiveIntervals * LIS)12908bcb0991SDimitry Andric KernelRewriter::KernelRewriter(MachineLoop &L, ModuloSchedule &S,
1291fe6060f1SDimitry Andric MachineBasicBlock *LoopBB, LiveIntervals *LIS)
1292fe6060f1SDimitry Andric : S(S), BB(LoopBB), PreheaderBB(L.getLoopPreheader()),
12938bcb0991SDimitry Andric ExitBB(L.getExitBlock()), MRI(BB->getParent()->getRegInfo()),
12948bcb0991SDimitry Andric TII(BB->getParent()->getSubtarget().getInstrInfo()), LIS(LIS) {
12958bcb0991SDimitry Andric PreheaderBB = *BB->pred_begin();
12968bcb0991SDimitry Andric if (PreheaderBB == BB)
12978bcb0991SDimitry Andric PreheaderBB = *std::next(BB->pred_begin());
12988bcb0991SDimitry Andric }
12998bcb0991SDimitry Andric
rewrite()13008bcb0991SDimitry Andric void KernelRewriter::rewrite() {
13018bcb0991SDimitry Andric // Rearrange the loop to be in schedule order. Note that the schedule may
13028bcb0991SDimitry Andric // contain instructions that are not owned by the loop block (InstrChanges and
13038bcb0991SDimitry Andric // friends), so we gracefully handle unowned instructions and delete any
13048bcb0991SDimitry Andric // instructions that weren't in the schedule.
13058bcb0991SDimitry Andric auto InsertPt = BB->getFirstTerminator();
13068bcb0991SDimitry Andric MachineInstr *FirstMI = nullptr;
13078bcb0991SDimitry Andric for (MachineInstr *MI : S.getInstructions()) {
13088bcb0991SDimitry Andric if (MI->isPHI())
13098bcb0991SDimitry Andric continue;
13108bcb0991SDimitry Andric if (MI->getParent())
13118bcb0991SDimitry Andric MI->removeFromParent();
13128bcb0991SDimitry Andric BB->insert(InsertPt, MI);
13138bcb0991SDimitry Andric if (!FirstMI)
13148bcb0991SDimitry Andric FirstMI = MI;
13158bcb0991SDimitry Andric }
13168bcb0991SDimitry Andric assert(FirstMI && "Failed to find first MI in schedule");
13178bcb0991SDimitry Andric
13188bcb0991SDimitry Andric // At this point all of the scheduled instructions are between FirstMI
13198bcb0991SDimitry Andric // and the end of the block. Kill from the first non-phi to FirstMI.
13208bcb0991SDimitry Andric for (auto I = BB->getFirstNonPHI(); I != FirstMI->getIterator();) {
13218bcb0991SDimitry Andric if (LIS)
13228bcb0991SDimitry Andric LIS->RemoveMachineInstrFromMaps(*I);
13238bcb0991SDimitry Andric (I++)->eraseFromParent();
13248bcb0991SDimitry Andric }
13258bcb0991SDimitry Andric
13268bcb0991SDimitry Andric // Now remap every instruction in the loop.
13278bcb0991SDimitry Andric for (MachineInstr &MI : *BB) {
13288bcb0991SDimitry Andric if (MI.isPHI() || MI.isTerminator())
13298bcb0991SDimitry Andric continue;
13308bcb0991SDimitry Andric for (MachineOperand &MO : MI.uses()) {
13318bcb0991SDimitry Andric if (!MO.isReg() || MO.getReg().isPhysical() || MO.isImplicit())
13328bcb0991SDimitry Andric continue;
13338bcb0991SDimitry Andric Register Reg = remapUse(MO.getReg(), MI);
13348bcb0991SDimitry Andric MO.setReg(Reg);
13358bcb0991SDimitry Andric }
13368bcb0991SDimitry Andric }
13378bcb0991SDimitry Andric EliminateDeadPhis(BB, MRI, LIS);
13388bcb0991SDimitry Andric
13398bcb0991SDimitry Andric // Ensure a phi exists for all instructions that are either referenced by
13408bcb0991SDimitry Andric // an illegal phi or by an instruction outside the loop. This allows us to
13418bcb0991SDimitry Andric // treat remaps of these values the same as "normal" values that come from
13428bcb0991SDimitry Andric // loop-carried phis.
13438bcb0991SDimitry Andric for (auto MI = BB->getFirstNonPHI(); MI != BB->end(); ++MI) {
13448bcb0991SDimitry Andric if (MI->isPHI()) {
13458bcb0991SDimitry Andric Register R = MI->getOperand(0).getReg();
13468bcb0991SDimitry Andric phi(R);
13478bcb0991SDimitry Andric continue;
13488bcb0991SDimitry Andric }
13498bcb0991SDimitry Andric
13508bcb0991SDimitry Andric for (MachineOperand &Def : MI->defs()) {
13518bcb0991SDimitry Andric for (MachineInstr &MI : MRI.use_instructions(Def.getReg())) {
13528bcb0991SDimitry Andric if (MI.getParent() != BB) {
13538bcb0991SDimitry Andric phi(Def.getReg());
13548bcb0991SDimitry Andric break;
13558bcb0991SDimitry Andric }
13568bcb0991SDimitry Andric }
13578bcb0991SDimitry Andric }
13588bcb0991SDimitry Andric }
13598bcb0991SDimitry Andric }
13608bcb0991SDimitry Andric
remapUse(Register Reg,MachineInstr & MI)13618bcb0991SDimitry Andric Register KernelRewriter::remapUse(Register Reg, MachineInstr &MI) {
13628bcb0991SDimitry Andric MachineInstr *Producer = MRI.getUniqueVRegDef(Reg);
13638bcb0991SDimitry Andric if (!Producer)
13648bcb0991SDimitry Andric return Reg;
13658bcb0991SDimitry Andric
13668bcb0991SDimitry Andric int ConsumerStage = S.getStage(&MI);
13678bcb0991SDimitry Andric if (!Producer->isPHI()) {
13688bcb0991SDimitry Andric // Non-phi producers are simple to remap. Insert as many phis as the
13698bcb0991SDimitry Andric // difference between the consumer and producer stages.
13708bcb0991SDimitry Andric if (Producer->getParent() != BB)
13718bcb0991SDimitry Andric // Producer was not inside the loop. Use the register as-is.
13728bcb0991SDimitry Andric return Reg;
13738bcb0991SDimitry Andric int ProducerStage = S.getStage(Producer);
13748bcb0991SDimitry Andric assert(ConsumerStage != -1 &&
13758bcb0991SDimitry Andric "In-loop consumer should always be scheduled!");
13768bcb0991SDimitry Andric assert(ConsumerStage >= ProducerStage);
13778bcb0991SDimitry Andric unsigned StageDiff = ConsumerStage - ProducerStage;
13788bcb0991SDimitry Andric
13798bcb0991SDimitry Andric for (unsigned I = 0; I < StageDiff; ++I)
13808bcb0991SDimitry Andric Reg = phi(Reg);
13818bcb0991SDimitry Andric return Reg;
13828bcb0991SDimitry Andric }
13838bcb0991SDimitry Andric
13848bcb0991SDimitry Andric // First, dive through the phi chain to find the defaults for the generated
13858bcb0991SDimitry Andric // phis.
1386bdd1243dSDimitry Andric SmallVector<std::optional<Register>, 4> Defaults;
13878bcb0991SDimitry Andric Register LoopReg = Reg;
13888bcb0991SDimitry Andric auto LoopProducer = Producer;
13898bcb0991SDimitry Andric while (LoopProducer->isPHI() && LoopProducer->getParent() == BB) {
13908bcb0991SDimitry Andric LoopReg = getLoopPhiReg(*LoopProducer, BB);
13918bcb0991SDimitry Andric Defaults.emplace_back(getInitPhiReg(*LoopProducer, BB));
13928bcb0991SDimitry Andric LoopProducer = MRI.getUniqueVRegDef(LoopReg);
13938bcb0991SDimitry Andric assert(LoopProducer);
13948bcb0991SDimitry Andric }
13958bcb0991SDimitry Andric int LoopProducerStage = S.getStage(LoopProducer);
13968bcb0991SDimitry Andric
1397bdd1243dSDimitry Andric std::optional<Register> IllegalPhiDefault;
13988bcb0991SDimitry Andric
13998bcb0991SDimitry Andric if (LoopProducerStage == -1) {
14008bcb0991SDimitry Andric // Do nothing.
14018bcb0991SDimitry Andric } else if (LoopProducerStage > ConsumerStage) {
14028bcb0991SDimitry Andric // This schedule is only representable if ProducerStage == ConsumerStage+1.
14038bcb0991SDimitry Andric // In addition, Consumer's cycle must be scheduled after Producer in the
14048bcb0991SDimitry Andric // rescheduled loop. This is enforced by the pipeliner's ASAP and ALAP
14058bcb0991SDimitry Andric // functions.
14068bcb0991SDimitry Andric #ifndef NDEBUG // Silence unused variables in non-asserts mode.
14078bcb0991SDimitry Andric int LoopProducerCycle = S.getCycle(LoopProducer);
14088bcb0991SDimitry Andric int ConsumerCycle = S.getCycle(&MI);
14098bcb0991SDimitry Andric #endif
14108bcb0991SDimitry Andric assert(LoopProducerCycle <= ConsumerCycle);
14118bcb0991SDimitry Andric assert(LoopProducerStage == ConsumerStage + 1);
14128bcb0991SDimitry Andric // Peel off the first phi from Defaults and insert a phi between producer
14138bcb0991SDimitry Andric // and consumer. This phi will not be at the front of the block so we
14148bcb0991SDimitry Andric // consider it illegal. It will only exist during the rewrite process; it
14158bcb0991SDimitry Andric // needs to exist while we peel off prologs because these could take the
14168bcb0991SDimitry Andric // default value. After that we can replace all uses with the loop producer
14178bcb0991SDimitry Andric // value.
14188bcb0991SDimitry Andric IllegalPhiDefault = Defaults.front();
14198bcb0991SDimitry Andric Defaults.erase(Defaults.begin());
14208bcb0991SDimitry Andric } else {
14218bcb0991SDimitry Andric assert(ConsumerStage >= LoopProducerStage);
14228bcb0991SDimitry Andric int StageDiff = ConsumerStage - LoopProducerStage;
14238bcb0991SDimitry Andric if (StageDiff > 0) {
14248bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << " -- padding defaults array from " << Defaults.size()
14258bcb0991SDimitry Andric << " to " << (Defaults.size() + StageDiff) << "\n");
14268bcb0991SDimitry Andric // If we need more phis than we have defaults for, pad out with undefs for
14278bcb0991SDimitry Andric // the earliest phis, which are at the end of the defaults chain (the
14288bcb0991SDimitry Andric // chain is in reverse order).
1429bdd1243dSDimitry Andric Defaults.resize(Defaults.size() + StageDiff,
1430bdd1243dSDimitry Andric Defaults.empty() ? std::optional<Register>()
14318bcb0991SDimitry Andric : Defaults.back());
14328bcb0991SDimitry Andric }
14338bcb0991SDimitry Andric }
14348bcb0991SDimitry Andric
14358bcb0991SDimitry Andric // Now we know the number of stages to jump back, insert the phi chain.
14368bcb0991SDimitry Andric auto DefaultI = Defaults.rbegin();
14378bcb0991SDimitry Andric while (DefaultI != Defaults.rend())
14388bcb0991SDimitry Andric LoopReg = phi(LoopReg, *DefaultI++, MRI.getRegClass(Reg));
14398bcb0991SDimitry Andric
144081ad6265SDimitry Andric if (IllegalPhiDefault) {
14418bcb0991SDimitry Andric // The consumer optionally consumes LoopProducer in the same iteration
14428bcb0991SDimitry Andric // (because the producer is scheduled at an earlier cycle than the consumer)
14438bcb0991SDimitry Andric // or the initial value. To facilitate this we create an illegal block here
14448bcb0991SDimitry Andric // by embedding a phi in the middle of the block. We will fix this up
14458bcb0991SDimitry Andric // immediately prior to pruning.
14468bcb0991SDimitry Andric auto RC = MRI.getRegClass(Reg);
14478bcb0991SDimitry Andric Register R = MRI.createVirtualRegister(RC);
14485ffd83dbSDimitry Andric MachineInstr *IllegalPhi =
14498bcb0991SDimitry Andric BuildMI(*BB, MI, DebugLoc(), TII->get(TargetOpcode::PHI), R)
145081ad6265SDimitry Andric .addReg(*IllegalPhiDefault)
14518bcb0991SDimitry Andric .addMBB(PreheaderBB) // Block choice is arbitrary and has no effect.
14528bcb0991SDimitry Andric .addReg(LoopReg)
14538bcb0991SDimitry Andric .addMBB(BB); // Block choice is arbitrary and has no effect.
14545ffd83dbSDimitry Andric // Illegal phi should belong to the producer stage so that it can be
14555ffd83dbSDimitry Andric // filtered correctly during peeling.
14565ffd83dbSDimitry Andric S.setStage(IllegalPhi, LoopProducerStage);
14578bcb0991SDimitry Andric return R;
14588bcb0991SDimitry Andric }
14598bcb0991SDimitry Andric
14608bcb0991SDimitry Andric return LoopReg;
14618bcb0991SDimitry Andric }
14628bcb0991SDimitry Andric
phi(Register LoopReg,std::optional<Register> InitReg,const TargetRegisterClass * RC)1463bdd1243dSDimitry Andric Register KernelRewriter::phi(Register LoopReg, std::optional<Register> InitReg,
14648bcb0991SDimitry Andric const TargetRegisterClass *RC) {
14658bcb0991SDimitry Andric // If the init register is not undef, try and find an existing phi.
146681ad6265SDimitry Andric if (InitReg) {
1467bdd1243dSDimitry Andric auto I = Phis.find({LoopReg, *InitReg});
14688bcb0991SDimitry Andric if (I != Phis.end())
14698bcb0991SDimitry Andric return I->second;
14708bcb0991SDimitry Andric } else {
14718bcb0991SDimitry Andric for (auto &KV : Phis) {
14728bcb0991SDimitry Andric if (KV.first.first == LoopReg)
14738bcb0991SDimitry Andric return KV.second;
14748bcb0991SDimitry Andric }
14758bcb0991SDimitry Andric }
14768bcb0991SDimitry Andric
14778bcb0991SDimitry Andric // InitReg is either undef or no existing phi takes InitReg as input. Try and
14788bcb0991SDimitry Andric // find a phi that takes undef as input.
14798bcb0991SDimitry Andric auto I = UndefPhis.find(LoopReg);
14808bcb0991SDimitry Andric if (I != UndefPhis.end()) {
14818bcb0991SDimitry Andric Register R = I->second;
148281ad6265SDimitry Andric if (!InitReg)
14838bcb0991SDimitry Andric // Found a phi taking undef as input, and this input is undef so return
14848bcb0991SDimitry Andric // without any more changes.
14858bcb0991SDimitry Andric return R;
14868bcb0991SDimitry Andric // Found a phi taking undef as input, so rewrite it to take InitReg.
14878bcb0991SDimitry Andric MachineInstr *MI = MRI.getVRegDef(R);
1488bdd1243dSDimitry Andric MI->getOperand(1).setReg(*InitReg);
1489bdd1243dSDimitry Andric Phis.insert({{LoopReg, *InitReg}, R});
149081ad6265SDimitry Andric const TargetRegisterClass *ConstrainRegClass =
1491bdd1243dSDimitry Andric MRI.constrainRegClass(R, MRI.getRegClass(*InitReg));
149281ad6265SDimitry Andric assert(ConstrainRegClass && "Expected a valid constrained register class!");
149381ad6265SDimitry Andric (void)ConstrainRegClass;
14948bcb0991SDimitry Andric UndefPhis.erase(I);
14958bcb0991SDimitry Andric return R;
14968bcb0991SDimitry Andric }
14978bcb0991SDimitry Andric
14988bcb0991SDimitry Andric // Failed to find any existing phi to reuse, so create a new one.
14998bcb0991SDimitry Andric if (!RC)
15008bcb0991SDimitry Andric RC = MRI.getRegClass(LoopReg);
15018bcb0991SDimitry Andric Register R = MRI.createVirtualRegister(RC);
150281ad6265SDimitry Andric if (InitReg) {
150381ad6265SDimitry Andric const TargetRegisterClass *ConstrainRegClass =
15048bcb0991SDimitry Andric MRI.constrainRegClass(R, MRI.getRegClass(*InitReg));
150581ad6265SDimitry Andric assert(ConstrainRegClass && "Expected a valid constrained register class!");
150681ad6265SDimitry Andric (void)ConstrainRegClass;
150781ad6265SDimitry Andric }
15088bcb0991SDimitry Andric BuildMI(*BB, BB->getFirstNonPHI(), DebugLoc(), TII->get(TargetOpcode::PHI), R)
150981ad6265SDimitry Andric .addReg(InitReg ? *InitReg : undef(RC))
15108bcb0991SDimitry Andric .addMBB(PreheaderBB)
15118bcb0991SDimitry Andric .addReg(LoopReg)
15128bcb0991SDimitry Andric .addMBB(BB);
151381ad6265SDimitry Andric if (!InitReg)
15148bcb0991SDimitry Andric UndefPhis[LoopReg] = R;
15158bcb0991SDimitry Andric else
15168bcb0991SDimitry Andric Phis[{LoopReg, *InitReg}] = R;
15178bcb0991SDimitry Andric return R;
15188bcb0991SDimitry Andric }
15198bcb0991SDimitry Andric
undef(const TargetRegisterClass * RC)15208bcb0991SDimitry Andric Register KernelRewriter::undef(const TargetRegisterClass *RC) {
15218bcb0991SDimitry Andric Register &R = Undefs[RC];
15228bcb0991SDimitry Andric if (R == 0) {
15238bcb0991SDimitry Andric // Create an IMPLICIT_DEF that defines this register if we need it.
15248bcb0991SDimitry Andric // All uses of this should be removed by the time we have finished unrolling
15258bcb0991SDimitry Andric // prologs and epilogs.
15268bcb0991SDimitry Andric R = MRI.createVirtualRegister(RC);
15278bcb0991SDimitry Andric auto *InsertBB = &PreheaderBB->getParent()->front();
15288bcb0991SDimitry Andric BuildMI(*InsertBB, InsertBB->getFirstTerminator(), DebugLoc(),
15298bcb0991SDimitry Andric TII->get(TargetOpcode::IMPLICIT_DEF), R);
15308bcb0991SDimitry Andric }
15318bcb0991SDimitry Andric return R;
15328bcb0991SDimitry Andric }
15338bcb0991SDimitry Andric
15348bcb0991SDimitry Andric namespace {
15358bcb0991SDimitry Andric /// Describes an operand in the kernel of a pipelined loop. Characteristics of
15368bcb0991SDimitry Andric /// the operand are discovered, such as how many in-loop PHIs it has to jump
15378bcb0991SDimitry Andric /// through and defaults for these phis.
15388bcb0991SDimitry Andric class KernelOperandInfo {
15398bcb0991SDimitry Andric MachineBasicBlock *BB;
15408bcb0991SDimitry Andric MachineRegisterInfo &MRI;
15418bcb0991SDimitry Andric SmallVector<Register, 4> PhiDefaults;
15428bcb0991SDimitry Andric MachineOperand *Source;
15438bcb0991SDimitry Andric MachineOperand *Target;
15448bcb0991SDimitry Andric
15458bcb0991SDimitry Andric public:
KernelOperandInfo(MachineOperand * MO,MachineRegisterInfo & MRI,const SmallPtrSetImpl<MachineInstr * > & IllegalPhis)15468bcb0991SDimitry Andric KernelOperandInfo(MachineOperand *MO, MachineRegisterInfo &MRI,
15478bcb0991SDimitry Andric const SmallPtrSetImpl<MachineInstr *> &IllegalPhis)
15488bcb0991SDimitry Andric : MRI(MRI) {
15498bcb0991SDimitry Andric Source = MO;
15508bcb0991SDimitry Andric BB = MO->getParent()->getParent();
15518bcb0991SDimitry Andric while (isRegInLoop(MO)) {
15528bcb0991SDimitry Andric MachineInstr *MI = MRI.getVRegDef(MO->getReg());
15538bcb0991SDimitry Andric if (MI->isFullCopy()) {
15548bcb0991SDimitry Andric MO = &MI->getOperand(1);
15558bcb0991SDimitry Andric continue;
15568bcb0991SDimitry Andric }
15578bcb0991SDimitry Andric if (!MI->isPHI())
15588bcb0991SDimitry Andric break;
15598bcb0991SDimitry Andric // If this is an illegal phi, don't count it in distance.
15608bcb0991SDimitry Andric if (IllegalPhis.count(MI)) {
15618bcb0991SDimitry Andric MO = &MI->getOperand(3);
15628bcb0991SDimitry Andric continue;
15638bcb0991SDimitry Andric }
15648bcb0991SDimitry Andric
15658bcb0991SDimitry Andric Register Default = getInitPhiReg(*MI, BB);
15668bcb0991SDimitry Andric MO = MI->getOperand(2).getMBB() == BB ? &MI->getOperand(1)
15678bcb0991SDimitry Andric : &MI->getOperand(3);
15688bcb0991SDimitry Andric PhiDefaults.push_back(Default);
15698bcb0991SDimitry Andric }
15708bcb0991SDimitry Andric Target = MO;
15718bcb0991SDimitry Andric }
15728bcb0991SDimitry Andric
operator ==(const KernelOperandInfo & Other) const15738bcb0991SDimitry Andric bool operator==(const KernelOperandInfo &Other) const {
15748bcb0991SDimitry Andric return PhiDefaults.size() == Other.PhiDefaults.size();
15758bcb0991SDimitry Andric }
15768bcb0991SDimitry Andric
print(raw_ostream & OS) const15778bcb0991SDimitry Andric void print(raw_ostream &OS) const {
15788bcb0991SDimitry Andric OS << "use of " << *Source << ": distance(" << PhiDefaults.size() << ") in "
15798bcb0991SDimitry Andric << *Source->getParent();
15808bcb0991SDimitry Andric }
15818bcb0991SDimitry Andric
15828bcb0991SDimitry Andric private:
isRegInLoop(MachineOperand * MO)15838bcb0991SDimitry Andric bool isRegInLoop(MachineOperand *MO) {
15848bcb0991SDimitry Andric return MO->isReg() && MO->getReg().isVirtual() &&
15858bcb0991SDimitry Andric MRI.getVRegDef(MO->getReg())->getParent() == BB;
15868bcb0991SDimitry Andric }
15878bcb0991SDimitry Andric };
15888bcb0991SDimitry Andric } // namespace
15898bcb0991SDimitry Andric
15908bcb0991SDimitry Andric MachineBasicBlock *
peelKernel(LoopPeelDirection LPD)15918bcb0991SDimitry Andric PeelingModuloScheduleExpander::peelKernel(LoopPeelDirection LPD) {
15928bcb0991SDimitry Andric MachineBasicBlock *NewBB = PeelSingleBlockLoop(LPD, BB, MRI, TII);
15938bcb0991SDimitry Andric if (LPD == LPD_Front)
15948bcb0991SDimitry Andric PeeledFront.push_back(NewBB);
15958bcb0991SDimitry Andric else
15968bcb0991SDimitry Andric PeeledBack.push_front(NewBB);
15978bcb0991SDimitry Andric for (auto I = BB->begin(), NI = NewBB->begin(); !I->isTerminator();
15988bcb0991SDimitry Andric ++I, ++NI) {
15998bcb0991SDimitry Andric CanonicalMIs[&*I] = &*I;
16008bcb0991SDimitry Andric CanonicalMIs[&*NI] = &*I;
16018bcb0991SDimitry Andric BlockMIs[{NewBB, &*I}] = &*NI;
16028bcb0991SDimitry Andric BlockMIs[{BB, &*I}] = &*I;
16038bcb0991SDimitry Andric }
16048bcb0991SDimitry Andric return NewBB;
16058bcb0991SDimitry Andric }
16068bcb0991SDimitry Andric
filterInstructions(MachineBasicBlock * MB,int MinStage)1607480093f4SDimitry Andric void PeelingModuloScheduleExpander::filterInstructions(MachineBasicBlock *MB,
1608480093f4SDimitry Andric int MinStage) {
1609480093f4SDimitry Andric for (auto I = MB->getFirstInstrTerminator()->getReverseIterator();
1610480093f4SDimitry Andric I != std::next(MB->getFirstNonPHI()->getReverseIterator());) {
1611480093f4SDimitry Andric MachineInstr *MI = &*I++;
1612480093f4SDimitry Andric int Stage = getStage(MI);
1613480093f4SDimitry Andric if (Stage == -1 || Stage >= MinStage)
1614480093f4SDimitry Andric continue;
1615480093f4SDimitry Andric
1616480093f4SDimitry Andric for (MachineOperand &DefMO : MI->defs()) {
1617480093f4SDimitry Andric SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
1618480093f4SDimitry Andric for (MachineInstr &UseMI : MRI.use_instructions(DefMO.getReg())) {
1619480093f4SDimitry Andric // Only PHIs can use values from this block by construction.
1620480093f4SDimitry Andric // Match with the equivalent PHI in B.
1621480093f4SDimitry Andric assert(UseMI.isPHI());
1622480093f4SDimitry Andric Register Reg = getEquivalentRegisterIn(UseMI.getOperand(0).getReg(),
1623480093f4SDimitry Andric MI->getParent());
1624480093f4SDimitry Andric Subs.emplace_back(&UseMI, Reg);
1625480093f4SDimitry Andric }
1626480093f4SDimitry Andric for (auto &Sub : Subs)
1627480093f4SDimitry Andric Sub.first->substituteRegister(DefMO.getReg(), Sub.second, /*SubIdx=*/0,
1628480093f4SDimitry Andric *MRI.getTargetRegisterInfo());
1629480093f4SDimitry Andric }
1630480093f4SDimitry Andric if (LIS)
1631480093f4SDimitry Andric LIS->RemoveMachineInstrFromMaps(*MI);
1632480093f4SDimitry Andric MI->eraseFromParent();
1633480093f4SDimitry Andric }
1634480093f4SDimitry Andric }
1635480093f4SDimitry Andric
moveStageBetweenBlocks(MachineBasicBlock * DestBB,MachineBasicBlock * SourceBB,unsigned Stage)1636480093f4SDimitry Andric void PeelingModuloScheduleExpander::moveStageBetweenBlocks(
1637480093f4SDimitry Andric MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage) {
1638480093f4SDimitry Andric auto InsertPt = DestBB->getFirstNonPHI();
1639480093f4SDimitry Andric DenseMap<Register, Register> Remaps;
1640349cc55cSDimitry Andric for (MachineInstr &MI : llvm::make_early_inc_range(
1641349cc55cSDimitry Andric llvm::make_range(SourceBB->getFirstNonPHI(), SourceBB->end()))) {
1642349cc55cSDimitry Andric if (MI.isPHI()) {
1643480093f4SDimitry Andric // This is an illegal PHI. If we move any instructions using an illegal
16445ffd83dbSDimitry Andric // PHI, we need to create a legal Phi.
1645349cc55cSDimitry Andric if (getStage(&MI) != Stage) {
16465ffd83dbSDimitry Andric // The legal Phi is not necessary if the illegal phi's stage
16475ffd83dbSDimitry Andric // is being moved.
1648349cc55cSDimitry Andric Register PhiR = MI.getOperand(0).getReg();
1649480093f4SDimitry Andric auto RC = MRI.getRegClass(PhiR);
1650480093f4SDimitry Andric Register NR = MRI.createVirtualRegister(RC);
16515ffd83dbSDimitry Andric MachineInstr *NI = BuildMI(*DestBB, DestBB->getFirstNonPHI(),
16525ffd83dbSDimitry Andric DebugLoc(), TII->get(TargetOpcode::PHI), NR)
1653480093f4SDimitry Andric .addReg(PhiR)
1654480093f4SDimitry Andric .addMBB(SourceBB);
1655349cc55cSDimitry Andric BlockMIs[{DestBB, CanonicalMIs[&MI]}] = NI;
1656349cc55cSDimitry Andric CanonicalMIs[NI] = CanonicalMIs[&MI];
1657480093f4SDimitry Andric Remaps[PhiR] = NR;
16585ffd83dbSDimitry Andric }
1659480093f4SDimitry Andric }
1660349cc55cSDimitry Andric if (getStage(&MI) != Stage)
1661480093f4SDimitry Andric continue;
1662349cc55cSDimitry Andric MI.removeFromParent();
1663349cc55cSDimitry Andric DestBB->insert(InsertPt, &MI);
1664349cc55cSDimitry Andric auto *KernelMI = CanonicalMIs[&MI];
1665349cc55cSDimitry Andric BlockMIs[{DestBB, KernelMI}] = &MI;
1666480093f4SDimitry Andric BlockMIs.erase({SourceBB, KernelMI});
1667480093f4SDimitry Andric }
1668480093f4SDimitry Andric SmallVector<MachineInstr *, 4> PhiToDelete;
1669480093f4SDimitry Andric for (MachineInstr &MI : DestBB->phis()) {
1670480093f4SDimitry Andric assert(MI.getNumOperands() == 3);
1671480093f4SDimitry Andric MachineInstr *Def = MRI.getVRegDef(MI.getOperand(1).getReg());
1672480093f4SDimitry Andric // If the instruction referenced by the phi is moved inside the block
1673480093f4SDimitry Andric // we don't need the phi anymore.
1674480093f4SDimitry Andric if (getStage(Def) == Stage) {
1675480093f4SDimitry Andric Register PhiReg = MI.getOperand(0).getReg();
16765ffd83dbSDimitry Andric assert(Def->findRegisterDefOperandIdx(MI.getOperand(1).getReg()) != -1);
16775ffd83dbSDimitry Andric MRI.replaceRegWith(MI.getOperand(0).getReg(), MI.getOperand(1).getReg());
1678480093f4SDimitry Andric MI.getOperand(0).setReg(PhiReg);
1679480093f4SDimitry Andric PhiToDelete.push_back(&MI);
1680480093f4SDimitry Andric }
1681480093f4SDimitry Andric }
1682480093f4SDimitry Andric for (auto *P : PhiToDelete)
1683480093f4SDimitry Andric P->eraseFromParent();
1684480093f4SDimitry Andric InsertPt = DestBB->getFirstNonPHI();
1685480093f4SDimitry Andric // Helper to clone Phi instructions into the destination block. We clone Phi
1686480093f4SDimitry Andric // greedily to avoid combinatorial explosion of Phi instructions.
1687480093f4SDimitry Andric auto clonePhi = [&](MachineInstr *Phi) {
1688480093f4SDimitry Andric MachineInstr *NewMI = MF.CloneMachineInstr(Phi);
1689480093f4SDimitry Andric DestBB->insert(InsertPt, NewMI);
1690480093f4SDimitry Andric Register OrigR = Phi->getOperand(0).getReg();
1691480093f4SDimitry Andric Register R = MRI.createVirtualRegister(MRI.getRegClass(OrigR));
1692480093f4SDimitry Andric NewMI->getOperand(0).setReg(R);
1693480093f4SDimitry Andric NewMI->getOperand(1).setReg(OrigR);
1694480093f4SDimitry Andric NewMI->getOperand(2).setMBB(*DestBB->pred_begin());
1695480093f4SDimitry Andric Remaps[OrigR] = R;
1696480093f4SDimitry Andric CanonicalMIs[NewMI] = CanonicalMIs[Phi];
1697480093f4SDimitry Andric BlockMIs[{DestBB, CanonicalMIs[Phi]}] = NewMI;
1698480093f4SDimitry Andric PhiNodeLoopIteration[NewMI] = PhiNodeLoopIteration[Phi];
1699480093f4SDimitry Andric return R;
1700480093f4SDimitry Andric };
1701480093f4SDimitry Andric for (auto I = DestBB->getFirstNonPHI(); I != DestBB->end(); ++I) {
1702480093f4SDimitry Andric for (MachineOperand &MO : I->uses()) {
1703480093f4SDimitry Andric if (!MO.isReg())
1704480093f4SDimitry Andric continue;
1705480093f4SDimitry Andric if (Remaps.count(MO.getReg()))
1706480093f4SDimitry Andric MO.setReg(Remaps[MO.getReg()]);
1707480093f4SDimitry Andric else {
1708480093f4SDimitry Andric // If we are using a phi from the source block we need to add a new phi
1709480093f4SDimitry Andric // pointing to the old one.
1710480093f4SDimitry Andric MachineInstr *Use = MRI.getUniqueVRegDef(MO.getReg());
1711480093f4SDimitry Andric if (Use && Use->isPHI() && Use->getParent() == SourceBB) {
1712480093f4SDimitry Andric Register R = clonePhi(Use);
1713480093f4SDimitry Andric MO.setReg(R);
1714480093f4SDimitry Andric }
1715480093f4SDimitry Andric }
1716480093f4SDimitry Andric }
1717480093f4SDimitry Andric }
1718480093f4SDimitry Andric }
1719480093f4SDimitry Andric
1720480093f4SDimitry Andric Register
getPhiCanonicalReg(MachineInstr * CanonicalPhi,MachineInstr * Phi)1721480093f4SDimitry Andric PeelingModuloScheduleExpander::getPhiCanonicalReg(MachineInstr *CanonicalPhi,
1722480093f4SDimitry Andric MachineInstr *Phi) {
1723480093f4SDimitry Andric unsigned distance = PhiNodeLoopIteration[Phi];
1724480093f4SDimitry Andric MachineInstr *CanonicalUse = CanonicalPhi;
17255ffd83dbSDimitry Andric Register CanonicalUseReg = CanonicalUse->getOperand(0).getReg();
1726480093f4SDimitry Andric for (unsigned I = 0; I < distance; ++I) {
1727480093f4SDimitry Andric assert(CanonicalUse->isPHI());
1728480093f4SDimitry Andric assert(CanonicalUse->getNumOperands() == 5);
1729480093f4SDimitry Andric unsigned LoopRegIdx = 3, InitRegIdx = 1;
1730480093f4SDimitry Andric if (CanonicalUse->getOperand(2).getMBB() == CanonicalUse->getParent())
1731480093f4SDimitry Andric std::swap(LoopRegIdx, InitRegIdx);
17325ffd83dbSDimitry Andric CanonicalUseReg = CanonicalUse->getOperand(LoopRegIdx).getReg();
17335ffd83dbSDimitry Andric CanonicalUse = MRI.getVRegDef(CanonicalUseReg);
1734480093f4SDimitry Andric }
17355ffd83dbSDimitry Andric return CanonicalUseReg;
1736480093f4SDimitry Andric }
1737480093f4SDimitry Andric
peelPrologAndEpilogs()17388bcb0991SDimitry Andric void PeelingModuloScheduleExpander::peelPrologAndEpilogs() {
17398bcb0991SDimitry Andric BitVector LS(Schedule.getNumStages(), true);
17408bcb0991SDimitry Andric BitVector AS(Schedule.getNumStages(), true);
17418bcb0991SDimitry Andric LiveStages[BB] = LS;
17428bcb0991SDimitry Andric AvailableStages[BB] = AS;
17438bcb0991SDimitry Andric
17448bcb0991SDimitry Andric // Peel out the prologs.
17458bcb0991SDimitry Andric LS.reset();
17468bcb0991SDimitry Andric for (int I = 0; I < Schedule.getNumStages() - 1; ++I) {
174704eeddc0SDimitry Andric LS[I] = true;
17488bcb0991SDimitry Andric Prologs.push_back(peelKernel(LPD_Front));
17498bcb0991SDimitry Andric LiveStages[Prologs.back()] = LS;
17508bcb0991SDimitry Andric AvailableStages[Prologs.back()] = LS;
17518bcb0991SDimitry Andric }
17528bcb0991SDimitry Andric
17538bcb0991SDimitry Andric // Create a block that will end up as the new loop exiting block (dominated by
17548bcb0991SDimitry Andric // all prologs and epilogs). It will only contain PHIs, in the same order as
17558bcb0991SDimitry Andric // BB's PHIs. This gives us a poor-man's LCSSA with the inductive property
17568bcb0991SDimitry Andric // that the exiting block is a (sub) clone of BB. This in turn gives us the
17578bcb0991SDimitry Andric // property that any value deffed in BB but used outside of BB is used by a
17588bcb0991SDimitry Andric // PHI in the exiting block.
17598bcb0991SDimitry Andric MachineBasicBlock *ExitingBB = CreateLCSSAExitingBlock();
1760480093f4SDimitry Andric EliminateDeadPhis(ExitingBB, MRI, LIS, /*KeepSingleSrcPhi=*/true);
17618bcb0991SDimitry Andric // Push out the epilogs, again in reverse order.
17628bcb0991SDimitry Andric // We can't assume anything about the minumum loop trip count at this point,
1763480093f4SDimitry Andric // so emit a fairly complex epilog.
1764480093f4SDimitry Andric
1765480093f4SDimitry Andric // We first peel number of stages minus one epilogue. Then we remove dead
1766480093f4SDimitry Andric // stages and reorder instructions based on their stage. If we have 3 stages
1767480093f4SDimitry Andric // we generate first:
1768480093f4SDimitry Andric // E0[3, 2, 1]
1769480093f4SDimitry Andric // E1[3', 2']
1770480093f4SDimitry Andric // E2[3'']
1771480093f4SDimitry Andric // And then we move instructions based on their stages to have:
1772480093f4SDimitry Andric // E0[3]
1773480093f4SDimitry Andric // E1[2, 3']
1774480093f4SDimitry Andric // E2[1, 2', 3'']
1775480093f4SDimitry Andric // The transformation is legal because we only move instructions past
1776480093f4SDimitry Andric // instructions of a previous loop iteration.
17778bcb0991SDimitry Andric for (int I = 1; I <= Schedule.getNumStages() - 1; ++I) {
1778480093f4SDimitry Andric Epilogs.push_back(peelKernel(LPD_Back));
1779480093f4SDimitry Andric MachineBasicBlock *B = Epilogs.back();
1780480093f4SDimitry Andric filterInstructions(B, Schedule.getNumStages() - I);
1781480093f4SDimitry Andric // Keep track at which iteration each phi belongs to. We need it to know
1782480093f4SDimitry Andric // what version of the variable to use during prologue/epilogue stitching.
1783480093f4SDimitry Andric EliminateDeadPhis(B, MRI, LIS, /*KeepSingleSrcPhi=*/true);
1784349cc55cSDimitry Andric for (MachineInstr &Phi : B->phis())
1785349cc55cSDimitry Andric PhiNodeLoopIteration[&Phi] = Schedule.getNumStages() - I;
17868bcb0991SDimitry Andric }
1787480093f4SDimitry Andric for (size_t I = 0; I < Epilogs.size(); I++) {
1788480093f4SDimitry Andric LS.reset();
1789480093f4SDimitry Andric for (size_t J = I; J < Epilogs.size(); J++) {
1790480093f4SDimitry Andric int Iteration = J;
1791480093f4SDimitry Andric unsigned Stage = Schedule.getNumStages() - 1 + I - J;
1792480093f4SDimitry Andric // Move stage one block at a time so that Phi nodes are updated correctly.
1793480093f4SDimitry Andric for (size_t K = Iteration; K > I; K--)
1794480093f4SDimitry Andric moveStageBetweenBlocks(Epilogs[K - 1], Epilogs[K], Stage);
179504eeddc0SDimitry Andric LS[Stage] = true;
1796480093f4SDimitry Andric }
1797480093f4SDimitry Andric LiveStages[Epilogs[I]] = LS;
1798480093f4SDimitry Andric AvailableStages[Epilogs[I]] = AS;
17998bcb0991SDimitry Andric }
18008bcb0991SDimitry Andric
18018bcb0991SDimitry Andric // Now we've defined all the prolog and epilog blocks as a fallthrough
18028bcb0991SDimitry Andric // sequence, add the edges that will be followed if the loop trip count is
18038bcb0991SDimitry Andric // lower than the number of stages (connecting prologs directly with epilogs).
18048bcb0991SDimitry Andric auto PI = Prologs.begin();
18058bcb0991SDimitry Andric auto EI = Epilogs.begin();
18068bcb0991SDimitry Andric assert(Prologs.size() == Epilogs.size());
18078bcb0991SDimitry Andric for (; PI != Prologs.end(); ++PI, ++EI) {
18088bcb0991SDimitry Andric MachineBasicBlock *Pred = *(*EI)->pred_begin();
18098bcb0991SDimitry Andric (*PI)->addSuccessor(*EI);
18108bcb0991SDimitry Andric for (MachineInstr &MI : (*EI)->phis()) {
18118bcb0991SDimitry Andric Register Reg = MI.getOperand(1).getReg();
18128bcb0991SDimitry Andric MachineInstr *Use = MRI.getUniqueVRegDef(Reg);
1813480093f4SDimitry Andric if (Use && Use->getParent() == Pred) {
1814480093f4SDimitry Andric MachineInstr *CanonicalUse = CanonicalMIs[Use];
1815480093f4SDimitry Andric if (CanonicalUse->isPHI()) {
1816480093f4SDimitry Andric // If the use comes from a phi we need to skip as many phi as the
1817480093f4SDimitry Andric // distance between the epilogue and the kernel. Trace through the phi
1818480093f4SDimitry Andric // chain to find the right value.
1819480093f4SDimitry Andric Reg = getPhiCanonicalReg(CanonicalUse, Use);
1820480093f4SDimitry Andric }
18218bcb0991SDimitry Andric Reg = getEquivalentRegisterIn(Reg, *PI);
1822480093f4SDimitry Andric }
18238bcb0991SDimitry Andric MI.addOperand(MachineOperand::CreateReg(Reg, /*isDef=*/false));
18248bcb0991SDimitry Andric MI.addOperand(MachineOperand::CreateMBB(*PI));
18258bcb0991SDimitry Andric }
18268bcb0991SDimitry Andric }
18278bcb0991SDimitry Andric
18288bcb0991SDimitry Andric // Create a list of all blocks in order.
18298bcb0991SDimitry Andric SmallVector<MachineBasicBlock *, 8> Blocks;
18308bcb0991SDimitry Andric llvm::copy(PeeledFront, std::back_inserter(Blocks));
18318bcb0991SDimitry Andric Blocks.push_back(BB);
18328bcb0991SDimitry Andric llvm::copy(PeeledBack, std::back_inserter(Blocks));
18338bcb0991SDimitry Andric
18348bcb0991SDimitry Andric // Iterate in reverse order over all instructions, remapping as we go.
18358bcb0991SDimitry Andric for (MachineBasicBlock *B : reverse(Blocks)) {
183681ad6265SDimitry Andric for (auto I = B->instr_rbegin();
18378bcb0991SDimitry Andric I != std::next(B->getFirstNonPHI()->getReverseIterator());) {
183881ad6265SDimitry Andric MachineBasicBlock::reverse_instr_iterator MI = I++;
183981ad6265SDimitry Andric rewriteUsesOf(&*MI);
18408bcb0991SDimitry Andric }
18418bcb0991SDimitry Andric }
1842480093f4SDimitry Andric for (auto *MI : IllegalPhisToDelete) {
1843480093f4SDimitry Andric if (LIS)
1844480093f4SDimitry Andric LIS->RemoveMachineInstrFromMaps(*MI);
1845480093f4SDimitry Andric MI->eraseFromParent();
1846480093f4SDimitry Andric }
1847480093f4SDimitry Andric IllegalPhisToDelete.clear();
1848480093f4SDimitry Andric
18498bcb0991SDimitry Andric // Now all remapping has been done, we're free to optimize the generated code.
18508bcb0991SDimitry Andric for (MachineBasicBlock *B : reverse(Blocks))
18518bcb0991SDimitry Andric EliminateDeadPhis(B, MRI, LIS);
18528bcb0991SDimitry Andric EliminateDeadPhis(ExitingBB, MRI, LIS);
18538bcb0991SDimitry Andric }
18548bcb0991SDimitry Andric
CreateLCSSAExitingBlock()18558bcb0991SDimitry Andric MachineBasicBlock *PeelingModuloScheduleExpander::CreateLCSSAExitingBlock() {
18568bcb0991SDimitry Andric MachineFunction &MF = *BB->getParent();
18578bcb0991SDimitry Andric MachineBasicBlock *Exit = *BB->succ_begin();
18588bcb0991SDimitry Andric if (Exit == BB)
18598bcb0991SDimitry Andric Exit = *std::next(BB->succ_begin());
18608bcb0991SDimitry Andric
18618bcb0991SDimitry Andric MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
18628bcb0991SDimitry Andric MF.insert(std::next(BB->getIterator()), NewBB);
18638bcb0991SDimitry Andric
18648bcb0991SDimitry Andric // Clone all phis in BB into NewBB and rewrite.
18658bcb0991SDimitry Andric for (MachineInstr &MI : BB->phis()) {
18668bcb0991SDimitry Andric auto RC = MRI.getRegClass(MI.getOperand(0).getReg());
18678bcb0991SDimitry Andric Register OldR = MI.getOperand(3).getReg();
18688bcb0991SDimitry Andric Register R = MRI.createVirtualRegister(RC);
18698bcb0991SDimitry Andric SmallVector<MachineInstr *, 4> Uses;
18708bcb0991SDimitry Andric for (MachineInstr &Use : MRI.use_instructions(OldR))
18718bcb0991SDimitry Andric if (Use.getParent() != BB)
18728bcb0991SDimitry Andric Uses.push_back(&Use);
18738bcb0991SDimitry Andric for (MachineInstr *Use : Uses)
18748bcb0991SDimitry Andric Use->substituteRegister(OldR, R, /*SubIdx=*/0,
18758bcb0991SDimitry Andric *MRI.getTargetRegisterInfo());
18768bcb0991SDimitry Andric MachineInstr *NI = BuildMI(NewBB, DebugLoc(), TII->get(TargetOpcode::PHI), R)
18778bcb0991SDimitry Andric .addReg(OldR)
18788bcb0991SDimitry Andric .addMBB(BB);
18798bcb0991SDimitry Andric BlockMIs[{NewBB, &MI}] = NI;
18808bcb0991SDimitry Andric CanonicalMIs[NI] = &MI;
18818bcb0991SDimitry Andric }
18828bcb0991SDimitry Andric BB->replaceSuccessor(Exit, NewBB);
18838bcb0991SDimitry Andric Exit->replacePhiUsesWith(BB, NewBB);
18848bcb0991SDimitry Andric NewBB->addSuccessor(Exit);
18858bcb0991SDimitry Andric
18868bcb0991SDimitry Andric MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
18878bcb0991SDimitry Andric SmallVector<MachineOperand, 4> Cond;
18888bcb0991SDimitry Andric bool CanAnalyzeBr = !TII->analyzeBranch(*BB, TBB, FBB, Cond);
18898bcb0991SDimitry Andric (void)CanAnalyzeBr;
18908bcb0991SDimitry Andric assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
18918bcb0991SDimitry Andric TII->removeBranch(*BB);
18928bcb0991SDimitry Andric TII->insertBranch(*BB, TBB == Exit ? NewBB : TBB, FBB == Exit ? NewBB : FBB,
18938bcb0991SDimitry Andric Cond, DebugLoc());
18948bcb0991SDimitry Andric TII->insertUnconditionalBranch(*NewBB, Exit, DebugLoc());
18958bcb0991SDimitry Andric return NewBB;
18968bcb0991SDimitry Andric }
18978bcb0991SDimitry Andric
18988bcb0991SDimitry Andric Register
getEquivalentRegisterIn(Register Reg,MachineBasicBlock * BB)18998bcb0991SDimitry Andric PeelingModuloScheduleExpander::getEquivalentRegisterIn(Register Reg,
19008bcb0991SDimitry Andric MachineBasicBlock *BB) {
19018bcb0991SDimitry Andric MachineInstr *MI = MRI.getUniqueVRegDef(Reg);
19028bcb0991SDimitry Andric unsigned OpIdx = MI->findRegisterDefOperandIdx(Reg);
19038bcb0991SDimitry Andric return BlockMIs[{BB, CanonicalMIs[MI]}]->getOperand(OpIdx).getReg();
19048bcb0991SDimitry Andric }
19058bcb0991SDimitry Andric
rewriteUsesOf(MachineInstr * MI)19068bcb0991SDimitry Andric void PeelingModuloScheduleExpander::rewriteUsesOf(MachineInstr *MI) {
19078bcb0991SDimitry Andric if (MI->isPHI()) {
19088bcb0991SDimitry Andric // This is an illegal PHI. The loop-carried (desired) value is operand 3,
19098bcb0991SDimitry Andric // and it is produced by this block.
19108bcb0991SDimitry Andric Register PhiR = MI->getOperand(0).getReg();
19118bcb0991SDimitry Andric Register R = MI->getOperand(3).getReg();
19128bcb0991SDimitry Andric int RMIStage = getStage(MRI.getUniqueVRegDef(R));
19138bcb0991SDimitry Andric if (RMIStage != -1 && !AvailableStages[MI->getParent()].test(RMIStage))
19148bcb0991SDimitry Andric R = MI->getOperand(1).getReg();
19158bcb0991SDimitry Andric MRI.setRegClass(R, MRI.getRegClass(PhiR));
19168bcb0991SDimitry Andric MRI.replaceRegWith(PhiR, R);
1917480093f4SDimitry Andric // Postpone deleting the Phi as it may be referenced by BlockMIs and used
1918480093f4SDimitry Andric // later to figure out how to remap registers.
1919480093f4SDimitry Andric MI->getOperand(0).setReg(PhiR);
1920480093f4SDimitry Andric IllegalPhisToDelete.push_back(MI);
19218bcb0991SDimitry Andric return;
19228bcb0991SDimitry Andric }
19238bcb0991SDimitry Andric
19248bcb0991SDimitry Andric int Stage = getStage(MI);
19258bcb0991SDimitry Andric if (Stage == -1 || LiveStages.count(MI->getParent()) == 0 ||
19268bcb0991SDimitry Andric LiveStages[MI->getParent()].test(Stage))
19278bcb0991SDimitry Andric // Instruction is live, no rewriting to do.
19288bcb0991SDimitry Andric return;
19298bcb0991SDimitry Andric
19308bcb0991SDimitry Andric for (MachineOperand &DefMO : MI->defs()) {
19318bcb0991SDimitry Andric SmallVector<std::pair<MachineInstr *, Register>, 4> Subs;
19328bcb0991SDimitry Andric for (MachineInstr &UseMI : MRI.use_instructions(DefMO.getReg())) {
19338bcb0991SDimitry Andric // Only PHIs can use values from this block by construction.
19348bcb0991SDimitry Andric // Match with the equivalent PHI in B.
19358bcb0991SDimitry Andric assert(UseMI.isPHI());
19368bcb0991SDimitry Andric Register Reg = getEquivalentRegisterIn(UseMI.getOperand(0).getReg(),
19378bcb0991SDimitry Andric MI->getParent());
19388bcb0991SDimitry Andric Subs.emplace_back(&UseMI, Reg);
19398bcb0991SDimitry Andric }
19408bcb0991SDimitry Andric for (auto &Sub : Subs)
19418bcb0991SDimitry Andric Sub.first->substituteRegister(DefMO.getReg(), Sub.second, /*SubIdx=*/0,
19428bcb0991SDimitry Andric *MRI.getTargetRegisterInfo());
19438bcb0991SDimitry Andric }
19448bcb0991SDimitry Andric if (LIS)
19458bcb0991SDimitry Andric LIS->RemoveMachineInstrFromMaps(*MI);
19468bcb0991SDimitry Andric MI->eraseFromParent();
19478bcb0991SDimitry Andric }
19488bcb0991SDimitry Andric
fixupBranches()19498bcb0991SDimitry Andric void PeelingModuloScheduleExpander::fixupBranches() {
19508bcb0991SDimitry Andric // Work outwards from the kernel.
19518bcb0991SDimitry Andric bool KernelDisposed = false;
19528bcb0991SDimitry Andric int TC = Schedule.getNumStages() - 1;
19538bcb0991SDimitry Andric for (auto PI = Prologs.rbegin(), EI = Epilogs.rbegin(); PI != Prologs.rend();
19548bcb0991SDimitry Andric ++PI, ++EI, --TC) {
19558bcb0991SDimitry Andric MachineBasicBlock *Prolog = *PI;
19568bcb0991SDimitry Andric MachineBasicBlock *Fallthrough = *Prolog->succ_begin();
19578bcb0991SDimitry Andric MachineBasicBlock *Epilog = *EI;
19588bcb0991SDimitry Andric SmallVector<MachineOperand, 4> Cond;
19598bcb0991SDimitry Andric TII->removeBranch(*Prolog);
1960bdd1243dSDimitry Andric std::optional<bool> StaticallyGreater =
19615ffd83dbSDimitry Andric LoopInfo->createTripCountGreaterCondition(TC, *Prolog, Cond);
196281ad6265SDimitry Andric if (!StaticallyGreater) {
19638bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << "Dynamic: TC > " << TC << "\n");
19648bcb0991SDimitry Andric // Dynamically branch based on Cond.
19658bcb0991SDimitry Andric TII->insertBranch(*Prolog, Epilog, Fallthrough, Cond, DebugLoc());
19668bcb0991SDimitry Andric } else if (*StaticallyGreater == false) {
19678bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << "Static-false: TC > " << TC << "\n");
19688bcb0991SDimitry Andric // Prolog never falls through; branch to epilog and orphan interior
19698bcb0991SDimitry Andric // blocks. Leave it to unreachable-block-elim to clean up.
19708bcb0991SDimitry Andric Prolog->removeSuccessor(Fallthrough);
19718bcb0991SDimitry Andric for (MachineInstr &P : Fallthrough->phis()) {
197281ad6265SDimitry Andric P.removeOperand(2);
197381ad6265SDimitry Andric P.removeOperand(1);
19748bcb0991SDimitry Andric }
19758bcb0991SDimitry Andric TII->insertUnconditionalBranch(*Prolog, Epilog, DebugLoc());
19768bcb0991SDimitry Andric KernelDisposed = true;
19778bcb0991SDimitry Andric } else {
19788bcb0991SDimitry Andric LLVM_DEBUG(dbgs() << "Static-true: TC > " << TC << "\n");
19798bcb0991SDimitry Andric // Prolog always falls through; remove incoming values in epilog.
19808bcb0991SDimitry Andric Prolog->removeSuccessor(Epilog);
19818bcb0991SDimitry Andric for (MachineInstr &P : Epilog->phis()) {
198281ad6265SDimitry Andric P.removeOperand(4);
198381ad6265SDimitry Andric P.removeOperand(3);
19848bcb0991SDimitry Andric }
19858bcb0991SDimitry Andric }
19868bcb0991SDimitry Andric }
19878bcb0991SDimitry Andric
19888bcb0991SDimitry Andric if (!KernelDisposed) {
19895ffd83dbSDimitry Andric LoopInfo->adjustTripCount(-(Schedule.getNumStages() - 1));
19905ffd83dbSDimitry Andric LoopInfo->setPreheader(Prologs.back());
19918bcb0991SDimitry Andric } else {
19925ffd83dbSDimitry Andric LoopInfo->disposed();
19938bcb0991SDimitry Andric }
19948bcb0991SDimitry Andric }
19958bcb0991SDimitry Andric
rewriteKernel()19968bcb0991SDimitry Andric void PeelingModuloScheduleExpander::rewriteKernel() {
1997fe6060f1SDimitry Andric KernelRewriter KR(*Schedule.getLoop(), Schedule, BB);
19988bcb0991SDimitry Andric KR.rewrite();
19998bcb0991SDimitry Andric }
20008bcb0991SDimitry Andric
expand()20018bcb0991SDimitry Andric void PeelingModuloScheduleExpander::expand() {
20028bcb0991SDimitry Andric BB = Schedule.getLoop()->getTopBlock();
20038bcb0991SDimitry Andric Preheader = Schedule.getLoop()->getLoopPreheader();
20048bcb0991SDimitry Andric LLVM_DEBUG(Schedule.dump());
20055ffd83dbSDimitry Andric LoopInfo = TII->analyzeLoopForPipelining(BB);
20065ffd83dbSDimitry Andric assert(LoopInfo);
20078bcb0991SDimitry Andric
20088bcb0991SDimitry Andric rewriteKernel();
20098bcb0991SDimitry Andric peelPrologAndEpilogs();
20108bcb0991SDimitry Andric fixupBranches();
20118bcb0991SDimitry Andric }
20128bcb0991SDimitry Andric
validateAgainstModuloScheduleExpander()20138bcb0991SDimitry Andric void PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander() {
20148bcb0991SDimitry Andric BB = Schedule.getLoop()->getTopBlock();
20158bcb0991SDimitry Andric Preheader = Schedule.getLoop()->getLoopPreheader();
20168bcb0991SDimitry Andric
20178bcb0991SDimitry Andric // Dump the schedule before we invalidate and remap all its instructions.
20188bcb0991SDimitry Andric // Stash it in a string so we can print it if we found an error.
20198bcb0991SDimitry Andric std::string ScheduleDump;
20208bcb0991SDimitry Andric raw_string_ostream OS(ScheduleDump);
20218bcb0991SDimitry Andric Schedule.print(OS);
20228bcb0991SDimitry Andric OS.flush();
20238bcb0991SDimitry Andric
20248bcb0991SDimitry Andric // First, run the normal ModuleScheduleExpander. We don't support any
20258bcb0991SDimitry Andric // InstrChanges.
20268bcb0991SDimitry Andric assert(LIS && "Requires LiveIntervals!");
20278bcb0991SDimitry Andric ModuloScheduleExpander MSE(MF, Schedule, *LIS,
20288bcb0991SDimitry Andric ModuloScheduleExpander::InstrChangesTy());
20298bcb0991SDimitry Andric MSE.expand();
20308bcb0991SDimitry Andric MachineBasicBlock *ExpandedKernel = MSE.getRewrittenKernel();
20318bcb0991SDimitry Andric if (!ExpandedKernel) {
20328bcb0991SDimitry Andric // The expander optimized away the kernel. We can't do any useful checking.
20338bcb0991SDimitry Andric MSE.cleanup();
20348bcb0991SDimitry Andric return;
20358bcb0991SDimitry Andric }
20368bcb0991SDimitry Andric // Before running the KernelRewriter, re-add BB into the CFG.
20378bcb0991SDimitry Andric Preheader->addSuccessor(BB);
20388bcb0991SDimitry Andric
20398bcb0991SDimitry Andric // Now run the new expansion algorithm.
2040fe6060f1SDimitry Andric KernelRewriter KR(*Schedule.getLoop(), Schedule, BB);
20418bcb0991SDimitry Andric KR.rewrite();
20428bcb0991SDimitry Andric peelPrologAndEpilogs();
20438bcb0991SDimitry Andric
20448bcb0991SDimitry Andric // Collect all illegal phis that the new algorithm created. We'll give these
20458bcb0991SDimitry Andric // to KernelOperandInfo.
20468bcb0991SDimitry Andric SmallPtrSet<MachineInstr *, 4> IllegalPhis;
20478bcb0991SDimitry Andric for (auto NI = BB->getFirstNonPHI(); NI != BB->end(); ++NI) {
20488bcb0991SDimitry Andric if (NI->isPHI())
20498bcb0991SDimitry Andric IllegalPhis.insert(&*NI);
20508bcb0991SDimitry Andric }
20518bcb0991SDimitry Andric
20528bcb0991SDimitry Andric // Co-iterate across both kernels. We expect them to be identical apart from
20538bcb0991SDimitry Andric // phis and full COPYs (we look through both).
20548bcb0991SDimitry Andric SmallVector<std::pair<KernelOperandInfo, KernelOperandInfo>, 8> KOIs;
20558bcb0991SDimitry Andric auto OI = ExpandedKernel->begin();
20568bcb0991SDimitry Andric auto NI = BB->begin();
20578bcb0991SDimitry Andric for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {
20588bcb0991SDimitry Andric while (OI->isPHI() || OI->isFullCopy())
20598bcb0991SDimitry Andric ++OI;
20608bcb0991SDimitry Andric while (NI->isPHI() || NI->isFullCopy())
20618bcb0991SDimitry Andric ++NI;
20628bcb0991SDimitry Andric assert(OI->getOpcode() == NI->getOpcode() && "Opcodes don't match?!");
20638bcb0991SDimitry Andric // Analyze every operand separately.
20648bcb0991SDimitry Andric for (auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();
20658bcb0991SDimitry Andric OOpI != OI->operands_end(); ++OOpI, ++NOpI)
20668bcb0991SDimitry Andric KOIs.emplace_back(KernelOperandInfo(&*OOpI, MRI, IllegalPhis),
20678bcb0991SDimitry Andric KernelOperandInfo(&*NOpI, MRI, IllegalPhis));
20688bcb0991SDimitry Andric }
20698bcb0991SDimitry Andric
20708bcb0991SDimitry Andric bool Failed = false;
20718bcb0991SDimitry Andric for (auto &OldAndNew : KOIs) {
20728bcb0991SDimitry Andric if (OldAndNew.first == OldAndNew.second)
20738bcb0991SDimitry Andric continue;
20748bcb0991SDimitry Andric Failed = true;
20758bcb0991SDimitry Andric errs() << "Modulo kernel validation error: [\n";
20768bcb0991SDimitry Andric errs() << " [golden] ";
20778bcb0991SDimitry Andric OldAndNew.first.print(errs());
20788bcb0991SDimitry Andric errs() << " ";
20798bcb0991SDimitry Andric OldAndNew.second.print(errs());
20808bcb0991SDimitry Andric errs() << "]\n";
20818bcb0991SDimitry Andric }
20828bcb0991SDimitry Andric
20838bcb0991SDimitry Andric if (Failed) {
20848bcb0991SDimitry Andric errs() << "Golden reference kernel:\n";
20858bcb0991SDimitry Andric ExpandedKernel->print(errs());
20868bcb0991SDimitry Andric errs() << "New kernel:\n";
20878bcb0991SDimitry Andric BB->print(errs());
20888bcb0991SDimitry Andric errs() << ScheduleDump;
20898bcb0991SDimitry Andric report_fatal_error(
20908bcb0991SDimitry Andric "Modulo kernel validation (-pipeliner-experimental-cg) failed");
20918bcb0991SDimitry Andric }
20928bcb0991SDimitry Andric
20938bcb0991SDimitry Andric // Cleanup by removing BB from the CFG again as the original
20948bcb0991SDimitry Andric // ModuloScheduleExpander intended.
20958bcb0991SDimitry Andric Preheader->removeSuccessor(BB);
20968bcb0991SDimitry Andric MSE.cleanup();
20978bcb0991SDimitry Andric }
20988bcb0991SDimitry Andric
20998bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
21008bcb0991SDimitry Andric // ModuloScheduleTestPass implementation
21018bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
21028bcb0991SDimitry Andric // This pass constructs a ModuloSchedule from its module and runs
21038bcb0991SDimitry Andric // ModuloScheduleExpander.
21048bcb0991SDimitry Andric //
21058bcb0991SDimitry Andric // The module is expected to contain a single-block analyzable loop.
21068bcb0991SDimitry Andric // The total order of instructions is taken from the loop as-is.
21078bcb0991SDimitry Andric // Instructions are expected to be annotated with a PostInstrSymbol.
21088bcb0991SDimitry Andric // This PostInstrSymbol must have the following format:
21098bcb0991SDimitry Andric // "Stage=%d Cycle=%d".
21108bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
21118bcb0991SDimitry Andric
21128bcb0991SDimitry Andric namespace {
21138bcb0991SDimitry Andric class ModuloScheduleTest : public MachineFunctionPass {
21148bcb0991SDimitry Andric public:
21158bcb0991SDimitry Andric static char ID;
21168bcb0991SDimitry Andric
ModuloScheduleTest()21178bcb0991SDimitry Andric ModuloScheduleTest() : MachineFunctionPass(ID) {
21188bcb0991SDimitry Andric initializeModuloScheduleTestPass(*PassRegistry::getPassRegistry());
21198bcb0991SDimitry Andric }
21208bcb0991SDimitry Andric
21218bcb0991SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override;
21228bcb0991SDimitry Andric void runOnLoop(MachineFunction &MF, MachineLoop &L);
21238bcb0991SDimitry Andric
getAnalysisUsage(AnalysisUsage & AU) const21248bcb0991SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override {
21258bcb0991SDimitry Andric AU.addRequired<MachineLoopInfo>();
21268bcb0991SDimitry Andric AU.addRequired<LiveIntervals>();
21278bcb0991SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU);
21288bcb0991SDimitry Andric }
21298bcb0991SDimitry Andric };
21308bcb0991SDimitry Andric } // namespace
21318bcb0991SDimitry Andric
21328bcb0991SDimitry Andric char ModuloScheduleTest::ID = 0;
21338bcb0991SDimitry Andric
21348bcb0991SDimitry Andric INITIALIZE_PASS_BEGIN(ModuloScheduleTest, "modulo-schedule-test",
21358bcb0991SDimitry Andric "Modulo Schedule test pass", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)21368bcb0991SDimitry Andric INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
21378bcb0991SDimitry Andric INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
21388bcb0991SDimitry Andric INITIALIZE_PASS_END(ModuloScheduleTest, "modulo-schedule-test",
21398bcb0991SDimitry Andric "Modulo Schedule test pass", false, false)
21408bcb0991SDimitry Andric
21418bcb0991SDimitry Andric bool ModuloScheduleTest::runOnMachineFunction(MachineFunction &MF) {
21428bcb0991SDimitry Andric MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
21438bcb0991SDimitry Andric for (auto *L : MLI) {
21448bcb0991SDimitry Andric if (L->getTopBlock() != L->getBottomBlock())
21458bcb0991SDimitry Andric continue;
21468bcb0991SDimitry Andric runOnLoop(MF, *L);
21478bcb0991SDimitry Andric return false;
21488bcb0991SDimitry Andric }
21498bcb0991SDimitry Andric return false;
21508bcb0991SDimitry Andric }
21518bcb0991SDimitry Andric
parseSymbolString(StringRef S,int & Cycle,int & Stage)21528bcb0991SDimitry Andric static void parseSymbolString(StringRef S, int &Cycle, int &Stage) {
21538bcb0991SDimitry Andric std::pair<StringRef, StringRef> StageAndCycle = getToken(S, "_");
21548bcb0991SDimitry Andric std::pair<StringRef, StringRef> StageTokenAndValue =
21558bcb0991SDimitry Andric getToken(StageAndCycle.first, "-");
21568bcb0991SDimitry Andric std::pair<StringRef, StringRef> CycleTokenAndValue =
21578bcb0991SDimitry Andric getToken(StageAndCycle.second, "-");
21588bcb0991SDimitry Andric if (StageTokenAndValue.first != "Stage" ||
21598bcb0991SDimitry Andric CycleTokenAndValue.first != "_Cycle") {
21608bcb0991SDimitry Andric llvm_unreachable(
21618bcb0991SDimitry Andric "Bad post-instr symbol syntax: see comment in ModuloScheduleTest");
21628bcb0991SDimitry Andric return;
21638bcb0991SDimitry Andric }
21648bcb0991SDimitry Andric
21658bcb0991SDimitry Andric StageTokenAndValue.second.drop_front().getAsInteger(10, Stage);
21668bcb0991SDimitry Andric CycleTokenAndValue.second.drop_front().getAsInteger(10, Cycle);
21678bcb0991SDimitry Andric
21688bcb0991SDimitry Andric dbgs() << " Stage=" << Stage << ", Cycle=" << Cycle << "\n";
21698bcb0991SDimitry Andric }
21708bcb0991SDimitry Andric
runOnLoop(MachineFunction & MF,MachineLoop & L)21718bcb0991SDimitry Andric void ModuloScheduleTest::runOnLoop(MachineFunction &MF, MachineLoop &L) {
21728bcb0991SDimitry Andric LiveIntervals &LIS = getAnalysis<LiveIntervals>();
21738bcb0991SDimitry Andric MachineBasicBlock *BB = L.getTopBlock();
21748bcb0991SDimitry Andric dbgs() << "--- ModuloScheduleTest running on BB#" << BB->getNumber() << "\n";
21758bcb0991SDimitry Andric
21768bcb0991SDimitry Andric DenseMap<MachineInstr *, int> Cycle, Stage;
21778bcb0991SDimitry Andric std::vector<MachineInstr *> Instrs;
21788bcb0991SDimitry Andric for (MachineInstr &MI : *BB) {
21798bcb0991SDimitry Andric if (MI.isTerminator())
21808bcb0991SDimitry Andric continue;
21818bcb0991SDimitry Andric Instrs.push_back(&MI);
21828bcb0991SDimitry Andric if (MCSymbol *Sym = MI.getPostInstrSymbol()) {
21838bcb0991SDimitry Andric dbgs() << "Parsing post-instr symbol for " << MI;
21848bcb0991SDimitry Andric parseSymbolString(Sym->getName(), Cycle[&MI], Stage[&MI]);
21858bcb0991SDimitry Andric }
21868bcb0991SDimitry Andric }
21878bcb0991SDimitry Andric
21888bcb0991SDimitry Andric ModuloSchedule MS(MF, &L, std::move(Instrs), std::move(Cycle),
21898bcb0991SDimitry Andric std::move(Stage));
21908bcb0991SDimitry Andric ModuloScheduleExpander MSE(
21918bcb0991SDimitry Andric MF, MS, LIS, /*InstrChanges=*/ModuloScheduleExpander::InstrChangesTy());
21928bcb0991SDimitry Andric MSE.expand();
21938bcb0991SDimitry Andric MSE.cleanup();
21948bcb0991SDimitry Andric }
21958bcb0991SDimitry Andric
21968bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
21978bcb0991SDimitry Andric // ModuloScheduleTestAnnotater implementation
21988bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
21998bcb0991SDimitry Andric
annotate()22008bcb0991SDimitry Andric void ModuloScheduleTestAnnotater::annotate() {
22018bcb0991SDimitry Andric for (MachineInstr *MI : S.getInstructions()) {
22028bcb0991SDimitry Andric SmallVector<char, 16> SV;
22038bcb0991SDimitry Andric raw_svector_ostream OS(SV);
22048bcb0991SDimitry Andric OS << "Stage-" << S.getStage(MI) << "_Cycle-" << S.getCycle(MI);
22058bcb0991SDimitry Andric MCSymbol *Sym = MF.getContext().getOrCreateSymbol(OS.str());
22068bcb0991SDimitry Andric MI->setPostInstrSymbol(MF, Sym);
22078bcb0991SDimitry Andric }
22088bcb0991SDimitry Andric }
2209