91using namespace PatternMatch;
93#define DEBUG_TYPE "simplifycfg"
96 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
98 cl::desc(
"Temorary development switch used to gradually uplift SimplifyCFG "
99 "into preserving DomTree,"));
108 "Control the amount of phi node folding to perform (default = 2)"));
112 cl::desc(
"Control the maximal total instruction cost that we are willing "
113 "to speculatively execute to fold a 2-entry PHI node into a "
114 "select (default = 4)"));
118 cl::desc(
"Hoist common instructions up to the parent block"));
123 cl::desc(
"Allow reordering across at most this many "
124 "instructions when hoisting"));
128 cl::desc(
"Sink common instructions down to the end block"));
132 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
136 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
137 "precede - hoist multiple conditional stores into a single "
138 "predicated store"));
142 cl::desc(
"When merging conditional stores, do so even if the resultant "
143 "basic blocks are unlikely to be if-converted as a result"));
147 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
152 cl::desc(
"Limit maximum recursion depth when calculating costs of "
153 "speculatively executed instructions"));
158 cl::desc(
"Max size of a block which is still considered "
159 "small enough to thread through"));
165 cl::desc(
"Maximum cost of combining conditions when "
166 "folding branches"));
169 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
171 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
172 "to fold branch to common destination when vector operations are "
177 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
181 cl::desc(
"Limit cases to analyze when converting a switch to select"));
183STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
185 "Number of switch instructions turned into linear mapping");
187 "Number of switch instructions turned into lookup tables");
189 NumLookupTablesHoles,
190 "Number of switch instructions turned into lookup tables (holes checked)");
191STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
193 "Number of value comparisons folded into predecessor basic blocks");
195 "Number of branches folded into predecessor basic block");
198 "Number of common instruction 'blocks' hoisted up to the begin block");
200 "Number of common instructions hoisted up to the begin block");
202 "Number of common instruction 'blocks' sunk down to the end block");
204 "Number of common instructions sunk down to the end block");
205STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
207 "Number of invokes with empty resume blocks simplified into calls");
208STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
209STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
216using SwitchCaseResultVectorTy =
225struct ValueEqualityComparisonCase {
232 bool operator<(ValueEqualityComparisonCase RHS)
const {
240class SimplifyCFGOpt {
250 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
251 bool SimplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
254 bool PerformValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
257 bool FoldValueComparisonIntoPredecessors(
Instruction *TI,
271 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
293 "SimplifyCFG is not yet capable of maintaining validity of a "
294 "PostDomTree, so don't ask for it.");
301 bool requestResimplify() {
320 "Only for a pair of incoming blocks at the time!");
326 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
327 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
330 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
331 EquivalenceSet->contains(IV1))
354 if (!SI1Succs.
count(Succ))
360 FailBlocks->insert(Succ);
376 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
378 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
379 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
388 assert((!isa<Instruction>(
I) ||
390 "Instruction is not safe to speculatively execute!");
416 unsigned Depth = 0) {
445 if (AggressiveInsts.
count(
I))
469 for (
Use &Op :
I->operands())
483 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
484 DL.isNonIntegralPointerType(V->getType()))
489 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
492 if (isa<ConstantPointerNull>(V))
497 if (CE->getOpcode() == Instruction::IntToPtr)
498 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
503 return cast<ConstantInt>(
521struct ConstantComparesGatherer {
525 Value *CompValue =
nullptr;
528 Value *Extra =
nullptr;
534 unsigned UsedICmps = 0;
541 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
542 ConstantComparesGatherer &
543 operator=(
const ConstantComparesGatherer &) =
delete;
548 bool setValueOnce(
Value *NewVal) {
549 if (CompValue && CompValue != NewVal)
552 return (CompValue !=
nullptr);
566 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
577 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
621 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
623 if (!setValueOnce(RHSVal))
629 C->getValue() | Mask));
644 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
646 if (!setValueOnce(RHSVal))
651 C->getValue() & ~Mask));
672 Value *CandidateVal =
I->getOperand(0);
675 CandidateVal = RHSVal;
690 if (!setValueOnce(CandidateVal))
706 void gather(
Value *V) {
717 while (!DFT.
empty()) {
725 if (Visited.
insert(Op1).second)
727 if (Visited.
insert(Op0).second)
734 if (matchInstruction(
I, isEQ))
759 Cond = dyn_cast<Instruction>(
SI->getCondition());
760 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
761 if (BI->isConditional())
762 Cond = dyn_cast<Instruction>(BI->getCondition());
764 Cond = dyn_cast<Instruction>(IBI->getAddress());
776 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
779 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
780 CV =
SI->getCondition();
781 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
782 if (BI->isConditional() && BI->getCondition()->hasOneUse())
783 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
791 Value *
Ptr = PTII->getPointerOperand();
792 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
801BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
802 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
803 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
804 Cases.reserve(
SI->getNumCases());
805 for (
auto Case :
SI->cases())
806 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
807 Case.getCaseSuccessor()));
808 return SI->getDefaultDest();
814 Cases.push_back(ValueEqualityComparisonCase(
823 std::vector<ValueEqualityComparisonCase> &Cases) {
829 std::vector<ValueEqualityComparisonCase> &C2) {
830 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
833 if (V1->size() > V2->size())
838 if (V1->size() == 1) {
841 for (
const ValueEqualityComparisonCase &VECC : *V2)
842 if (TheVal == VECC.
Value)
849 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
850 while (i1 != e1 && i2 != e2) {
869 SI->setMetadata(LLVMContext::MD_prof,
N);
876 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
880 if (TrueWeight || FalseWeight)
883 I->setMetadata(LLVMContext::MD_prof,
N);
891bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
897 Value *ThisVal = isValueEqualityComparison(TI);
898 assert(ThisVal &&
"This isn't a value comparison!!");
899 if (ThisVal != PredVal)
906 std::vector<ValueEqualityComparisonCase> PredCases;
908 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
912 std::vector<ValueEqualityComparisonCase> ThisCases;
913 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
925 if (isa<BranchInst>(TI)) {
928 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
934 ThisCases[0].Dest->removePredecessor(PredDef);
937 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
944 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
952 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
956 <<
"Through successor TI: " << *TI);
964 if (DeadCases.
count(i->getCaseValue())) {
973 std::vector<DominatorTree::UpdateType> Updates;
974 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
976 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
977 DTU->applyUpdates(Updates);
988 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
989 if (PredCases[i].Dest == TIBB) {
992 TIV = PredCases[i].
Value;
994 assert(TIV &&
"No edge from pred to succ?");
999 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1000 if (ThisCases[i].
Value == TIV) {
1001 TheRealDest = ThisCases[i].Dest;
1007 TheRealDest = ThisDef;
1014 if (Succ != CheckEdge) {
1015 if (Succ != TheRealDest)
1016 RemovedSuccs.
insert(Succ);
1019 CheckEdge =
nullptr;
1026 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1033 for (
auto *RemovedSucc : RemovedSuccs)
1034 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1035 DTU->applyUpdates(Updates);
1045struct ConstantIntOrdering {
1047 return LHS->getValue().ult(
RHS->getValue());
1059 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1077 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1088 if (Max > UINT_MAX) {
1103 if (isa<DbgInfoIntrinsic>(BonusInst) || BonusInst.isTerminator())
1118 VMap[&BonusInst] = NewBonusInst;
1129 LLVMContext::MD_annotation);
1132 NewBonusInst->
takeName(&BonusInst);
1133 BonusInst.setName(NewBonusInst->
getName() +
".old");
1139 auto *UI = cast<Instruction>(U.getUser());
1140 auto *PN = dyn_cast<PHINode>(UI);
1142 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1143 "If the user is not a PHI node, then it should be in the same "
1144 "block as, and come after, the original bonus instruction.");
1148 if (PN->getIncomingBlock(U) == BB)
1152 assert(PN->getIncomingBlock(U) == PredBlock &&
1153 "Not in block-closed SSA form?");
1154 U.set(NewBonusInst);
1159bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1167 std::vector<ValueEqualityComparisonCase> BBCases;
1168 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1170 std::vector<ValueEqualityComparisonCase> PredCases;
1171 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1183 if (PredHasWeights) {
1186 if (Weights.
size() != 1 + PredCases.size())
1187 PredHasWeights = SuccHasWeights =
false;
1188 }
else if (SuccHasWeights)
1192 Weights.
assign(1 + PredCases.size(), 1);
1195 if (SuccHasWeights) {
1198 if (SuccWeights.
size() != 1 + BBCases.size())
1199 PredHasWeights = SuccHasWeights =
false;
1200 }
else if (PredHasWeights)
1201 SuccWeights.
assign(1 + BBCases.size(), 1);
1203 if (PredDefault == BB) {
1206 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1207 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1208 if (PredCases[i].Dest != BB)
1209 PTIHandled.insert(PredCases[i].
Value);
1212 std::swap(PredCases[i], PredCases.back());
1214 if (PredHasWeights || SuccHasWeights) {
1216 Weights[0] += Weights[i + 1];
1221 PredCases.pop_back();
1227 if (PredDefault != BBDefault) {
1229 if (DTU && PredDefault != BB)
1230 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1231 PredDefault = BBDefault;
1232 ++NewSuccessors[BBDefault];
1235 unsigned CasesFromPred = Weights.
size();
1237 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1238 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1239 PredCases.push_back(BBCases[i]);
1240 ++NewSuccessors[BBCases[i].Dest];
1241 if (SuccHasWeights || PredHasWeights) {
1245 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1246 ValidTotalSuccWeight += SuccWeights[i + 1];
1250 if (SuccHasWeights || PredHasWeights) {
1251 ValidTotalSuccWeight += SuccWeights[0];
1253 for (
unsigned i = 1; i < CasesFromPred; ++i)
1254 Weights[i] *= ValidTotalSuccWeight;
1256 Weights[0] *= SuccWeights[0];
1262 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1263 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1264 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1265 if (PredCases[i].Dest == BB) {
1268 if (PredHasWeights || SuccHasWeights) {
1269 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1274 std::swap(PredCases[i], PredCases.back());
1275 PredCases.pop_back();
1282 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1283 if (PTIHandled.count(BBCases[i].Value)) {
1285 if (PredHasWeights || SuccHasWeights)
1287 PredCases.push_back(BBCases[i]);
1288 ++NewSuccessors[BBCases[i].Dest];
1295 if (PredHasWeights || SuccHasWeights)
1297 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1298 ++NewSuccessors[BBDefault];
1310 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1312 for (
auto I :
seq(0, NewSuccessor.second)) {
1316 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1317 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1330 for (ValueEqualityComparisonCase &V : PredCases)
1333 if (PredHasWeights || SuccHasWeights) {
1350 if (!InfLoopBlock) {
1358 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1365 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1367 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1369 DTU->applyUpdates(Updates);
1372 ++NumFoldValueComparisonIntoPredecessors;
1380bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1383 Value *CV = isValueEqualityComparison(TI);
1384 assert(CV &&
"Not a comparison?");
1386 bool Changed =
false;
1389 while (!Preds.empty()) {
1398 Value *PCV = isValueEqualityComparison(PTI);
1404 for (
auto *Succ : FailBlocks) {
1410 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1423 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1424 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1425 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1444 if (
I->mayReadFromMemory())
1448 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1465 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects()))
1475 if (
auto *CB = dyn_cast<CallBase>(
I))
1476 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1482 for (
Value *Op :
I->operands()) {
1483 if (
auto *J = dyn_cast<Instruction>(Op))
1484 if (J->getParent() == BB)
1498bool SimplifyCFGOpt::HoistThenElseCodeToIf(
BranchInst *BI,
1524 while (isa<DbgInfoIntrinsic>(I1))
1526 while (isa<DbgInfoIntrinsic>(I2))
1529 if (isa<PHINode>(I1))
1534 bool Changed =
false;
1538 ++NumHoistCommonCode;
1547 if (!I1NonDbg->isIdenticalToWhenDefined(I2NonDbg))
1549 if (!I1NonDbg->isTerminator())
1558 unsigned NumSkipped = 0;
1562 unsigned SkipFlagsBB1 = 0;
1563 unsigned SkipFlagsBB2 = 0;
1568 if (
I1->isTerminator() || I2->isTerminator()) {
1570 if (NumSkipped || !
I1->isIdenticalToWhenDefined(I2))
1572 goto HoistTerminator;
1575 if (
I1->isIdenticalToWhenDefined(I2)) {
1589 auto *C1 = dyn_cast<CallInst>(I1);
1590 auto *C2 = dyn_cast<CallInst>(I2);
1592 if (C1->isMustTailCall() != C2->isMustTailCall())
1600 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1601 if (CB1->cannotMerge() || CB1->isConvergent())
1603 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1604 if (CB2->cannotMerge() || CB2->isConvergent())
1607 if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
1608 assert(isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2));
1619 if (!I2->use_empty())
1620 I2->replaceAllUsesWith(I1);
1626 I1->applyMergedLocation(
I1->getDebugLoc(), I2->getDebugLoc());
1628 I2->eraseFromParent();
1631 ++NumHoistCommonInstrs;
1649 while (isa<DbgInfoIntrinsic>(I1))
1651 while (isa<DbgInfoIntrinsic>(I2))
1665 if (isa<CallBrInst>(I1))
1670 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1671 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1686 if (!
NT->getType()->isVoidTy()) {
1687 I1->replaceAllUsesWith(NT);
1688 I2->replaceAllUsesWith(NT);
1692 ++NumHoistCommonInstrs;
1696 NT->applyMergedLocation(
I1->getDebugLoc(), I2->getDebugLoc());
1705 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1708 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1709 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1715 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1719 if (isa<FPMathOperator>(PN))
1720 Builder.setFastMathFlags(PN.getFastMathFlags());
1722 SI = cast<SelectInst>(
1728 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1729 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1730 PN.setIncomingValue(i, SI);
1740 Updates.
push_back({DominatorTree::Insert, BIParent, Succ});
1745 Updates.
push_back({DominatorTree::Delete, BIParent, Succ});
1749 DTU->applyUpdates(Updates);
1755 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1756 switch (II->getIntrinsicID()) {
1759 case Intrinsic::lifetime_start:
1760 case Intrinsic::lifetime_end:
1771 return !isa<IntrinsicInst>(
I);
1785 bool HasUse = !Insts.
front()->user_empty();
1786 for (
auto *
I : Insts) {
1788 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1789 I->getType()->isTokenTy())
1794 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1801 if (
const auto *
C = dyn_cast<CallBase>(
I))
1802 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1806 if (HasUse && !
I->hasOneUse())
1808 if (!HasUse && !
I->user_empty())
1813 for (
auto *
I : Insts)
1814 if (!
I->isSameOperationAs(I0))
1822 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1825 auto *U = cast<Instruction>(*
I->user_begin());
1827 PNUse->getParent() == Succ &&
1828 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
1829 U->getParent() ==
I->getParent();
1844 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
1848 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
1852 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
1860 if (isa<CallBase>(I0)) {
1862 return cast<CallBase>(
I)->isIndirectCall();
1864 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
1865 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
1866 if (HaveIndirectCalls) {
1867 if (!AllCallsAreIndirect)
1873 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
1876 else if (
Callee != CurrCallee)
1882 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
1884 if (Op->getType()->isTokenTy())
1892 if (!
all_of(Insts, SameAsI0)) {
1897 for (
auto *
I : Insts)
1898 PHIOperands[
I].push_back(
I->getOperand(OI));
1908 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
1913 for (
auto *BB : Blocks) {
1916 I =
I->getPrevNode();
1917 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
1918 if (!isa<DbgInfoIntrinsic>(
I))
1928 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1930 auto *U = cast<Instruction>(*
I->user_begin());
1956 assert(!Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
1958 Op->getName() +
".sink", &BBEnd->front());
1959 for (
auto *
I : Insts)
1960 PN->addIncoming(
I->getOperand(O),
I->getParent());
1968 I0->
moveBefore(&*BBEnd->getFirstInsertionPt());
1971 for (
auto *
I : Insts)
1990 PN->replaceAllUsesWith(I0);
1991 PN->eraseFromParent();
1995 for (
auto *
I : Insts) {
2000 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2001 I->replaceAllUsesWith(I0);
2002 I->eraseFromParent();
2018 class LockstepReverseIterator {
2031 for (
auto *BB : Blocks) {
2033 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2051 for (
auto *&Inst : Insts) {
2052 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2065 for (
auto *&Inst : Insts) {
2066 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2129 bool HaveNonUnconditionalPredecessors =
false;
2131 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2132 if (PredBr && PredBr->isUnconditional())
2135 HaveNonUnconditionalPredecessors =
true;
2137 if (UnconditionalPreds.
size() < 2)
2149 LockstepReverseIterator LRI(UnconditionalPreds);
2150 while (LRI.isValid() &&
2152 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2154 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2165 if (!followedByDeoptOrUnreachable) {
2169 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2170 unsigned NumPHIdValues = 0;
2171 for (
auto *
I : *LRI)
2172 for (
auto *V : PHIOperands[
I]) {
2173 if (!InstructionsToSink.
contains(V))
2179 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2180 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.
size();
2181 if ((NumPHIdValues % UnconditionalPreds.
size()) != 0)
2184 return NumPHIInsts <= 1;
2201 while (
Idx < ScanIdx) {
2202 if (!ProfitableToSinkInstruction(LRI)) {
2205 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2208 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2218 if (
Idx < ScanIdx) {
2221 InstructionsToSink = InstructionsProfitableToSink;
2227 !ProfitableToSinkInstruction(LRI) &&
2228 "We already know that the last instruction is unprofitable to sink");
2236 for (
auto *
I : *LRI)
2237 InstructionsProfitableToSink.
erase(
I);
2238 if (!ProfitableToSinkInstruction(LRI)) {
2241 InstructionsToSink = InstructionsProfitableToSink;
2253 bool Changed =
false;
2255 if (HaveNonUnconditionalPredecessors) {
2256 if (!followedByDeoptOrUnreachable) {
2264 bool Profitable =
false;
2265 while (
Idx < ScanIdx) {
2299 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2301 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2311 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2315 NumSinkCommonInstrs++;
2319 ++NumSinkCommonCode;
2325struct CompatibleSets {
2343 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2352 getCompatibleSet(II).emplace_back(II);
2356 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2362 if (
any_of(Invokes, IsIllegalToMerge))
2368 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2369 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2370 if (HaveIndirectCalls) {
2371 if (!AllCallsAreIndirect)
2378 assert(CurrCallee &&
"There is always a called operand.");
2381 else if (
Callee != CurrCallee)
2391 if (
any_of(Invokes, HasNormalDest)) {
2394 if (!
all_of(Invokes, HasNormalDest))
2401 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2403 NormalBB = CurrNormalBB;
2404 else if (NormalBB != CurrNormalBB)
2412 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2423 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2425 UnwindBB = CurrUnwindBB;
2427 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2434 Invokes.front()->getUnwindDest(),
2435 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2441 for (
auto *II : Invokes.drop_front())
2446 auto IsIllegalToMergeArguments = [](
auto Ops) {
2447 Use &U0 = std::get<0>(Ops);
2448 Use &U1 = std::get<1>(Ops);
2455 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2456 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2457 IsIllegalToMergeArguments))
2469 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2475 bool HasNormalDest =
2476 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2480 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2489 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2491 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2493 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2495 if (!HasNormalDest) {
2499 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2506 return MergedInvoke;
2520 SuccBBOfMergedInvoke});
2527 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2530 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2533 for (
Use &U : MergedInvoke->operands()) {
2535 if (MergedInvoke->isCallee(&U)) {
2536 if (!IsIndirectCall)
2538 }
else if (!MergedInvoke->isDataOperand(&U))
2550 U->getType(), Invokes.size(),
"", MergedInvoke);
2562 Invokes.front()->getParent());
2570 if (!MergedDebugLoc)
2579 OrigSuccBB->removePredecessor(II->
getParent());
2585 MergedInvoke->setDebugLoc(MergedDebugLoc);
2586 ++NumInvokeSetsFormed;
2589 DTU->applyUpdates(Updates);
2616 bool Changed =
false;
2622 CompatibleSets Grouper;
2628 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2632 if (Invokes.
size() < 2)
2644class EphemeralValueTracker {
2648 if (isa<AssumeInst>(
I))
2650 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2652 return EphValues.count(cast<Instruction>(U));
2658 if (isEphemeral(
I)) {
2697 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2709 unsigned MaxNumInstToLookAt = 9;
2713 if (!MaxNumInstToLookAt)
2715 --MaxNumInstToLookAt;
2718 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2721 if (
auto *
SI = dyn_cast<StoreInst>(&CurI)) {
2725 if (
SI->getPointerOperand() == StorePtr &&
2726 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple())
2728 return SI->getValueOperand();
2732 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2733 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2757 unsigned &SpeculatedInstructions,
2765 bool HaveRewritablePHIs =
false;
2783 HaveRewritablePHIs =
true;
2786 if (!OrigCE && !ThenCE)
2793 if (OrigCost + ThenCost > MaxCost)
2800 ++SpeculatedInstructions;
2801 if (SpeculatedInstructions > 1)
2805 return HaveRewritablePHIs;
2849 if (isa<FCmpInst>(BrCond))
2859 bool Invert =
false;
2868 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
2871 (TWeight + FWeight) != 0) {
2872 uint64_t EndWeight = Invert ? TWeight : FWeight;
2876 if (BIEndProb >= Likely)
2890 unsigned SpeculatedInstructions = 0;
2891 Value *SpeculatedStoreValue =
nullptr;
2893 EphemeralValueTracker EphTracker;
2896 if (isa<DbgInfoIntrinsic>(
I)) {
2904 if (isa<PseudoProbeInst>(
I)) {
2914 if (EphTracker.track(&
I))
2919 ++SpeculatedInstructions;
2920 if (SpeculatedInstructions > 1)
2926 &
I, BB, ThenBB, EndBB))))
2928 if (!SpeculatedStoreValue &&
2934 if (SpeculatedStoreValue)
2935 SpeculatedStore = cast<StoreInst>(&
I);
2940 for (
Use &Op :
I.operands()) {
2945 ++SinkCandidateUseCounts[OpI];
2952 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
2954 ++SpeculatedInstructions;
2955 if (SpeculatedInstructions > 1)
2961 bool Convert = SpeculatedStore !=
nullptr;
2964 SpeculatedInstructions,
2966 if (!Convert || Cost > Budget)
2970 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
2973 if (SpeculatedStoreValue) {
2977 Value *FalseV = SpeculatedStoreValue;
2981 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3011 if (
any_of(DAI->location_ops(), [&](
Value *V) { return V == OrigV; }))
3012 DAI->replaceVariableLocationOp(OrigV, S);
3023 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3025 if (!isa<DbgAssignIntrinsic>(&
I))
3028 I.dropUBImplyingAttrsAndUnknownMetadata();
3031 if (EphTracker.contains(&
I)) {
3033 I.eraseFromParent();
3039 std::prev(ThenBB->
end()));
3056 Value *TrueV = ThenV, *FalseV = OrigV;
3059 Value *
V =
Builder.CreateSelect(BrCond, TrueV, FalseV,
"spec.select", BI);
3070 if (!isa<DbgAssignIntrinsic>(
I))
3071 I->eraseFromParent();
3081 EphemeralValueTracker EphTracker;
3087 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3088 if (CI->cannotDuplicate() || CI->isConvergent())
3094 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3101 for (
User *U :
I.users()) {
3103 if (UI->
getParent() != BB || isa<PHINode>(UI))
3117 auto *
I = dyn_cast<Instruction>(V);
3118 if (
I &&
I->getParent() == To)
3122 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3134static std::optional<bool>
3150 if (
auto *CB = dyn_cast<ConstantInt>(U))
3155 KnownValues[CB].
insert(Pred);
3159 if (KnownValues.
empty())
3168 for (
const auto &Pair : KnownValues) {
3186 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3189 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3197 EdgeBB->setName(RealDest->
getName() +
".critedge");
3198 EdgeBB->moveBefore(RealDest);
3208 TranslateMap[
Cond] = CB;
3210 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3217 N->setName(BBI->getName() +
".c");
3220 for (
Use &Op :
N->operands()) {
3222 if (PI != TranslateMap.
end())
3228 if (!BBI->use_empty())
3229 TranslateMap[&*BBI] = V;
3230 if (!
N->mayHaveSideEffects()) {
3235 if (!BBI->use_empty())
3236 TranslateMap[&*BBI] =
N;
3240 N->insertInto(EdgeBB, InsertPt);
3243 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3250 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3256 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3257 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3268 return std::nullopt;
3278 std::optional<bool> Result;
3279 bool EverChanged =
false;
3283 EverChanged |= Result == std::nullopt || *Result;
3284 }
while (Result == std::nullopt);
3306 if (isa<ConstantInt>(IfCond))
3313 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3316 "Will have either one or two blocks to speculate.");
3323 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3326 (TWeight + FWeight) != 0) {
3331 if (IfBlocks.
size() == 1) {
3333 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3334 if (BIBBProb >= Likely)
3337 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3345 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3346 if (IfCondPhiInst->getParent() == BB)
3354 unsigned NumPhis = 0;
3367 bool Changed =
false;
3369 PHINode *PN = cast<PHINode>(II++);
3386 PN = dyn_cast<PHINode>(BB->
begin());
3392 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3403 auto IsBinOpOrAnd = [](
Value *V) {
3423 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3436 <<
" T: " << IfTrue->
getName()
3437 <<
" F: " << IfFalse->
getName() <<
"\n");
3451 if (isa<FPMathOperator>(PN))
3458 Value *Sel =
Builder.CreateSelect(IfCond, TrueVal, FalseVal,
"", DomBI);
3471 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3489 if (Opc == Instruction::And)
3491 if (Opc == Instruction::Or)
3504 bool PredHasWeights =
3506 bool SuccHasWeights =
3508 if (PredHasWeights || SuccHasWeights) {
3509 if (!PredHasWeights)
3510 PredTrueWeight = PredFalseWeight = 1;
3511 if (!SuccHasWeights)
3512 SuccTrueWeight = SuccFalseWeight = 1;
3522static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3526 "Both blocks must end with a conditional branches.");
3528 "PredBB must be a predecessor of BB.");
3536 (PTWeight + PFWeight) != 0) {
3544 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3545 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3549 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3552 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3553 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3559 return std::nullopt;
3572 bool InvertPredCond;
3573 std::tie(CommonSucc, Opc, InvertPredCond) =
3576 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3583 {LLVMContext::MD_annotation});
3586 if (InvertPredCond) {
3588 if (NewCond->
hasOneUse() && isa<CmpInst>(NewCond)) {
3589 CmpInst *CI = cast<CmpInst>(NewCond);
3609 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3611 SuccTrueWeight, SuccFalseWeight)) {
3618 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3624 (SuccFalseWeight + SuccTrueWeight) +
3625 PredTrueWeight * SuccFalseWeight);
3631 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3632 PredFalseWeight * SuccTrueWeight);
3634 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3652 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3653 {DominatorTree::Delete, PredBlock, BB}});
3671 if (isa<DbgInfoIntrinsic>(
I)) {
3679 ++NumFoldBranchToCommonDest;
3686 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3687 return U->getType()->isVectorTy();
3697 unsigned BonusInstThreshold) {
3711 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3712 !isa<SelectInst>(
Cond)) ||
3713 Cond->getParent() != BB || !
Cond->hasOneUse())
3723 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3734 bool InvertPredCond;
3736 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3768 unsigned NumBonusInsts = 0;
3769 bool SawVectorOp =
false;
3770 const unsigned PredCount = Preds.
size();
3776 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3787 NumBonusInsts += PredCount;
3795 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3796 auto *UI = cast<Instruction>(U.getUser());
3797 if (
auto *PN = dyn_cast<PHINode>(UI))
3799 return UI->
getParent() == BB &&
I.comesBefore(UI);
3803 if (!
all_of(
I.uses(), IsBCSSAUse))
3807 BonusInstThreshold *
3813 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
3823 for (
auto *BB : {BB1, BB2}) {
3827 if (
auto *
SI = dyn_cast<StoreInst>(&
I)) {
3839 Value *AlternativeV =
nullptr) {
3857 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
3858 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
3859 PHI = cast<PHINode>(
I);
3865 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
3866 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
3874 if (!AlternativeV &&
3875 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
3879 PHI->addIncoming(V, BB);
3889 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
3898 if (!PStore || !QStore)
3919 if (
I.mayReadOrWriteMemory())
3921 for (
auto &
I : *QFB)
3922 if (&
I != QStore &&
I.mayReadOrWriteMemory())
3925 for (
auto &
I : *QTB)
3926 if (&
I != QStore &&
I.mayReadOrWriteMemory())
3930 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
3946 if (
I.isTerminator())
3950 if (
auto *S = dyn_cast<StoreInst>(&
I))
3954 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
3964 "When we run out of budget we will eagerly return from within the "
3965 "per-instruction loop.");
3969 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
3971 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
3972 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4076 bool InvertPCond =
false, InvertQCond =
false;
4082 if (QFB == PostBB) {
4101 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4104 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4112 for (
auto *BB : {PTB, PFB}) {
4117 PStoreAddresses.
insert(
SI->getPointerOperand());
4119 for (
auto *BB : {QTB, QFB}) {
4124 QStoreAddresses.
insert(
SI->getPointerOperand());
4130 auto &CommonAddresses = PStoreAddresses;
4132 bool Changed =
false;
4133 for (
auto *Address : CommonAddresses)
4136 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4156 if (!IfFalseBB->
phis().empty())
4166 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4177 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4178 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4189 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4190 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4273 unsigned NumPhis = 0;
4295 if (OtherDest == BB) {
4302 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4303 OtherDest = InfLoopBlock;
4315 PBICond =
Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4338 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4339 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4342 SuccTrueWeight, SuccFalseWeight);
4344 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4345 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4346 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4347 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4351 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4352 PredOther * SuccCommon,
4353 PredOther * SuccOther};
4375 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4382 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4383 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4384 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4385 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4388 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4389 PredOther * SuccCommon};
4411bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4422 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4429 if (Succ == KeepEdge1)
4430 KeepEdge1 =
nullptr;
4431 else if (Succ == KeepEdge2)
4432 KeepEdge2 =
nullptr;
4437 if (Succ != TrueBB && Succ != FalseBB)
4438 RemovedSuccessors.
insert(Succ);
4446 if (!KeepEdge1 && !KeepEdge2) {
4447 if (TrueBB == FalseBB) {
4455 if (TrueWeight != FalseWeight)
4458 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4480 for (
auto *RemovedSuccessor : RemovedSuccessors)
4481 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4482 DTU->applyUpdates(Updates);
4492bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4497 if (!TrueVal || !FalseVal)
4502 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4503 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4506 uint32_t TrueWeight = 0, FalseWeight = 0;
4511 if (Weights.
size() == 1 +
SI->getNumCases()) {
4513 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4515 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4520 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4529bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4542 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4563bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4583 if (
SI->getCondition() != V)
4589 if (
SI->getDefaultDest() != BB) {
4591 assert(VVal &&
"Should have a unique destination value");
4599 return requestResimplify();
4605 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4615 return requestResimplify();
4622 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4647 auto W0 = SIW.getSuccessorWeight(0);
4651 SIW.setSuccessorWeight(0, *NewW);
4653 SIW.addCase(Cst, NewBB, NewW);
4655 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4659 Builder.SetInsertPoint(NewBB);
4660 Builder.SetCurrentDebugLocation(
SI->getDebugLoc());
4664 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4665 DTU->applyUpdates(Updates);
4673bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4685 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4688 Value *CompVal = ConstantCompare.CompValue;
4689 unsigned UsedICmps = ConstantCompare.UsedICmps;
4690 Value *ExtraCase = ConstantCompare.Extra;
4709 if (ExtraCase && Values.
size() < 2)
4724 <<
" cases into SWITCH. BB is:\n"
4734 nullptr,
"switch.early.test");
4738 Builder.SetInsertPoint(OldTI);
4748 ExtraCase =
Builder.CreateFreeze(ExtraCase);
4751 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
4753 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
4758 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4764 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4765 <<
"\nEXTRABB = " << *BB);
4772 CompVal =
Builder.CreatePtrToInt(
4773 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4780 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4781 New->addCase(Values[i], EdgeBB);
4787 PHINode *PN = cast<PHINode>(BBI);
4789 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
4796 DTU->applyUpdates(Updates);
4798 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
4804 return simplifyCommonResume(RI);
4808 return simplifySingleResume(RI);
4816 auto *II = dyn_cast<IntrinsicInst>(&
I);
4821 switch (IntrinsicID) {
4822 case Intrinsic::dbg_declare:
4823 case Intrinsic::dbg_value:
4824 case Intrinsic::dbg_label:
4825 case Intrinsic::lifetime_end:
4835bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
4845 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
4848 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues();
Idx != End;
4850 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
4851 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
4855 if (IncomingBB->getUniqueSuccessor() != BB)
4858 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
4860 if (IncomingValue != LandingPad)
4864 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
4865 TrivialUnwindBlocks.
insert(IncomingBB);
4869 if (TrivialUnwindBlocks.
empty())
4873 for (
auto *TrivialBB : TrivialUnwindBlocks) {
4877 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
4891 TrivialBB->getTerminator()->eraseFromParent();
4894 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
4901 return !TrivialUnwindBlocks.empty();
4905bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
4909 "Resume must unwind the exception that caused control to here");
4913 make_range<Instruction *>(LPInst->getNextNode(), RI)))
4949 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
4966 int Idx = DestPN.getBasicBlockIndex(BB);
4980 Value *SrcVal = DestPN.getIncomingValue(
Idx);
4981 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
4983 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
4987 DestPN.addIncoming(Incoming, Pred);
5014 std::vector<DominatorTree::UpdateType> Updates;
5018 if (UnwindDest ==
nullptr) {
5030 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5031 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5058 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5059 if (!SuccessorCleanupPad)
5068 SuccessorCleanupPad->eraseFromParent();
5097 bool Changed =
false;
5117 BBI->eraseFromParent();
5123 if (&BB->
front() != UI)
5126 std::vector<DominatorTree::UpdateType> Updates;
5129 for (
unsigned i = 0, e = Preds.size(); i != e; ++i) {
5130 auto *Predecessor = Preds[i];
5133 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5137 [BB](
auto *
Successor) { return Successor == BB; })) {
5145 "The destinations are guaranteed to be different here.");