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];
124 generateProlog(MaxStageCount, KernelBB, VRMap, PrologBBs);
132 unsigned StageNum = Schedule.
getStage(CI);
133 MachineInstr *NewMI = cloneInstr(CI, MaxStageCount, StageNum);
134 updateInstruction(NewMI,
false, MaxStageCount, StageNum, VRMap);
136 InstrMap[NewMI] = CI;
143 updateInstruction(NewMI,
false, MaxStageCount, 0, VRMap);
145 InstrMap[NewMI] = &
MI;
148 NewKernel = KernelBB;
152 generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap,
153 InstrMap, MaxStageCount, MaxStageCount,
false);
154 generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap, InstrMap,
155 MaxStageCount, MaxStageCount,
false);
161 generateEpilog(MaxStageCount, KernelBB, BB, VRMap, EpilogBBs, PrologBBs);
165 splitLifetimes(KernelBB, EpilogBBs);
168 removeDeadInstructions(KernelBB, EpilogBBs);
171 addBranches(*Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap);
181 BB->eraseFromParent();
185 void ModuloScheduleExpander::generateProlog(
unsigned LastStage,
188 MBBVectorTy &PrologBBs) {
195 for (
unsigned i = 0;
i < LastStage; ++
i) {
207 for (
int StageNum =
i; StageNum >= 0; --StageNum) {
211 if (Schedule.
getStage(&*BBI) == StageNum) {
215 cloneAndChangeInstr(&*BBI,
i, (
unsigned)StageNum);
216 updateInstruction(NewMI,
false,
i, (
unsigned)StageNum, VRMap);
218 InstrMap[NewMI] = &*BBI;
222 rewritePhiValues(NewBB,
i, VRMap, InstrMap);
224 dbgs() <<
"prolog:\n";
243 void ModuloScheduleExpander::generateEpilog(
245 ValueMapTy *VRMap, MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs) {
251 assert(!checkBranch &&
"generateEpilog must be able to analyze the branch");
256 if (*LoopExitI == KernelBB)
258 assert(LoopExitI != KernelBB->
succ_end() &&
"Expecting a successor");
268 int EpilogStage = LastStage + 1;
269 for (
unsigned i = LastStage;
i >= 1; --
i, ++EpilogStage) {
277 if (EpilogStart == LoopExitBB)
282 for (
unsigned StageNum =
i; StageNum <= LastStage; ++StageNum) {
283 for (
auto &BBI : *BB) {
287 if ((
unsigned)Schedule.
getStage(
In) == StageNum) {
291 updateInstruction(NewMI,
i == 1, EpilogStage, 0, VRMap);
293 InstrMap[NewMI] =
In;
297 generateExistingPhis(NewBB, PrologBBs[
i - 1], PredBB, KernelBB, VRMap,
298 InstrMap, LastStage, EpilogStage,
i == 1);
299 generatePhis(NewBB, PrologBBs[
i - 1], PredBB, KernelBB, VRMap, InstrMap,
300 LastStage, EpilogStage,
i == 1);
304 dbgs() <<
"epilog:\n";
315 assert((OrigBB == TBB || OrigBB == FBB) &&
316 "Unable to determine looping branch direction");
322 if (EpilogBBs.size() > 0) {
337 if (
O.getParent()->getParent() !=
MBB)
348 if (MO.getParent()->getParent() !=
BB)
356 void ModuloScheduleExpander::generateExistingPhis(
359 unsigned LastStageNum,
unsigned CurStageNum,
bool IsLast) {
363 unsigned PrologStage = 0;
364 unsigned PrevStage = 0;
365 bool InKernel = (LastStageNum == CurStageNum);
367 PrologStage = LastStageNum - 1;
368 PrevStage = CurStageNum;
370 PrologStage = LastStageNum - (CurStageNum - LastStageNum);
371 PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;
375 BBE =
BB->getFirstNonPHI();
379 unsigned InitVal = 0;
380 unsigned LoopVal = 0;
386 unsigned PhiOp2 = LoopVal;
387 if (VRMap[LastStageNum].
count(LoopVal))
388 PhiOp2 = VRMap[LastStageNum][LoopVal];
390 int StageScheduled = Schedule.
getStage(&*BBI);
392 unsigned NumStages = getStagesForReg(
Def, CurStageNum);
393 if (NumStages == 0) {
396 unsigned NewReg = VRMap[PrevStage][LoopVal];
397 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, 0, &*BBI,
Def,
399 if (VRMap[CurStageNum].
count(LoopVal))
400 VRMap[CurStageNum][
Def] = VRMap[CurStageNum][LoopVal];
406 unsigned MaxPhis = PrologStage + 2;
407 if (!InKernel && (
int)PrologStage <= LoopValStage)
408 MaxPhis =
std::max((
int)MaxPhis - (
int)LoopValStage, 1);
409 unsigned NumPhis =
std::min(NumStages, MaxPhis);
412 unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;
419 if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&
424 if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)
425 StageDiff = StageScheduled - LoopValStage;
426 for (
unsigned np = 0; np < NumPhis; ++np) {
430 if (np > PrologStage || StageScheduled >= (
int)LastStageNum)
433 else if (PrologStage >= AccessStage + StageDiff + np &&
434 VRMap[PrologStage - StageDiff - np].
count(LoopVal) != 0)
435 PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];
438 else if (PrologStage >= AccessStage + StageDiff + np) {
445 int PhiStage = Schedule.
getStage(InstOp1);
446 if ((
int)(PrologStage - StageDiff - np) < PhiStage + Indirects)
451 int PhiOpStage = Schedule.
getStage(InstOp1);
452 int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);
453 if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np &&
454 VRMap[PrologStage - StageAdj - Indirects - np].
count(PhiOp1)) {
455 PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1];
469 bool LoopDefIsPhi = PhiInst && PhiInst->
isPHI();
474 int StageDiffAdj = 0;
475 if (LoopValStage != -1 && StageScheduled > LoopValStage)
476 StageDiffAdj = StageScheduled - LoopValStage;
479 if (np == 0 && PrevStage == LastStageNum &&
480 (StageScheduled != 0 || LoopValStage != 0) &&
481 VRMap[PrevStage - StageDiffAdj].count(LoopVal))
482 PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal];
485 else if (np > 0 && PrevStage == LastStageNum &&
486 VRMap[PrevStage - np + 1].
count(
Def))
487 PhiOp2 = VRMap[PrevStage - np + 1][
Def];
489 else if (
static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&
490 VRMap[PrevStage - StageDiffAdj - np].count(LoopVal))
491 PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal];
494 else if (VRMap[PrevStage - np].
count(
Def) &&
495 (!LoopDefIsPhi || (PrevStage != LastStageNum) ||
496 (LoopValStage == StageScheduled)))
497 PhiOp2 = VRMap[PrevStage - np][
Def];
505 if (
static_cast<int>(PrologStage - np) >= StageScheduled) {
506 int LVNumStages = getStagesForPhi(LoopVal);
507 int StageDiff = (StageScheduled - LoopValStage);
508 LVNumStages -= StageDiff;
510 if (LVNumStages > (
int)np && VRMap[CurStageNum].count(LoopVal)) {
512 unsigned ReuseStage = CurStageNum;
513 if (isLoopCarried(*PhiInst))
514 ReuseStage -= LVNumStages;
517 if (VRMap[ReuseStage - np].
count(LoopVal)) {
518 NewReg = VRMap[ReuseStage - np][LoopVal];
520 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
523 VRMap[CurStageNum - np][
Def] = NewReg;
525 if (VRMap[LastStageNum - np - 1].
count(LoopVal))
526 PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];
528 if (IsLast && np == NumPhis - 1)
534 if (InKernel && StageDiff > 0 &&
535 VRMap[CurStageNum - StageDiff - np].
count(LoopVal))
536 PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];
544 TII->
get(TargetOpcode::PHI), NewReg);
548 InstrMap[NewPhi] = &*BBI;
553 unsigned PrevReg = 0;
554 if (InKernel && VRMap[PrevStage - np].
count(LoopVal))
555 PrevReg = VRMap[PrevStage - np][LoopVal];
556 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
Def,
559 if (VRMap[CurStageNum - np].
count(
Def)) {
560 unsigned R = VRMap[CurStageNum - np][
Def];
561 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, R,
568 if (IsLast && np == NumPhis - 1)
576 VRMap[CurStageNum - np][
Def] = NewReg;
579 while (NumPhis++ < NumStages) {
580 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, NumPhis, &*BBI,
Def,
586 if (NumStages == 0 && IsLast && VRMap[CurStageNum].
count(LoopVal))
594 void ModuloScheduleExpander::generatePhis(
597 unsigned LastStageNum,
unsigned CurStageNum,
bool IsLast) {
600 unsigned PrologStage = 0;
601 unsigned PrevStage = 0;
602 unsigned StageDiff = CurStageNum - LastStageNum;
603 bool InKernel = (StageDiff == 0);
605 PrologStage = LastStageNum - 1;
606 PrevStage = CurStageNum;
608 PrologStage = LastStageNum - StageDiff;
609 PrevStage = LastStageNum + StageDiff - 1;
613 BBE =
BB->instr_end();
615 for (
unsigned i = 0,
e = BBI->getNumOperands();
i !=
e; ++
i) {
621 int StageScheduled = Schedule.
getStage(&*BBI);
622 assert(StageScheduled != -1 &&
"Expecting scheduled instruction.");
624 unsigned NumPhis = getStagesForReg(
Def, CurStageNum);
628 if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&
631 if (!InKernel && (
unsigned)StageScheduled > PrologStage)
634 unsigned PhiOp2 = VRMap[PrevStage][
Def];
636 if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)
640 if (NumPhis > PrologStage + 1 - StageScheduled)
641 NumPhis = PrologStage + 1 - StageScheduled;
642 for (
unsigned np = 0; np < NumPhis; ++np) {
643 unsigned PhiOp1 = VRMap[PrologStage][
Def];
644 if (np <= PrologStage)
645 PhiOp1 = VRMap[PrologStage - np][
Def];
653 PhiOp2 = VRMap[PrevStage - np][
Def];
660 TII->
get(TargetOpcode::PHI), NewReg);
664 InstrMap[NewPhi] = &*BBI;
669 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp1,
671 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp2,
675 VRMap[PrevStage - np - 1][
Def] = NewReg;
677 VRMap[CurStageNum - np][
Def] = NewReg;
678 if (np == NumPhis - 1)
679 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
Def,
682 if (IsLast && np == NumPhis - 1)
694 MBBVectorTy &EpilogBBs) {
702 if (
MI->isInlineAsm()) {
706 bool SawStore =
false;
709 if (!
MI->isSafeToMove(
nullptr, SawStore) && !
MI->isPHI()) {
725 unsigned realUses = 0;
729 if (U.getParent()->getParent() != BB) {
741 MI++->eraseFromParent();
752 MI.eraseFromParent();
768 MBBVectorTy &EpilogBBs) {
770 for (
auto &PHI : KernelBB->
phis()) {
777 if (
I->isPHI() &&
I->getParent() == KernelBB) {
783 if (!
MI ||
MI->getParent() != KernelBB ||
MI->isPHI())
787 unsigned SplitReg = 0;
790 if (BBJ.readsRegister(
Def)) {
795 TII->
get(TargetOpcode::COPY), SplitReg)
798 BBJ.substituteRegister(
Def, SplitReg, 0, *
TRI);
803 for (
auto &
Epilog : EpilogBBs)
805 if (
I.readsRegister(
Def))
806 I.substituteRegister(
Def, SplitReg, 0, *
TRI);
818 for (
unsigned i = 1,
e =
MI.getNumOperands();
i !=
e;
i += 2)
819 if (
MI.getOperand(
i + 1).getMBB() == Incoming) {
820 MI.removeOperand(
i + 1);
831 MBBVectorTy &PrologBBs,
833 MBBVectorTy &EpilogBBs,
835 assert(PrologBBs.size() == EpilogBBs.size() &&
"Prolog/Epilog mismatch");
842 unsigned MaxIter = PrologBBs.size() - 1;
843 for (
unsigned i = 0,
j = MaxIter;
i <= MaxIter; ++
i, --
j) {
852 unsigned numAdded = 0;
853 if (!StaticallyGreater.
hasValue()) {
856 }
else if (*StaticallyGreater ==
false) {
858 Prolog->removeSuccessor(LastPro);
863 if (LastPro != LastEpi) {
867 if (LastPro == KernelBB) {
881 I !=
E && numAdded > 0; ++
I, --numAdded)
882 updateInstruction(&*
I,
false,
j, 0, VRMap);
886 LoopInfo->setPreheader(PrologBBs[MaxIter]);
887 LoopInfo->adjustTripCount(-(MaxIter + 1));
893 bool ModuloScheduleExpander::computeDelta(
MachineInstr &
MI,
unsigned &Delta) {
897 bool OffsetIsScalable;
902 if (OffsetIsScalable)
905 if (!BaseOp->
isReg())
913 if (BaseDef && BaseDef->
isPHI()) {
931 void ModuloScheduleExpander::updateMemOperands(
MachineInstr &NewMI,
943 if (MMO->isVolatile() || MMO->isAtomic() ||
944 (MMO->isInvariant() && MMO->isDereferenceable()) ||
945 (!MMO->getValue())) {
946 NewMMOs.push_back(MMO);
950 if (Num != UINT_MAX && computeDelta(OldMI, Delta)) {
951 int64_t AdjOffset = Delta * Num;
965 unsigned CurStageNum,
966 unsigned InstStageNum) {
979 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
986 MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
987 MachineInstr *OldMI,
unsigned CurStageNum,
unsigned InstStageNum) {
989 auto It = InstrChanges.
find(OldMI);
990 if (It != InstrChanges.
end()) {
991 std::pair<unsigned, int64_t> RegAndOffset = It->second;
992 unsigned BasePos, OffsetPos;
996 MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first);
997 if (Schedule.
getStage(LoopDef) > (
signed)InstStageNum)
998 NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
1001 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
1007 void ModuloScheduleExpander::updateInstruction(
MachineInstr *NewMI,
1009 unsigned CurStageNum,
1010 unsigned InstrStageNum,
1011 ValueMapTy *VRMap) {
1021 VRMap[CurStageNum][reg] = NewReg;
1024 }
else if (MO.
isUse()) {
1028 unsigned StageNum = CurStageNum;
1029 if (DefStageNum != -1 && (
int)InstrStageNum > DefStageNum) {
1031 unsigned StageDiff = (InstrStageNum - DefStageNum);
1033 StageNum -= StageDiff;
1035 if (VRMap[StageNum].
count(reg))
1036 MO.
setReg(VRMap[StageNum][reg]);
1047 while (
Def->isPHI()) {
1050 for (
unsigned i = 1,
e =
Def->getNumOperands();
i <
e;
i += 2)
1051 if (
Def->getOperand(
i + 1).getMBB() == BB) {
1060 unsigned ModuloScheduleExpander::getPrevMapVal(
1061 unsigned StageNum,
unsigned PhiStage,
unsigned LoopVal,
unsigned LoopStage,
1063 unsigned PrevVal = 0;
1064 if (StageNum > PhiStage) {
1066 if (PhiStage == LoopStage && VRMap[StageNum - 1].
count(LoopVal))
1068 PrevVal = VRMap[StageNum - 1][LoopVal];
1069 else if (VRMap[StageNum].
count(LoopVal))
1072 PrevVal = VRMap[StageNum][LoopVal];
1076 else if (StageNum == PhiStage + 1)
1079 else if (StageNum > PhiStage + 1 && LoopInst->
getParent() == BB)
1082 getPrevMapVal(StageNum - 1, PhiStage,
getLoopPhiReg(*LoopInst, BB),
1083 LoopStage, VRMap, BB);
1095 InstrMapTy &InstrMap) {
1096 for (
auto &PHI :
BB->phis()) {
1097 unsigned InitVal = 0;
1098 unsigned LoopVal = 0;
1100 Register PhiDef = PHI.getOperand(0).getReg();
1104 unsigned NumPhis = getStagesForPhi(PhiDef);
1105 if (NumPhis > StageNum)
1107 for (
unsigned np = 0; np <= NumPhis; ++np) {
1109 getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
1112 rewriteScheduledInstr(NewBB, InstrMap, StageNum - np, np, &PHI, PhiDef,
1121 void ModuloScheduleExpander::rewriteScheduledInstr(
1123 unsigned PhiNum,
MachineInstr *Phi,
unsigned OldReg,
unsigned NewReg,
1125 bool InProlog = (CurStageNum < (unsigned)Schedule.
getNumStages() - 1);
1126 int StagePhi = Schedule.
getStage(Phi) + PhiNum;
1141 assert(OrigInstr != InstrMap.end() &&
"Instruction not scheduled.");
1143 int StageSched = Schedule.
getStage(OrigMI);
1144 int CycleSched = Schedule.
getCycle(OrigMI);
1145 unsigned ReplaceReg = 0;
1147 if (StagePhi == StageSched && Phi->
isPHI()) {
1148 int CyclePhi = Schedule.
getCycle(Phi);
1149 if (PrevReg && InProlog)
1150 ReplaceReg = PrevReg;
1151 else if (PrevReg && !isLoopCarried(*Phi) &&
1152 (CyclePhi <= CycleSched || OrigMI->isPHI()))
1153 ReplaceReg = PrevReg;
1155 ReplaceReg = NewReg;
1159 if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(*Phi))
1160 ReplaceReg = NewReg;
1161 if (StagePhi > StageSched && Phi->
isPHI())
1162 ReplaceReg = NewReg;
1163 if (!InProlog && !Phi->
isPHI() && StagePhi < StageSched)
1164 ReplaceReg = NewReg;
1167 UseOp.setReg(ReplaceReg);
1172 bool ModuloScheduleExpander::isLoopCarried(
MachineInstr &Phi) {
1175 int DefCycle = Schedule.
getCycle(&Phi);
1176 int DefStage = Schedule.
getStage(&Phi);
1178 unsigned InitVal = 0;
1179 unsigned LoopVal = 0;
1182 if (!
Use ||
Use->isPHI())
1186 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
1201 bool Changed =
true;
1209 MI.eraseFromParent();
1211 }
else if (!KeepSingleSrcPhi &&
MI.getNumExplicitOperands() == 3) {
1215 MI.getOperand(1).getReg());
1218 MI.eraseFromParent();
1227 class KernelRewriter {
1263 :
S(
S),
BB(LoopBB), PreheaderBB(L.getLoopPreheader()),
1266 PreheaderBB = *
BB->pred_begin();
1267 if (PreheaderBB ==
BB)
1268 PreheaderBB = *std::next(
BB->pred_begin());
1276 auto InsertPt =
BB->getFirstTerminator();
1281 if (
MI->getParent())
1282 MI->removeFromParent();
1283 BB->insert(InsertPt,
MI);
1287 assert(FirstMI &&
"Failed to find first MI in schedule");
1294 (
I++)->eraseFromParent();
1299 if (
MI.isPHI() ||
MI.isTerminator())
1308 EliminateDeadPhis(
BB,
MRI, LIS);
1314 for (
auto MI =
BB->getFirstNonPHI();
MI !=
BB->end(); ++
MI) {
1323 if (
MI.getParent() !=
BB) {
1337 int ConsumerStage =
S.getStage(&
MI);
1338 if (!Producer->
isPHI()) {
1344 int ProducerStage =
S.getStage(Producer);
1345 assert(ConsumerStage != -1 &&
1346 "In-loop consumer should always be scheduled!");
1347 assert(ConsumerStage >= ProducerStage);
1348 unsigned StageDiff = ConsumerStage - ProducerStage;
1350 for (
unsigned I = 0;
I < StageDiff; ++
I)
1359 auto LoopProducer = Producer;
1360 while (LoopProducer->isPHI() && LoopProducer->getParent() ==
BB) {
1366 int LoopProducerStage =
S.getStage(LoopProducer);
1370 if (LoopProducerStage == -1) {
1372 }
else if (LoopProducerStage > ConsumerStage) {
1377 #ifndef NDEBUG // Silence unused variables in non-asserts mode.
1378 int LoopProducerCycle =
S.getCycle(LoopProducer);
1379 int ConsumerCycle =
S.getCycle(&
MI);
1381 assert(LoopProducerCycle <= ConsumerCycle);
1382 assert(LoopProducerStage == ConsumerStage + 1);
1389 IllegalPhiDefault = Defaults.front();
1390 Defaults.
erase(Defaults.begin());
1392 assert(ConsumerStage >= LoopProducerStage);
1393 int StageDiff = ConsumerStage - LoopProducerStage;
1394 if (StageDiff > 0) {
1395 LLVM_DEBUG(
dbgs() <<
" -- padding defaults array from " << Defaults.size()
1396 <<
" to " << (Defaults.size() + StageDiff) <<
"\n");
1400 Defaults.
resize(Defaults.size() + StageDiff, Defaults.empty()
1407 auto DefaultI = Defaults.rbegin();
1408 while (DefaultI != Defaults.rend())
1411 if (IllegalPhiDefault.
hasValue()) {
1427 S.setStage(IllegalPhi, LoopProducerStage);
1438 auto I = Phis.find({LoopReg, InitReg.
getValue()});
1439 if (
I != Phis.end())
1442 for (
auto &KV : Phis) {
1443 if (KV.first.first == LoopReg)
1450 auto I = UndefPhis.find(LoopReg);
1451 if (
I != UndefPhis.end()) {
1459 MI->getOperand(1).setReg(InitReg.
getValue());
1460 Phis.insert({{LoopReg, InitReg.
getValue()},
R});
1478 UndefPhis[LoopReg] =
R;
1480 Phis[{LoopReg, *InitReg}] =
R;
1493 TII->get(TargetOpcode::IMPLICIT_DEF),
R);
1502 class KernelOperandInfo {
1515 while (isRegInLoop(MO)) {
1517 if (
MI->isFullCopy()) {
1518 MO = &
MI->getOperand(1);
1525 MO = &
MI->getOperand(3);
1530 MO =
MI->getOperand(2).getMBB() ==
BB ? &
MI->getOperand(1)
1531 : &
MI->getOperand(3);
1532 PhiDefaults.push_back(
Default);
1538 return PhiDefaults.size() ==
Other.PhiDefaults.size();
1542 OS <<
"use of " << *
Source <<
": distance(" << PhiDefaults.size() <<
") in "
1561 for (
auto I =
BB->
begin(), NI = NewBB->
begin(); !
I->isTerminator();
1577 if (Stage == -1 || Stage >= MinStage)
1590 for (
auto &Sub : Subs)
1591 Sub.first->substituteRegister(DefMO.getReg(), Sub.second, 0,
1596 MI->eraseFromParent();
1626 MI.removeFromParent();
1630 BlockMIs.erase({SourceBB, KernelMI});
1640 assert(
Def->findRegisterDefOperandIdx(
MI.getOperand(1).getReg()) != -1);
1642 MI.getOperand(0).setReg(PhiReg);
1643 PhiToDelete.push_back(&
MI);
1646 for (
auto *
P : PhiToDelete)
1647 P->eraseFromParent();
1653 DestBB->
insert(InsertPt, NewMI);
1675 if (
Use &&
Use->isPHI() &&
Use->getParent() == SourceBB) {
1690 for (
unsigned I = 0;
I < distance; ++
I) {
1693 unsigned LoopRegIdx = 3, InitRegIdx = 1;
1699 return CanonicalUseReg;
1724 EliminateDeadPhis(ExitingBB,
MRI,
LIS,
true);
1747 EliminateDeadPhis(
B,
MRI,
LIS,
true);
1751 for (
size_t I = 0;
I <
Epilogs.size();
I++) {
1753 for (
size_t J =
I; J <
Epilogs.size(); J++) {
1757 for (
size_t K = Iteration; K >
I; K--)
1771 for (; PI !=
Prologs.end(); ++PI, ++EI) {
1773 (*PI)->addSuccessor(*EI);
1777 if (
Use &&
Use->getParent() == Pred) {
1779 if (CanonicalUse->
isPHI()) {
1795 Blocks.push_back(
BB);
1800 for (
auto I =
B->getFirstInstrTerminator()->getReverseIterator();
1801 I != std::next(
B->getFirstNonPHI()->getReverseIterator());) {
1809 MI->eraseFromParent();
1815 EliminateDeadPhis(
B,
MRI,
LIS);
1816 EliminateDeadPhis(ExitingBB,
MRI,
LIS);
1835 if (
Use.getParent() !=
BB)
1838 Use->substituteRegister(OldR, R, 0,
1854 assert(CanAnalyzeBr &&
"Must be able to analyze the loop branch!");
1866 unsigned OpIdx =
MI->findRegisterDefOperandIdx(
Reg);
1878 R =
MI->getOperand(1).getReg();
1883 MI->getOperand(0).setReg(PhiR);
1889 if (Stage == -1 ||
LiveStages.count(
MI->getParent()) == 0 ||
1904 for (
auto &Sub : Subs)
1905 Sub.first->substituteRegister(DefMO.getReg(), Sub.second, 0,
1910 MI->eraseFromParent();
1915 bool KernelDisposed =
false;
1926 if (!StaticallyGreater.
hasValue()) {
1930 }
else if (*StaticallyGreater ==
false) {
1934 Prolog->removeSuccessor(Fallthrough);
1940 KernelDisposed =
true;
1952 if (!KernelDisposed) {
1983 std::string ScheduleDump;
1990 assert(
LIS &&
"Requires LiveIntervals!");
1995 if (!ExpandedKernel) {
2013 IllegalPhis.
insert(&*NI);
2019 auto OI = ExpandedKernel->
begin();
2021 for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {
2022 while (OI->isPHI() || OI->isFullCopy())
2024 while (NI->isPHI() || NI->isFullCopy())
2026 assert(OI->getOpcode() == NI->getOpcode() &&
"Opcodes don't match?!");
2028 for (
auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();
2029 OOpI != OI->operands_end(); ++OOpI, ++NOpI)
2031 KernelOperandInfo(&*NOpI,
MRI, IllegalPhis));
2035 for (
auto &OldAndNew : KOIs) {
2036 if (OldAndNew.first == OldAndNew.second)
2039 errs() <<
"Modulo kernel validation error: [\n";
2040 errs() <<
" [golden] ";
2041 OldAndNew.first.print(
errs());
2043 OldAndNew.second.print(
errs());
2048 errs() <<
"Golden reference kernel:\n";
2050 errs() <<
"New kernel:\n";
2052 errs() << ScheduleDump;
2054 "Modulo kernel validation (-pipeliner-experimental-cg) failed");
2099 "Modulo Schedule test pass",
false,
false)
2107 for (
auto *L : MLI) {
2117 std::pair<StringRef, StringRef> StageAndCycle = getToken(
S,
"_");
2118 std::pair<StringRef, StringRef> StageTokenAndValue =
2119 getToken(StageAndCycle.first,
"-");
2120 std::pair<StringRef, StringRef> CycleTokenAndValue =
2121 getToken(StageAndCycle.second,
"-");
2122 if (StageTokenAndValue.first !=
"Stage" ||
2123 CycleTokenAndValue.first !=
"_Cycle") {
2125 "Bad post-instr symbol syntax: see comment in ModuloScheduleTest");
2129 StageTokenAndValue.second.drop_front().getAsInteger(10, Stage);
2130 CycleTokenAndValue.second.drop_front().getAsInteger(10,
Cycle);
2132 dbgs() <<
" Stage=" << Stage <<
", Cycle=" <<
Cycle <<
"\n";
2138 dbgs() <<
"--- ModuloScheduleTest running on BB#" <<
BB->getNumber() <<
"\n";
2141 std::vector<MachineInstr *> Instrs;
2143 if (
MI.isTerminator())
2145 Instrs.push_back(&
MI);
2146 if (
MCSymbol *Sym =
MI.getPostInstrSymbol()) {
2147 dbgs() <<
"Parsing post-instr symbol for " <<
MI;
2168 OS <<
"Stage-" <<
S.getStage(
MI) <<
"_Cycle-" <<
S.getCycle(
MI);
2170 MI->setPostInstrSymbol(MF, Sym);