22#define DEBUG_TYPE "pipeliner"
37 unsigned &InitVal,
unsigned &LoopVal) {
38 assert(Phi.isPHI() &&
"Expecting a Phi.");
42 for (
unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
43 if (Phi.getOperand(i + 1).getMBB() !=
Loop)
44 InitVal = Phi.getOperand(i).getReg();
46 LoopVal = Phi.getOperand(i).getReg();
48 assert(InitVal != 0 && LoopVal != 0 &&
"Unexpected Phi structure.");
53 for (
unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
54 if (Phi.getOperand(i + 1).getMBB() != LoopBB)
55 return Phi.getOperand(i).getReg();
61 for (
unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
62 if (Phi.getOperand(i + 1).getMBB() == LoopBB)
63 return Phi.getOperand(i).getReg();
80 bool PhiIsSwapped =
false;
85 if (UseStage != -1 && UseStage >= DefStage)
86 Diff = UseStage - DefStage;
88 if (isLoopCarried(*
MI))
93 MaxDiff = std::max(Diff, MaxDiff);
95 RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped);
99 generatePipelinedLoop();
102void ModuloScheduleExpander::generatePipelinedLoop() {
115 ValueMapTy *VRMap =
new ValueMapTy[(MaxStageCount + 1) * 2];
120 ValueMapTy *VRMapPhi =
new ValueMapTy[(MaxStageCount + 1) * 2];
127 generateProlog(MaxStageCount, KernelBB, VRMap, PrologBBs);
135 unsigned StageNum = Schedule.
getStage(CI);
136 MachineInstr *NewMI = cloneInstr(CI, MaxStageCount, StageNum);
137 updateInstruction(NewMI,
false, MaxStageCount, StageNum, VRMap);
139 InstrMap[NewMI] = CI;
146 updateInstruction(NewMI,
false, MaxStageCount, 0, VRMap);
148 InstrMap[NewMI] = &
MI;
151 NewKernel = KernelBB;
155 generateExistingPhis(KernelBB, PrologBBs.
back(), KernelBB, KernelBB, VRMap,
156 InstrMap, MaxStageCount, MaxStageCount,
false);
157 generatePhis(KernelBB, PrologBBs.
back(), KernelBB, KernelBB, VRMap, VRMapPhi,
158 InstrMap, MaxStageCount, MaxStageCount,
false);
164 generateEpilog(MaxStageCount, KernelBB, BB, VRMap, VRMapPhi, EpilogBBs,
169 splitLifetimes(KernelBB, EpilogBBs);
172 removeDeadInstructions(KernelBB, EpilogBBs);
175 addBranches(*Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap);
186 BB->eraseFromParent();
190void ModuloScheduleExpander::generateProlog(
unsigned LastStage,
193 MBBVectorTy &PrologBBs) {
200 for (
unsigned i = 0; i < LastStage; ++i) {
212 for (
int StageNum = i; StageNum >= 0; --StageNum) {
216 if (Schedule.
getStage(&*BBI) == StageNum) {
220 cloneAndChangeInstr(&*BBI, i, (
unsigned)StageNum);
221 updateInstruction(NewMI,
false, i, (
unsigned)StageNum, VRMap);
223 InstrMap[NewMI] = &*BBI;
227 rewritePhiValues(NewBB, i, VRMap, InstrMap);
229 dbgs() <<
"prolog:\n";
248void ModuloScheduleExpander::generateEpilog(
250 ValueMapTy *VRMap, ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,
251 MBBVectorTy &PrologBBs) {
257 assert(!checkBranch &&
"generateEpilog must be able to analyze the branch");
262 if (*LoopExitI == KernelBB)
264 assert(LoopExitI != KernelBB->
succ_end() &&
"Expecting a successor");
274 int EpilogStage = LastStage + 1;
275 for (
unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {
283 if (EpilogStart == LoopExitBB)
288 for (
unsigned StageNum = i; StageNum <= LastStage; ++StageNum) {
289 for (
auto &BBI : *BB) {
293 if ((
unsigned)Schedule.
getStage(In) == StageNum) {
297 updateInstruction(NewMI, i == 1, EpilogStage, 0, VRMap);
299 InstrMap[NewMI] =
In;
303 generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap,
304 InstrMap, LastStage, EpilogStage, i == 1);
305 generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap, VRMapPhi,
306 InstrMap, LastStage, EpilogStage, i == 1);
310 dbgs() <<
"epilog:\n";
321 assert((OrigBB ==
TBB || OrigBB == FBB) &&
322 "Unable to determine looping branch direction");
328 if (EpilogBBs.size() > 0) {
343 if (O.getParent()->getParent() !=
MBB)
354 if (MO.getParent()->getParent() != BB)
362void ModuloScheduleExpander::generateExistingPhis(
365 unsigned LastStageNum,
unsigned CurStageNum,
bool IsLast) {
369 unsigned PrologStage = 0;
370 unsigned PrevStage = 0;
371 bool InKernel = (LastStageNum == CurStageNum);
373 PrologStage = LastStageNum - 1;
374 PrevStage = CurStageNum;
376 PrologStage = LastStageNum - (CurStageNum - LastStageNum);
377 PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;
381 BBE = BB->getFirstNonPHI();
385 unsigned InitVal = 0;
386 unsigned LoopVal = 0;
392 unsigned PhiOp2 = LoopVal;
393 if (VRMap[LastStageNum].
count(LoopVal))
394 PhiOp2 = VRMap[LastStageNum][LoopVal];
396 int StageScheduled = Schedule.
getStage(&*BBI);
398 unsigned NumStages = getStagesForReg(Def, CurStageNum);
399 if (NumStages == 0) {
402 unsigned NewReg = VRMap[PrevStage][LoopVal];
403 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, 0, &*BBI, Def,
405 if (VRMap[CurStageNum].
count(LoopVal))
406 VRMap[CurStageNum][
Def] = VRMap[CurStageNum][LoopVal];
412 unsigned MaxPhis = PrologStage + 2;
413 if (!InKernel && (
int)PrologStage <= LoopValStage)
414 MaxPhis = std::max((
int)MaxPhis - (
int)LoopValStage, 1);
415 unsigned NumPhis = std::min(NumStages, MaxPhis);
418 unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;
425 if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&
430 if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)
431 StageDiff = StageScheduled - LoopValStage;
432 for (
unsigned np = 0; np < NumPhis; ++np) {
436 if (np > PrologStage || StageScheduled >= (
int)LastStageNum)
439 else if (PrologStage >= AccessStage + StageDiff + np &&
440 VRMap[PrologStage - StageDiff - np].
count(LoopVal) != 0)
441 PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];
444 else if (PrologStage >= AccessStage + StageDiff + np) {
450 while (InstOp1 && InstOp1->
isPHI() && InstOp1->
getParent() == BB) {
451 int PhiStage = Schedule.
getStage(InstOp1);
452 if ((
int)(PrologStage - StageDiff - np) < PhiStage + Indirects)
457 int PhiOpStage = Schedule.
getStage(InstOp1);
458 int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);
459 if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np &&
460 VRMap[PrologStage - StageAdj - Indirects - np].
count(PhiOp1)) {
461 PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1];
475 bool LoopDefIsPhi = PhiInst && PhiInst->
isPHI();
480 int StageDiffAdj = 0;
481 if (LoopValStage != -1 && StageScheduled > LoopValStage)
482 StageDiffAdj = StageScheduled - LoopValStage;
485 if (np == 0 && PrevStage == LastStageNum &&
486 (StageScheduled != 0 || LoopValStage != 0) &&
487 VRMap[PrevStage - StageDiffAdj].count(LoopVal))
488 PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal];
491 else if (np > 0 && PrevStage == LastStageNum &&
492 VRMap[PrevStage - np + 1].
count(Def))
493 PhiOp2 = VRMap[PrevStage - np + 1][Def];
495 else if (
static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&
496 VRMap[PrevStage - StageDiffAdj - np].count(LoopVal))
497 PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal];
500 else if (VRMap[PrevStage - np].
count(Def) &&
501 (!LoopDefIsPhi || (PrevStage != LastStageNum) ||
502 (LoopValStage == StageScheduled)))
503 PhiOp2 = VRMap[PrevStage - np][
Def];
511 if (
static_cast<int>(PrologStage - np) >= StageScheduled) {
512 int LVNumStages = getStagesForPhi(LoopVal);
513 int StageDiff = (StageScheduled - LoopValStage);
514 LVNumStages -= StageDiff;
516 if (LVNumStages > (
int)np && VRMap[CurStageNum].count(LoopVal)) {
518 unsigned ReuseStage = CurStageNum;
519 if (isLoopCarried(*PhiInst))
520 ReuseStage -= LVNumStages;
523 if (VRMap[ReuseStage - np].
count(LoopVal)) {
524 NewReg = VRMap[ReuseStage - np][LoopVal];
526 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI,
529 VRMap[CurStageNum - np][
Def] = NewReg;
531 if (VRMap[LastStageNum - np - 1].
count(LoopVal))
532 PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];
534 if (IsLast && np == NumPhis - 1)
540 if (InKernel && StageDiff > 0 &&
541 VRMap[CurStageNum - StageDiff - np].
count(LoopVal))
542 PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];
550 TII->
get(TargetOpcode::PHI), NewReg);
554 InstrMap[NewPhi] = &*BBI;
559 unsigned PrevReg = 0;
560 if (InKernel && VRMap[PrevStage - np].
count(LoopVal))
561 PrevReg = VRMap[PrevStage - np][LoopVal];
562 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,
565 if (VRMap[CurStageNum - np].
count(Def)) {
566 unsigned R = VRMap[CurStageNum - np][
Def];
567 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, R,
574 if (IsLast && np == NumPhis - 1)
582 VRMap[CurStageNum - np][
Def] = NewReg;
585 while (NumPhis++ < NumStages) {
586 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, NumPhis, &*BBI, Def,
592 if (NumStages == 0 && IsLast && VRMap[CurStageNum].
count(LoopVal))
600void ModuloScheduleExpander::generatePhis(
603 InstrMapTy &InstrMap,
unsigned LastStageNum,
unsigned CurStageNum,
607 unsigned PrologStage = 0;
608 unsigned PrevStage = 0;
609 unsigned StageDiff = CurStageNum - LastStageNum;
610 bool InKernel = (StageDiff == 0);
612 PrologStage = LastStageNum - 1;
613 PrevStage = CurStageNum;
615 PrologStage = LastStageNum - StageDiff;
616 PrevStage = LastStageNum + StageDiff - 1;
620 BBE = BB->instr_end();
622 for (
unsigned i = 0, e = BBI->getNumOperands(); i !=
e; ++i) {
627 int StageScheduled = Schedule.
getStage(&*BBI);
628 assert(StageScheduled != -1 &&
"Expecting scheduled instruction.");
630 unsigned NumPhis = getStagesForReg(Def, CurStageNum);
634 if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&
637 if (!InKernel && (
unsigned)StageScheduled > PrologStage)
642 PhiOp2 = VRMap[PrevStage][
Def];
644 if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)
649 if (NumPhis > PrologStage + 1 - StageScheduled)
650 NumPhis = PrologStage + 1 - StageScheduled;
651 for (
unsigned np = 0; np < NumPhis; ++np) {
674 unsigned PhiOp1 = VRMap[PrologStage][
Def];
675 if (np <= PrologStage)
676 PhiOp1 = VRMap[PrologStage - np][
Def];
678 if (PrevStage == LastStageNum && np == 0)
679 PhiOp2 = VRMap[LastStageNum][
Def];
681 PhiOp2 = VRMapPhi[PrevStage - np][
Def];
689 TII->
get(TargetOpcode::PHI), NewReg);
693 InstrMap[NewPhi] = &*BBI;
698 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp1,
700 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp2,
704 VRMapPhi[PrevStage - np - 1][
Def] = NewReg;
706 VRMapPhi[CurStageNum - np][
Def] = NewReg;
707 if (np == NumPhis - 1)
708 rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def,
711 if (IsLast && np == NumPhis - 1)
723 MBBVectorTy &EpilogBBs) {
731 if (
MI->isInlineAsm()) {
735 bool SawStore =
false;
738 if (!
MI->isSafeToMove(
nullptr, SawStore) && !
MI->isPHI()) {
752 unsigned realUses = 0;
756 if (
U.getParent()->getParent() != BB) {
768 MI++->eraseFromParent();
779 MI.eraseFromParent();
795 MBBVectorTy &EpilogBBs) {
797 for (
auto &
PHI : KernelBB->
phis()) {
804 if (
I->isPHI() &&
I->getParent() == KernelBB) {
810 if (!
MI ||
MI->getParent() != KernelBB ||
MI->isPHI())
814 unsigned SplitReg = 0;
817 if (BBJ.readsRegister(Def)) {
822 TII->
get(TargetOpcode::COPY), SplitReg)
825 BBJ.substituteRegister(Def, SplitReg, 0, *
TRI);
830 for (
auto &
Epilog : EpilogBBs)
832 if (
I.readsRegister(Def))
833 I.substituteRegister(Def, SplitReg, 0, *
TRI);
845 for (
unsigned i = 1, e =
MI.getNumOperands(); i != e; i += 2)
846 if (
MI.getOperand(i + 1).getMBB() == Incoming) {
847 MI.removeOperand(i + 1);
858 MBBVectorTy &PrologBBs,
860 MBBVectorTy &EpilogBBs,
862 assert(PrologBBs.size() == EpilogBBs.size() &&
"Prolog/Epilog mismatch");
869 unsigned MaxIter = PrologBBs.
size() - 1;
870 for (
unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --
j) {
877 std::optional<bool> StaticallyGreater =
879 unsigned numAdded = 0;
880 if (!StaticallyGreater) {
883 }
else if (*StaticallyGreater ==
false) {
885 Prolog->removeSuccessor(LastPro);
890 if (LastPro != LastEpi) {
894 if (LastPro == KernelBB) {
908 I !=
E && numAdded > 0; ++
I, --numAdded)
909 updateInstruction(&*
I,
false, j, 0, VRMap);
913 LoopInfo->setPreheader(PrologBBs[MaxIter]);
914 LoopInfo->adjustTripCount(-(MaxIter + 1));
920bool ModuloScheduleExpander::computeDelta(
MachineInstr &
MI,
unsigned &Delta) {
924 bool OffsetIsScalable;
929 if (OffsetIsScalable)
932 if (!BaseOp->
isReg())
940 if (BaseDef && BaseDef->
isPHI()) {
942 BaseDef =
MRI.getVRegDef(BaseReg);
958void ModuloScheduleExpander::updateMemOperands(
MachineInstr &NewMI,
970 if (MMO->isVolatile() || MMO->isAtomic() ||
971 (MMO->isInvariant() && MMO->isDereferenceable()) ||
972 (!MMO->getValue())) {
977 if (Num != UINT_MAX && computeDelta(OldMI, Delta)) {
978 int64_t AdjOffset = Delta * Num;
992 unsigned CurStageNum,
993 unsigned InstStageNum) {
995 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
1002MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
1003 MachineInstr *OldMI,
unsigned CurStageNum,
unsigned InstStageNum) {
1005 auto It = InstrChanges.
find(OldMI);
1006 if (It != InstrChanges.
end()) {
1007 std::pair<unsigned, int64_t> RegAndOffset = It->second;
1008 unsigned BasePos, OffsetPos;
1012 MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first);
1013 if (Schedule.
getStage(LoopDef) > (
signed)InstStageNum)
1014 NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
1017 updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
1023void ModuloScheduleExpander::updateInstruction(
MachineInstr *NewMI,
1025 unsigned CurStageNum,
1026 unsigned InstrStageNum,
1027 ValueMapTy *VRMap) {
1037 VRMap[CurStageNum][reg] = NewReg;
1040 }
else if (MO.
isUse()) {
1043 int DefStageNum = Schedule.
getStage(Def);
1044 unsigned StageNum = CurStageNum;
1045 if (DefStageNum != -1 && (
int)InstrStageNum > DefStageNum) {
1047 unsigned StageDiff = (InstrStageNum - DefStageNum);
1049 StageNum -= StageDiff;
1051 if (VRMap[StageNum].
count(reg))
1052 MO.
setReg(VRMap[StageNum][reg]);
1060MachineInstr *ModuloScheduleExpander::findDefInLoop(
unsigned Reg) {
1063 while (
Def->isPHI()) {
1064 if (!Visited.
insert(Def).second)
1066 for (
unsigned i = 1, e =
Def->getNumOperands(); i < e; i += 2)
1067 if (
Def->getOperand(i + 1).getMBB() == BB) {
1068 Def =
MRI.getVRegDef(
Def->getOperand(i).getReg());
1076unsigned ModuloScheduleExpander::getPrevMapVal(
1077 unsigned StageNum,
unsigned PhiStage,
unsigned LoopVal,
unsigned LoopStage,
1079 unsigned PrevVal = 0;
1080 if (StageNum > PhiStage) {
1082 if (PhiStage == LoopStage && VRMap[StageNum - 1].
count(LoopVal))
1084 PrevVal = VRMap[StageNum - 1][LoopVal];
1085 else if (VRMap[StageNum].
count(LoopVal))
1088 PrevVal = VRMap[StageNum][LoopVal];
1092 else if (StageNum == PhiStage + 1)
1095 else if (StageNum > PhiStage + 1 && LoopInst->
getParent() == BB)
1098 getPrevMapVal(StageNum - 1, PhiStage,
getLoopPhiReg(*LoopInst, BB),
1099 LoopStage, VRMap, BB);
1111 InstrMapTy &InstrMap) {
1112 for (
auto &
PHI : BB->
phis()) {
1113 unsigned InitVal = 0;
1114 unsigned LoopVal = 0;
1120 unsigned NumPhis = getStagesForPhi(PhiDef);
1121 if (NumPhis > StageNum)
1123 for (
unsigned np = 0; np <= NumPhis; ++np) {
1125 getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
1128 rewriteScheduledInstr(NewBB, InstrMap, StageNum - np, np, &
PHI, PhiDef,
1137void ModuloScheduleExpander::rewriteScheduledInstr(
1139 unsigned PhiNum,
MachineInstr *Phi,
unsigned OldReg,
unsigned NewReg,
1142 int StagePhi = Schedule.
getStage(Phi) + PhiNum;
1157 assert(OrigInstr != InstrMap.end() &&
"Instruction not scheduled.");
1159 int StageSched = Schedule.
getStage(OrigMI);
1160 int CycleSched = Schedule.
getCycle(OrigMI);
1161 unsigned ReplaceReg = 0;
1163 if (StagePhi == StageSched &&
Phi->isPHI()) {
1164 int CyclePhi = Schedule.
getCycle(Phi);
1165 if (PrevReg && InProlog)
1166 ReplaceReg = PrevReg;
1167 else if (PrevReg && !isLoopCarried(*Phi) &&
1168 (CyclePhi <= CycleSched || OrigMI->isPHI()))
1169 ReplaceReg = PrevReg;
1171 ReplaceReg = NewReg;
1175 if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(*Phi))
1176 ReplaceReg = NewReg;
1177 if (StagePhi > StageSched &&
Phi->isPHI())
1178 ReplaceReg = NewReg;
1179 if (!InProlog && !
Phi->isPHI() && StagePhi < StageSched)
1180 ReplaceReg = NewReg;
1183 MRI.constrainRegClass(ReplaceReg,
MRI.getRegClass(OldReg));
1185 UseOp.setReg(ReplaceReg);
1187 Register SplitReg =
MRI.createVirtualRegister(
MRI.getRegClass(OldReg));
1191 UseOp.setReg(SplitReg);
1197bool ModuloScheduleExpander::isLoopCarried(
MachineInstr &Phi) {
1200 int DefCycle = Schedule.
getCycle(&Phi);
1201 int DefStage = Schedule.
getStage(&Phi);
1203 unsigned InitVal = 0;
1204 unsigned LoopVal = 0;
1207 if (!
Use ||
Use->isPHI())
1211 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
1226 bool Changed =
true;
1231 if (
MRI.use_empty(
MI.getOperand(0).getReg())) {
1234 MI.eraseFromParent();
1236 }
else if (!KeepSingleSrcPhi &&
MI.getNumExplicitOperands() == 3) {
1238 MRI.constrainRegClass(
MI.getOperand(1).getReg(),
1239 MRI.getRegClass(
MI.getOperand(0).getReg()));
1240 assert(ConstrainRegClass &&
1241 "Expected a valid constrained register class!");
1242 (void)ConstrainRegClass;
1243 MRI.replaceRegWith(
MI.getOperand(0).getReg(),
1244 MI.getOperand(1).getReg());
1247 MI.eraseFromParent();
1256class KernelRewriter {
1292 : S(S), BB(LoopBB), PreheaderBB(
L.getLoopPreheader()),
1293 ExitBB(
L.getExitBlock()),
MRI(BB->
getParent()->getRegInfo()),
1294 TII(BB->
getParent()->getSubtarget().getInstrInfo()), LIS(LIS) {
1296 if (PreheaderBB == BB)
1300void KernelRewriter::rewrite() {
1310 if (
MI->getParent())
1311 MI->removeFromParent();
1316 assert(FirstMI &&
"Failed to find first MI in schedule");
1323 (
I++)->eraseFromParent();
1328 if (
MI.isPHI() ||
MI.isTerminator())
1337 EliminateDeadPhis(BB,
MRI, LIS);
1343 for (
auto MI = BB->getFirstNonPHI();
MI != BB->end(); ++
MI) {
1352 if (
MI.getParent() != BB) {
1373 int ProducerStage = S.
getStage(Producer);
1374 assert(ConsumerStage != -1 &&
1375 "In-loop consumer should always be scheduled!");
1376 assert(ConsumerStage >= ProducerStage);
1377 unsigned StageDiff = ConsumerStage - ProducerStage;
1379 for (
unsigned I = 0;
I < StageDiff; ++
I)
1389 while (LoopProducer->isPHI() && LoopProducer->getParent() == BB) {
1392 LoopProducer =
MRI.getUniqueVRegDef(LoopReg);
1395 int LoopProducerStage = S.
getStage(LoopProducer);
1397 std::optional<Register> IllegalPhiDefault;
1399 if (LoopProducerStage == -1) {
1401 }
else if (LoopProducerStage > ConsumerStage) {
1407 int LoopProducerCycle = S.
getCycle(LoopProducer);
1410 assert(LoopProducerCycle <= ConsumerCycle);
1411 assert(LoopProducerStage == ConsumerStage + 1);
1418 IllegalPhiDefault = Defaults.
front();
1421 assert(ConsumerStage >= LoopProducerStage);
1422 int StageDiff = ConsumerStage - LoopProducerStage;
1423 if (StageDiff > 0) {
1425 <<
" to " << (Defaults.
size() + StageDiff) <<
"\n");
1430 Defaults.
empty() ? std::optional<Register>()
1436 auto DefaultI = Defaults.
rbegin();
1437 while (DefaultI != Defaults.
rend())
1438 LoopReg =
phi(LoopReg, *DefaultI++,
MRI.getRegClass(Reg));
1440 if (IllegalPhiDefault) {
1446 auto RC =
MRI.getRegClass(Reg);
1450 .
addReg(*IllegalPhiDefault)
1456 S.
setStage(IllegalPhi, LoopProducerStage);
1463Register KernelRewriter::phi(
Register LoopReg, std::optional<Register> InitReg,
1467 auto I = Phis.find({LoopReg, *InitReg});
1468 if (
I != Phis.end())
1471 for (
auto &KV : Phis) {
1472 if (KV.first.first == LoopReg)
1479 auto I = UndefPhis.find(LoopReg);
1480 if (
I != UndefPhis.end()) {
1488 MI->getOperand(1).setReg(*InitReg);
1489 Phis.insert({{LoopReg, *InitReg},
R});
1491 MRI.constrainRegClass(R,
MRI.getRegClass(*InitReg));
1492 assert(ConstrainRegClass &&
"Expected a valid constrained register class!");
1493 (void)ConstrainRegClass;
1500 RC =
MRI.getRegClass(LoopReg);
1504 MRI.constrainRegClass(R,
MRI.getRegClass(*InitReg));
1505 assert(ConstrainRegClass &&
"Expected a valid constrained register class!");
1506 (void)ConstrainRegClass;
1509 .
addReg(InitReg ? *InitReg : undef(RC))
1514 UndefPhis[LoopReg] =
R;
1516 Phis[{LoopReg, *InitReg}] =
R;
1526 R =
MRI.createVirtualRegister(RC);
1529 TII->get(TargetOpcode::IMPLICIT_DEF), R);
1538class KernelOperandInfo {
1551 while (isRegInLoop(MO)) {
1553 if (
MI->isFullCopy()) {
1554 MO = &
MI->getOperand(1);
1561 MO = &
MI->getOperand(3);
1566 MO =
MI->getOperand(2).getMBB() == BB ? &
MI->getOperand(1)
1567 : &
MI->getOperand(3);
1574 return PhiDefaults.
size() ==
Other.PhiDefaults.size();
1578 OS <<
"use of " << *
Source <<
": distance(" << PhiDefaults.
size() <<
") in "
1585 MRI.getVRegDef(MO->
getReg())->getParent() == BB;
1597 for (
auto I =
BB->
begin(), NI = NewBB->
begin(); !
I->isTerminator();
1613 if (Stage == -1 || Stage >= MinStage)
1626 for (
auto &Sub : Subs)
1627 Sub.first->substituteRegister(DefMO.getReg(), Sub.second, 0,
1632 MI->eraseFromParent();
1662 MI.removeFromParent();
1666 BlockMIs.erase({SourceBB, KernelMI});
1676 assert(Def->findRegisterDefOperandIdx(
MI.getOperand(1).getReg()) != -1);
1678 MI.getOperand(0).setReg(PhiReg);
1682 for (
auto *
P : PhiToDelete)
1683 P->eraseFromParent();
1689 DestBB->
insert(InsertPt, NewMI);
1690 Register OrigR = Phi->getOperand(0).getReg();
1711 if (
Use &&
Use->isPHI() &&
Use->getParent() == SourceBB) {
1726 for (
unsigned I = 0;
I < distance; ++
I) {
1729 unsigned LoopRegIdx = 3, InitRegIdx = 1;
1735 return CanonicalUseReg;
1760 EliminateDeadPhis(ExitingBB,
MRI,
LIS,
true);
1783 EliminateDeadPhis(
B,
MRI,
LIS,
true);
1787 for (
size_t I = 0;
I <
Epilogs.size();
I++) {
1789 for (
size_t J =
I; J <
Epilogs.size(); J++) {
1793 for (
size_t K = Iteration; K >
I; K--)
1807 for (; PI !=
Prologs.end(); ++PI, ++EI) {
1809 (*PI)->addSuccessor(*EI);
1813 if (
Use &&
Use->getParent() == Pred) {
1815 if (CanonicalUse->
isPHI()) {
1836 for (
auto I =
B->instr_rbegin();
1837 I != std::next(
B->getFirstNonPHI()->getReverseIterator());) {
1845 MI->eraseFromParent();
1851 EliminateDeadPhis(
B,
MRI,
LIS);
1852 EliminateDeadPhis(ExitingBB,
MRI,
LIS);
1871 if (
Use.getParent() !=
BB)
1874 Use->substituteRegister(OldR, R, 0,
1890 assert(CanAnalyzeBr &&
"Must be able to analyze the loop branch!");
1902 unsigned OpIdx =
MI->findRegisterDefOperandIdx(Reg);
1914 R =
MI->getOperand(1).getReg();
1919 MI->getOperand(0).setReg(PhiR);
1925 if (Stage == -1 ||
LiveStages.count(
MI->getParent()) == 0 ||
1940 for (
auto &Sub : Subs)
1941 Sub.first->substituteRegister(DefMO.getReg(), Sub.second, 0,
1946 MI->eraseFromParent();
1951 bool KernelDisposed =
false;
1960 std::optional<bool> StaticallyGreater =
1962 if (!StaticallyGreater) {
1966 }
else if (*StaticallyGreater ==
false) {
1970 Prolog->removeSuccessor(Fallthrough);
1976 KernelDisposed =
true;
1988 if (!KernelDisposed) {
2019 std::string ScheduleDump;
2026 assert(
LIS &&
"Requires LiveIntervals!");
2031 if (!ExpandedKernel) {
2049 IllegalPhis.
insert(&*NI);
2055 auto OI = ExpandedKernel->
begin();
2057 for (; !OI->isTerminator() && !NI->isTerminator(); ++OI, ++NI) {
2058 while (OI->isPHI() || OI->isFullCopy())
2060 while (NI->isPHI() || NI->isFullCopy())
2062 assert(OI->getOpcode() == NI->getOpcode() &&
"Opcodes don't match?!");
2064 for (
auto OOpI = OI->operands_begin(), NOpI = NI->operands_begin();
2065 OOpI != OI->operands_end(); ++OOpI, ++NOpI)
2067 KernelOperandInfo(&*NOpI,
MRI, IllegalPhis));
2071 for (
auto &OldAndNew : KOIs) {
2072 if (OldAndNew.first == OldAndNew.second)
2075 errs() <<
"Modulo kernel validation error: [\n";
2076 errs() <<
" [golden] ";
2077 OldAndNew.first.print(
errs());
2079 OldAndNew.second.print(
errs());
2084 errs() <<
"Golden reference kernel:\n";
2086 errs() <<
"New kernel:\n";
2088 errs() << ScheduleDump;
2090 "Modulo kernel validation (-pipeliner-experimental-cg) failed");
2132char ModuloScheduleTest::ID = 0;
2135 "Modulo Schedule test pass",
false,
false)
2143 for (
auto *L : MLI) {
2144 if (L->getTopBlock() != L->getBottomBlock())
2153 std::pair<StringRef, StringRef> StageAndCycle = getToken(S,
"_");
2154 std::pair<StringRef, StringRef> StageTokenAndValue =
2155 getToken(StageAndCycle.first,
"-");
2156 std::pair<StringRef, StringRef> CycleTokenAndValue =
2157 getToken(StageAndCycle.second,
"-");
2158 if (StageTokenAndValue.first !=
"Stage" ||
2159 CycleTokenAndValue.first !=
"_Cycle") {
2161 "Bad post-instr symbol syntax: see comment in ModuloScheduleTest");
2165 StageTokenAndValue.second.drop_front().getAsInteger(10, Stage);
2166 CycleTokenAndValue.second.drop_front().getAsInteger(10,
Cycle);
2168 dbgs() <<
" Stage=" << Stage <<
", Cycle=" <<
Cycle <<
"\n";
2174 dbgs() <<
"--- ModuloScheduleTest running on BB#" << BB->
getNumber() <<
"\n";
2177 std::vector<MachineInstr *> Instrs;
2179 if (
MI.isTerminator())
2181 Instrs.push_back(&
MI);
2183 dbgs() <<
"Parsing post-instr symbol for " <<
MI;
2206 MI->setPostInstrSymbol(MF,
Sym);
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::optional< std::vector< StOtherPiece > > Other
DenseMap< Block *, BlockRelaxAux > Blocks
Rewrite Partial Register Uses
const HexagonInstrInfo * TII
static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB)
Return the Phi register value that comes the loop block.
static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop, unsigned &InitVal, unsigned &LoopVal)
Return the register values for the operands of a Phi instruction.
unsigned const TargetRegisterInfo * TRI
This file provides utility analysis objects describing memory locations.
static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming)
Remove the incoming block from the Phis in a basic block.
modulo schedule Modulo Schedule test pass
static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB)
Return the Phi register value that comes the loop block.
static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg, MachineBasicBlock *MBB, MachineRegisterInfo &MRI, LiveIntervals &LIS)
Replace all uses of FromReg that appear outside the specified basic block with ToReg.
static void parseSymbolString(StringRef S, int &Cycle, int &Stage)
static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB, MachineRegisterInfo &MRI)
Return true if the register has a use that occurs outside the specified loop.
static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB)
Return the Phi register value that comes from the incoming block.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static bool rewrite(Function &F)
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
A possibly irreducible generalization of a Loop.
bool hasInterval(Register Reg) const
void RemoveMachineInstrFromMaps(MachineInstr &MI)
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Represents a single loop in the control flow graph.
MCSymbol * getOrCreateSymbol(const Twine &Name)
Lookup the symbol inside with the specified Name.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.
instr_iterator instr_begin()
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator_range< iterator > phis()
Returns a range that iterates over the phis in the basic block.
reverse_instr_iterator instr_rbegin()
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
void push_back(MachineInstr *MI)
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
succ_iterator succ_begin()
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
std::vector< MachineBasicBlock * >::iterator succ_iterator
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const
reverse_instr_iterator instr_rend()
pred_iterator pred_begin()
void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
instr_iterator instr_end()
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< iterator > terminators()
instr_iterator getFirstInstrTerminator()
Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineMemOperand * getMachineMemOperand(MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, uint64_t s, Align base_alignment, const AAMDNodes &AAInfo=AAMDNodes(), const MDNode *Ranges=nullptr, SyncScope::ID SSID=SyncScope::System, AtomicOrdering Ordering=AtomicOrdering::NotAtomic, AtomicOrdering FailureOrdering=AtomicOrdering::NotAtomic)
getMachineMemOperand - Allocate a new MachineMemOperand.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MCContext & getContext() const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
const MachineBasicBlock & front() const
void insert(iterator MBBI, MachineBasicBlock *MBB)
Register getReg(unsigned Idx) const
Get the register for the operand index.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
unsigned getNumOperands() const
Retuns the total number of operands.
bool memoperands_empty() const
Return true if we don't have any memory operands which described the memory access done by this instr...
void setMemRefs(MachineFunction &MF, ArrayRef< MachineMemOperand * > MemRefs)
Assign this MachineInstr's memory reference descriptor list.
iterator_range< mop_iterator > operands()
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
MachineBasicBlock * getTopBlock()
Return the "top" block in the loop, which is the first block in the linear layout,...
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
void setImm(int64_t immVal)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
void setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
void setMBB(MachineBasicBlock *MBB)
Register getReg() const
getReg - Returns the register number.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0)
defusechain_iterator - This class provides iterator support for machine operands in the function that...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
use_instr_iterator use_instr_begin(Register RegNo) const
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
static use_instr_iterator use_instr_end()
void setRegClass(Register Reg, const TargetRegisterClass *RC)
setRegClass - Set the register class of the specified virtual register.
iterator_range< use_instr_iterator > use_instructions(Register Reg) const
const TargetRegisterInfo * getTargetRegisterInfo() const
use_iterator use_begin(Register RegNo) const
static use_iterator use_end()
iterator_range< use_iterator > use_operands(Register Reg) const
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place, rewriting the old loop and...
MachineBasicBlock * getRewrittenKernel()
Returns the newly rewritten kernel block, or nullptr if this was optimized away.
void cleanup()
Performs final cleanup after expansion.
void expand()
Performs the actual expansion.
void annotate()
Performs the annotation.
Represents a schedule for a single-block loop.
int getNumStages() const
Return the number of stages contained in this schedule, which is the largest stage index + 1.
MachineLoop * getLoop() const
Return the single-block loop being scheduled.
ArrayRef< MachineInstr * > getInstructions()
Return the rescheduled instructions in order.
void print(raw_ostream &OS)
int getCycle(MachineInstr *MI)
Return the cycle that MI is scheduled at, or -1.
void setStage(MachineInstr *MI, int MIStage)
Set the stage of a newly created instruction.
int getStage(MachineInstr *MI)
Return the stage that MI is scheduled in, or -1.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
std::deque< MachineBasicBlock * > PeeledBack
SmallVector< MachineInstr *, 4 > IllegalPhisToDelete
Illegal phis that need to be deleted once we re-link stages.
DenseMap< MachineInstr *, MachineInstr * > CanonicalMIs
CanonicalMIs and BlockMIs form a bidirectional map between any of the loop kernel clones.
SmallVector< MachineBasicBlock *, 4 > Prologs
All prolog and epilog blocks.
MachineBasicBlock * peelKernel(LoopPeelDirection LPD)
Peels one iteration of the rewritten kernel (BB) in the specified direction.
ModuloSchedule & Schedule
std::deque< MachineBasicBlock * > PeeledFront
State passed from peelKernel to peelPrologAndEpilogs().
unsigned getStage(MachineInstr *MI)
Helper to get the stage of an instruction in the schedule.
void rewriteUsesOf(MachineInstr *MI)
Change all users of MI, if MI is predicated out (LiveStages[MI->getParent()] == false).
SmallVector< MachineBasicBlock *, 4 > Epilogs
DenseMap< MachineBasicBlock *, BitVector > AvailableStages
For every block, the stages that are available.
DenseMap< std::pair< MachineBasicBlock *, MachineInstr * >, MachineInstr * > BlockMIs
Register getEquivalentRegisterIn(Register Reg, MachineBasicBlock *BB)
All prolog and epilog blocks are clones of the kernel, so any produced register in one block has an c...
MachineBasicBlock * Preheader
The original loop preheader.
void rewriteKernel()
Converts BB from the original loop body to the rewritten, pipelined steady-state.
DenseMap< MachineInstr *, unsigned > PhiNodeLoopIteration
When peeling the epilogue keep track of the distance between the phi nodes and the kernel.
DenseMap< MachineBasicBlock *, BitVector > LiveStages
For every block, the stages that are produced.
const TargetInstrInfo * TII
void filterInstructions(MachineBasicBlock *MB, int MinStage)
void peelPrologAndEpilogs()
Peel the kernel forwards and backwards to produce prologs and epilogs, and stitch them together.
MachineBasicBlock * BB
The original loop block that gets rewritten in-place.
void fixupBranches()
Insert branches between prologs, kernel and epilogs.
MachineBasicBlock * CreateLCSSAExitingBlock()
Create a poor-man's LCSSA by cloning only the PHIs from the kernel block to a block dominated by all ...
void validateAgainstModuloScheduleExpander()
Runs ModuloScheduleExpander and treats it as a golden input to validate aspects of the code generated...
Register getPhiCanonicalReg(MachineInstr *CanonicalPhi, MachineInstr *Phi)
Helper function to find the right canonical register for a phi instruction coming from a peeled out p...
MachineRegisterInfo & MRI
void moveStageBetweenBlocks(MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage)
Wrapper class representing virtual and physical registers.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
reference emplace_back(ArgTypes &&... Args)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
reverse_iterator rbegin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
TargetInstrInfo - Interface to description of machine instruction set.
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
virtual std::unique_ptr< PipelinerLoopInfo > analyzeLoopForPipelining(MachineBasicBlock *LoopBB) const
Analyze loop L, which must be a single-basic-block loop, and if the conditions can be understood enou...
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
virtual bool getBaseAndOffsetPosition(const MachineInstr &MI, unsigned &BasePos, unsigned &OffsetPos) const
Return true if the instruction contains a base register and offset.
virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const
Insert branch code into the end of the specified MachineBasicBlock.
unsigned insertUnconditionalBranch(MachineBasicBlock &MBB, MachineBasicBlock *DestBB, const DebugLoc &DL, int *BytesAdded=nullptr) const
virtual bool getIncrementValue(const MachineInstr &MI, int &Value) const
If the instruction is an increment of a constant value, return the amount.
bool getMemOperandWithOffset(const MachineInstr &MI, const MachineOperand *&BaseOp, int64_t &Offset, bool &OffsetIsScalable, const TargetRegisterInfo *TRI) const
Get the base operand and byte offset of an instruction that reads/writes memory.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Target - Wrapper for Target specific information.
A Use represents the edge between a Value definition and its users.
Iterator for intrusive lists based on ilist_node.
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
A raw_ostream that writes to an SmallVector or SmallString.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Reg
All possible values of the reg field in the ModR/M byte.
NodeAddr< PhiNode * > Phi
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
MachineBasicBlock * PeelSingleBlockLoop(LoopPeelDirection Direction, MachineBasicBlock *Loop, MachineRegisterInfo &MRI, const TargetInstrInfo *TII)
Peels a single block loop.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
testing::Matcher< const detail::ErrorHolder & > Failed()
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
OutputIt copy(R &&Range, OutputIt Out)
void initializeModuloScheduleTestPass(PassRegistry &)
@ LPD_Back
Peel the last iteration of the loop.
@ LPD_Front
Peel the first iteration of the loop.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.