22 #define DEBUG_TYPE "pipeliner"
37 unsigned &InitVal,
unsigned &LoopVal) {
48 assert(InitVal != 0 && LoopVal != 0 &&
"Unexpected Phi structure.");
78 if (!
Op.isReg() || !
Op.isDef())
83 bool PhiIsSwapped =
false;
88 if (UseStage != -1 && UseStage >= DefStage)
89 Diff = UseStage - DefStage;
91 if (isLoopCarried(*
MI))
98 RegToStageDiff[
Reg] = std::make_pair(MaxDiff, PhiIsSwapped);
102 generatePipelinedLoop();
105 void ModuloScheduleExpander::generatePipelinedLoop() {
118 ValueMapTy *VRMap =
new ValueMapTy[(MaxStageCount + 1) * 2];
123 ValueMapTy *VRMapPhi =
new ValueMapTy[(MaxStageCount + 1) * 2];
130 generateProlog(MaxStageCount, KernelBB, VRMap, PrologBBs);
138 unsigned StageNum = Schedule.
getStage(CI);
139 MachineInstr *NewMI = cloneInstr(CI, MaxStageCount, StageNum);
140 updateInstruction(NewMI,
false, MaxStageCount, StageNum, VRMap);
142 InstrMap[NewMI] = CI;
149 updateInstruction(NewMI,
false, MaxStageCount, 0, VRMap);
151 InstrMap[NewMI] = &
MI;
154 NewKernel = KernelBB;
158 generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap,
159 InstrMap, MaxStageCount, MaxStageCount,
false);
160 generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap, VRMapPhi,
161 InstrMap, MaxStageCount, MaxStageCount,
false);
167 generateEpilog(MaxStageCount, KernelBB, BB, VRMap, VRMapPhi, EpilogBBs,
172 splitLifetimes(KernelBB, EpilogBBs);
175 removeDeadInstructions(KernelBB, EpilogBBs);
178 addBranches(*Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap);
189 BB->eraseFromParent();
193 void ModuloScheduleExpander::generateProlog(
unsigned LastStage,
196 MBBVectorTy &PrologBBs) {
203 for (
unsigned i = 0;
i < LastStage; ++
i) {
215 for (
int StageNum =
i; StageNum >= 0; --StageNum) {
219 if (Schedule.
getStage(&*BBI) == StageNum) {
223 cloneAndChangeInstr(&*BBI,
i, (
unsigned)StageNum);
224 updateInstruction(NewMI,
false,
i, (
unsigned)StageNum, VRMap);
226 InstrMap[NewMI] = &*BBI;
230 rewritePhiValues(NewBB,
i, VRMap, InstrMap);
232 dbgs() <<
"prolog:\n";
251 void ModuloScheduleExpander::generateEpilog(
253 ValueMapTy *VRMap, ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,
254 MBBVectorTy &PrologBBs) {
260 assert(!checkBranch &&
"generateEpilog must be able to analyze the branch");
265 if (*LoopExitI == KernelBB)
267 assert(LoopExitI != KernelBB->
succ_end() &&
"Expecting a successor");
277 int EpilogStage = LastStage + 1;
278 for (
unsigned i = LastStage;
i >= 1; --
i, ++EpilogStage) {
286 if (EpilogStart == LoopExitBB)
291 for (
unsigned StageNum =
i; StageNum <= LastStage; ++StageNum) {
292 for (
auto &BBI : *BB) {
296 if ((
unsigned)Schedule.
getStage(
In) == StageNum) {
300 updateInstruction(NewMI,
i == 1, EpilogStage, 0, VRMap);
302 InstrMap[NewMI] =
In;
306 generateExistingPhis(NewBB, PrologBBs[
i - 1], PredBB, KernelBB, VRMap,
307 InstrMap, LastStage, EpilogStage,
i == 1);
308 generatePhis(NewBB, PrologBBs[
i - 1], PredBB, KernelBB, VRMap, VRMapPhi,
309 InstrMap, LastStage, EpilogStage,
i == 1);
313 dbgs() <<
"epilog:\n";
324 assert((OrigBB ==
TBB || OrigBB == FBB) &&
325 "Unable to determine looping branch direction");
331 if (EpilogBBs.size() > 0) {
346 if (
O.getParent()->getParent() !=
MBB)
357 if (MO.getParent()->getParent() !=
BB)
365 void ModuloScheduleExpander::generateExistingPhis(
368 unsigned LastStageNum,
unsigned CurStageNum,
bool IsLast) {
372 unsigned PrologStage = 0;
373 unsigned PrevStage = 0;
374 bool InKernel = (LastStageNum == CurStageNum);
376 PrologStage = LastStageNum - 1;
377 PrevStage = CurStageNum;
379 PrologStage = LastStageNum - (CurStageNum - LastStageNum);
380 PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;
384 BBE =
BB->getFirstNonPHI();
388 unsigned InitVal = 0;
389 unsigned LoopVal = 0;
395 unsigned PhiOp2 = LoopVal;
396 if (VRMap[LastStageNum].
count(LoopVal))
397 PhiOp2 = VRMap[LastStageNum][LoopVal];
399 int StageScheduled = Schedule.
getStage(&*BBI);
401 unsigned NumStages = getStagesForReg(
Def, CurStageNum);
402 if (NumStages == 0) {
405 unsigned NewReg = VRMap[PrevStage][LoopVal];
406 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, 0, &*BBI,
Def,
408 if (VRMap[CurStageNum].
count(LoopVal))
409 VRMap[CurStageNum][
Def] = VRMap[CurStageNum][LoopVal];
415 unsigned MaxPhis = PrologStage + 2;
416 if (!InKernel && (
int)PrologStage <= LoopValStage)
417 MaxPhis =
std::max((
int)MaxPhis - (
int)LoopValStage, 1);
418 unsigned NumPhis =
std::min(NumStages, MaxPhis);
421 unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;
428 if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&
433 if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)
434 StageDiff = StageScheduled - LoopValStage;
435 for (
unsigned np = 0; np < NumPhis; ++np) {
439 if (np > PrologStage || StageScheduled >= (
int)LastStageNum)
442 else if (PrologStage >= AccessStage + StageDiff + np &&
443 VRMap[PrologStage - StageDiff - np].
count(LoopVal) != 0)
444 PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];
447 else if (PrologStage >= AccessStage + StageDiff + np) {
454 int PhiStage = Schedule.
getStage(InstOp1);
455 if ((
int)(PrologStage - StageDiff - np) < PhiStage + Indirects)
460 int PhiOpStage = Schedule.
getStage(InstOp1);
461 int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);
462 if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np &&
463 VRMap[PrologStage - StageAdj - Indirects - np].
count(PhiOp1)) {
464 PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1];
478 bool LoopDefIsPhi = PhiInst && PhiInst->
isPHI();
483 int StageDiffAdj = 0;
484 if (LoopValStage != -1 && StageScheduled > LoopValStage)
485 StageDiffAdj = StageScheduled - LoopValStage;
488 if (np == 0 && PrevStage == LastStageNum &&
489 (StageScheduled != 0 || LoopValStage != 0) &&
490 VRMap[PrevStage - StageDiffAdj].count(LoopVal))
491 PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal];
494 else if (np > 0 && PrevStage == LastStageNum &&
495 VRMap[PrevStage - np + 1].
count(
Def))
496 PhiOp2 = VRMap[PrevStage - np + 1][
Def];
498 else if (
static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&
499 VRMap[PrevStage - StageDiffAdj - np].count(LoopVal))
500 PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal];
503 else if (VRMap[PrevStage - np].
count(
Def) &&
504 (!LoopDefIsPhi || (PrevStage != LastStageNum) ||
505 (LoopValStage == StageScheduled)))
506 PhiOp2 = VRMap[PrevStage - np][
Def];
514 if (
static_cast<int>(PrologStage - np) >= StageScheduled) {
515 int LVNumStages = getStagesForPhi(LoopVal);
516 int StageDiff = (StageScheduled - LoopValStage);
517 LVNumStages -= StageDiff;
519 if (LVNumStages > (
int)np && VRMap[CurStageNum].count(LoopVal)) {
521 unsigned ReuseStage = CurStageNum;
522 if (isLoopCarried(*PhiInst))
523 ReuseStage -= LVNumStages;
526 if (VRMap[ReuseStage - np].
count(LoopVal)) {
527 NewReg = VRMap[ReuseStage - np][LoopVal];
529 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
532 VRMap[CurStageNum - np][
Def] = NewReg;
534 if (VRMap[LastStageNum - np - 1].
count(LoopVal))
535 PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];
537 if (IsLast && np == NumPhis - 1)
543 if (InKernel && StageDiff > 0 &&
544 VRMap[CurStageNum - StageDiff - np].
count(LoopVal))
545 PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];
557 InstrMap[NewPhi] = &*BBI;
562 unsigned PrevReg = 0;
563 if (InKernel && VRMap[PrevStage - np].
count(LoopVal))
564 PrevReg = VRMap[PrevStage - np][LoopVal];
565 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
Def,
568 if (VRMap[CurStageNum - np].
count(
Def)) {
569 unsigned R = VRMap[CurStageNum - np][
Def];
570 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, R,
577 if (IsLast && np == NumPhis - 1)
585 VRMap[CurStageNum - np][
Def] = NewReg;
588 while (NumPhis++ < NumStages) {
589 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, NumPhis, &*BBI,
Def,
595 if (NumStages == 0 && IsLast && VRMap[CurStageNum].
count(LoopVal))
603 void ModuloScheduleExpander::generatePhis(
606 InstrMapTy &InstrMap,
unsigned LastStageNum,
unsigned CurStageNum,
610 unsigned PrologStage = 0;
611 unsigned PrevStage = 0;
612 unsigned StageDiff = CurStageNum - LastStageNum;
613 bool InKernel = (StageDiff == 0);
615 PrologStage = LastStageNum - 1;
616 PrevStage = CurStageNum;
618 PrologStage = LastStageNum - StageDiff;
619 PrevStage = LastStageNum + StageDiff - 1;
623 BBE =
BB->instr_end();
625 for (
unsigned i = 0,
e = BBI->getNumOperands();
i !=
e; ++
i) {
630 int StageScheduled = Schedule.
getStage(&*BBI);
631 assert(StageScheduled != -1 &&
"Expecting scheduled instruction.");
633 unsigned NumPhis = getStagesForReg(
Def, CurStageNum);
637 if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&
640 if (!InKernel && (
unsigned)StageScheduled > PrologStage)
645 PhiOp2 = VRMap[PrevStage][
Def];
647 if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)
652 if (NumPhis > PrologStage + 1 - StageScheduled)
653 NumPhis = PrologStage + 1 - StageScheduled;
654 for (
unsigned np = 0; np < NumPhis; ++np) {
677 unsigned PhiOp1 = VRMap[PrologStage][
Def];
678 if (np <= PrologStage)
679 PhiOp1 = VRMap[PrologStage - np][
Def];
681 if (PrevStage == LastStageNum && np == 0)
682 PhiOp2 = VRMap[LastStageNum][
Def];
684 PhiOp2 = VRMapPhi[PrevStage - np][
Def];
696 InstrMap[NewPhi] = &*BBI;
701 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp1,
703 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp2,
707 VRMapPhi[PrevStage - np - 1][
Def] = NewReg;
709 VRMapPhi[CurStageNum - np][
Def] = NewReg;
710 if (np == NumPhis - 1)
711 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
Def,
714 if (IsLast && np == NumPhis - 1)
726 MBBVectorTy &EpilogBBs) {
734 if (
MI->isInlineAsm()) {
738 bool SawStore =
false;
741 if (!
MI->isSafeToMove(
nullptr, SawStore) && !
MI->isPHI()) {
757 unsigned realUses = 0;
761 if (U.getParent()->getParent() != BB) {
773 MI++->eraseFromParent();
784 MI.eraseFromParent();
800 MBBVectorTy &EpilogBBs) {
802 for (
auto &
PHI : KernelBB->
phis()) {
809 if (
I->isPHI() &&
I->getParent() == KernelBB) {
815 if (!
MI ||
MI->getParent() != KernelBB ||
MI->isPHI())
819 unsigned SplitReg = 0;
822 if (BBJ.readsRegister(
Def)) {
827 TII->
get(TargetOpcode::COPY), SplitReg)
830 BBJ.substituteRegister(
Def, SplitReg, 0, *
TRI);
835 for (
auto &
Epilog : EpilogBBs)
837 if (
I.readsRegister(
Def))
838 I.substituteRegister(
Def, SplitReg, 0, *
TRI);
850 for (
unsigned i = 1,
e =
MI.getNumOperands();
i !=
e;
i += 2)
851 if (
MI.getOperand(
i + 1).getMBB() == Incoming) {
852 MI.removeOperand(
i + 1);
863 MBBVectorTy &PrologBBs,
865 MBBVectorTy &EpilogBBs,
867 assert(PrologBBs.size() == EpilogBBs.size() &&
"Prolog/Epilog mismatch");
874 unsigned MaxIter = PrologBBs.size() - 1;
875 for (
unsigned i = 0,
j = MaxIter;
i <= MaxIter; ++
i, --
j) {
882 std::optional<bool> StaticallyGreater =
884 unsigned numAdded = 0;
885 if (!StaticallyGreater) {
888 }
else if (*StaticallyGreater ==
false) {
890 Prolog->removeSuccessor(LastPro);
895 if (LastPro != LastEpi) {
899 if (LastPro == KernelBB) {
913 I !=
E && numAdded > 0; ++
I, --numAdded)
914 updateInstruction(&*
I,
false,
j, 0, VRMap);
918 LoopInfo->setPreheader(PrologBBs[MaxIter]);
919 LoopInfo->adjustTripCount(-(MaxIter + 1));
925 bool ModuloScheduleExpander::computeDelta(
MachineInstr &
MI,
unsigned &Delta) {
929 bool OffsetIsScalable;
934 if (OffsetIsScalable)
937 if (!BaseOp->
isReg())
945 if (BaseDef && BaseDef->
isPHI()) {
963 void ModuloScheduleExpander::updateMemOperands(
MachineInstr &NewMI,
975 if (MMO->isVolatile() || MMO->isAtomic() ||
976 (MMO->isInvariant() && MMO->isDereferenceable()) ||
977 (!MMO->getValue())) {
978 NewMMOs.push_back(MMO);
982 if (Num != UINT_MAX && computeDelta(OldMI, Delta)) {
983 int64_t AdjOffset = Delta * Num;
997 unsigned CurStageNum,
998 unsigned InstStageNum) {
1000 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
1007 MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
1008 MachineInstr *OldMI,
unsigned CurStageNum,
unsigned InstStageNum) {
1010 auto It = InstrChanges.
find(OldMI);
1011 if (It != InstrChanges.
end()) {
1012 std::pair<unsigned, int64_t> RegAndOffset = It->second;
1013 unsigned BasePos, OffsetPos;
1017 MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first);
1018 if (Schedule.
getStage(LoopDef) > (
signed)InstStageNum)
1019 NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
1022 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
1028 void ModuloScheduleExpander::updateInstruction(
MachineInstr *NewMI,
1030 unsigned CurStageNum,
1031 unsigned InstrStageNum,
1032 ValueMapTy *VRMap) {
1042 VRMap[CurStageNum][reg] = NewReg;
1045 }
else if (MO.
isUse()) {
1049 unsigned StageNum = CurStageNum;
1050 if (DefStageNum != -1 && (
int)InstrStageNum > DefStageNum) {
1052 unsigned StageDiff = (InstrStageNum - DefStageNum);
1054 StageNum -= StageDiff;
1056 if (VRMap[StageNum].
count(reg))
1057 MO.
setReg(VRMap[StageNum][reg]);
1068 while (
Def->isPHI()) {
1071 for (
unsigned i = 1,
e =
Def->getNumOperands();
i <
e;
i += 2)
1072 if (
Def->getOperand(
i + 1).getMBB() == BB) {
1081 unsigned ModuloScheduleExpander::getPrevMapVal(
1082 unsigned StageNum,
unsigned PhiStage,
unsigned LoopVal,
unsigned LoopStage,
1084 unsigned PrevVal = 0;
1085 if (StageNum > PhiStage) {
1087 if (PhiStage == LoopStage && VRMap[StageNum - 1].
count(LoopVal))
1089 PrevVal = VRMap[StageNum - 1][LoopVal];
1090 else if (VRMap[StageNum].
count(LoopVal))
1093 PrevVal = VRMap[StageNum][LoopVal];
1097 else if (StageNum == PhiStage + 1)
1100 else if (StageNum > PhiStage + 1 && LoopInst->
getParent() == BB)
1103 getPrevMapVal(StageNum - 1, PhiStage,
getLoopPhiReg(*LoopInst, BB),
1104 LoopStage, VRMap, BB);
1116 InstrMapTy &InstrMap) {
1117 for (
auto &
PHI :
BB->phis()) {
1118 unsigned InitVal = 0;
1119 unsigned LoopVal = 0;
1125 unsigned NumPhis = getStagesForPhi(PhiDef);
1126 if (NumPhis > StageNum)
1128 for (
unsigned np = 0; np <= NumPhis; ++np) {
1130 getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
1133 rewriteScheduledInstr(NewBB, InstrMap, StageNum - np, np, &
PHI, PhiDef,
1142 void ModuloScheduleExpander::rewriteScheduledInstr(
1144 unsigned PhiNum,
MachineInstr *Phi,
unsigned OldReg,
unsigned NewReg,
1146 bool InProlog = (CurStageNum < (unsigned)Schedule.
getNumStages() - 1);
1147 int StagePhi = Schedule.
getStage(Phi) + PhiNum;
1162 assert(OrigInstr != InstrMap.end() &&
"Instruction not scheduled.");
1164 int StageSched = Schedule.
getStage(OrigMI);
1165 int CycleSched = Schedule.
getCycle(OrigMI);
1166 unsigned ReplaceReg = 0;
1168 if (StagePhi == StageSched && Phi->
isPHI()) {
1169 int CyclePhi = Schedule.
getCycle(Phi);
1170 if (PrevReg && InProlog)
1171 ReplaceReg = PrevReg;
1172 else if (PrevReg && !isLoopCarried(*Phi) &&
1173 (CyclePhi <= CycleSched || OrigMI->isPHI()))
1174 ReplaceReg = PrevReg;
1176 ReplaceReg = NewReg;
1180 if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(*Phi))
1181 ReplaceReg = NewReg;
1182 if (StagePhi > StageSched && Phi->
isPHI())
1183 ReplaceReg = NewReg;
1184 if (!InProlog && !Phi->
isPHI() && StagePhi < StageSched)
1185 ReplaceReg = NewReg;
1190 UseOp.setReg(ReplaceReg);
1196 UseOp.setReg(SplitReg);
1202 bool ModuloScheduleExpander::isLoopCarried(
MachineInstr &Phi) {
1205 int DefCycle = Schedule.
getCycle(&Phi);
1206 int DefStage = Schedule.
getStage(&Phi);
1208 unsigned InitVal = 0;
1209 unsigned LoopVal = 0;
1212 if (!
Use ||
Use->isPHI())
1216 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
1231 bool Changed =
true;
1239 MI.eraseFromParent();
1241 }
else if (!KeepSingleSrcPhi &&
MI.getNumExplicitOperands() == 3) {
1245 assert(ConstrainRegClass &&
1246 "Expected a valid constrained register class!");
1247 (void)ConstrainRegClass;
1249 MI.getOperand(1).getReg());
1252 MI.eraseFromParent();
1261 class KernelRewriter {
1297 :
S(
S),
BB(LoopBB), PreheaderBB(L.getLoopPreheader()),
1300 PreheaderBB = *
BB->pred_begin();
1301 if (PreheaderBB ==
BB)
1302 PreheaderBB = *std::next(
BB->pred_begin());
1310 auto InsertPt =
BB->getFirstTerminator();
1315 if (
MI->getParent())
1316 MI->removeFromParent();
1317 BB->insert(InsertPt,
MI);
1321 assert(FirstMI &&
"Failed to find first MI in schedule");
1328 (
I++)->eraseFromParent();
1333 if (
MI.isPHI() ||
MI.isTerminator())
1342 EliminateDeadPhis(
BB,
MRI, LIS);
1348 for (
auto MI =
BB->getFirstNonPHI();
MI !=
BB->end(); ++
MI) {
1357 if (
MI.getParent() !=
BB) {
1371 int ConsumerStage =
S.getStage(&
MI);
1378 int ProducerStage =
S.getStage(Producer);
1379 assert(ConsumerStage != -1 &&
1380 "In-loop consumer should always be scheduled!");
1381 assert(ConsumerStage >= ProducerStage);
1382 unsigned StageDiff = ConsumerStage - ProducerStage;
1384 for (
unsigned I = 0;
I < StageDiff; ++
I)
1394 while (LoopProducer->isPHI() && LoopProducer->getParent() ==
BB) {
1400 int LoopProducerStage =
S.getStage(LoopProducer);
1402 std::optional<Register> IllegalPhiDefault;
1404 if (LoopProducerStage == -1) {
1406 }
else if (LoopProducerStage > ConsumerStage) {
1411 #ifndef NDEBUG // Silence unused variables in non-asserts mode.
1412 int LoopProducerCycle =
S.getCycle(LoopProducer);
1413 int ConsumerCycle =
S.getCycle(&
MI);
1415 assert(LoopProducerCycle <= ConsumerCycle);
1416 assert(LoopProducerStage == ConsumerStage + 1);
1423 IllegalPhiDefault = Defaults.front();
1424 Defaults.
erase(Defaults.begin());
1426 assert(ConsumerStage >= LoopProducerStage);
1427 int StageDiff = ConsumerStage - LoopProducerStage;
1428 if (StageDiff > 0) {
1429 LLVM_DEBUG(
dbgs() <<
" -- padding defaults array from " << Defaults.size()
1430 <<
" to " << (Defaults.size() + StageDiff) <<
"\n");
1434 Defaults.
resize(Defaults.size() + StageDiff,
1435 Defaults.empty() ? std::optional<Register>()
1441 auto DefaultI = Defaults.rbegin();
1442 while (DefaultI != Defaults.rend())
1445 if (IllegalPhiDefault) {
1455 .
addReg(*IllegalPhiDefault)
1461 S.setStage(IllegalPhi, LoopProducerStage);
1472 auto I = Phis.find({LoopReg, *InitReg});
1473 if (
I != Phis.end())
1476 for (
auto &KV : Phis) {
1477 if (KV.first.first == LoopReg)
1484 auto I = UndefPhis.find(LoopReg);
1485 if (
I != UndefPhis.end()) {
1493 MI->getOperand(1).setReg(*InitReg);
1494 Phis.insert({{LoopReg, *InitReg},
R});
1497 assert(ConstrainRegClass &&
"Expected a valid constrained register class!");
1498 (void)ConstrainRegClass;
1510 assert(ConstrainRegClass &&
"Expected a valid constrained register class!");
1511 (void)ConstrainRegClass;
1514 .
addReg(InitReg ? *InitReg : undef(RC))
1519 UndefPhis[LoopReg] =
R;
1521 Phis[{LoopReg, *InitReg}] =
R;
1534 TII->get(TargetOpcode::IMPLICIT_DEF),
R);
1543 class KernelOperandInfo {
1556 while (isRegInLoop(MO)) {
1558 if (
MI->isFullCopy()) {
1559 MO = &
MI->getOperand(1);
1566 MO = &
MI->getOperand(3);
1571 MO =
MI->getOperand(2).getMBB() ==
BB ? &
MI->getOperand(1)
1572 : &
MI->getOperand(3);
1573 PhiDefaults.push_back(
Default);
1579 return PhiDefaults.size() ==
Other.PhiDefaults.size();
1583 OS <<
"use of " << *
Source <<
": distance(" << PhiDefaults.size() <<
") in "
1602 for (
auto I =
BB->
begin(), NI = NewBB->
begin(); !
I->isTerminator();
1618 if (Stage == -1 || Stage >= MinStage)
1631 for (
auto &Sub : Subs)
1632 Sub.first->substituteRegister(DefMO.getReg(), Sub.second, 0,
1637 MI->eraseFromParent();
1667 MI.removeFromParent();
1671 BlockMIs.erase({SourceBB, KernelMI});
1681 assert(
Def->findRegisterDefOperandIdx(
MI.getOperand(1).getReg()) != -1);
1683 MI.getOperand(0).setReg(PhiReg);
1684 PhiToDelete.push_back(&
MI);
1687 for (
auto *
P : PhiToDelete)
1688 P->eraseFromParent();
1694 DestBB->
insert(InsertPt, NewMI);
1716 if (
Use &&
Use->isPHI() &&
Use->getParent() == SourceBB) {
1731 for (
unsigned I = 0;
I < distance; ++
I) {
1734 unsigned LoopRegIdx = 3, InitRegIdx = 1;
1740 return CanonicalUseReg;
1765 EliminateDeadPhis(ExitingBB,
MRI,
LIS,
true);
1788 EliminateDeadPhis(
B,
MRI,
LIS,
true);
1792 for (
size_t I = 0;
I <
Epilogs.size();
I++) {
1794 for (
size_t J =
I; J <
Epilogs.size(); J++) {
1798 for (
size_t K = Iteration; K >
I; K--)
1812 for (; PI !=
Prologs.end(); ++PI, ++EI) {
1814 (*PI)->addSuccessor(*EI);
1818 if (
Use &&
Use->getParent() == Pred) {
1820 if (CanonicalUse->
isPHI()) {
1836 Blocks.push_back(
BB);
1841 for (
auto I =
B->instr_rbegin();
1842 I != std::next(
B->getFirstNonPHI()->getReverseIterator());) {
1850 MI->eraseFromParent();
1856 EliminateDeadPhis(
B,
MRI,
LIS);
1857 EliminateDeadPhis(ExitingBB,
MRI,
LIS);
1876 if (
Use.getParent() !=
BB)
1879 Use->substituteRegister(OldR, R, 0,
1895 assert(CanAnalyzeBr &&
"Must be able to analyze the loop branch!");
1907 unsigned OpIdx =
MI->findRegisterDefOperandIdx(
Reg);
1919 R =
MI->getOperand(1).getReg();
1924 MI->getOperand(0).setReg(PhiR);
1930 if (Stage == -1 ||
LiveStages.count(
MI->getParent()) == 0 ||
1945 for (
auto &Sub : Subs)
1946 Sub.first->substituteRegister(DefMO.getReg(), Sub.second, 0,
1951 MI->eraseFromParent();
1956 bool KernelDisposed =
false;
1965 std::optional<bool> StaticallyGreater =
1967 if (!StaticallyGreater) {
1971 }
else if (*StaticallyGreater ==
false) {
1975 Prolog->removeSuccessor(Fallthrough);
1981 KernelDisposed =
true;
1993 if (!KernelDisposed) {
2024 std::string ScheduleDump;
2031 assert(
LIS &&
"Requires LiveIntervals!");
2036 if (!ExpandedKernel) {
2054 IllegalPhis.
insert(&*NI);
2060 auto OI = ExpandedKernel->
begin();
2062 for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {
2063 while (OI->isPHI() || OI->isFullCopy())
2065 while (NI->isPHI() || NI->isFullCopy())
2067 assert(OI->getOpcode() == NI->getOpcode() &&
"Opcodes don't match?!");
2069 for (
auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();
2070 OOpI != OI->operands_end(); ++OOpI, ++NOpI)
2072 KernelOperandInfo(&*NOpI,
MRI, IllegalPhis));
2076 for (
auto &OldAndNew : KOIs) {
2077 if (OldAndNew.first == OldAndNew.second)
2080 errs() <<
"Modulo kernel validation error: [\n";
2081 errs() <<
" [golden] ";
2082 OldAndNew.first.print(
errs());
2084 OldAndNew.second.print(
errs());
2089 errs() <<
"Golden reference kernel:\n";
2091 errs() <<
"New kernel:\n";
2093 errs() << ScheduleDump;
2095 "Modulo kernel validation (-pipeliner-experimental-cg) failed");
2140 "Modulo Schedule test pass",
false,
false)
2148 for (
auto *L : MLI) {
2158 std::pair<StringRef, StringRef> StageAndCycle = getToken(
S,
"_");
2159 std::pair<StringRef, StringRef> StageTokenAndValue =
2160 getToken(StageAndCycle.first,
"-");
2161 std::pair<StringRef, StringRef> CycleTokenAndValue =
2162 getToken(StageAndCycle.second,
"-");
2163 if (StageTokenAndValue.first !=
"Stage" ||
2164 CycleTokenAndValue.first !=
"_Cycle") {
2166 "Bad post-instr symbol syntax: see comment in ModuloScheduleTest");
2170 StageTokenAndValue.second.drop_front().getAsInteger(10, Stage);
2171 CycleTokenAndValue.second.drop_front().getAsInteger(10,
Cycle);
2173 dbgs() <<
" Stage=" << Stage <<
", Cycle=" <<
Cycle <<
"\n";
2179 dbgs() <<
"--- ModuloScheduleTest running on BB#" <<
BB->getNumber() <<
"\n";
2182 std::vector<MachineInstr *> Instrs;
2184 if (
MI.isTerminator())
2186 Instrs.push_back(&
MI);
2187 if (
MCSymbol *Sym =
MI.getPostInstrSymbol()) {
2188 dbgs() <<
"Parsing post-instr symbol for " <<
MI;
2209 OS <<
"Stage-" <<
S.getStage(
MI) <<
"_Cycle-" <<
S.getCycle(
MI);
2211 MI->setPostInstrSymbol(MF, Sym);