65#define DEBUG_TYPE "branch-folder"
67STATISTIC(NumDeadBlocks,
"Number of dead blocks removed");
68STATISTIC(NumBranchOpts,
"Number of branches optimized");
69STATISTIC(NumTailMerge ,
"Number of block tails merged");
70STATISTIC(NumHoist ,
"Number of times common instructions are hoisted");
71STATISTIC(NumTailCalls,
"Number of tail calls optimized");
79 cl::desc(
"Max number of predecessors to consider tail merging"),
86 cl::desc(
"Min number of instructions to consider tail merging"),
110 MachineFunctionProperties::Property::NoPHIs);
116char BranchFolderPass::ID = 0;
121 "Control Flow Optimizer",
false,
false)
124 if (skipFunction(MF.getFunction()))
130 bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
133 getAnalysis<MachineBlockFrequencyInfo>());
135 EnableTailMerge,
true, MBBFreqInfo,
136 getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI(),
137 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
139 MF.getSubtarget().getRegisterInfo());
146 : EnableHoistCommonCode(CommonHoist), MinCommonTailLength(MinTailLength),
147 MBBFreqInfo(FreqInfo), MBPI(ProbInfo), PSI(PSI) {
148 if (MinCommonTailLength == 0)
152 EnableTailMerge = DefaultEnableTailMerge;
169 TriedMerging.erase(
MBB);
173 if (
MI.shouldUpdateCallSiteInfo())
178 EHScopeMembership.erase(
MBB);
187 if (!tii)
return false;
189 TriedMerging.clear();
192 AfterBlockPlacement = AfterPlacement;
200 MRI.invalidateLiveness();
202 bool MadeChange =
false;
207 bool MadeChangeThisIteration =
true;
208 while (MadeChangeThisIteration) {
209 MadeChangeThisIteration = TailMergeBlocks(MF);
212 if (!AfterBlockPlacement || MadeChangeThisIteration)
213 MadeChangeThisIteration |= OptimizeBranches(MF);
214 if (EnableHoistCommonCode)
215 MadeChangeThisIteration |= HoistCommonCode(MF);
216 MadeChange |= MadeChangeThisIteration;
230 if (!
Op.isJTI())
continue;
233 JTIsLive.
set(
Op.getIndex());
239 for (
unsigned i = 0, e = JTIsLive.
size(); i != e; ++i)
240 if (!JTIsLive.
test(i)) {
254 unsigned Hash =
MI.getOpcode();
255 for (
unsigned i = 0, e =
MI.getNumOperands(); i != e; ++i) {
261 unsigned OperandHash = 0;
262 switch (
Op.getType()) {
264 OperandHash =
Op.getReg();
267 OperandHash =
Op.getImm();
270 OperandHash =
Op.getMBB()->getNumber();
275 OperandHash =
Op.getIndex();
281 OperandHash =
Op.getOffset();
287 Hash += ((OperandHash << 3) |
Op.getType()) << (i & 31);
303 return !(
MI.isDebugInstr() ||
MI.isCFIInstruction());
333 unsigned TailLen = 0;
337 if (MBBI1 == MBB1->
end() || MBBI2 == MBB2->
end())
339 if (!MBBI1->isIdenticalTo(*MBBI2) ||
345 MBBI1->isInlineAsm()) {
371 }
while (
I != OldInst);
380 "Can only handle full register.");
385 BuildMI(OldMBB, OldInst,
DL, TII->
get(TargetOpcode::IMPLICIT_DEF), Reg);
413 NewMBB->
splice(NewMBB->
end(), &CurMBB, BBI1, CurMBB.
end());
418 ML->addBasicBlockToLoop(NewMBB, MLI->
getBase());
427 const auto &EHScopeI = EHScopeMembership.find(&CurMBB);
428 if (EHScopeI != EHScopeMembership.end()) {
429 auto n = EHScopeI->second;
430 EHScopeMembership[NewMBB] = n;
441 for (;
I != E; ++
I) {
446 else if (
I->mayLoadOrStore())
469 if (
TBB == NextBB && !
Cond.empty() && !FBB) {
482BranchFolder::MergePotentialsElt::operator<(
const MergePotentialsElt &o)
const {
483 if (getHash() <
o.getHash())
485 if (getHash() >
o.getHash())
487 if (getBlock()->getNumber() <
o.getBlock()->getNumber())
489 if (getBlock()->getNumber() >
o.getBlock()->getNumber())
500 unsigned NumTerms = 0;
507 if (!
I->isTerminator())
break;
542 unsigned MinCommonTailLength,
unsigned &CommonTailLen,
551 if (!EHScopeMembership.
empty()) {
552 auto EHScope1 = EHScopeMembership.
find(MBB1);
553 assert(EHScope1 != EHScopeMembership.
end());
554 auto EHScope2 = EHScopeMembership.
find(MBB2);
555 assert(EHScope2 != EHScopeMembership.
end());
556 if (EHScope1->second != EHScope2->second)
561 if (CommonTailLen == 0)
565 << CommonTailLen <<
'\n');
575 bool FullBlockTail1 = I1 == MBB1->
begin();
576 bool FullBlockTail2 = I2 == MBB2->
begin();
583 if ((MBB1 == PredBB || MBB2 == PredBB) &&
584 (!AfterPlacement || MBB1->
succ_size() == 1)) {
587 if (CommonTailLen > NumTerms)
596 if (FullBlockTail1 && FullBlockTail2 &&
613 if (AfterPlacement && FullBlockTail1 && FullBlockTail2) {
619 return (
MBB != &*MF->
begin()) && std::prev(
I)->canFallThrough();
621 if (!BothFallThrough(MBB1) || !BothFallThrough(MBB2))
630 unsigned EffectiveTailLen = CommonTailLen;
631 if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
632 (MBB1->
succ_size() == 1 || !AfterPlacement) &&
638 if (EffectiveTailLen >= MinCommonTailLength)
650 return EffectiveTailLen >= 2 && OptForSize &&
651 (FullBlockTail1 || FullBlockTail2);
654unsigned BranchFolder::ComputeSameTails(
unsigned CurHash,
655 unsigned MinCommonTailLength,
658 unsigned maxCommonTailLength = 0
U;
661 MPIterator HighestMPIter = std::prev(MergePotentials.end());
662 for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
663 B = MergePotentials.begin();
664 CurMPIter !=
B && CurMPIter->getHash() == CurHash; --CurMPIter) {
665 for (MPIterator
I = std::prev(CurMPIter);
I->getHash() == CurHash; --
I) {
666 unsigned CommonTailLen;
669 CommonTailLen, TrialBBI1, TrialBBI2,
672 AfterBlockPlacement, MBBFreqInfo, PSI)) {
673 if (CommonTailLen > maxCommonTailLength) {
675 maxCommonTailLength = CommonTailLen;
676 HighestMPIter = CurMPIter;
677 SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
679 if (HighestMPIter == CurMPIter &&
680 CommonTailLen == maxCommonTailLength)
681 SameTails.push_back(SameTailElt(
I, TrialBBI2));
687 return maxCommonTailLength;
690void BranchFolder::RemoveBlocksWithHash(
unsigned CurHash,
694 MPIterator CurMPIter,
B;
695 for (CurMPIter = std::prev(MergePotentials.end()),
696 B = MergePotentials.begin();
697 CurMPIter->getHash() == CurHash; --CurMPIter) {
700 if (SuccBB && CurMBB != PredBB)
701 FixTail(CurMBB, SuccBB, TII, BranchDL);
705 if (CurMPIter->getHash() != CurHash)
707 MergePotentials.erase(CurMPIter, MergePotentials.end());
712 unsigned maxCommonTailLength,
713 unsigned &commonTailIndex) {
715 unsigned TimeEstimate = ~0
U;
716 for (
unsigned i = 0, e = SameTails.size(); i != e; ++i) {
718 if (SameTails[i].getBlock() == PredBB) {
725 SameTails[i].getTailStartPos());
726 if (t <= TimeEstimate) {
733 SameTails[commonTailIndex].getTailStartPos();
737 << maxCommonTailLength);
750 SameTails[commonTailIndex].setBlock(newMBB);
751 SameTails[commonTailIndex].setTailStartPos(newMBB->
begin());
767 unsigned CommonTailLen = 0;
768 for (
auto E =
MBB->
end(); MBBIStartPos != E; ++MBBIStartPos)
776 while (CommonTailLen--) {
777 assert(
MBBI != MBBIE &&
"Reached BB end within common tail length!");
788 assert(MBBICommon != MBBIECommon &&
789 "Reached BB end within common tail length!");
790 assert(MBBICommon->isIdenticalTo(*
MBBI) &&
"Expected matching MIIs!");
793 if (MBBICommon->mayLoadOrStore())
794 MBBICommon->cloneMergedMemRefs(*
MBB->
getParent(), {&*MBBICommon, &*MBBI});
796 for (
unsigned I = 0, E = MBBICommon->getNumOperands();
I != E; ++
I) {
810void BranchFolder::mergeCommonTails(
unsigned commonTailIndex) {
813 std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
814 for (
unsigned int i = 0 ; i != SameTails.size() ; ++i) {
815 if (i != commonTailIndex) {
816 NextCommonInsts[i] = SameTails[i].getTailStartPos();
820 "MBB is not a common tail only block");
824 for (
auto &
MI : *
MBB) {
828 for (
unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
829 if (i == commonTailIndex)
832 auto &Pos = NextCommonInsts[i];
833 assert(Pos != SameTails[i].getBlock()->
end() &&
834 "Reached BB end within common tail");
837 assert(Pos != SameTails[i].getBlock()->
end() &&
838 "Reached BB end within common tail");
840 assert(
MI.isIdenticalTo(*Pos) &&
"Expected matching MIIs!");
842 NextCommonInsts[i] = ++Pos;
865 return NewLiveIns.contains(SReg) && !MRI->isReserved(SReg);
870 BuildMI(*Pred, InsertBefore,
DL, TII->
get(TargetOpcode::IMPLICIT_DEF),
891 unsigned MinCommonTailLength) {
892 bool MadeChange =
false;
895 dbgs() <<
"\nTryTailMergeBlocks: ";
896 for (
unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
dbgs()
898 << (i == e - 1 ?
"" :
", ");
899 dbgs() <<
"\n";
if (SuccBB) {
902 dbgs() <<
" which has fall-through from "
904 }
dbgs() <<
"Looking for common tails of at least "
905 << MinCommonTailLength <<
" instruction"
906 << (MinCommonTailLength == 1 ?
"" :
"s") <<
'\n';);
913 while (MergePotentials.size() > 1) {
914 unsigned CurHash = MergePotentials.back().getHash();
915 const DebugLoc &BranchDL = MergePotentials.back().getBranchDebugLoc();
919 unsigned maxCommonTailLength = ComputeSameTails(CurHash,
925 if (SameTails.empty()) {
926 RemoveBlocksWithHash(CurHash, SuccBB, PredBB, BranchDL);
935 &MergePotentials.front().getBlock()->getParent()->front();
936 unsigned commonTailIndex = SameTails.size();
939 if (SameTails.size() == 2 &&
940 SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
941 SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
943 else if (SameTails.size() == 2 &&
944 SameTails[1].getBlock()->isLayoutSuccessor(
945 SameTails[0].getBlock()) &&
946 SameTails[0].tailIsWholeBlock() &&
947 !SameTails[0].getBlock()->isEHPad())
952 for (
unsigned i = 0, e = SameTails.size(); i != e; ++i) {
955 SameTails[i].tailIsWholeBlock())
961 if (SameTails[i].tailIsWholeBlock())
966 if (commonTailIndex == SameTails.size() ||
967 (SameTails[commonTailIndex].getBlock() == PredBB &&
968 !SameTails[commonTailIndex].tailIsWholeBlock())) {
971 if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
972 maxCommonTailLength, commonTailIndex)) {
973 RemoveBlocksWithHash(CurHash, SuccBB, PredBB, BranchDL);
981 setCommonTailEdgeWeights(*
MBB);
985 mergeCommonTails(commonTailIndex);
991 for (
unsigned int i=0, e = SameTails.size(); i != e; ++i) {
992 if (commonTailIndex == i)
995 << (i == e - 1 ?
"" :
", "));
997 replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *
MBB);
999 MergePotentials.erase(SameTails[i].getMPIter());
1010 bool MadeChange =
false;
1011 if (!EnableTailMerge)
1016 MergePotentials.clear();
1028 for (
const MergePotentialsElt &Elt : MergePotentials)
1029 TriedMerging.insert(Elt.getBlock());
1032 if (MergePotentials.size() >= 2)
1033 MadeChange |= TryTailMergeBlocks(
nullptr,
nullptr, MinCommonTailLength);
1056 if (
I->pred_size() < 2)
continue;
1060 MergePotentials.clear();
1073 if (AfterBlockPlacement && MLI) {
1075 if (
ML && IBB ==
ML->getHeader())
1083 if (TriedMerging.count(PBB))
1091 if (!UniquePreds.
insert(PBB).second)
1096 if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())
1102 if (AfterBlockPlacement && MLI)
1112 if (!
Cond.empty() &&
TBB == IBB) {
1117 auto Next = ++PBB->getIterator();
1118 if (Next != MF.end())
1124 DebugLoc dl = PBB->findBranchDebugLoc();
1125 if (
TBB && (
Cond.empty() || FBB)) {
1133 MergePotentials.push_back(
1141 for (MergePotentialsElt &Elt : MergePotentials)
1142 TriedMerging.insert(Elt.getBlock());
1144 if (MergePotentials.size() >= 2)
1145 MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);
1149 PredBB = &*std::prev(
I);
1150 if (MergePotentials.size() == 1 &&
1151 MergePotentials.begin()->getBlock() != PredBB)
1152 FixTail(MergePotentials.begin()->getBlock(), IBB, TII,
1153 MergePotentials.begin()->getBranchDebugLoc());
1166 for (
const auto &Src : SameTails) {
1169 AccumulatedMBBFreq += BlockFreq;
1176 auto EdgeFreq = EdgeFreqLs.begin();
1179 SuccI != SuccE; ++SuccI, ++EdgeFreq)
1183 MBBFreqInfo.
setBlockFreq(&TailMBB, AccumulatedMBBFreq);
1189 std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(),
BlockFrequency(0))
1191 auto EdgeFreq = EdgeFreqLs.begin();
1193 if (SumEdgeFreq > 0) {
1195 SuccI != SuccE; ++SuccI, ++EdgeFreq) {
1197 EdgeFreq->getFrequency(), SumEdgeFreq);
1208 bool MadeChange =
false;
1217 MadeChange |= OptimizeBlock(&
MBB);
1221 RemoveDeadBlock(&
MBB);
1241 return I->isBranch();
1250 assert(MBB1 && MBB2 &&
"Unknown MachineBasicBlock");
1258 if (MBB1I == MBB1->
end() || MBB2I == MBB2->
end())
1266 return MBB2I->isCall() && !MBB1I->isCall();
1273 if (
I !=
MBB.
end() &&
I->isBranch())
1274 return I->getDebugLoc();
1283 if (
MI.isDebugInstr()) {
1284 TII->duplicate(PredMBB, InsertBefore,
MI);
1285 LLVM_DEBUG(
dbgs() <<
"Copied debug entity from empty block to pred: "
1295 if (
MI.isDebugInstr()) {
1296 TII->duplicate(SuccMBB, InsertBefore,
MI);
1297 LLVM_DEBUG(
dbgs() <<
"Copied debug entity from empty block to succ: "
1326 bool MadeChange =
false;
1334 bool SameEHScope =
true;
1335 if (!EHScopeMembership.empty() && FallThrough != MF.
end()) {
1336 auto MBBEHScope = EHScopeMembership.find(
MBB);
1337 assert(MBBEHScope != EHScopeMembership.end());
1338 auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
1339 assert(FallThroughEHScope != EHScopeMembership.end());
1340 SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
1347 bool CurUnAnalyzable =
1360 if (FallThrough == MF.
end()) {
1362 }
else if (FallThrough->isEHPad()) {
1378 if (*SI != &*FallThrough && !FallThrough->isSuccessor(*SI)) {
1379 assert((*SI)->isEHPad() &&
"Bad CFG");
1380 FallThrough->copySuccessor(
MBB, SI);
1385 MJTI->ReplaceMBBInJumpTables(
MBB, &*FallThrough);
1397 bool PriorUnAnalyzable =
1398 TII->
analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond,
true);
1399 if (!PriorUnAnalyzable) {
1403 if (PriorTBB && PriorTBB == PriorFBB) {
1407 if (PriorTBB !=
MBB)
1408 TII->
insertBranch(PrevBB, PriorTBB,
nullptr, PriorCond, dl);
1411 goto ReoptimizeBlock;
1425 <<
"From MBB: " << *
MBB);
1427 if (!PrevBB.
empty()) {
1433 while (PrevBBIter != PrevBB.
begin() && MBBIter !=
MBB->
end()
1434 && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
1435 if (!MBBIter->isIdenticalTo(*PrevBBIter))
1438 ++MBBIter; -- PrevBBIter;
1452 if (PriorTBB ==
MBB && !PriorFBB) {
1456 goto ReoptimizeBlock;
1461 if (PriorFBB ==
MBB) {
1464 TII->
insertBranch(PrevBB, PriorTBB,
nullptr, PriorCond, dl);
1467 goto ReoptimizeBlock;
1473 if (PriorTBB ==
MBB) {
1478 TII->
insertBranch(PrevBB, PriorFBB,
nullptr, NewPriorCond, dl);
1481 goto ReoptimizeBlock;
1496 bool DoTransform =
true;
1503 if (FallThrough == --MF.
end() &&
1505 DoTransform =
false;
1512 <<
"To make fallthrough to: " << *PriorTBB <<
"\n");
1535 bool PredAnalyzable =
1536 !TII->
analyzeBranch(*Pred, PredTBB, PredFBB, PredCond,
true);
1539 if (PredAnalyzable && !PredCond.
empty() && PredTBB ==
MBB &&
1540 PredTBB != PredFBB) {
1558 if (!PredsChanged.
empty()) {
1559 NumTailCalls += PredsChanged.
size();
1560 for (
auto &Pred : PredsChanged)
1568 if (!CurUnAnalyzable) {
1574 if (CurTBB && CurFBB && CurFBB ==
MBB && CurTBB !=
MBB) {
1582 goto ReoptimizeBlock;
1588 if (CurTBB && CurCond.
empty() && !CurFBB &&
1611 if (PredHasNoFallThrough || !PriorUnAnalyzable ||
1616 PriorTBB !=
MBB && PriorFBB !=
MBB) {
1619 "Bad branch analysis");
1622 assert(!PriorFBB &&
"Machine CFG out of date!");
1627 TII->
insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
1632 bool DidChange =
false;
1633 bool HasBranchToSelf =
false;
1639 HasBranchToSelf =
true;
1649 assert((*SI)->isEHPad() &&
"Bad CFG");
1658 *PMBB, NewCurTBB, NewCurFBB, NewCurCond,
true);
1659 if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
1663 TII->
insertBranch(*PMBB, NewCurTBB,
nullptr, NewCurCond, pdl);
1672 MJTI->ReplaceMBBInJumpTables(
MBB, CurTBB);
1676 if (!HasBranchToSelf)
return MadeChange;
1703 !TII->
analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond,
true) &&
1704 (PredTBB ==
MBB || PredFBB ==
MBB) &&
1705 (!CurFallsThru || !CurTBB || !CurFBB) &&
1724 goto ReoptimizeBlock;
1729 if (!CurFallsThru) {
1732 if (!CurUnAnalyzable) {
1742 if (SuccBB !=
MBB && &*SuccPrev !=
MBB &&
1743 !SuccPrev->canFallThrough()) {
1746 goto ReoptimizeBlock;
1767 if (FallThrough != MF.
end() &&
1768 !FallThrough->isEHPad() &&
1769 !TII->
analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond,
true) &&
1786 bool MadeChange =
false;
1788 MadeChange |= HoistCommonCodeInSuccs(&
MBB);
1798 if (SuccBB != TrueBB)
1803template <
class Container>
1806 if (Reg.isPhysical()) {
1828 if (!
TII->isUnpredicatedTerminator(*Loc))
1869 if (!MO.isReg() || MO.isUse())
1874 if (
Uses.count(Reg)) {
1890 bool DontMoveAcrossStore =
true;
1891 if (!PI->isSafeToMove(
nullptr, DontMoveAcrossStore) ||
TII->
isPredicated(*PI))
1905 if (
Uses.erase(Reg)) {
1906 if (Reg.isPhysical()) {
1943 bool HasDups =
false;
1949 while (TIB != TIE && FIB != FIE) {
1953 if (TIB == TIE || FIB == FIE)
1966 if (MO.isRegMask()) {
1976 if (
Uses.count(Reg)) {
1983 if (Defs.
count(Reg) && !MO.isDead()) {
1998 }
else if (!ActiveDefsSet.
count(Reg)) {
1999 if (Defs.
count(Reg)) {
2005 if (MO.isKill() &&
Uses.count(Reg))
2008 MO.setIsKill(
false);
2014 bool DontMoveAcrossStore =
true;
2015 if (!TIB->isSafeToMove(
nullptr, DontMoveAcrossStore))
2025 if (!AllDefsSet.
count(Reg)) {
2028 if (
Reg.isPhysical()) {
2030 ActiveDefsSet.
erase(*AI);
2032 ActiveDefsSet.
erase(Reg);
2041 if (!Reg ||
Reg.isVirtual())
2056 FBB->erase(FBB->begin(), FIB);
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
This file implements the BitVector class.
static unsigned EstimateRuntime(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E)
EstimateRuntime - Make a rough estimate for how long it will take to run the specified code.
static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2)
Given two machine basic blocks, return the number of instructions they actually have in common togeth...
static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
findFalseBlock - BB has a fallthrough.
static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &PredMBB)
static unsigned HashMachineInstr(const MachineInstr &MI)
HashMachineInstr - Compute a hash value for MI and its operands.
static bool countsAsInstruction(const MachineInstr &MI)
Whether MI should be counted as an instruction when calculating common tail.
static unsigned CountTerminators(MachineBasicBlock *MBB, MachineBasicBlock::iterator &I)
CountTerminators - Count the number of terminators in the given block and set I to the position of th...
static bool blockEndsInUnreachable(const MachineBasicBlock *MBB)
A no successor, non-return block probably ends in unreachable and is cold.
static void salvageDebugInfoFromEmptyBlock(const TargetInstrInfo *TII, MachineBasicBlock &MBB)
static MachineBasicBlock::iterator skipBackwardPastNonInstructions(MachineBasicBlock::iterator I, MachineBasicBlock *MBB)
Iterate backwards from the given iterator I, towards the beginning of the block.
static cl::opt< unsigned > TailMergeThreshold("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden)
static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI, Container &Set)
static cl::opt< cl::boolOrDefault > FlagEnableTailMerge("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)
static cl::opt< unsigned > TailMergeSize("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden)
static bool IsEmptyBlock(MachineBasicBlock *MBB)
static bool ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, unsigned MinCommonTailLength, unsigned &CommonTailLen, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB, MachineBasicBlock *PredBB, DenseMap< const MachineBasicBlock *, int > &EHScopeMembership, bool AfterPlacement, MBFIWrapper &MBBFreqInfo, ProfileSummaryInfo *PSI)
ProfitableToMerge - Check if two machine basic blocks have a common tail and decide if it would be pr...
static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &SuccMBB)
static bool IsBranchOnlyBlock(MachineBasicBlock *MBB)
static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, const TargetInstrInfo *TII, const DebugLoc &BranchDL)
static bool IsBetterFallthrough(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)
IsBetterFallthrough - Return true if it would be clearly better to fall-through to MBB1 than to fall ...
static unsigned HashEndOfMBB(const MachineBasicBlock &MBB)
HashEndOfMBB - Hash the last instruction in the MBB.
static void mergeOperations(MachineBasicBlock::iterator MBBIStartPos, MachineBasicBlock &MBBCommon)
static MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, SmallSet< Register, 4 > &Uses, SmallSet< Register, 4 > &Defs)
findHoistingInsertPosAndDeps - Find the location to move common instructions in successors to.
static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB)
getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Rewrite Partial Register Uses
const HexagonInstrInfo * TII
A common definition of LaneBitmask for use in TableGen and CodeGen.
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Target-Independent Code Generator Pass Configuration Options pass.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
LLVM Basic Block Representation.
bool test(unsigned Idx) const
size_type size() const
size - Returns the number of bits in this bitvector.
bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii, const TargetRegisterInfo *tri, MachineLoopInfo *mli=nullptr, bool AfterPlacement=false)
Perhaps branch folding, tail merging and other CFG optimizations on the given function.
BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist, MBFIWrapper &FreqInfo, const MachineBranchProbabilityInfo &ProbInfo, ProfileSummaryInfo *PSI, unsigned MinTailLength=0)
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
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....
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
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.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
void clear()
Clears the set.
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F)
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
MCRegAliasIterator enumerates all registers aliasing Reg.
iterator_range< MCSuperRegIterator > superregs(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, excluding Reg.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
void moveBefore(MachineBasicBlock *NewAfter)
Move 'this' block before or after the specified block.
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
iterator_range< livein_iterator > liveins() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
succ_iterator succ_begin()
void clearLiveIns()
Clear live in list.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
bool hasAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void copySuccessor(const MachineBasicBlock *Orig, succ_iterator I)
Copy a successor (and any probability info) from original block to this block's.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
pred_iterator pred_begin()
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Given a machine basic block that branched to 'Old', change the code and CFG so that it branches to 'N...
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
iterator_range< succ_iterator > successors()
reverse_iterator rbegin()
bool isMachineBlockAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
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 '...
void moveAfter(MachineBasicBlock *NewBefore)
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
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...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineBasicBlock & back() const
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void erase(iterator MBBI)
void insert(iterator MBBI, MachineBasicBlock *MBB)
Representation of each machine instruction.
bool isReturn(QueryType Type=AnyInBundle) const
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
bool isIndirectBranch(QueryType Type=AnyInBundle) const
Return true if this is an indirect branch, such as a branch through a register.
void RemoveJumpTable(unsigned Idx)
RemoveJumpTable - Mark the specific index as being dead.
const std::vector< MachineJumpTableEntry > & getJumpTables() const
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()
void removeBlock(MachineBasicBlock *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setIsUndef(bool Val=true)
@ MO_Immediate
Immediate operand.
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
@ MO_GlobalAddress
Address of a global value.
@ MO_MachineBasicBlock
MachineBasicBlock reference.
@ MO_FrameIndex
Abstract Stack Frame Index.
@ MO_Register
Register operand.
@ MO_ExternalSymbol
Name of external global symbol.
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
Wrapper class representing virtual and physical registers.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const
Reverses the branch condition of the specified condition list, returning false on success and true if...
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
virtual bool canMakeTailCallConditional(SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const
Returns true if the tail call can be made conditional on BranchCond.
virtual void ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail, MachineBasicBlock *NewDest) const
Delete the instruction OldInst and everything after it, replacing it with an unconditional branch to ...
virtual bool isUnconditionalTailCall(const MachineInstr &MI) const
Returns true if MI is an unconditional tail call.
virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const
Insert branch code into the end of the specified MachineBasicBlock.
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
virtual void replaceBranchWithTailCall(MachineBasicBlock &MBB, SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const
Replace the conditional branch in MBB with a conditional tail call.
virtual bool isLegalToSplitMBBAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI) const
Return true if it's legal to split the given basic block at the specified instruction (i....
Target-Independent Code Generator Pass Configuration Options.
bool getEnableTailMerge() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const
Returns true if the live-ins should be tracked after register allocation.
self_iterator getIterator()
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB)
Computes registers live-in to MBB assuming all of its successors live-in lists are up-to-date.
char & BranchFolderPassID
BranchFolding - This pass performs machine code CFG based optimizations to delete branches to branche...
IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It, then continue decrementing it while it points to a debug instruction.
void fullyRecomputeLiveIns(ArrayRef< MachineBasicBlock * > MBBs)
Convenience function for recomputing live-in's for a set of MBBs until the computation converges.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
DenseMap< const MachineBasicBlock *, int > getEHScopeMembership(const MachineFunction &MF)
static constexpr LaneBitmask getAll()
Pair of physical register and lane mask.