28#define DEBUG_TYPE "amdgpucfgstructurizer"
32class PHILinearizeDestIterator;
35 friend class PHILinearizeDestIterator;
38 using PHISourceT = std::pair<unsigned, MachineBasicBlock *>;
42 using PHIInfoElementT =
struct {
50 static unsigned phiInfoElementGetDest(PHIInfoElementT *
Info);
51 static void phiInfoElementSetDef(PHIInfoElementT *
Info,
unsigned NewDef);
52 static PHISourcesT &phiInfoElementGetSources(PHIInfoElementT *
Info);
53 static void phiInfoElementAddSource(PHIInfoElementT *
Info,
unsigned SourceReg,
55 static void phiInfoElementRemoveSource(PHIInfoElementT *
Info,
58 PHIInfoElementT *findPHIInfoElement(
unsigned DestReg);
59 PHIInfoElementT *findPHIInfoElementFromSource(
unsigned SourceReg,
65 void addDest(
unsigned DestReg,
const DebugLoc &
DL);
66 void replaceDef(
unsigned OldDestReg,
unsigned NewDestReg);
67 void deleteDef(
unsigned DestReg);
68 void addSource(
unsigned DestReg,
unsigned SourceReg,
70 void removeSource(
unsigned DestReg,
unsigned SourceReg,
75 unsigned getNumSources(
unsigned DestReg);
80 using dest_iterator = PHILinearizeDestIterator;
82 dest_iterator dests_begin();
83 dest_iterator dests_end();
85 source_iterator sources_begin(
unsigned Reg);
86 source_iterator sources_end(
unsigned Reg);
89class PHILinearizeDestIterator {
96 unsigned operator*() {
return PHILinearize::phiInfoElementGetDest(*Iter); }
97 PHILinearizeDestIterator &operator++() {
101 bool operator==(
const PHILinearizeDestIterator &
I)
const {
102 return I.Iter == Iter;
104 bool operator!=(
const PHILinearizeDestIterator &
I)
const {
105 return I.Iter != Iter;
111unsigned PHILinearize::phiInfoElementGetDest(PHIInfoElementT *Info) {
112 return Info->DestReg;
115void PHILinearize::phiInfoElementSetDef(PHIInfoElementT *Info,
117 Info->DestReg = NewDef;
121PHILinearize::phiInfoElementGetSources(PHIInfoElementT *Info) {
122 return Info->Sources;
125void PHILinearize::phiInfoElementAddSource(PHIInfoElementT *Info,
133 for (
auto SI : phiInfoElementGetSources(Info)) {
134 assert((
SI.second != SourceMBB || SourceReg ==
SI.first));
138 phiInfoElementGetSources(Info).insert(PHISourceT(SourceReg, SourceMBB));
141void PHILinearize::phiInfoElementRemoveSource(PHIInfoElementT *Info,
144 auto &Sources = phiInfoElementGetSources(Info);
146 for (
auto SI : Sources) {
147 if (
SI.first == SourceReg &&
148 (
SI.second ==
nullptr ||
SI.second == SourceMBB)) {
153 for (
auto &Source : ElimiatedSources) {
154 Sources.erase(Source);
158PHILinearize::PHIInfoElementT *
159PHILinearize::findPHIInfoElement(
unsigned DestReg) {
160 for (
auto *
I : PHIInfo) {
161 if (phiInfoElementGetDest(
I) == DestReg) {
168PHILinearize::PHIInfoElementT *
169PHILinearize::findPHIInfoElementFromSource(
unsigned SourceReg,
171 for (
auto *
I : PHIInfo) {
172 for (
auto SI : phiInfoElementGetSources(
I)) {
173 if (
SI.first == SourceReg &&
174 (
SI.second ==
nullptr ||
SI.second == SourceMBB)) {
184 bool FoundSource =
false;
185 for (
auto *
I : PHIInfo) {
186 for (
auto SI : phiInfoElementGetSources(
I)) {
187 if (
SI.second == SourceMBB) {
196void PHILinearize::addDest(
unsigned DestReg,
const DebugLoc &
DL) {
197 assert(findPHIInfoElement(DestReg) ==
nullptr &&
"Dest already exists");
198 PHISourcesT EmptySet;
199 PHIInfoElementT *NewElement =
new PHIInfoElementT();
200 NewElement->DestReg = DestReg;
202 NewElement->Sources = EmptySet;
203 PHIInfo.
insert(NewElement);
206void PHILinearize::replaceDef(
unsigned OldDestReg,
unsigned NewDestReg) {
207 phiInfoElementSetDef(findPHIInfoElement(OldDestReg), NewDestReg);
210void PHILinearize::deleteDef(
unsigned DestReg) {
211 PHIInfoElementT *InfoElement = findPHIInfoElement(DestReg);
212 PHIInfo.erase(InfoElement);
216void PHILinearize::addSource(
unsigned DestReg,
unsigned SourceReg,
218 phiInfoElementAddSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
221void PHILinearize::removeSource(
unsigned DestReg,
unsigned SourceReg,
223 phiInfoElementRemoveSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
228 PHIInfoElementT *InfoElement =
229 findPHIInfoElementFromSource(SourceReg, SourceMBB);
230 if (InfoElement !=
nullptr) {
231 DestReg = phiInfoElementGetDest(InfoElement);
239 return findDest(Reg, SourceMBB, DestReg);
242unsigned PHILinearize::getNumSources(
unsigned DestReg) {
243 return phiInfoElementGetSources(findPHIInfoElement(DestReg)).size();
246#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
249 dbgs() <<
"=PHIInfo Start=\n";
250 for (
auto *PII : this->PHIInfo) {
251 PHIInfoElementT &Element = *PII;
254 for (
auto &SI : Element.Sources) {
260 dbgs() <<
"=PHIInfo End=\n";
264void PHILinearize::clear() { PHIInfo = PHIInfoT(); }
266PHILinearize::dest_iterator PHILinearize::dests_begin() {
267 return PHILinearizeDestIterator(PHIInfo.begin());
270PHILinearize::dest_iterator PHILinearize::dests_end() {
271 return PHILinearizeDestIterator(PHIInfo.end());
274PHILinearize::source_iterator PHILinearize::sources_begin(
unsigned Reg) {
275 auto InfoElement = findPHIInfoElement(Reg);
276 return phiInfoElementGetSources(InfoElement).begin();
279PHILinearize::source_iterator PHILinearize::sources_end(
unsigned Reg) {
280 auto InfoElement = findPHIInfoElement(Reg);
281 return phiInfoElementGetSources(InfoElement).end();
286 return (
PHI.getNumOperands() - 1) / 2;
291 return PHI.getOperand(
Index * 2 + 2).getMBB();
296 PHI.getOperand(
Index * 2 + 2).setMBB(NewPred);
301 return PHI.getOperand(
Index * 2 + 1).getReg();
306 return PHI.getOperand(0).getReg();
314class LinearizedRegion {
323 LinearizedRegion *Parent;
334 PHILinearize &PHIInfo);
338 RegionMRT *TopRegion);
345 RegionMRT *TopRegion =
nullptr);
351 ~LinearizedRegion() =
default;
355 RegionMRT *getRegionMRT() {
return RMRT; }
357 void setParent(LinearizedRegion *
P) { Parent =
P; }
359 LinearizedRegion *
getParent() {
return Parent; }
363 void setBBSelectRegIn(
unsigned Reg);
365 unsigned getBBSelectRegIn();
367 void setBBSelectRegOut(
unsigned Reg,
bool IsLiveOut);
369 unsigned getBBSelectRegOut();
371 void setHasLoop(
bool Value);
375 void addLiveOut(
unsigned VReg);
377 void removeLiveOut(
unsigned Reg);
379 void replaceLiveOut(
unsigned OldReg,
unsigned NewReg);
383 bool ReplaceOutside,
bool IncludeLoopPHIs);
385 void replaceRegisterInsideRegion(
unsigned Register,
unsigned NewRegister,
386 bool IncludeLoopPHIs,
389 void replaceRegisterOutsideRegion(
unsigned Register,
unsigned NewRegister,
390 bool IncludeLoopPHIs,
405 void addMBBs(LinearizedRegion *InnerRegion);
422 unsigned BBSelectRegIn;
423 unsigned BBSelectRegOut;
426 virtual ~MRT() =
default;
428 unsigned getBBSelectRegIn() {
return BBSelectRegIn; }
430 unsigned getBBSelectRegOut() {
return BBSelectRegOut; }
432 void setBBSelectRegIn(
unsigned Reg) { BBSelectRegIn =
Reg; }
434 void setBBSelectRegOut(
unsigned Reg) { BBSelectRegOut =
Reg; }
436 virtual RegionMRT *getRegionMRT() {
return nullptr; }
438 virtual MBBMRT *getMBBMRT() {
return nullptr; }
440 bool isRegion() {
return getRegionMRT() !=
nullptr; }
442 bool isMBB() {
return getMBBMRT() !=
nullptr; }
444 bool isRoot() {
return Parent ==
nullptr; }
448 RegionMRT *
getParent() {
return Parent; }
461 void dumpDepth(
int depth) {
462 for (
int i = depth; i > 0; --i) {
468class MBBMRT :
public MRT {
474 setBBSelectRegOut(0);
478 MBBMRT *getMBBMRT()
override {
return this; }
484 dbgs() <<
"MBB: " << getMBB()->getNumber();
490class RegionMRT :
public MRT {
493 LinearizedRegion *LRegion =
nullptr;
500 setBBSelectRegOut(0);
504 ~RegionMRT()
override {
509 for (
auto *CI : Children) {
514 RegionMRT *getRegionMRT()
override {
return this; }
516 void setLinearizedRegion(LinearizedRegion *LinearizeRegion) {
517 LRegion = LinearizeRegion;
520 LinearizedRegion *getLinearizedRegion() {
return LRegion; }
524 unsigned getInnerOutputRegister() {
525 return (*(
Children.begin()))->getBBSelectRegOut();
528 void addChild(MRT *Tree) {
Children.insert(Tree); }
540 dbgs() <<
"Succ: " << getSucc()->getNumber() <<
"\n";
542 dbgs() <<
"Succ: none \n";
543 for (
auto *MRTI : Children) {
544 MRTI->dump(
TRI, depth + 1);
548 MRT *getEntryTree() {
return Children.back(); }
550 MRT *getExitTree() {
return Children.front(); }
554 return (Tree->isRegion()) ? Tree->getRegionMRT()->getEntry()
555 : Tree->getMBBMRT()->getMBB();
560 return (Tree->isRegion()) ? Tree->getRegionMRT()->getExit()
561 : Tree->getMBBMRT()->getMBB();
569 for (
auto *CI : Children) {
571 if (
MBB == CI->getMBBMRT()->getMBB()) {
575 if (CI->getRegionMRT()->contains(
MBB)) {
577 }
else if (CI->getRegionMRT()->getLinearizedRegion() !=
nullptr &&
578 CI->getRegionMRT()->getLinearizedRegion()->contains(
MBB)) {
586 void replaceLiveOutReg(
unsigned Register,
unsigned NewRegister) {
587 LinearizedRegion *LRegion = getLinearizedRegion();
588 LRegion->replaceLiveOut(
Register, NewRegister);
589 for (
auto &CI : Children) {
590 if (CI->isRegion()) {
591 CI->getRegionMRT()->replaceLiveOutReg(
Register, NewRegister);
601 return MRI->createVirtualRegister(
TII->getPreferredSelectRegClass(32));
607 for (
auto &MFI : MF) {
623 RegionMRT *
Result =
new RegionMRT(TopLevelRegion);
624 RegionMap[TopLevelRegion] =
Result;
631 MBBMRT *ExitMRT =
new MBBMRT(Exit);
633 ExitMRT->setBBSelectRegIn(BBSelectRegIn);
644 MBBMRT *NewMBB =
new MBBMRT(
MBB);
649 RegionMRT *NewMRTRegion =
new RegionMRT(
Region);
650 RegionMap[
Region] = NewMRTRegion;
654 while (RegionMap.
count(Parent) == 0) {
655 RegionMRT *NewMRTParent =
new RegionMRT(Parent);
656 NewMRTParent->addChild(NewMRTRegion);
657 NewMRTRegion->setParent(NewMRTParent);
658 RegionMap[Parent] = NewMRTParent;
659 NewMRTRegion = NewMRTParent;
662 RegionMap[Parent]->addChild(NewMRTRegion);
663 NewMRTRegion->setParent(RegionMap[Parent]);
667 RegionMap[
Region]->addChild(NewMBB);
668 NewMBB->setParent(RegionMap[
Region]);
678 PHILinearize &PHIInfo) {
679 if (
Reg.isVirtual()) {
684 if (PHIInfo.isSource(Reg)) {
689 for (
auto &UI :
MRI->use_operands(Reg)) {
690 if (UI.getParent()->getParent() !=
MBB) {
702 if ((&(*MII)) == DefInstr) {
714void LinearizedRegion::storeLiveOutRegRegion(RegionMRT *
Region,
Register Reg,
718 PHILinearize &PHIInfo) {
719 if (
Reg.isVirtual()) {
722 for (
auto &UI :
MRI->use_operands(Reg)) {
735 PHILinearize &PHIInfo) {
738 for (
auto &II : *
MBB) {
739 for (
auto &RI : II.defs()) {
742 for (
auto &IRI : II.implicit_operands()) {
752 for (
auto &II : *Succ) {
756 for (
int i = 0; i < numPreds; ++i) {
776 PHILinearize &PHIInfo,
777 RegionMRT *TopRegion) {
778 for (
auto &II : *
MBB) {
779 for (
auto &RI : II.defs()) {
780 storeLiveOutRegRegion(TopRegion, RI.getReg(), RI.getParent(),
MRI,
TRI,
783 for (
auto &IRI : II.implicit_operands()) {
785 storeLiveOutRegRegion(TopRegion, IRI.getReg(), IRI.getParent(),
MRI,
792void LinearizedRegion::storeLiveOuts(RegionMRT *
Region,
795 PHILinearize &PHIInfo,
796 RegionMRT *CurrentTopRegion) {
799 RegionMRT *TopRegion =
800 CurrentTopRegion ==
nullptr ?
Region : CurrentTopRegion;
807 for (
auto *CI : *Children) {
809 auto MBB = CI->getMBBMRT()->getMBB();
810 storeMBBLiveOuts(
MBB,
MRI,
TRI, PHIInfo, TopRegion);
812 LinearizedRegion *SubRegion = CI->getRegionMRT()->getLinearizedRegion();
815 for (
auto *
MBBI : SubRegion->MBBs) {
816 storeMBBLiveOuts(
MBBI,
MRI,
TRI, PHIInfo, TopRegion);
821 if (CurrentTopRegion ==
nullptr) {
822 auto Succ =
Region->getSucc();
823 for (
auto &II : *Succ) {
827 for (
int i = 0; i < numPreds; ++i) {
842 OS <<
"Linearized Region {";
844 for (
auto *
MBB : MBBs) {
852 OS <<
"} (" << Entry->getNumber() <<
", "
853 << (Exit ==
nullptr ? -1 : Exit->
getNumber())
855 <<
" Out:" <<
printReg(getBBSelectRegOut(),
TRI) <<
" {";
856 for (
auto &LI : LiveOuts) {
863unsigned LinearizedRegion::getBBSelectRegIn() {
864 return getRegionMRT()->getBBSelectRegIn();
867unsigned LinearizedRegion::getBBSelectRegOut() {
868 return getRegionMRT()->getBBSelectRegOut();
871void LinearizedRegion::setHasLoop(
bool Value) { HasLoop =
Value; }
873bool LinearizedRegion::getHasLoop() {
return HasLoop; }
875void LinearizedRegion::addLiveOut(
unsigned VReg) { LiveOuts.insert(VReg); }
877void LinearizedRegion::removeLiveOut(
unsigned Reg) {
882void LinearizedRegion::replaceLiveOut(
unsigned OldReg,
unsigned NewReg) {
884 removeLiveOut(OldReg);
889void LinearizedRegion::replaceRegister(
unsigned Register,
892 bool ReplaceInside,
bool ReplaceOutside,
893 bool IncludeLoopPHI) {
894 assert(
Register != NewRegister &&
"Cannot replace a reg with itself");
897 dbgs() <<
"Preparing to replace register (region): "
899 <<
printReg(NewRegister,
MRI->getTargetRegisterInfo()) <<
"\n");
902 if (ReplaceOutside &&
904 LinearizedRegion *Current =
this;
905 while (Current !=
nullptr && Current->getEntry() !=
nullptr) {
908 Current->replaceLiveOut(
Register, NewRegister);
911 Current = Current->getParent();
925 bool IsInside =
contains(
O.getParent()->getParent());
926 bool IsLoopPHI = IsInside && (
O.getParent()->isPHI() &&
927 O.getParent()->getParent() == getEntry());
928 bool ShouldReplace = (IsInside && ReplaceInside) ||
929 (!IsInside && ReplaceOutside) ||
930 (IncludeLoopPHI && IsLoopPHI);
935 <<
printReg(NewRegister,
MRI->getTargetRegisterInfo())
942 <<
printReg(NewRegister,
MRI->getTargetRegisterInfo())
944 O.setReg(NewRegister);
950void LinearizedRegion::replaceRegisterInsideRegion(
unsigned Register,
951 unsigned NewRegister,
952 bool IncludeLoopPHIs,
954 replaceRegister(
Register, NewRegister,
MRI,
true,
false, IncludeLoopPHIs);
957void LinearizedRegion::replaceRegisterOutsideRegion(
unsigned Register,
958 unsigned NewRegister,
959 bool IncludeLoopPHIs,
961 replaceRegister(
Register, NewRegister,
MRI,
false,
true, IncludeLoopPHIs);
978void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) {
979 for (
auto *
MBB : InnerRegion->MBBs) {
985 return MBBs.contains(
MBB);
988bool LinearizedRegion::isLiveOut(
unsigned Reg) {
989 return LiveOuts.contains(Reg);
993 return MRI->def_begin(Reg) ==
MRI->def_end();
1002 for (
auto *
MBBI : MBBs) {
1004 for (
auto &II : *
MBB) {
1005 for (
auto &RI : II.uses()) {
1008 if (
Reg.isVirtual()) {
1009 if (hasNoDef(Reg,
MRI))
1011 if (!
MRI->hasOneDef(Reg)) {
1016 if (
MRI->def_begin(Reg) ==
MRI->def_end()) {
1019 <<
" has NO defs\n");
1020 }
else if (!
MRI->hasOneDef(Reg)) {
1023 <<
" has multiple defs\n");
1026 assert(
MRI->hasOneDef(Reg) &&
"Register has multiple definitions");
1029 bool UseIsOutsideDefMBB =
Def->getParent()->getParent() !=
MBB;
1030 if (UseIsOutsideDefMBB && UseOperand->
isKill()) {
1042void LinearizedRegion::initLiveOut(RegionMRT *
Region,
1045 PHILinearize &PHIInfo) {
1052 PHILinearize &PHIInfo) {
1060LinearizedRegion::LinearizedRegion() {
1074 PHILinearize PHIInfo;
1085 void storePHILinearizationInfoDest(
1095 unsigned *ReplaceReg);
1109 unsigned CombinedSourceReg,
1110 LinearizedRegion *LRegion);
1115 LinearizedRegion *LRegion);
1118 void rewriteRegionEntryPHIs(LinearizedRegion *
Region,
1121 bool regionIsSimpleIf(RegionMRT *
Region);
1123 void transformSimpleIfRegion(RegionMRT *
Region);
1133 unsigned IfSourceRegister,
unsigned CodeSourceRegister,
1134 bool IsUndefIfSource =
false);
1143 void createEntryPHI(LinearizedRegion *CurrentRegion,
unsigned DestReg);
1145 void createEntryPHIs(LinearizedRegion *CurrentRegion);
1152 LinearizedRegion *LRegion,
1153 unsigned BBSelectRegIn,
1154 unsigned BBSelectRegOut);
1159 unsigned BBSelectRegIn,
unsigned BBSelectRegOut);
1164 unsigned BBSelectReg);
1169 LinearizedRegion *InnerRegion,
unsigned DestReg,
1170 unsigned SourceReg);
1175 LinearizedRegion *InnerRegion,
1176 LinearizedRegion *LRegion);
1181 LinearizedRegion *LRegion);
1187 LinearizedRegion *initLinearizedRegion(RegionMRT *
Region);
1189 bool structurizeComplexRegion(RegionMRT *
Region);
1191 bool structurizeRegion(RegionMRT *
Region);
1193 bool structurizeRegions(RegionMRT *
Region,
bool isTopRegion);
1209 void createLinearizedRegion(RegionMRT *
Region,
unsigned SelectOut);
1211 unsigned initializeSelectRegisters(MRT *MRT,
unsigned ExistingExitReg,
1215 void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; }
1217 RegionMRT *getRegionMRT() {
return RMRT; }
1224char AMDGPUMachineCFGStructurizer::ID = 0;
1226bool AMDGPUMachineCFGStructurizer::regionIsSimpleIf(RegionMRT *
Region) {
1229 bool FoundBypass =
false;
1230 bool FoundIf =
false;
1232 if (Entry->succ_size() != 2) {
1237 if (Current == Succ) {
1239 }
else if ((Current->succ_size() == 1) &&
1240 *(Current->succ_begin()) == Succ) {
1245 return FoundIf && FoundBypass;
1248void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *
Region) {
1251 TII->convertNonUniformIfRegion(Entry, Exit);
1258 for (
auto &UI : TI.uses()) {
1259 if (UI.isMBB() && UI.getMBB() != Succ) {
1270 LinearizedRegion *LRegion =
Region->getLinearizedRegion();
1271 auto Exit = LRegion->getExit();
1275 if (LRegion->contains(Succ)) {
1277 assert(InternalSucc ==
nullptr);
1278 InternalSucc = Succ;
1281 assert(ExternalSucc ==
nullptr);
1282 ExternalSucc = Succ;
1287 for (
auto &UI : TI.uses()) {
1289 auto Target = UI.getMBB();
1290 if (
Target != InternalSucc &&
Target != ExternalSucc) {
1291 UI.setMBB(ExternalSucc);
1302 auto Children =
Region->getChildren();
1303 for (
auto *CI : *Children) {
1304 if (!CI->isRegion()) {
1305 if (CI->getMBBMRT()->getMBB()->succ_size() > 1) {
1314 auto Children =
Region->getChildren();
1315 for (
auto *CI : *Children) {
1316 if (!CI->isRegion()) {
1324void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
1328 for (
unsigned i = 0; i < NumInputs; ++i) {
1336void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
1340 for (
unsigned i = 0; i < NumInputs; ++i) {
1348void AMDGPUMachineCFGStructurizer::getPHINonRegionIndices(
1352 for (
unsigned i = 0; i < NumInputs; ++i) {
1360void AMDGPUMachineCFGStructurizer::storePHILinearizationInfoDest(
1363 if (RegionIndices) {
1364 for (
auto i : *RegionIndices) {
1369 for (
unsigned i = 0; i < NumInputs; ++i) {
1375unsigned AMDGPUMachineCFGStructurizer::storePHILinearizationInfo(
1379 MRI->createVirtualRegister(
MRI->getRegClass(DestReg));
1380 PHIInfo.addDest(LinearizeDestReg,
PHI.getDebugLoc());
1381 storePHILinearizationInfoDest(LinearizeDestReg,
PHI, RegionIndices);
1382 return LinearizeDestReg;
1393 if (
Instr.isPHI()) {
1398 PHIInfo.addDest(PHIDestReg,
Instr.getDebugLoc());
1399 storePHILinearizationInfoDest(PHIDestReg, Instr);
1403 for (
auto *PI : PHIs) {
1404 PI->eraseFromParent();
1415 unsigned *ReplaceReg) {
1416 return shrinkPHI(
PHI, 0,
nullptr, PHIIndices, ReplaceReg);
1420 unsigned CombinedSourceReg,
1423 unsigned *ReplaceReg) {
1429 bool Replaced =
false;
1431 int SingleExternalEntryIndex = -1;
1432 for (
unsigned i = 0; i < NumInputs; ++i) {
1434 if (SingleExternalEntryIndex == -1) {
1436 SingleExternalEntryIndex = i;
1439 SingleExternalEntryIndex = -2;
1444 if (SingleExternalEntryIndex > -1) {
1455 MIB.
addReg(CombinedSourceReg);
1461 for (
unsigned i = 0; i < NumInputs; ++i) {
1474 PHI.eraseFromParent();
1478void AMDGPUMachineCFGStructurizer::replacePHI(
1486 bool HasExternalEdge =
false;
1488 for (
unsigned i = 0; i < NumInputs; ++i) {
1490 HasExternalEdge =
true;
1494 if (HasExternalEdge) {
1499 MIB.
addReg(CombinedSourceReg);
1503 for (
unsigned i = 0; i < NumInputs; ++i) {
1518 PHI.eraseFromParent();
1521void AMDGPUMachineCFGStructurizer::replaceEntryPHI(
1529 unsigned NumNonRegionInputs = NumInputs;
1530 for (
unsigned i = 0; i < NumInputs; ++i) {
1532 NumNonRegionInputs--;
1536 if (NumNonRegionInputs == 0) {
1538 replaceRegisterWith(DestReg, CombinedSourceReg);
1541 PHI.eraseFromParent();
1548 MIB.
addReg(CombinedSourceReg);
1553 for (
unsigned i = 0; i < NumInputs; ++i) {
1565 PHI.eraseFromParent();
1569void AMDGPUMachineCFGStructurizer::replaceLiveOutRegs(
1571 unsigned CombinedSourceReg, LinearizedRegion *LRegion) {
1572 bool WasLiveOut =
false;
1573 for (
auto PII : PHIRegionIndices) {
1575 if (LRegion->isLiveOut(Reg)) {
1581 if (MO.getParent()->getParent() != DefMBB)
1585 << (
IsDead ?
"dead" :
"alive")
1586 <<
" after PHI replace\n");
1588 LRegion->removeLiveOut(Reg);
1595 LRegion->addLiveOut(CombinedSourceReg);
1598void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHI(RegionMRT *
Region,
1601 LinearizedRegion *LRegion) {
1603 getPHIRegionIndices(
Region,
PHI, PHIRegionIndices);
1604 unsigned LinearizedSourceReg =
1605 storePHILinearizationInfo(
PHI, &PHIRegionIndices);
1607 replacePHI(
PHI, LinearizedSourceReg, LastMerge, PHIRegionIndices);
1608 replaceLiveOutRegs(
PHI, PHIRegionIndices, LinearizedSourceReg, LRegion);
1611void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHI(LinearizedRegion *
Region,
1615 getPHINonRegionIndices(
Region,
PHI, PHINonRegionIndices);
1616 unsigned LinearizedSourceReg =
1617 storePHILinearizationInfo(
PHI, &PHINonRegionIndices);
1618 replaceEntryPHI(
PHI, LinearizedSourceReg, IfMBB, PHINonRegionIndices);
1623 for (
auto &BBI : *
MBB) {
1630void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs(RegionMRT *
Region,
1632 LinearizedRegion *LRegion) {
1634 auto Exit =
Region->getSucc();
1635 if (Exit ==
nullptr)
1640 for (
auto *PHII : PHIs) {
1641 rewriteRegionExitPHI(
Region, LastMerge, *PHII, LRegion);
1645void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHIs(LinearizedRegion *
Region,
1652 for (
auto *PHII : PHIs) {
1653 rewriteRegionEntryPHI(
Region, IfMBB, *PHII);
1661 <<
" -> " << Dest->
getNumber() <<
"\n");
1664 if (HasTerminator) {
1665 TII->ReplaceTailWithBranchTo(Terminator, Dest);
1668 TII->insertUnconditionalBranch(*
MBB, Dest,
DL);
1674 for (
auto &MFI : MF) {
1675 if (MFI.succ_empty()) {
1676 if (result ==
nullptr) {
1692AMDGPUMachineCFGStructurizer::createLinearizedExitBlock(RegionMRT *
Region) {
1693 auto Exit =
Region->getSucc();
1702 if (Exit ==
nullptr) {
1704 MF->
insert(ExitIter, LastMerge);
1707 MF->
insert(ExitIter, LastMerge);
1709 insertUnconditionalBranch(LastMerge, Exit);
1719 unsigned DestRegister,
1720 unsigned IfSourceRegister,
1721 unsigned CodeSourceRegister,
1722 bool IsUndefIfSource) {
1728 <<
"): " <<
printReg(DestRegister,
TRI) <<
" = PHI("
1735 TII->get(TargetOpcode::PHI), DestRegister);
1736 if (IsUndefIfSource &&
false) {
1739 MIB.
addReg(IfSourceRegister);
1742 MIB.
addReg(CodeSourceRegister);
1751 (
MBB)->removeSuccessor(*PI);
1763 unsigned SuccSize = StartMBB->
succ_size();
1769 if (Succ != StartMBB &&
1770 !(Succ == StartMBBSucc && StartMBB != EndMBB && SuccSize == 1)) {
1772 std::pair<MachineBasicBlock *, MachineBasicBlock *>(EndMBB, Succ));
1779 Succs.
insert(std::pair(Pred, StartMBB));
1781 for (
auto SI : Succs) {
1782 std::pair<MachineBasicBlock *, MachineBasicBlock *> Edge = SI;
1785 Edge.first->removeSuccessor(Edge.second);
1792 bool InheritPreds) {
1798 if (Pred != CodeBBEnd)
1807 MF->
insert(MergeIter, IfBB);
1808 MF->
splice(MergeIter, CodeBBStartI, ++CodeBBEndI);
1828 TII->insertEQ(IfBB, IfBB->
begin(),
DL, IfReg,
1831 TII->materializeImmediate(*IfBB, IfBB->
begin(),
DL, IfReg,
1841void AMDGPUMachineCFGStructurizer::ensureCondIsNotKilled(
1843 if (
Cond.size() != 1)
1850 MO.setIsKill(
false);
1853void AMDGPUMachineCFGStructurizer::rewriteCodeBBTerminator(
MachineBasicBlock *CodeBB,
1855 unsigned BBSelectReg) {
1864 if (FalseBB ==
nullptr && TrueBB ==
nullptr && FallthroughBB ==
nullptr) {
1870 insertUnconditionalBranch(CodeBB, MergeBB,
DL);
1874 if (FalseBB ==
nullptr && TrueBB ==
nullptr) {
1875 TrueBB = FallthroughBB;
1876 }
else if (TrueBB !=
nullptr) {
1878 (FallthroughBB && (FallthroughBB != TrueBB)) ? FallthroughBB : FalseBB;
1881 if ((TrueBB !=
nullptr && FalseBB ==
nullptr) || (TrueBB == FalseBB)) {
1886 Register TrueBBReg =
MRI->createVirtualRegister(RegClass);
1887 Register FalseBBReg =
MRI->createVirtualRegister(RegClass);
1892 ensureCondIsNotKilled(
Cond);
1894 BBSelectReg,
Cond, TrueBBReg, FalseBBReg);
1897 insertUnconditionalBranch(CodeBB, MergeBB,
DL);
1900MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(
unsigned Reg) {
1901 if (
MRI->def_begin(Reg) ==
MRI->def_end()) {
1904 <<
" has NO defs\n");
1905 }
else if (!
MRI->hasOneDef(Reg)) {
1908 <<
" has multiple defs\n");
1910 for (
auto DI =
MRI->def_begin(Reg), DE =
MRI->def_end(); DI != DE; ++DI) {
1916 assert(
MRI->hasOneDef(Reg) &&
"Register has multiple definitions");
1917 return (*(
MRI->def_begin(Reg))).getParent();
1923 LinearizedRegion *InnerRegion,
1925 unsigned SourceReg) {
1929 bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
1931 if (DefInstr->
isPHI() && DefInstr->
getParent() == CodeBB && IsSingleBB) {
1936 InnerRegion->replaceRegisterInsideRegion(SourceReg, DestReg,
true,
MRI);
1940 storePHILinearizationInfoDest(DestReg, *DefInstr);
1943 PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
1947 if (IsSingleBB && DefInstr->
getParent() == InnerRegion->getEntry()) {
1950 InnerRegion->replaceRegisterOutsideRegion(SourceReg, DestReg,
false,
MRI);
1953 Register NextDestReg =
MRI->createVirtualRegister(RegClass);
1954 bool IsLastDef = PHIInfo.getNumSources(DestReg) == 1;
1956 insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, DestReg, NextDestReg,
1957 SourceReg, IsLastDef);
1959 PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
1964 PHIInfo.deleteDef(DestReg);
1966 PHIInfo.replaceDef(DestReg, NextDestReg);
1972 LinearizedRegion *InnerRegion,
1974 return getDefInstr(
Register)->getParent() ==
MBB ||
1981 LinearizedRegion *InnerRegion,
1982 LinearizedRegion *LRegion) {
1985 bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
1986 for (
auto OLI : *LiveOuts) {
1990 for (
auto LI : OldLiveOuts) {
1992 if (!containsDef(CodeBB, InnerRegion, LI) ||
1993 (!IsSingleBB && (getDefInstr(LI)->
getParent() == LRegion->getExit()))) {
2002 if ( Reg != InnerRegion->getBBSelectRegOut()) {
2013 Register PHIDestReg =
MRI->createVirtualRegister(RegClass);
2014 Register IfSourceReg =
MRI->createVirtualRegister(RegClass);
2021 InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg,
true,
MRI);
2023 insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, PHIDestReg,
2024 IfSourceReg, Reg,
true);
2031 if (PHIInfo.findSourcesFromMBB(CodeBB, Sources)) {
2034 for (
auto SI : Sources) {
2036 PHIInfo.findDest(SI, CodeBB, DestReg);
2037 insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI);
2050 for (
auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2053 unsigned DestReg = *DRI;
2054 auto SE = PHIInfo.sources_end(DestReg);
2056 bool MBBContainsPHISource =
false;
2058 for (
auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2059 unsigned SourceReg = (*SRI).first;
2061 if (
Def->getParent()->getParent() ==
MBB) {
2062 MBBContainsPHISource =
true;
2068 if (MBBContainsPHISource) {
2069 for (
auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2070 PHILinearize::PHISourceT
Source = *SRI;
2071 unsigned SourceReg =
Source.first;
2074 if (
Def->getParent()->getParent() !=
MBB) {
2075 ElimiatedSources.
push_back(std::tuple(DestReg, SourceReg, SourceMBB));
2082 for (
auto &SourceInfo : ElimiatedSources) {
2083 PHIInfo.removeSource(std::get<0>(SourceInfo), std::get<1>(SourceInfo),
2084 std::get<2>(SourceInfo));
2090void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion,
2096 << (*(Entry->pred_begin()))->getNumber() <<
"\n");
2099 auto SE = PHIInfo.sources_end(DestReg);
2101 for (
auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2105 if (NumSources == 1) {
2106 auto SRI = PHIInfo.sources_begin(DestReg);
2107 unsigned SourceReg = (*SRI).first;
2108 replaceRegisterWith(DestReg, SourceReg);
2110 const DebugLoc &
DL = Entry->findDebugLoc(Entry->begin());
2112 TII->get(TargetOpcode::PHI), DestReg);
2115 unsigned CurrentBackedgeReg = 0;
2117 for (
auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2118 unsigned SourceReg = (*SRI).first;
2120 if (CurrentRegion->contains((*SRI).second)) {
2121 if (CurrentBackedgeReg == 0) {
2122 CurrentBackedgeReg = SourceReg;
2127 MRI->getRegClass(CurrentBackedgeReg);
2128 Register NewBackedgeReg =
MRI->createVirtualRegister(RegClass);
2131 TII->get(TargetOpcode::PHI), NewBackedgeReg);
2132 BackedgePHI.
addReg(CurrentBackedgeReg);
2135 BackedgePHI.
addMBB((*SRI).second);
2136 CurrentBackedgeReg = NewBackedgeReg;
2138 <<
"Inserting backedge PHI: "
2147 MIB.
addMBB((*SRI).second);
2154 if (CurrentBackedgeReg != 0) {
2155 MIB.
addReg(CurrentBackedgeReg);
2165void AMDGPUMachineCFGStructurizer::createEntryPHIs(LinearizedRegion *CurrentRegion) {
2168 for (
auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2171 unsigned DestReg = *DRI;
2172 createEntryPHI(CurrentRegion, DestReg);
2177void AMDGPUMachineCFGStructurizer::replaceRegisterWith(
2179 assert(
Register != NewRegister &&
"Cannot replace a reg with itself");
2188 <<
printReg(NewRegister,
MRI->getTargetRegisterInfo())
2198 <<
printReg(NewRegister,
MRI->getTargetRegisterInfo())
2200 O.setReg(NewRegister);
2205 getRegionMRT()->replaceLiveOutReg(
Register, NewRegister);
2210void AMDGPUMachineCFGStructurizer::resolvePHIInfos(
MachineBasicBlock *FunctionEntry) {
2213 for (
auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2215 unsigned DestReg = *DRI;
2217 auto SRI = PHIInfo.sources_begin(DestReg);
2218 unsigned SourceReg = (*SRI).first;
2220 <<
" SourceReg: " <<
printReg(SourceReg,
TRI) <<
"\n");
2222 assert(PHIInfo.sources_end(DestReg) == ++SRI &&
2223 "More than one phi source in entry node");
2224 replaceRegisterWith(DestReg, SourceReg);
2234 LinearizedRegion *CurrentRegion,
unsigned BBSelectRegIn,
2235 unsigned BBSelectRegOut) {
2239 rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
2240 resolvePHIInfos(CodeBB);
2243 CurrentRegion->addMBB(CodeBB);
2246 if (CurrentRegion->getEntry() == CodeBB && !CurrentRegion->getHasLoop()) {
2252 if (CodeBBEndIter != MergeIter) {
2253 MF->
splice(MergeIter, CodeBBStartIter, CodeBBEndIter);
2255 rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
2256 prunePHIInfo(CodeBB);
2257 createEntryPHIs(CurrentRegion);
2260 CurrentRegion->addMBB(CodeBB);
2265 Register CodeBBSelectReg =
MRI->createVirtualRegister(RegClass);
2266 rewriteCodeBBTerminator(CodeBB, MergeBB, CodeBBSelectReg);
2267 bool IsRegionEntryBB = CurrentRegion->getEntry() == CodeBB;
2269 BBSelectRegIn, IsRegionEntryBB);
2270 CurrentRegion->addMBB(IfBB);
2273 if (IsRegionEntryBB) {
2274 CurrentRegion->setEntry(IfBB);
2276 if (CurrentRegion->getHasLoop()) {
2289 CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
2290 CurrentRegion->getRegionMRT()->getEntry()->
getNumber());
2302 CurrentRegion->addMBB(CodeBB);
2303 LinearizedRegion InnerRegion(CodeBB,
MRI,
TRI, PHIInfo);
2305 InnerRegion.setParent(CurrentRegion);
2307 insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
2309 InnerRegion.addMBB(MergeBB);
2312 rewriteLiveOutRegs(IfBB, CodeBB, MergeBB, &InnerRegion, CurrentRegion);
2313 extractKilledPHIs(CodeBB);
2314 if (IsRegionEntryBB) {
2315 createEntryPHIs(CurrentRegion);
2324 unsigned BBSelectRegIn,
unsigned BBSelectRegOut) {
2325 unsigned CodeBBSelectReg =
2326 InnerRegion->getRegionMRT()->getInnerOutputRegister();
2330 SelectBB, BBSelectRegIn,
true);
2331 CurrentRegion->addMBB(IfBB);
2332 bool isEntry = CurrentRegion->getEntry() == InnerRegion->getEntry();
2335 if (CurrentRegion->getHasLoop()) {
2348 CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
2349 CurrentRegion->getRegionMRT()->getEntry()->
getNumber());
2360 CurrentRegion->addMBBs(InnerRegion);
2362 insertMergePHI(IfBB, CodeExitBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
2365 rewriteLiveOutRegs(IfBB, CodeExitBB, MergeBB, InnerRegion,
2368 rewriteRegionEntryPHIs(InnerRegion, IfBB);
2371 CurrentRegion->setEntry(IfBB);
2375 createEntryPHIs(CurrentRegion);
2384 LinearizedRegion *LRegion) {
2386 getPHIRegionIndices(LRegion,
PHI, PHIRegionIndices);
2390 unsigned RegionIndex = PHIRegionIndices[0];
2394 unsigned PHISource = PHIDest;
2395 unsigned ReplaceReg;
2397 if (shrinkPHI(
PHI, PHIRegionIndices, &ReplaceReg)) {
2398 PHISource = ReplaceReg;
2402 Register NewDestReg =
MRI->createVirtualRegister(RegClass);
2403 LRegion->replaceRegisterInsideRegion(PHIDest, NewDestReg,
false,
MRI);
2406 TII->get(TargetOpcode::PHI), NewDestReg);
2413 MIB.
addReg(RegionSourceReg);
2414 MIB.
addMBB(RegionSourceMBB);
2421 LinearizedRegion *LRegion) {
2425 for (
auto *PHII : PHIs) {
2426 splitLoopPHI(*PHII, Entry, EntrySucc, LRegion);
2432AMDGPUMachineCFGStructurizer::splitExit(LinearizedRegion *LRegion) {
2433 auto MRTRegion = LRegion->getRegionMRT();
2434 auto Exit = LRegion->getExit();
2436 auto Succ = MRTRegion->getSucc();
2441 MF->
insert(AfterExitIter, NewExit);
2444 NewExit->addSuccessor(Succ);
2445 insertUnconditionalBranch(NewExit, Succ);
2446 LRegion->addMBB(NewExit);
2447 LRegion->setExit(NewExit);
2449 LLVM_DEBUG(
dbgs() <<
"Created new exit block: " << NewExit->getNumber()
2453 for (
auto &II : *Succ) {
2461 for (
int i = 0; i < numPreds; ++i) {
2478 MF->
insert(MBBIter, SuccMBB);
2493AMDGPUMachineCFGStructurizer::splitEntry(LinearizedRegion *LRegion) {
2501 LRegion->addMBB(EntrySucc);
2509 for (
auto &UI :
Branch.uses()) {
2510 if (UI.isMBB() && UI.getMBB() == Entry) {
2511 UI.setMBB(EntrySucc);
2515 splitLoopPHIs(Entry, EntrySucc, LRegion);
2521AMDGPUMachineCFGStructurizer::initLinearizedRegion(RegionMRT *
Region) {
2522 LinearizedRegion *LRegion =
Region->getLinearizedRegion();
2530 if (Exit ==
nullptr) {
2537 (*PI)->removeSuccessor(Exit);
2553 if (Tree ==
nullptr)
2556 if (Tree->isMBB()) {
2563 RegionMRT *
Region = Tree->getRegionMRT();
2576bool AMDGPUMachineCFGStructurizer::structurizeComplexRegion(RegionMRT *
Region) {
2577 auto *LRegion = initLinearizedRegion(
Region);
2581 LRegion->addMBB(LastMerge);
2582 LRegion->setExit(LastMerge);
2584 rewriteRegionExitPHIs(
Region, LastMerge, LRegion);
2590 LLVM_DEBUG(
dbgs() <<
"===========If Region Start===============\n");
2591 if (LRegion->getHasLoop()) {
2597 unsigned BBSelectRegIn;
2598 unsigned BBSelectRegOut;
2605 if (Child->isRegion()) {
2607 LinearizedRegion *InnerLRegion =
2608 Child->getRegionMRT()->getLinearizedRegion();
2619 unsigned OuterSelect = InnerLRegion->getBBSelectRegOut();
2620 unsigned InnerSelectReg =
2621 InnerLRegion->getRegionMRT()->getInnerOutputRegister();
2622 replaceRegisterWith(InnerSelectReg, OuterSelect),
2623 resolvePHIInfos(InnerEntry);
2624 if (!InnerLRegion->getExit()->isSuccessor(CurrentMerge))
2625 InnerLRegion->getExit()->addSuccessor(CurrentMerge);
2629 BBSelectRegOut = Child->getBBSelectRegOut();
2630 BBSelectRegIn = Child->getBBSelectRegIn();
2638 CurrentMerge = createIfRegion(CurrentMerge, InnerLRegion, LRegion,
2639 Child->getRegionMRT()->getEntry(),
2640 BBSelectRegIn, BBSelectRegOut);
2641 TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
2653 BBSelectRegOut = Child->getBBSelectRegOut();
2654 BBSelectRegIn = Child->getBBSelectRegIn();
2664 CurrentMerge = createIfRegion(CurrentMerge,
MBB, LRegion, BBSelectRegIn,
2667 TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
2674 LRegion->removeFalseRegisterKills(
MRI);
2676 if (LRegion->getHasLoop()) {
2679 resolvePHIInfos(LRegion->getEntry());
2682 unsigned InReg = LRegion->getBBSelectRegIn();
2684 MRI->createVirtualRegister(
MRI->getRegClass(InReg));
2685 Register NewInReg =
MRI->createVirtualRegister(
MRI->getRegClass(InReg));
2686 TII->materializeImmediate(*(LRegion->getEntry()),
2687 LRegion->getEntry()->getFirstTerminator(),
DL,
2690 LRegion->replaceRegisterInsideRegion(InReg, InnerSelectReg,
false,
MRI);
2692 insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc,
2693 InnerSelectReg, NewInReg,
2694 LRegion->getRegionMRT()->getInnerOutputRegister());
2696 TII->convertNonUniformLoopRegion(NewSucc, LastMerge);
2700 TII->insertReturn(*LastMerge);
2707 LLVM_DEBUG(
dbgs() <<
"===========If Region End===============\n");
2709 Region->setLinearizedRegion(LRegion);
2713bool AMDGPUMachineCFGStructurizer::structurizeRegion(RegionMRT *
Region) {
2714 if (
false && regionIsSimpleIf(
Region)) {
2715 transformSimpleIfRegion(
Region);
2721 structurizeComplexRegion(
Region);
2728bool AMDGPUMachineCFGStructurizer::structurizeRegions(RegionMRT *
Region,
2730 bool Changed =
false;
2732 auto Children =
Region->getChildren();
2733 for (
auto *CI : *Children) {
2734 if (CI->isRegion()) {
2735 Changed |= structurizeRegions(CI->getRegionMRT(),
false);
2740 Changed |= structurizeRegion(
Region);
2746void AMDGPUMachineCFGStructurizer::initFallthroughMap(
MachineFunction &MF) {
2748 for (
auto &
MBBI : MF) {
2750 if (
MBB !=
nullptr) {
2758void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *
Region,
2759 unsigned SelectOut) {
2760 LinearizedRegion *LRegion =
new LinearizedRegion();
2762 LRegion->addLiveOut(SelectOut);
2766 LRegion->setRegionMRT(
Region);
2767 Region->setLinearizedRegion(LRegion);
2774AMDGPUMachineCFGStructurizer::initializeSelectRegisters(MRT *MRT,
unsigned SelectOut,
2777 if (MRT->isRegion()) {
2778 RegionMRT *
Region = MRT->getRegionMRT();
2779 Region->setBBSelectRegOut(SelectOut);
2783 createLinearizedRegion(
Region, SelectOut);
2785 for (
auto *CI : *
Region->getChildren())
2786 InnerSelectOut = initializeSelectRegisters(CI, InnerSelectOut,
MRI,
TII);
2787 MRT->setBBSelectRegIn(InnerSelectOut);
2788 return InnerSelectOut;
2790 MRT->setBBSelectRegOut(SelectOut);
2792 MRT->setBBSelectRegIn(NewSelectIn);
2798 for (
auto &
MBBI : MF) {
2803 if (Instr.isPHI()) {
2805 for (
int i = 0; i < numPreds; ++i) {
2806 assert(Instr.getOperand(i * 2 + 1).isReg() &&
2807 "PHI Operand not a register");
2814bool AMDGPUMachineCFGStructurizer::runOnMachineFunction(
MachineFunction &MF) {
2817 TRI =
ST.getRegisterInfo();
2819 initFallthroughMap(MF);
2825 Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo());
2828 RegionMRT *RTree = MRT::buildMRT(MF, Regions,
TII,
MRI);
2829 setRegionMRT(RTree);
2830 initializeSelectRegisters(RTree, 0,
MRI,
TII);
2832 bool result = structurizeRegions(RTree,
true);
2835 initFallthroughMap(MF);
2842 "AMDGPU Machine CFG Structurizer",
false,
false)
2848 return new AMDGPUMachineCFGStructurizer();
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
static bool containsNewBackedge(MRT *Tree, SmallPtrSet< MachineBasicBlock *, 8 > &MBBs)
static MachineBasicBlock * split(MachineBasicBlock::iterator I)
static unsigned getPHISourceReg(MachineInstr &PHI, unsigned Index)
bool regionIsSequence(RegionMRT *Region)
static unsigned getPHIDestReg(MachineInstr &PHI)
amdgpu machine cfg structurizer
static void collectPHIs(MachineBasicBlock *MBB, SmallVector< MachineInstr *, 2 > &PHIs)
static void setPhiPred(MachineInstr &PHI, unsigned Index, MachineBasicBlock *NewPred)
static bool isFunctionEntryBlock(MachineBasicBlock *MBB)
static void removeOldExitPreds(RegionMRT *Region)
static bool isPHIRegionIndex(SmallVector< unsigned, 2 > PHIRegionIndices, unsigned Index)
static void checkRegOnlyPHIInputs(MachineFunction &MF)
static void fixMBBTerminator(MachineBasicBlock *MBB)
static bool hasOneExitNode(MachineFunction &MF)
static void removeExternalCFGEdges(MachineBasicBlock *StartMBB, MachineBasicBlock *EndMBB)
static void removeExternalCFGSuccessors(MachineBasicBlock *MBB)
static MachineBasicBlock * getSingleExitNode(MachineFunction &MF)
static unsigned createBBSelectReg(const SIInstrInfo *TII, MachineRegisterInfo *MRI)
void fixupRegionExits(RegionMRT *Region)
static int structurize_once
static MachineBasicBlock * getPHIPred(MachineInstr &PHI, unsigned Index)
char AMDGPUMachineCFGStructurizerID
amdgpu machine cfg AMDGPU Machine CFG Structurizer
static unsigned getPHINumInputs(MachineInstr &PHI)
static void fixRegionTerminator(RegionMRT *Region)
static bool mbbHasBackEdge(MachineBasicBlock *MBB, SmallPtrSet< MachineBasicBlock *, 8 > &MBBs)
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static const Function * getParent(const Value *V)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static void clear(coro::Shape &Shape)
This file defines the DenseSet and SmallDenseSet classes.
AMD GCN specific subclass of TargetSubtarget.
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
static bool isReg(const MCInst &MI, unsigned OpNo)
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Implements a dense probed hash-table based set.
FunctionPass class - This class is used to implement most global optimizations.
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
unsigned pred_size() const
void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
instr_iterator instr_begin()
MachineBasicBlock * getFallThrough(bool JumpToFallThrough=true)
Return the fallthrough block if the block can implicitly transfer control to the block after it by fa...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
reverse_instr_iterator instr_rbegin()
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
succ_iterator succ_begin()
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
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.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
Instructions::iterator instr_iterator
pred_iterator pred_begin()
instr_iterator instr_end()
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< iterator > terminators()
iterator_range< succ_iterator > successors()
instr_iterator getFirstInstrTerminator()
Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
std::vector< MachineBasicBlock * >::iterator pred_iterator
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.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void dump() const
dump - Print the current MachineFunction to cerr, useful for debugger use.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const MachineBasicBlock & front() const
void splice(iterator InsertPt, iterator MBBI)
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void insert(iterator MBBI, MachineBasicBlock *MBB)
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
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
MachineOperand class - Representation of each machine instruction operand.
void setIsKill(bool Val=true)
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)
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
BlockT * getExit() const
Get the exit BasicBlock of the Region.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
RegionT * getParent() const
Get the parent of the Region.
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
RegionT * getTopLevelRegion() const
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
Wrapper class representing virtual and physical registers.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
A vector that has set insertion semantics.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Target - Wrapper for Target specific information.
LLVM Value Representation.
std::pair< iterator, bool > insert(const ValueT &V)
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
#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.
@ C
The default llvm calling convention, compatible with C.
@ Undef
Value of the register doesn't matter.
Reg
All possible values of the reg field in the ModR/M byte.
NodeAddr< InstrNode * > Instr
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
APInt operator*(APInt a, uint64_t RHS)
bool operator!=(uint64_t V1, const APInt &V2)
iterator_range< po_iterator< T > > post_order(const T &G)
void initializeAMDGPUMachineCFGStructurizerPass(PassRegistry &)
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.
FunctionPass * createAMDGPUMachineCFGStructurizerPass()
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.