Go to the documentation of this file.
65 #define DEBUG_TYPE "branch-folder"
67 STATISTIC(NumDeadBlocks,
"Number of dead blocks removed");
68 STATISTIC(NumBranchOpts,
"Number of branches optimized");
69 STATISTIC(NumTailMerge ,
"Number of block tails merged");
70 STATISTIC(NumHoist ,
"Number of times common instructions are hoisted");
71 STATISTIC(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"),
121 "Control Flow Optimizer",
false,
false)
124 if (skipFunction(MF.getFunction()))
130 bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
133 getAnalysis<MachineBlockFrequencyInfo>());
135 getAnalysis<MachineBranchProbabilityInfo>(),
136 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
138 MF.getSubtarget().getRegisterInfo());
145 : EnableHoistCommonCode(CommonHoist), MinCommonTailLength(MinTailLength),
146 MBBFreqInfo(FreqInfo), MBPI(ProbInfo), PSI(PSI) {
147 if (MinCommonTailLength == 0)
151 EnableTailMerge = DefaultEnableTailMerge;
168 TriedMerging.erase(
MBB);
172 if (
MI.shouldUpdateCallSiteInfo())
177 EHScopeMembership.erase(
MBB);
186 if (!tii)
return false;
188 TriedMerging.clear();
191 AfterBlockPlacement = AfterPlacement;
201 bool MadeChange =
false;
206 bool MadeChangeThisIteration =
true;
207 while (MadeChangeThisIteration) {
208 MadeChangeThisIteration = TailMergeBlocks(MF);
211 if (!AfterBlockPlacement || MadeChangeThisIteration)
212 MadeChangeThisIteration |= OptimizeBranches(MF);
213 if (EnableHoistCommonCode)
214 MadeChangeThisIteration |= HoistCommonCode(MF);
215 MadeChange |= MadeChangeThisIteration;
229 if (!
Op.isJTI())
continue;
232 JTIsLive.
set(
Op.getIndex());
238 for (
unsigned i = 0,
e = JTIsLive.
size();
i !=
e; ++
i)
239 if (!JTIsLive.
test(
i)) {
253 unsigned Hash =
MI.getOpcode();
254 for (
unsigned i = 0,
e =
MI.getNumOperands();
i !=
e; ++
i) {
260 unsigned OperandHash = 0;
261 switch (
Op.getType()) {
263 OperandHash =
Op.getReg();
266 OperandHash =
Op.getImm();
269 OperandHash =
Op.getMBB()->getNumber();
274 OperandHash =
Op.getIndex();
280 OperandHash =
Op.getOffset();
286 Hash += ((OperandHash << 3) |
Op.getType()) << (
i & 31);
302 return !(
MI.isDebugInstr() ||
MI.isCFIInstruction());
332 unsigned TailLen = 0;
336 if (MBBI1 == MBB1->
end() || MBBI2 == MBB2->
end())
338 if (!MBBI1->isIdenticalTo(*MBBI2) ||
344 MBBI1->isInlineAsm()) {
370 }
while (
I != OldInst);
379 "Can only handle full register.");
384 BuildMI(OldMBB, OldInst,
DL, TII->
get(TargetOpcode::IMPLICIT_DEF),
Reg);
412 NewMBB->
splice(NewMBB->
end(), &CurMBB, BBI1, CurMBB.
end());
417 ML->addBasicBlockToLoop(NewMBB, MLI->
getBase());
426 const auto &EHScopeI = EHScopeMembership.find(&CurMBB);
427 if (EHScopeI != EHScopeMembership.end()) {
428 auto n = EHScopeI->second;
429 EHScopeMembership[NewMBB] =
n;
440 for (;
I !=
E; ++
I) {
445 else if (
I->mayLoadOrStore())
466 if (TBB == NextBB && !
Cond.empty() && !FBB) {
480 if (getHash() < o.getHash())
482 if (getHash() > o.getHash())
484 if (getBlock()->getNumber() < o.getBlock()->getNumber())
486 if (getBlock()->getNumber() > o.getBlock()->getNumber())
490 #ifndef _GLIBCXX_DEBUG
503 unsigned NumTerms = 0;
510 if (!
I->isTerminator())
break;
545 unsigned MinCommonTailLength,
unsigned &CommonTailLen,
554 if (!EHScopeMembership.
empty()) {
555 auto EHScope1 = EHScopeMembership.
find(MBB1);
556 assert(EHScope1 != EHScopeMembership.
end());
557 auto EHScope2 = EHScopeMembership.
find(MBB2);
558 assert(EHScope2 != EHScopeMembership.
end());
559 if (EHScope1->second != EHScope2->second)
564 if (CommonTailLen == 0)
568 << CommonTailLen <<
'\n');
578 bool FullBlockTail1 =
I1 == MBB1->
begin();
579 bool FullBlockTail2 = I2 == MBB2->
begin();
586 if ((MBB1 == PredBB || MBB2 == PredBB) &&
587 (!AfterPlacement || MBB1->
succ_size() == 1)) {
590 if (CommonTailLen > NumTerms)
599 if (FullBlockTail1 && FullBlockTail2 &&
616 if (AfterPlacement && FullBlockTail1 && FullBlockTail2) {
622 return (
MBB != &*MF->
begin()) && std::prev(
I)->canFallThrough();
624 if (!BothFallThrough(MBB1) || !BothFallThrough(MBB2))
633 unsigned EffectiveTailLen = CommonTailLen;
634 if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
635 (MBB1->
succ_size() == 1 || !AfterPlacement) &&
641 if (EffectiveTailLen >= MinCommonTailLength)
653 return EffectiveTailLen >= 2 && OptForSize &&
654 (FullBlockTail1 || FullBlockTail2);
657 unsigned BranchFolder::ComputeSameTails(
unsigned CurHash,
658 unsigned MinCommonTailLength,
661 unsigned maxCommonTailLength = 0U;
664 MPIterator HighestMPIter = std::prev(MergePotentials.end());
665 for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
666 B = MergePotentials.begin();
667 CurMPIter !=
B && CurMPIter->getHash() == CurHash; --CurMPIter) {
668 for (MPIterator
I = std::prev(CurMPIter);
I->getHash() == CurHash; --
I) {
669 unsigned CommonTailLen;
672 CommonTailLen, TrialBBI1, TrialBBI2,
675 AfterBlockPlacement, MBBFreqInfo, PSI)) {
676 if (CommonTailLen > maxCommonTailLength) {
678 maxCommonTailLength = CommonTailLen;
679 HighestMPIter = CurMPIter;
680 SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
682 if (HighestMPIter == CurMPIter &&
683 CommonTailLen == maxCommonTailLength)
684 SameTails.push_back(SameTailElt(
I, TrialBBI2));
690 return maxCommonTailLength;
693 void BranchFolder::RemoveBlocksWithHash(
unsigned CurHash,
696 MPIterator CurMPIter,
B;
697 for (CurMPIter = std::prev(MergePotentials.end()),
698 B = MergePotentials.begin();
699 CurMPIter->getHash() == CurHash; --CurMPIter) {
702 if (SuccBB && CurMBB != PredBB)
707 if (CurMPIter->getHash() != CurHash)
709 MergePotentials.erase(CurMPIter, MergePotentials.end());
714 unsigned maxCommonTailLength,
715 unsigned &commonTailIndex) {
717 unsigned TimeEstimate = ~0U;
718 for (
unsigned i = 0,
e = SameTails.size();
i !=
e; ++
i) {
720 if (SameTails[
i].getBlock() == PredBB) {
727 SameTails[
i].getTailStartPos());
728 if (
t <= TimeEstimate) {
735 SameTails[commonTailIndex].getTailStartPos();
739 << maxCommonTailLength);
752 SameTails[commonTailIndex].setBlock(newMBB);
753 SameTails[commonTailIndex].setTailStartPos(newMBB->
begin());
769 unsigned CommonTailLen = 0;
770 for (
auto E =
MBB->
end(); MBBIStartPos !=
E; ++MBBIStartPos)
778 while (CommonTailLen--) {
779 assert(
MBBI != MBBIE &&
"Reached BB end within common tail length!");
790 assert(MBBICommon != MBBIECommon &&
791 "Reached BB end within common tail length!");
792 assert(MBBICommon->isIdenticalTo(*
MBBI) &&
"Expected matching MIIs!");
795 if (MBBICommon->mayLoadOrStore())
796 MBBICommon->cloneMergedMemRefs(*
MBB->
getParent(), {&*MBBICommon, &*MBBI});
798 for (
unsigned I = 0,
E = MBBICommon->getNumOperands();
I !=
E; ++
I) {
812 void BranchFolder::mergeCommonTails(
unsigned commonTailIndex) {
815 std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
816 for (
unsigned int i = 0 ;
i != SameTails.size() ; ++
i) {
817 if (
i != commonTailIndex) {
818 NextCommonInsts[
i] = SameTails[
i].getTailStartPos();
822 "MBB is not a common tail only block");
826 for (
auto &
MI : *
MBB) {
830 for (
unsigned int i = 0 ;
i < NextCommonInsts.size() ;
i++) {
831 if (
i == commonTailIndex)
834 auto &Pos = NextCommonInsts[
i];
835 assert(Pos != SameTails[
i].getBlock()->
end() &&
836 "Reached BB end within common tail");
839 assert(Pos != SameTails[
i].getBlock()->
end() &&
840 "Reached BB end within common tail");
842 assert(
MI.isIdenticalTo(*Pos) &&
"Expected matching MIIs!");
844 NextCommonInsts[
i] = ++Pos;
864 BuildMI(*Pred, InsertBefore,
DL, TII->
get(TargetOpcode::IMPLICIT_DEF),
885 unsigned MinCommonTailLength) {
886 bool MadeChange =
false;
889 dbgs() <<
"\nTryTailMergeBlocks: ";
890 for (
unsigned i = 0,
e = MergePotentials.size();
i !=
e; ++
i)
dbgs()
892 << (
i ==
e - 1 ?
"" :
", ");
893 dbgs() <<
"\n";
if (SuccBB) {
896 dbgs() <<
" which has fall-through from "
898 }
dbgs() <<
"Looking for common tails of at least "
899 << MinCommonTailLength <<
" instruction"
900 << (MinCommonTailLength == 1 ?
"" :
"s") <<
'\n';);
907 while (MergePotentials.size() > 1) {
908 unsigned CurHash = MergePotentials.back().getHash();
912 unsigned maxCommonTailLength = ComputeSameTails(CurHash,
918 if (SameTails.empty()) {
919 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
928 &MergePotentials.front().getBlock()->getParent()->front();
929 unsigned commonTailIndex = SameTails.size();
932 if (SameTails.size() == 2 &&
933 SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
934 SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
936 else if (SameTails.size() == 2 &&
937 SameTails[1].getBlock()->isLayoutSuccessor(
938 SameTails[0].getBlock()) &&
939 SameTails[0].tailIsWholeBlock() &&
940 !SameTails[0].getBlock()->isEHPad())
945 for (
unsigned i = 0,
e = SameTails.size();
i !=
e; ++
i) {
948 SameTails[
i].tailIsWholeBlock())
954 if (SameTails[
i].tailIsWholeBlock())
959 if (commonTailIndex == SameTails.size() ||
960 (SameTails[commonTailIndex].getBlock() == PredBB &&
961 !SameTails[commonTailIndex].tailIsWholeBlock())) {
964 if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
965 maxCommonTailLength, commonTailIndex)) {
966 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
974 setCommonTailEdgeWeights(*
MBB);
978 mergeCommonTails(commonTailIndex);
984 for (
unsigned int i=0,
e = SameTails.size();
i !=
e; ++
i) {
985 if (commonTailIndex ==
i)
988 << (
i ==
e - 1 ?
"" :
", "));
990 replaceTailWithBranchTo(SameTails[
i].getTailStartPos(), *
MBB);
992 MergePotentials.erase(SameTails[
i].getMPIter());
1003 bool MadeChange =
false;
1004 if (!EnableTailMerge)
1009 MergePotentials.clear();
1020 for (
const MergePotentialsElt &Elt : MergePotentials)
1021 TriedMerging.insert(Elt.getBlock());
1024 if (MergePotentials.size() >= 2)
1025 MadeChange |= TryTailMergeBlocks(
nullptr,
nullptr, MinCommonTailLength);
1048 if (
I->pred_size() < 2)
continue;
1052 MergePotentials.clear();
1065 if (AfterBlockPlacement && MLI) {
1075 if (TriedMerging.count(PBB))
1083 if (!UniquePreds.
insert(PBB).second)
1088 if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())
1094 if (AfterBlockPlacement && MLI)
1104 if (!
Cond.empty() && TBB == IBB) {
1109 auto Next = ++PBB->getIterator();
1110 if (Next != MF.end())
1116 if (TBB && (
Cond.empty() || FBB)) {
1117 DebugLoc dl = PBB->findBranchDebugLoc();
1121 TII->
insertBranch(*PBB, (TBB == IBB) ? FBB : TBB,
nullptr,
1125 MergePotentials.push_back(MergePotentialsElt(
HashEndOfMBB(*PBB), PBB));
1132 for (MergePotentialsElt &Elt : MergePotentials)
1133 TriedMerging.insert(Elt.getBlock());
1135 if (MergePotentials.size() >= 2)
1136 MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);
1140 PredBB = &*std::prev(
I);
1141 if (MergePotentials.size() == 1 &&
1142 MergePotentials.begin()->getBlock() != PredBB)
1143 FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
1156 for (
const auto &Src : SameTails) {
1159 AccumulatedMBBFreq += BlockFreq;
1166 auto EdgeFreq = EdgeFreqLs.begin();
1169 SuccI != SuccE; ++SuccI, ++EdgeFreq)
1173 MBBFreqInfo.
setBlockFreq(&TailMBB, AccumulatedMBBFreq);
1179 std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(),
BlockFrequency(0))
1181 auto EdgeFreq = EdgeFreqLs.begin();
1183 if (SumEdgeFreq > 0) {
1185 SuccI != SuccE; ++SuccI, ++EdgeFreq) {
1187 EdgeFreq->getFrequency(), SumEdgeFreq);
1198 bool MadeChange =
false;
1207 MadeChange |= OptimizeBlock(&
MBB);
1211 RemoveDeadBlock(&
MBB);
1231 return I->isBranch();
1240 assert(MBB1 && MBB2 &&
"Unknown MachineBasicBlock");
1248 if (MBB1I == MBB1->
end() || MBB2I == MBB2->
end())
1256 return MBB2I->isCall() && !MBB1I->isCall();
1263 if (
I !=
MBB.
end() &&
I->isBranch())
1264 return I->getDebugLoc();
1273 if (
MI.isDebugInstr()) {
1274 TII->duplicate(PredMBB, InsertBefore,
MI);
1275 LLVM_DEBUG(
dbgs() <<
"Copied debug entity from empty block to pred: "
1285 if (
MI.isDebugInstr()) {
1286 TII->duplicate(SuccMBB, InsertBefore,
MI);
1287 LLVM_DEBUG(
dbgs() <<
"Copied debug entity from empty block to succ: "
1316 bool MadeChange =
false;
1324 bool SameEHScope =
true;
1325 if (!EHScopeMembership.empty() && FallThrough != MF.
end()) {
1326 auto MBBEHScope = EHScopeMembership.find(
MBB);
1327 assert(MBBEHScope != EHScopeMembership.end());
1328 auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
1329 assert(FallThroughEHScope != EHScopeMembership.end());
1330 SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
1337 bool CurUnAnalyzable =
1350 if (FallThrough == MF.
end()) {
1352 }
else if (FallThrough->isEHPad()) {
1367 MJTI->ReplaceMBBInJumpTables(
MBB, &*FallThrough);
1379 bool PriorUnAnalyzable =
1380 TII->
analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond,
true);
1381 if (!PriorUnAnalyzable) {
1385 if (PriorTBB && PriorTBB == PriorFBB) {
1389 if (PriorTBB !=
MBB)
1390 TII->
insertBranch(PrevBB, PriorTBB,
nullptr, PriorCond, dl);
1393 goto ReoptimizeBlock;
1403 if (PriorCond.empty() && !PriorTBB &&
MBB->
pred_size() == 1 &&
1407 <<
"From MBB: " << *
MBB);
1409 if (!PrevBB.
empty()) {
1415 while (PrevBBIter != PrevBB.
begin() && MBBIter !=
MBB->
end()
1416 && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
1417 if (!MBBIter->isIdenticalTo(*PrevBBIter))
1420 ++MBBIter; -- PrevBBIter;
1434 if (PriorTBB ==
MBB && !PriorFBB) {
1438 goto ReoptimizeBlock;
1443 if (PriorFBB ==
MBB) {
1446 TII->
insertBranch(PrevBB, PriorTBB,
nullptr, PriorCond, dl);
1449 goto ReoptimizeBlock;
1455 if (PriorTBB ==
MBB) {
1460 TII->
insertBranch(PrevBB, PriorFBB,
nullptr, NewPriorCond, dl);
1463 goto ReoptimizeBlock;
1478 bool DoTransform =
true;
1485 if (FallThrough == --MF.
end() &&
1487 DoTransform =
false;
1494 <<
"To make fallthrough to: " << *PriorTBB <<
"\n");
1522 bool PredAnalyzable =
1523 !TII->
analyzeBranch(*Pred, PredTBB, PredFBB, PredCond,
true);
1525 if (PredAnalyzable && !PredCond.empty() && PredTBB ==
MBB &&
1526 PredTBB != PredFBB) {
1549 if (!CurUnAnalyzable) {
1555 if (CurTBB && CurFBB && CurFBB ==
MBB && CurTBB !=
MBB) {
1563 goto ReoptimizeBlock;
1569 if (CurTBB && CurCond.empty() && !CurFBB &&
1592 if (PredHasNoFallThrough || !PriorUnAnalyzable ||
1597 PriorTBB !=
MBB && PriorFBB !=
MBB) {
1599 assert(PriorCond.empty() && !PriorFBB &&
1600 "Bad branch analysis");
1603 assert(!PriorFBB &&
"Machine CFG out of date!");
1608 TII->
insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
1613 bool DidChange =
false;
1614 bool HasBranchToSelf =
false;
1620 HasBranchToSelf =
true;
1630 *PMBB, NewCurTBB, NewCurFBB, NewCurCond,
true);
1631 if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
1635 TII->
insertBranch(*PMBB, NewCurTBB,
nullptr, NewCurCond, pdl);
1644 MJTI->ReplaceMBBInJumpTables(
MBB, CurTBB);
1648 if (!HasBranchToSelf)
return MadeChange;
1675 !TII->
analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond,
true) &&
1676 (PredTBB ==
MBB || PredFBB ==
MBB) &&
1677 (!CurFallsThru || !CurTBB || !CurFBB) &&
1696 goto ReoptimizeBlock;
1701 if (!CurFallsThru) {
1704 if (!CurUnAnalyzable) {
1714 if (SuccBB !=
MBB && &*SuccPrev !=
MBB &&
1715 !SuccPrev->canFallThrough()) {
1718 goto ReoptimizeBlock;
1739 if (FallThrough != MF.
end() &&
1740 !FallThrough->isEHPad() &&
1741 !TII->
analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond,
true) &&
1758 bool MadeChange =
false;
1760 MadeChange |= HoistCommonCodeInSuccs(&
MBB);
1770 if (SuccBB != TrueBB)
1775 template <
class Container>
1778 if (
Reg.isPhysical()) {
1800 if (!
TII->isUnpredicatedTerminator(*Loc))
1841 if (!MO.isReg() || MO.isUse())
1862 bool DontMoveAcrossStore =
true;
1863 if (!PI->isSafeToMove(
nullptr, DontMoveAcrossStore) ||
TII->
isPredicated(*PI))
1880 Uses.erase(*SubRegs);
1903 if (TBB->
pred_size() > 1 || FBB->pred_size() > 1)
1915 bool HasDups =
false;
1921 while (TIB != TIE && FIB != FIE) {
1925 if (TIB == TIE || FIB == FIE)
1938 if (MO.isRegMask()) {
1955 if (Defs.
count(
Reg) && !MO.isDead()) {
1970 }
else if (!ActiveDefsSet.
count(
Reg)) {
1977 if (MO.isKill() &&
Uses.count(
Reg))
1980 MO.setIsKill(
false);
1986 bool DontMoveAcrossStore =
true;
1987 if (!TIB->isSafeToMove(
nullptr, DontMoveAcrossStore))
1992 if (!MO.isReg() || !MO.isUse() || !MO.isKill())
2000 if (
Reg.isPhysical()) {
2002 ActiveDefsSet.
erase(*AI);
2010 if (!MO.isReg() || !MO.isDef() || MO.isDead())
2013 if (!
Reg ||
Reg.isVirtual())
2028 FBB->erase(FBB->begin(), FIB);
2030 if (UpdateLiveIns) {
virtual bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const
Returns true if the live-ins should be tracked after register allocation.
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.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
unsigned succ_size() const
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.
pred_iterator pred_begin()
@ MO_Immediate
Immediate operand.
This is an optimization pass for GlobalISel generic memory operations.
static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &SuccMBB)
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.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
bool isIndirectBranch(QueryType Type=AnyInBundle) const
Return true if this is an indirect branch, such as a branch through a register.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
virtual void replaceBranchWithTailCall(MachineBasicBlock &MBB, SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const
Replace the conditional branch in MBB with a conditional tail call.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static MachineBasicBlock::iterator skipBackwardPastNonInstructions(MachineBasicBlock::iterator I, MachineBasicBlock *MBB)
Iterate backwards from the given iterator I, towards the beginning of the block.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
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...
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
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....
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
static void recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for MBB.
Reg
All possible values of the reg field in the ModR/M byte.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
const MachineBasicBlock & back() const
A set of physical registers with utility functions to track liveness when walking backward/forward th...
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...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
void moveBefore(MachineBasicBlock *NewAfter)
Move 'this' block before or after the specified block.
virtual void ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail, MachineBasicBlock *NewDest) const
Delete the instruction OldInst and everything after it, replacing it with an unconditional branch to ...
iterator_range< livein_iterator > liveins() const
const_iterator end(StringRef path)
Get end iterator over path.
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
void insert(iterator MBBI, MachineBasicBlock *MBB)
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Properties which a MachineFunction may have at a given point in time.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &PredMBB)
static bool IsEmptyBlock(MachineBasicBlock *MBB)
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, const TargetInstrInfo *TII)
unsigned const TargetRegisterInfo * TRI
void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static bool countsAsInstruction(const MachineInstr &MI)
Whether MI should be counted as an instruction when calculating common tail.
@ MO_Register
Register operand.
SmallPtrSet< MachineInstr *, 2 > Uses
LLVM Basic Block Representation.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
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.
bool tracksLiveness() const
tracksLiveness - Returns true when tracking register liveness accurately.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
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...
unsigned pred_size() const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
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.
TargetInstrInfo - Interface to description of machine instruction set.
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
@ MO_GlobalAddress
Address of a global value.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static cl::opt< unsigned > TailMergeThreshold("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden)
size_type size() const
size - Returns the number of bits in this bitvector.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
@ MO_FrameIndex
Abstract Stack Frame Index.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Represent the analysis usage information of a pass.
bitcast float %x to i32 %s=and i32 %t, 2147483647 %d=bitcast i32 %s to float ret float %d } declare float @fabsf(float %n) define float @bar(float %x) nounwind { %d=call float @fabsf(float %x) ret float %d } This IR(from PR6194):target datalayout="e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple="x86_64-apple-darwin10.0.0" %0=type { double, double } %struct.float3=type { float, float, float } define void @test(%0, %struct.float3 *nocapture %res) nounwind noinline ssp { entry:%tmp18=extractvalue %0 %0, 0 t
bool getEnableTailMerge() const
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
const HexagonInstrInfo * TII
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineOperand class - Representation of each machine instruction operand.
MachineFunctionProperties & set(Property P)
Pair of physical register and lane mask.
BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist, MBFIWrapper &FreqInfo, const MachineBranchProbabilityInfo &ProbInfo, ProfileSummaryInfo *PSI, unsigned MinTailLength=0)
STATISTIC(NumFunctions, "Total number of functions")
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.
static cl::opt< cl::boolOrDefault > FlagEnableTailMerge("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)
virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const
Reverses the branch condition of the specified condition list, returning false on success and true if...
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB)
getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Analysis providing profile information.
Target-Independent Code Generator Pass Configuration Options.
virtual bool canMakeTailCallConditional(SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const
Returns true if the tail call can be made conditional on BranchCond.
const std::vector< MachineJumpTableEntry > & getJumpTables() const
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
static cl::opt< unsigned > TailMergeSize("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE, "Control Flow Optimizer", false, false) bool BranchFolderPass
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
initializer< Ty > init(const Ty &Val)
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...
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI, Container &Set)
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It, then continue decrementing it while it points to a debug instruction.
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
succ_iterator succ_begin()
static void salvageDebugInfoFromEmptyBlock(const TargetInstrInfo *TII, MachineBasicBlock &MBB)
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void erase(iterator MBBI)
iterator_range< pred_iterator > predecessors()
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
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.
bool isReturn(QueryType Type=AnyInBundle) const
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....
void moveAfter(MachineBasicBlock *NewBefore)
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
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.
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...
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
static unsigned HashMachineInstr(const MachineInstr &MI)
HashMachineInstr - Compute a hash value for MI and its operands.
SmallVector< MachineOperand, 4 > Cond
iterator_range< succ_iterator > successors()
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
bool isEHPad() const
Returns true if the block is a landing pad.
reverse_iterator rbegin()
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 init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
MachineBasicBlock MachineBasicBlock::iterator MBBI
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
char & BranchFolderPassID
BranchFolding - This pass performs machine code CFG based optimizations to delete branches to branche...
void setIsUndef(bool Val=true)
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
@ MO_MachineBasicBlock
MachineBasicBlock reference.
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
void RemoveJumpTable(unsigned Idx)
RemoveJumpTable - Mark the specific index as being dead.
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
LLVM_NODISCARD bool empty() const
bool test(unsigned Idx) const
virtual bool isUnconditionalTailCall(const MachineInstr &MI) const
Returns true if MI is an unconditional tail call.
Function & getFunction()
Return the LLVM function that this machine code represents.
bool operator<(const DeltaInfo &LHS, int64_t Delta)
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
Iterator for intrusive lists based on ilist_node.
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....
@ MO_ExternalSymbol
Name of external global symbol.
BlockT * getHeader() const
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
MCSubRegIterator enumerates all sub-registers of Reg.
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
void clear()
Clears the set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
void removeBlock(MachineBasicBlock *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
void clearLiveIns()
Clear live in list.
static bool blockEndsInUnreachable(const MachineBasicBlock *MBB)
A no successor, non-return block probably ends in unreachable and is cold.
static bool IsBranchOnlyBlock(MachineBasicBlock *MBB)
static void mergeOperations(MachineBasicBlock::iterator MBBIStartPos, MachineBasicBlock &MBBCommon)
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
AnalysisUsage & addRequired()
DenseMap< const MachineBasicBlock *, int > getEHScopeMembership(const MachineFunction &MF)
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.
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
findFalseBlock - BB has a fallthrough.
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
static constexpr LaneBitmask getAll()
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
MCRegAliasIterator enumerates all registers aliasing Reg.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.