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()) {
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;
2608 if (Child->isRegion()) {
2610 LinearizedRegion *InnerLRegion =
2611 Child->getRegionMRT()->getLinearizedRegion();
2622 unsigned OuterSelect = InnerLRegion->getBBSelectRegOut();
2623 unsigned InnerSelectReg =
2624 InnerLRegion->getRegionMRT()->getInnerOutputRegister();
2625 replaceRegisterWith(InnerSelectReg, OuterSelect),
2626 resolvePHIInfos(InnerEntry);
2627 if (!InnerLRegion->getExit()->isSuccessor(CurrentMerge))
2628 InnerLRegion->getExit()->addSuccessor(CurrentMerge);
2632 BBSelectRegOut = Child->getBBSelectRegOut();
2633 BBSelectRegIn = Child->getBBSelectRegIn();
2641 CurrentMerge = createIfRegion(CurrentMerge, InnerLRegion, LRegion,
2642 Child->getRegionMRT()->getEntry(),
2643 BBSelectRegIn, BBSelectRegOut);
2644 TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
2656 BBSelectRegOut = Child->getBBSelectRegOut();
2657 BBSelectRegIn = Child->getBBSelectRegIn();
2667 CurrentMerge = createIfRegion(CurrentMerge,
MBB, LRegion, BBSelectRegIn,
2670 TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
2677 LRegion->removeFalseRegisterKills(
MRI);
2679 if (LRegion->getHasLoop()) {
2682 resolvePHIInfos(LRegion->getEntry());
2685 unsigned InReg = LRegion->getBBSelectRegIn();
2687 MRI->createVirtualRegister(
MRI->getRegClass(InReg));
2688 Register NewInReg =
MRI->createVirtualRegister(
MRI->getRegClass(InReg));
2689 TII->materializeImmediate(*(LRegion->getEntry()),
2690 LRegion->getEntry()->getFirstTerminator(),
DL,
2693 LRegion->replaceRegisterInsideRegion(InReg, InnerSelectReg,
false,
MRI);
2695 insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc,
2696 InnerSelectReg, NewInReg,
2697 LRegion->getRegionMRT()->getInnerOutputRegister());
2699 TII->convertNonUniformLoopRegion(NewSucc, LastMerge);
2703 TII->insertReturn(*LastMerge);
2710 LLVM_DEBUG(
dbgs() <<
"===========If Region End===============\n");
2712 Region->setLinearizedRegion(LRegion);
2716bool AMDGPUMachineCFGStructurizer::structurizeRegion(RegionMRT *
Region) {
2717 if (
false && regionIsSimpleIf(
Region)) {
2718 transformSimpleIfRegion(
Region);
2724 structurizeComplexRegion(
Region);
2731bool AMDGPUMachineCFGStructurizer::structurizeRegions(RegionMRT *
Region,
2733 bool Changed =
false;
2735 auto Children =
Region->getChildren();
2736 for (
auto *CI : *Children) {
2737 if (CI->isRegion()) {
2738 Changed |= structurizeRegions(CI->getRegionMRT(),
false);
2743 Changed |= structurizeRegion(
Region);
2749void AMDGPUMachineCFGStructurizer::initFallthroughMap(
MachineFunction &MF) {
2751 for (
auto &
MBBI : MF) {
2753 if (
MBB !=
nullptr) {
2761void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *
Region,
2762 unsigned SelectOut) {
2763 LinearizedRegion *LRegion =
new LinearizedRegion();
2765 LRegion->addLiveOut(SelectOut);
2769 LRegion->setRegionMRT(
Region);
2770 Region->setLinearizedRegion(LRegion);
2777AMDGPUMachineCFGStructurizer::initializeSelectRegisters(MRT *MRT,
unsigned SelectOut,
2780 if (MRT->isRegion()) {
2781 RegionMRT *
Region = MRT->getRegionMRT();
2782 Region->setBBSelectRegOut(SelectOut);
2786 createLinearizedRegion(
Region, SelectOut);
2788 for (
auto *CI : *
Region->getChildren())
2789 InnerSelectOut = initializeSelectRegisters(CI, InnerSelectOut,
MRI,
TII);
2790 MRT->setBBSelectRegIn(InnerSelectOut);
2791 return InnerSelectOut;
2793 MRT->setBBSelectRegOut(SelectOut);
2795 MRT->setBBSelectRegIn(NewSelectIn);
2801 for (
auto &
MBBI : MF) {
2806 if (Instr.
isPHI()) {
2808 for (
int i = 0; i < numPreds; ++i) {
2810 "PHI Operand not a register");
2817bool AMDGPUMachineCFGStructurizer::runOnMachineFunction(
MachineFunction &MF) {
2820 TRI =
ST.getRegisterInfo();
2822 initFallthroughMap(MF);
2828 Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo());
2831 RegionMRT *RTree = MRT::buildMRT(MF, Regions,
TII,
MRI);
2832 setRegionMRT(RTree);
2833 initializeSelectRegisters(RTree, 0,
MRI,
TII);
2835 bool result = structurizeRegions(RTree,
true);
2838 initFallthroughMap(MF);
2845 "AMDGPU Machine CFG Structurizer",
false,
false)
2851 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)
SmallVector< MachineOperand, 4 > Cond
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.
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()
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()
MachineBasicBlock * getFallThrough(bool JumpToFallThrough=false)
Return the fallthrough block if the block can implicitly transfer control to the block after it by fa...
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 DBG_VALUE and DBG_LABEL instructions.
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...
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.
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)
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
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register 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.
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)
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.
#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.
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.