89 using namespace PatternMatch;
91 #define DEBUG_TYPE "simplifycfg"
94 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
96 cl::desc(
"Temorary development switch used to gradually uplift SimplifyCFG "
97 "into preserving DomTree,"));
106 "Control the amount of phi node folding to perform (default = 2)"));
110 cl::desc(
"Control the maximal total instruction cost that we are willing "
111 "to speculatively execute to fold a 2-entry PHI node into a "
112 "select (default = 4)"));
116 cl::desc(
"Hoist common instructions up to the parent block"));
120 cl::desc(
"Sink common instructions down to the end block"));
124 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
128 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
129 "precede - hoist multiple conditional stores into a single "
130 "predicated store"));
134 cl::desc(
"When merging conditional stores, do so even if the resultant "
135 "basic blocks are unlikely to be if-converted as a result"));
139 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
144 cl::desc(
"Limit maximum recursion depth when calculating costs of "
145 "speculatively executed instructions"));
150 cl::desc(
"Max size of a block which is still considered "
151 "small enough to thread through"));
157 cl::desc(
"Maximum cost of combining conditions when "
158 "folding branches"));
161 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
163 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
164 "to fold branch to common destination when vector operations are "
169 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
173 cl::desc(
"Limit cases to analyze when converting a switch to select"));
175 STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
177 "Number of switch instructions turned into linear mapping");
179 "Number of switch instructions turned into lookup tables");
181 NumLookupTablesHoles,
182 "Number of switch instructions turned into lookup tables (holes checked)");
183 STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
184 STATISTIC(NumFoldValueComparisonIntoPredecessors,
185 "Number of value comparisons folded into predecessor basic blocks");
187 "Number of branches folded into predecessor basic block");
190 "Number of common instruction 'blocks' hoisted up to the begin block");
192 "Number of common instructions hoisted up to the begin block");
194 "Number of common instruction 'blocks' sunk down to the end block");
196 "Number of common instructions sunk down to the end block");
197 STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
199 "Number of invokes with empty resume blocks simplified into calls");
200 STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
201 STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
208 using SwitchCaseResultVectorTy =
217 struct ValueEqualityComparisonCase {
232 class SimplifyCFGOpt {
242 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
243 bool SimplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
246 bool PerformValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
249 bool FoldValueComparisonIntoPredecessors(
Instruction *TI,
263 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
285 "SimplifyCFG is not yet capable of maintaining validity of a "
286 "PostDomTree, so don't ask for it.");
293 bool requestResimplify() {
312 "Only for a pair of incoming blocks at the time!");
317 return all_of(
BB->phis(), [IncomingBlocks, EquivalenceSet](
PHINode &PN) {
318 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
319 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
322 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
323 EquivalenceSet->contains(IV1))
346 if (!SI1Succs.
count(Succ))
352 FailBlocks->insert(Succ);
368 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
370 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
371 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
381 "Instruction is not safe to speculatively execute!");
387 if (
auto *
C = dyn_cast<Constant>(V))
414 unsigned Depth = 0) {
443 if (AggressiveInsts.
count(
I))
467 for (
Use &
Op :
I->operands())
489 if (isa<ConstantPointerNull>(V))
494 if (CE->getOpcode() == Instruction::IntToPtr)
495 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
500 return cast<ConstantInt>(
518 struct ConstantComparesGatherer {
522 Value *CompValue =
nullptr;
525 Value *Extra =
nullptr;
531 unsigned UsedICmps = 0;
538 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
539 ConstantComparesGatherer &
540 operator=(
const ConstantComparesGatherer &) =
delete;
545 bool setValueOnce(
Value *NewVal) {
546 if (CompValue && CompValue != NewVal)
549 return (CompValue !=
nullptr);
563 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
618 if (
Mask.isPowerOf2() && (
C->getValue() & ~
Mask) ==
C->getValue()) {
620 if (!setValueOnce(RHSVal))
626 C->getValue() |
Mask));
641 if (
Mask.isPowerOf2() && (
C->getValue() |
Mask) ==
C->getValue()) {
643 if (!setValueOnce(RHSVal))
648 C->getValue() & ~
Mask));
669 Value *CandidateVal =
I->getOperand(0);
672 CandidateVal = RHSVal;
687 if (!setValueOnce(CandidateVal))
703 void gather(
Value *V) {
714 while (!DFT.empty()) {
722 if (Visited.
insert(Op1).second)
724 if (Visited.
insert(Op0).second)
731 if (matchInstruction(
I, isEQ))
756 Cond = dyn_cast<Instruction>(
SI->getCondition());
757 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
758 if (BI->isConditional())
759 Cond = dyn_cast<Instruction>(BI->getCondition());
761 Cond = dyn_cast<Instruction>(IBI->getAddress());
776 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
777 CV =
SI->getCondition();
778 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
779 if (BI->isConditional() && BI->getCondition()->hasOneUse())
780 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
788 Value *Ptr = PTII->getPointerOperand();
789 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
798 BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
799 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
801 Cases.reserve(
SI->getNumCases());
802 for (
auto Case :
SI->cases())
803 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
804 Case.getCaseSuccessor()));
805 return SI->getDefaultDest();
811 Cases.push_back(ValueEqualityComparisonCase(
820 std::vector<ValueEqualityComparisonCase> &Cases) {
826 std::vector<ValueEqualityComparisonCase> &C2) {
827 std::vector<ValueEqualityComparisonCase> *V1 = &
C1, *
V2 = &C2;
830 if (V1->size() >
V2->size())
835 if (V1->size() == 1) {
838 for (
unsigned i = 0,
e =
V2->size();
i !=
e; ++
i)
846 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 =
V2->size();
847 while (
i1 != e1 && i2 != e2) {
866 SI->setMetadata(LLVMContext::MD_prof,
N);
873 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
877 if (TrueWeight || FalseWeight)
880 I->setMetadata(LLVMContext::MD_prof,
N);
888 bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
894 Value *ThisVal = isValueEqualityComparison(TI);
895 assert(ThisVal &&
"This isn't a value comparison!!");
896 if (ThisVal != PredVal)
903 std::vector<ValueEqualityComparisonCase> PredCases;
905 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
909 std::vector<ValueEqualityComparisonCase> ThisCases;
910 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
922 if (isa<BranchInst>(TI)) {
925 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
931 ThisCases[0].Dest->removePredecessor(PredDef);
934 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
949 for (
unsigned i = 0,
e = PredCases.size();
i !=
e; ++
i)
953 <<
"Through successor TI: " << *TI);
961 if (DeadCases.
count(
i->getCaseValue())) {
970 std::vector<DominatorTree::UpdateType> Updates;
971 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
974 DTU->applyUpdates(Updates);
985 for (
unsigned i = 0,
e = PredCases.size();
i !=
e; ++
i)
986 if (PredCases[
i].Dest == TIBB) {
991 assert(TIV &&
"No edge from pred to succ?");
996 for (
unsigned i = 0,
e = ThisCases.size();
i !=
e; ++
i)
997 if (ThisCases[
i].
Value == TIV) {
998 TheRealDest = ThisCases[
i].Dest;
1004 TheRealDest = ThisDef;
1011 if (Succ != CheckEdge) {
1012 if (Succ != TheRealDest)
1013 RemovedSuccs.
insert(Succ);
1016 CheckEdge =
nullptr;
1023 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1030 for (
auto *RemovedSucc : RemovedSuccs)
1032 DTU->applyUpdates(Updates);
1042 struct ConstantIntOrdering {
1044 return LHS->getValue().ult(
RHS->getValue());
1056 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1060 MDNode *ProfMD =
I->getMetadata(LLVMContext::MD_prof);
1063 return MDS->getString().equals(
"branch_weights");
1083 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1084 assert(Weights.size() == 2);
1087 std::swap(Weights.front(), Weights.back());
1094 if (Max > UINT_MAX) {
1109 if (isa<DbgInfoIntrinsic>(BonusInst) || BonusInst.isTerminator())
1124 VMap[&BonusInst] = NewBonusInst;
1135 LLVMContext::MD_annotation);
1138 NewBonusInst->
takeName(&BonusInst);
1139 BonusInst.setName(NewBonusInst->
getName() +
".old");
1145 auto *UI = cast<Instruction>(U.getUser());
1146 auto *PN = dyn_cast<PHINode>(UI);
1148 assert(UI->getParent() ==
BB && BonusInst.comesBefore(UI) &&
1149 "If the user is not a PHI node, then it should be in the same "
1150 "block as, and come after, the original bonus instruction.");
1154 if (PN->getIncomingBlock(U) ==
BB)
1158 assert(PN->getIncomingBlock(U) == PredBlock &&
1159 "Not in block-closed SSA form?");
1160 U.set(NewBonusInst);
1165 bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1173 std::vector<ValueEqualityComparisonCase> BBCases;
1174 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1176 std::vector<ValueEqualityComparisonCase> PredCases;
1177 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1189 if (PredHasWeights) {
1192 if (Weights.size() != 1 + PredCases.size())
1193 PredHasWeights = SuccHasWeights =
false;
1194 }
else if (SuccHasWeights)
1198 Weights.
assign(1 + PredCases.size(), 1);
1201 if (SuccHasWeights) {
1204 if (SuccWeights.size() != 1 + BBCases.size())
1205 PredHasWeights = SuccHasWeights =
false;
1206 }
else if (PredHasWeights)
1207 SuccWeights.
assign(1 + BBCases.size(), 1);
1209 if (PredDefault ==
BB) {
1212 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1213 for (
unsigned i = 0,
e = PredCases.size();
i !=
e; ++
i)
1214 if (PredCases[
i].Dest !=
BB)
1215 PTIHandled.insert(PredCases[
i].
Value);
1220 if (PredHasWeights || SuccHasWeights) {
1222 Weights[0] += Weights[
i + 1];
1227 PredCases.pop_back();
1233 if (PredDefault != BBDefault) {
1235 if (DTU && PredDefault !=
BB)
1237 PredDefault = BBDefault;
1238 ++NewSuccessors[BBDefault];
1241 unsigned CasesFromPred = Weights.size();
1243 for (
unsigned i = 0,
e = BBCases.size();
i !=
e; ++
i)
1244 if (!PTIHandled.count(BBCases[
i].Value) && BBCases[
i].Dest != BBDefault) {
1245 PredCases.push_back(BBCases[
i]);
1246 ++NewSuccessors[BBCases[
i].Dest];
1247 if (SuccHasWeights || PredHasWeights) {
1251 Weights.push_back(Weights[0] * SuccWeights[
i + 1]);
1252 ValidTotalSuccWeight += SuccWeights[
i + 1];
1256 if (SuccHasWeights || PredHasWeights) {
1257 ValidTotalSuccWeight += SuccWeights[0];
1259 for (
unsigned i = 1;
i < CasesFromPred; ++
i)
1260 Weights[
i] *= ValidTotalSuccWeight;
1262 Weights[0] *= SuccWeights[0];
1268 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1269 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1270 for (
unsigned i = 0,
e = PredCases.size();
i !=
e; ++
i)
1271 if (PredCases[
i].Dest ==
BB) {
1274 if (PredHasWeights || SuccHasWeights) {
1275 WeightsForHandled[PredCases[
i].Value] = Weights[
i + 1];
1281 PredCases.pop_back();
1288 for (
unsigned i = 0,
e = BBCases.size();
i !=
e; ++
i)
1289 if (PTIHandled.count(BBCases[
i].Value)) {
1291 if (PredHasWeights || SuccHasWeights)
1292 Weights.push_back(WeightsForHandled[BBCases[
i].
Value]);
1293 PredCases.push_back(BBCases[
i]);
1294 ++NewSuccessors[BBCases[
i].Dest];
1301 if (PredHasWeights || SuccHasWeights)
1302 Weights.push_back(WeightsForHandled[
I]);
1303 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1304 ++NewSuccessors[BBDefault];
1314 Updates.
reserve(Updates.size() + NewSuccessors.
size());
1316 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1318 for (
auto I :
seq(0, NewSuccessor.second)) {
1322 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1336 for (ValueEqualityComparisonCase &V : PredCases)
1339 if (PredHasWeights || SuccHasWeights) {
1356 if (!InfLoopBlock) {
1375 DTU->applyUpdates(Updates);
1378 ++NumFoldValueComparisonIntoPredecessors;
1386 bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1389 Value *CV = isValueEqualityComparison(TI);
1390 assert(CV &&
"Not a comparison?");
1392 bool Changed =
false;
1395 while (!Preds.empty()) {
1404 Value *PCV = isValueEqualityComparison(PTI);
1410 for (
auto *Succ : FailBlocks) {
1416 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI,
Builder);
1429 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1430 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1431 if (BB1V != BB2V && (BB1V ==
I1 || BB2V == I2)) {
1446 bool SimplifyCFGOpt::HoistThenElseCodeToIf(
BranchInst *BI,
1471 while (isa<DbgInfoIntrinsic>(
I1))
1473 while (isa<DbgInfoIntrinsic>(I2))
1477 if (isa<PHINode>(
I1) || !
I1->isIdenticalToWhenDefined(I2) ||
1479 isa<CallBrInst>(
I1))
1484 bool Changed =
false;
1488 ++NumHoistCommonCode;
1497 if (!I1NonDbg->isIdenticalToWhenDefined(I2NonDbg))
1499 if (!I1NonDbg->isTerminator())
1508 if (
I1->isTerminator())
1509 goto HoistTerminator;
1516 auto *
C1 = dyn_cast<CallInst>(
I1);
1517 auto *C2 = dyn_cast<CallInst>(I2);
1519 if (
C1->isMustTailCall() != C2->isMustTailCall())
1526 if (
const auto *CB1 = dyn_cast<CallBase>(
I1))
1527 if (CB1->cannotMerge())
1529 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1530 if (CB2->cannotMerge())
1533 if (isa<DbgInfoIntrinsic>(
I1) || isa<DbgInfoIntrinsic>(I2)) {
1534 assert (isa<DbgInfoIntrinsic>(
I1) && isa<DbgInfoIntrinsic>(I2));
1549 if (!I2->use_empty())
1550 I2->replaceAllUsesWith(
I1);
1552 unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
1553 LLVMContext::MD_range,
1554 LLVMContext::MD_fpmath,
1555 LLVMContext::MD_invariant_load,
1556 LLVMContext::MD_nonnull,
1557 LLVMContext::MD_invariant_group,
1558 LLVMContext::MD_align,
1559 LLVMContext::MD_dereferenceable,
1560 LLVMContext::MD_dereferenceable_or_null,
1561 LLVMContext::MD_mem_parallel_loop_access,
1562 LLVMContext::MD_access_group,
1563 LLVMContext::MD_preserve_access_index};
1568 I1->applyMergedLocation(
I1->getDebugLoc(), I2->getDebugLoc());
1570 I2->eraseFromParent();
1573 ++NumHoistCommonInstrs;
1581 while (isa<DbgInfoIntrinsic>(
I1))
1583 while (isa<DbgInfoIntrinsic>(I2))
1586 }
while (
I1->isIdenticalToWhenDefined(I2));
1597 if (isa<CallBrInst>(
I1))
1602 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1603 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1623 if (!
NT->getType()->isVoidTy()) {
1624 I1->replaceAllUsesWith(
NT);
1625 I2->replaceAllUsesWith(
NT);
1629 ++NumHoistCommonInstrs;
1633 NT->applyMergedLocation(
I1->getDebugLoc(), I2->getDebugLoc());
1642 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1645 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1646 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1652 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1656 if (isa<FPMathOperator>(PN))
1657 Builder.setFastMathFlags(PN.getFastMathFlags());
1659 SI = cast<SelectInst>(
1665 for (
unsigned i = 0,
e = PN.getNumIncomingValues();
i !=
e; ++
i)
1666 if (PN.getIncomingBlock(
i) == BB1 || PN.getIncomingBlock(
i) == BB2)
1667 PN.setIncomingValue(
i,
SI);
1686 DTU->applyUpdates(Updates);
1692 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1693 switch (II->getIntrinsicID()) {
1696 case Intrinsic::lifetime_start:
1697 case Intrinsic::lifetime_end:
1708 return !isa<IntrinsicInst>(
I);
1723 for (
auto *
I : Insts) {
1725 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1726 I->getType()->isTokenTy())
1731 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1738 if (
const auto *
C = dyn_cast<CallBase>(
I))
1739 if (
C->isInlineAsm() ||
C->cannotMerge())
1743 if (HasUse && !
I->hasOneUse())
1745 if (!HasUse && !
I->user_empty())
1750 for (
auto *
I : Insts)
1751 if (!
I->isSameOperationAs(I0))
1759 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1762 auto *U = cast<Instruction>(*
I->user_begin());
1764 PNUse->getParent() == Succ &&
1765 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
1766 U->getParent() ==
I->getParent();
1781 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
1785 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
1789 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
1797 if (isa<CallBase>(I0)) {
1799 return cast<CallBase>(
I)->isIndirectCall();
1801 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
1802 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
1803 if (HaveIndirectCalls) {
1804 if (!AllCallsAreIndirect)
1810 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
1813 else if (
Callee != CurrCallee)
1819 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
1821 if (
Op->getType()->isTokenTy())
1829 if (!
all_of(Insts, SameAsI0)) {
1834 for (
auto *
I : Insts)
1835 PHIOperands[
I].push_back(
I->getOperand(OI));
1845 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
1850 for (
auto *
BB : Blocks) {
1853 I =
I->getPrevNode();
1854 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &
BB->front());
1855 if (!isa<DbgInfoIntrinsic>(
I))
1865 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1867 auto *U = cast<Instruction>(*
I->user_begin());
1893 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
1895 Op->getName() +
".sink", &BBEnd->front());
1896 for (
auto *
I : Insts)
1897 PN->addIncoming(
I->getOperand(
O),
I->getParent());
1898 NewOperands.push_back(PN);
1905 I0->
moveBefore(&*BBEnd->getFirstInsertionPt());
1908 for (
auto *
I : Insts)
1927 PN->replaceAllUsesWith(I0);
1928 PN->eraseFromParent();
1932 for (
auto *
I : Insts)
1934 I->eraseFromParent();
1949 class LockstepReverseIterator {
1962 for (
auto *
BB : Blocks) {
1964 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1971 Insts.push_back(Inst);
1982 for (
auto *&Inst : Insts) {
1983 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1996 for (
auto *&Inst : Insts) {
1997 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2060 bool HaveNonUnconditionalPredecessors =
false;
2062 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2063 if (PredBr && PredBr->isUnconditional())
2064 UnconditionalPreds.push_back(PredBB);
2066 HaveNonUnconditionalPredecessors =
true;
2068 if (UnconditionalPreds.size() < 2)
2080 LockstepReverseIterator LRI(UnconditionalPreds);
2081 while (LRI.isValid() &&
2083 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2085 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2096 if (!followedByDeoptOrUnreachable) {
2100 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2101 unsigned NumPHIdValues = 0;
2102 for (
auto *
I : *LRI)
2103 for (
auto *V : PHIOperands[
I]) {
2104 if (!InstructionsToSink.
contains(V))
2110 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2111 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.size();
2112 if ((NumPHIdValues % UnconditionalPreds.size()) != 0)
2115 return NumPHIInsts <= 1;
2132 while (Idx < ScanIdx) {
2133 if (!ProfitableToSinkInstruction(LRI)) {
2136 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2139 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2149 if (Idx < ScanIdx) {
2152 InstructionsToSink = InstructionsProfitableToSink;
2158 !ProfitableToSinkInstruction(LRI) &&
2159 "We already know that the last instruction is unprofitable to sink");
2167 for (
auto *
I : *LRI)
2168 InstructionsProfitableToSink.
erase(
I);
2169 if (!ProfitableToSinkInstruction(LRI)) {
2172 InstructionsToSink = InstructionsProfitableToSink;
2184 bool Changed =
false;
2186 if (HaveNonUnconditionalPredecessors) {
2187 if (!followedByDeoptOrUnreachable) {
2195 bool Profitable =
false;
2196 while (Idx < ScanIdx) {
2230 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2232 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2242 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2246 NumSinkCommonInstrs++;
2250 ++NumSinkCommonCode;
2256 struct CompatibleSets {
2274 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2282 void CompatibleSets::insert(
InvokeInst *II) {
2283 getCompatibleSet(II).emplace_back(II);
2287 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2293 if (
any_of(Invokes, IsIllegalToMerge))
2299 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2300 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2301 if (HaveIndirectCalls) {
2302 if (!AllCallsAreIndirect)
2309 assert(CurrCallee &&
"There is always a called operand.");
2312 else if (Callee != CurrCallee)
2322 if (
any_of(Invokes, HasNormalDest)) {
2325 if (!
all_of(Invokes, HasNormalDest))
2332 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2334 NormalBB = CurrNormalBB;
2335 else if (NormalBB != CurrNormalBB)
2343 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2354 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2356 UnwindBB = CurrUnwindBB;
2358 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2365 Invokes.front()->getUnwindDest(),
2366 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2372 for (
auto *II : Invokes.drop_front())
2377 auto IsIllegalToMergeArguments = [](
auto Ops) {
2378 Type *Ty = std::get<0>(Ops)->getType();
2379 assert(Ty == std::get<1>(Ops)->
getType() &&
"Incompatible types?");
2380 return Ty->
isTokenTy() && std::get<0>(Ops) != std::get<1>(Ops);
2382 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2383 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2384 IsIllegalToMergeArguments))
2396 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2402 bool HasNormalDest =
2403 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2407 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2416 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2418 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2420 MergedInvokeBB->
getInstList().push_back(MergedInvoke);
2422 if (!HasNormalDest) {
2426 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2433 return MergedInvoke;
2447 SuccBBOfMergedInvoke});
2457 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2460 for (
Use &U : MergedInvoke->operands()) {
2462 if (MergedInvoke->isCallee(&U)) {
2463 if (!IsIndirectCall)
2465 }
else if (!MergedInvoke->isDataOperand(&U))
2470 return II->
getOperand(U.getOperandNo()) != U.get();
2477 U->getType(), Invokes.size(),
"", MergedInvoke);
2489 Invokes.front()->getParent());
2497 if (!MergedDebugLoc)
2506 OrigSuccBB->removePredecessor(II->
getParent());
2512 MergedInvoke->setDebugLoc(MergedDebugLoc);
2513 ++NumInvokeSetsFormed;
2516 DTU->applyUpdates(Updates);
2543 bool Changed =
false;
2546 if (!
BB->isLandingPad())
2549 CompatibleSets Grouper;
2555 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2559 if (Invokes.
size() < 2)
2596 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2608 unsigned MaxNumInstToLookAt = 9;
2612 if (!MaxNumInstToLookAt)
2614 --MaxNumInstToLookAt;
2617 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2620 if (
auto *
SI = dyn_cast<StoreInst>(&CurI)) {
2624 if (
SI->getPointerOperand() == StorePtr &&
2625 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple())
2627 return SI->getValueOperand();
2631 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2632 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2656 unsigned &SpeculatedInstructions,
2660 BB->getParent()->hasMinSize()
2661 ? TargetTransformInfo::TCK_CodeSize
2662 : TargetTransformInfo::TCK_SizeAndLatency;
2664 bool HaveRewritablePHIs =
false;
2675 CmpInst::BAD_ICMP_PREDICATE,
CostKind);
2685 HaveRewritablePHIs =
true;
2688 if (!OrigCE && !ThenCE)
2695 if (OrigCost + ThenCost > MaxCost)
2702 ++SpeculatedInstructions;
2703 if (SpeculatedInstructions > 1)
2707 return HaveRewritablePHIs;
2751 if (isa<FCmpInst>(BrCond))
2761 bool Invert =
false;
2770 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
2773 uint64_t EndWeight = Invert ? TWeight : FWeight;
2775 BranchProbability::getBranchProbability(EndWeight, TWeight + FWeight);
2777 if (BIEndProb >= Likely)
2791 unsigned SpeculatedInstructions = 0;
2792 Value *SpeculatedStoreValue =
nullptr;
2795 BBE = std::prev(ThenBB->
end());
2796 BBI != BBE; ++BBI) {
2799 if (isa<DbgInfoIntrinsic>(
I)) {
2800 SpeculatedDbgIntrinsics.push_back(
I);
2807 if (isa<PseudoProbeInst>(
I)) {
2812 SpeculatedDbgIntrinsics.push_back(
I);
2818 ++SpeculatedInstructions;
2819 if (SpeculatedInstructions > 1)
2825 I,
BB, ThenBB, EndBB))))
2827 if (!SpeculatedStoreValue &&
2833 if (SpeculatedStoreValue)
2834 SpeculatedStore = cast<StoreInst>(
I);
2839 for (
Use &
Op :
I->operands()) {
2844 ++SinkCandidateUseCounts[OpI];
2852 I = SinkCandidateUseCounts.
begin(),
2853 E = SinkCandidateUseCounts.
end();
2855 if (
I->first->hasNUses(
I->second)) {
2856 ++SpeculatedInstructions;
2857 if (SpeculatedInstructions > 1)
2863 bool Convert = SpeculatedStore !=
nullptr;
2866 SpeculatedInstructions,
2868 if (!Convert || Cost > Budget)
2872 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
2875 if (SpeculatedStoreValue) {
2878 Value *FalseV = SpeculatedStoreValue;
2882 BrCond, TrueV, FalseV,
"spec.store.select", BI);
2894 for (
auto &
I : *ThenBB) {
2895 if (!SpeculatedStoreValue || &
I != SpeculatedStore)
2897 I.dropUndefImplyingAttrsAndUnknownMetadata();
2901 BB->getInstList().splice(BI->
getIterator(), ThenBB->getInstList(),
2902 ThenBB->begin(), std::prev(ThenBB->end()));
2919 Value *TrueV = ThenV, *FalseV = OrigV;
2922 Value *V =
Builder.CreateSelect(BrCond, TrueV, FalseV,
"spec.select", BI);
2931 I->eraseFromParent();
2943 if (isa<AssumeInst>(
I))
2945 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2947 [&](
const User *U) { return EphValues.count(U); });
2954 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
2955 if (CI->cannotDuplicate() || CI->isConvergent())
2959 if (IsEphemeral(&
I))
2963 else if (!isa<PHINode>(
I)) {
2970 for (
User *U :
I.users()) {
2988 auto *
I = dyn_cast<Instruction>(V);
2989 if (
I &&
I->getParent() == To)
2993 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3000 if (Visited.
size() >= 8)
3003 auto Pair = Visited.try_emplace({
From, To},
nullptr);
3005 return Pair.first->second;
3011 if (!
C || (Common && Common !=
C))
3015 return Visited[{
From, To}] = Common;
3037 if (
auto *CB = dyn_cast<ConstantInt>(U))
3043 KnownValues.
insert({Pred, CB});
3047 if (KnownValues.
empty())
3056 for (
const auto &Pair : KnownValues) {
3076 BasicBlock::Create(
BB->getContext(), RealDest->
getName() +
".critedge",
3078 BranchInst *CritEdgeBranch = BranchInst::Create(RealDest, EdgeBB);
3091 TranslateMap[
Cond] = Pair.second;
3093 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3100 N->setName(BBI->getName() +
".c");
3103 for (
Use &
Op :
N->operands()) {
3105 if (PI != TranslateMap.
end())
3111 if (!BBI->use_empty())
3112 TranslateMap[&*BBI] = V;
3113 if (!
N->mayHaveSideEffects()) {
3118 if (!BBI->use_empty())
3119 TranslateMap[&*BBI] =
N;
3126 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3137 BB->removePredecessor(PredBB);
3143 Updates.push_back({DominatorTree::Delete, PredBB,
BB});
3166 bool EverChanged =
false;
3170 EverChanged |= Result ==
None || *Result;
3171 }
while (Result ==
None);
3193 if (isa<ConstantInt>(IfCond))
3200 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3202 assert((IfBlocks.size() == 1 || IfBlocks.size() == 2) &&
3203 "Will have either one or two blocks to speculate.");
3210 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3213 (TWeight + FWeight) != 0) {
3215 BranchProbability::getBranchProbability(TWeight, TWeight + FWeight);
3218 if (IfBlocks.size() == 1) {
3221 if (BIBBProb >= Likely)
3224 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3232 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3233 if (IfCondPhiInst->getParent() ==
BB)
3241 unsigned NumPhis = 0;
3254 bool Changed =
false;
3256 PHINode *PN = cast<PHINode>(II++);
3265 Cost, Budget,
TTI) ||
3273 PN = dyn_cast<PHINode>(
BB->begin());
3279 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3290 auto IsBinOpOrAnd = [](
Value *V) {
3310 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3323 <<
" T: " << IfTrue->
getName()
3324 <<
" F: " << IfFalse->
getName() <<
"\n");
3337 while (
PHINode *PN = dyn_cast<PHINode>(
BB->begin())) {
3338 if (isa<FPMathOperator>(PN))
3360 Updates.push_back({DominatorTree::Delete, DomBlock,
Successor});
3376 if (Opc == Instruction::And)
3378 if (Opc == Instruction::Or)
3391 bool PredHasWeights =
3393 bool SuccHasWeights =
3395 if (PredHasWeights || SuccHasWeights) {
3396 if (!PredHasWeights)
3397 PredTrueWeight = PredFalseWeight = 1;
3398 if (!SuccHasWeights)
3399 SuccTrueWeight = SuccFalseWeight = 1;
3413 "Both blocks must end with a conditional branches.");
3415 "PredBB must be a predecessor of BB.");
3423 (PTWeight + PFWeight) != 0) {
3425 BranchProbability::getBranchProbability(PTWeight, PTWeight + PFWeight);
3431 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3432 return {{Instruction::Or,
false}};
3436 return {{Instruction::And,
false}};
3439 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3440 return {{Instruction::And,
true}};
3444 return {{Instruction::Or,
true}};
3458 bool InvertPredCond;
3459 std::tie(Opc, InvertPredCond) =
3468 Builder.CollectMetadataToCopy(
BB->getTerminator(),
3469 {LLVMContext::MD_annotation});
3472 if (InvertPredCond) {
3474 if (NewCond->
hasOneUse() && isa<CmpInst>(NewCond)) {
3475 CmpInst *CI = cast<CmpInst>(NewCond);
3495 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3497 SuccTrueWeight, SuccFalseWeight)) {
3504 NewWeights.push_back(PredTrueWeight * SuccTrueWeight);
3509 NewWeights.push_back(PredFalseWeight *
3510 (SuccFalseWeight + SuccTrueWeight) +
3511 PredTrueWeight * SuccFalseWeight);
3517 NewWeights.push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3518 PredFalseWeight * SuccTrueWeight);
3520 NewWeights.push_back(PredFalseWeight * SuccFalseWeight);
3539 {DominatorTree::Delete, PredBlock,
BB}});
3557 if (isa<DbgInfoIntrinsic>(
I)) {
3565 ++NumFoldBranchToCommonDest;
3572 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3573 return U->getType()->isVectorTy();
3583 unsigned BonusInstThreshold) {
3591 BB->getParent()->hasMinSize() ? TargetTransformInfo::TCK_CodeSize
3592 : TargetTransformInfo::TCK_SizeAndLatency;
3597 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3598 !isa<SelectInst>(
Cond)) ||
3599 Cond->getParent() !=
BB || !
Cond->hasOneUse())
3616 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3626 bool InvertPredCond;
3628 std::tie(Opc, InvertPredCond) = *Recipe;
3660 unsigned NumBonusInsts = 0;
3661 bool SawVectorOp =
false;
3662 const unsigned PredCount = Preds.size();
3668 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3679 NumBonusInsts += PredCount;
3687 auto IsBCSSAUse = [
BB, &
I](
Use &U) {
3688 auto *UI = cast<Instruction>(U.getUser());
3689 if (
auto *PN = dyn_cast<PHINode>(UI))
3691 return UI->getParent() ==
BB &&
I.comesBefore(UI);
3695 if (!
all_of(
I.uses(), IsBCSSAUse))
3699 BonusInstThreshold *
3705 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
3715 for (
auto *
BB : {BB1, BB2}) {
3719 if (
auto *
SI = dyn_cast<StoreInst>(&
I)) {
3731 Value *AlternativeV =
nullptr) {
3749 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
3750 if (cast<PHINode>(
I)->getIncomingValueForBlock(
BB) == V) {
3751 PHI = cast<PHINode>(
I);
3757 BasicBlock *OtherPredBB = *PredI ==
BB ? *++PredI : *PredI;
3766 if (!AlternativeV &&
3767 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() !=
BB))
3770 PHI = PHINode::Create(V->
getType(), 2,
"simplifycfg.merge", &Succ->
front());
3781 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
3790 if (!PStore || !QStore)
3811 if (
I.mayReadOrWriteMemory())
3813 for (
auto &
I : *QFB)
3814 if (&
I != QStore &&
I.mayReadOrWriteMemory())
3817 for (
auto &
I : *QTB)
3818 if (&
I != QStore &&
I.mayReadOrWriteMemory())
3822 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
3836 for (
auto &
I :
BB->instructionsWithoutDebug(
false)) {
3838 if (
I.isTerminator())
3842 if (
auto *
S = dyn_cast<StoreInst>(&
I))
3846 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
3855 "When we run out of budget we will eagerly return from within the "
3856 "per-instruction loop.");
3860 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
3862 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
3863 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
3885 Value *QCond = cast<BranchInst>(QFB->getSinglePredecessor()->getTerminator())
3967 bool InvertPCond =
false, InvertQCond =
false;
3973 if (QFB == PostBB) {
3989 return BB->getSinglePredecessor() ==
P &&
BB->getSingleSuccessor() ==
S;
3992 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
3995 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4003 for (
auto *
BB : {PTB, PFB}) {
4008 PStoreAddresses.
insert(
SI->getPointerOperand());
4010 for (
auto *
BB : {QTB, QFB}) {
4015 QStoreAddresses.
insert(
SI->getPointerOperand());
4021 auto &CommonAddresses = PStoreAddresses;
4023 bool Changed =
false;
4024 for (
auto *Address : CommonAddresses)
4027 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4047 if (!IfFalseBB->
phis().empty())
4052 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4064 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4076 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4101 if (
BB->getSinglePredecessor()) {
4130 if (&*
BB->instructionsWithoutDebug(
false).begin() != BI)
4166 unsigned NumPhis = 0;
4172 PHINode *PN = cast<PHINode>(II);
4198 if (OtherDest ==
BB) {
4202 BasicBlock::Create(
BB->getContext(),
"infloop",
BB->getParent());
4203 BranchInst::Create(InfLoopBlock, InfLoopBlock);
4206 OtherDest = InfLoopBlock;
4218 PBICond =
Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4235 Updates.push_back({DominatorTree::Delete, PBI->
getParent(), RemovedDest});
4241 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4242 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4245 SuccTrueWeight, SuccFalseWeight);
4247 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4248 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4249 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4250 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4254 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4255 PredOther * SuccCommon,
4256 PredOther * SuccOther};
4278 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4285 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4286 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4287 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4288 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4291 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4292 PredOther * SuccCommon};
4314 bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4325 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4332 if (Succ == KeepEdge1)
4333 KeepEdge1 =
nullptr;
4334 else if (Succ == KeepEdge2)
4335 KeepEdge2 =
nullptr;
4340 if (Succ != TrueBB && Succ != FalseBB)
4341 RemovedSuccessors.
insert(Succ);
4349 if (!KeepEdge1 && !KeepEdge2) {
4350 if (TrueBB == FalseBB) {
4358 if (TrueWeight != FalseWeight)
4361 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4383 for (
auto *RemovedSuccessor : RemovedSuccessors)
4384 Updates.push_back({DominatorTree::Delete,
BB, RemovedSuccessor});
4385 DTU->applyUpdates(Updates);
4395 bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *
SI,
4409 uint32_t TrueWeight = 0, FalseWeight = 0;
4414 if (Weights.size() == 1 +
SI->getNumCases()) {
4423 return SimplifyTerminatorOnSelect(
SI, Condition, TrueBB, FalseBB, TrueWeight,
4432 bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4445 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4466 bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4472 if (isa<PHINode>(
BB->begin()) || !ICI->
hasOneUse())
4486 if (
SI->getCondition() != V)
4492 if (
SI->getDefaultDest() !=
BB) {
4494 assert(VVal &&
"Should have a unique destination value");
4502 return requestResimplify();
4508 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4518 return requestResimplify();
4523 BasicBlock *SuccBlock =
BB->getTerminator()->getSuccessor(0);
4525 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4547 BasicBlock::Create(
BB->getContext(),
"switch.edge",
BB->getParent(),
BB);
4550 auto W0 = SIW.getSuccessorWeight(0);
4554 SIW.setSuccessorWeight(0, *NewW);
4556 SIW.addCase(Cst, NewBB, NewW);
4562 Builder.SetInsertPoint(NewBB);
4563 Builder.SetCurrentDebugLocation(
SI->getDebugLoc());
4568 DTU->applyUpdates(Updates);
4576 bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4588 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4591 Value *CompVal = ConstantCompare.CompValue;
4592 unsigned UsedICmps = ConstantCompare.UsedICmps;
4593 Value *ExtraCase = ConstantCompare.Extra;
4612 if (ExtraCase && Values.size() < 2)
4626 LLVM_DEBUG(
dbgs() <<
"Converting 'icmp' chain with " << Values.size()
4627 <<
" cases into SWITCH. BB is:\n"
4637 nullptr,
"switch.early.test");
4641 Builder.SetInsertPoint(OldTI);
4651 ExtraCase =
Builder.CreateFreeze(ExtraCase);
4654 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
4656 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
4667 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4668 <<
"\nEXTRABB = " << *
BB);
4675 CompVal =
Builder.CreatePtrToInt(
4676 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4683 for (
unsigned i = 0,
e = Values.size();
i !=
e; ++
i)
4684 New->addCase(Values[
i], EdgeBB);
4690 PHINode *PN = cast<PHINode>(BBI);
4692 for (
unsigned i = 0,
e = Values.size() - 1;
i !=
e; ++
i)
4699 DTU->applyUpdates(Updates);
4707 return simplifyCommonResume(RI);
4711 return simplifySingleResume(RI);
4719 auto *II = dyn_cast<IntrinsicInst>(&
I);
4724 switch (IntrinsicID) {
4725 case Intrinsic::dbg_declare:
4726 case Intrinsic::dbg_value:
4727 case Intrinsic::dbg_label:
4728 case Intrinsic::lifetime_end:
4738 bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
4748 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
4751 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
4753 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
4754 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
4758 if (IncomingBB->getUniqueSuccessor() !=
BB)
4761 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
4763 if (IncomingValue != LandingPad)
4767 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
4768 TrivialUnwindBlocks.
insert(IncomingBB);
4772 if (TrivialUnwindBlocks.
empty())
4776 for (
auto *TrivialBB : TrivialUnwindBlocks) {
4780 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
4781 BB->removePredecessor(TrivialBB,
true);
4794 TrivialBB->getTerminator()->eraseFromParent();
4797 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB,
BB}});
4804 return !TrivialUnwindBlocks.empty();
4808 bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
4810 auto *LPInst = cast<LandingPadInst>(
BB->getFirstNonPHI());
4812 "Resume must unwind the exception that caused control to here");
4816 make_range<Instruction *>(LPInst->getNextNode(), RI)))
4852 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
4869 int Idx = DestPN.getBasicBlockIndex(
BB);
4883 Value *SrcVal = DestPN.getIncomingValue(Idx);
4884 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
4886 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() ==
BB;
4890 DestPN.addIncoming(Incoming, Pred);
4917 std::vector<DominatorTree::UpdateType> Updates;
4921 if (UnwindDest ==
nullptr) {
4929 BB->removePredecessor(PredBB);
4934 Updates.push_back({DominatorTree::Delete, PredBB,
BB});
4961 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
4962 if (!SuccessorCleanupPad)
4971 SuccessorCleanupPad->eraseFromParent();
4974 BranchInst::Create(UnwindDest, RI->
getParent());
5000 bool Changed =
false;
5020 BBI->eraseFromParent();
5026 if (&
BB->front() != UI)
5029 std::vector<DominatorTree::UpdateType> Updates;
5032 for (
unsigned i = 0,
e = Preds.size();
i !=
e; ++
i) {
5033 auto *Predecessor = Preds[
i];
5036 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5040 [
BB](
auto *
Successor) { return Successor == BB; })) {
5048 "The destinations are guaranteed to be different here.");
5061 Updates.push_back({DominatorTree::Delete, Predecessor,
BB});
5062 }
else if (
auto *
SI = dyn_cast<SwitchInst>(TI)) {
5064 for (
auto i = SU->case_begin(),
e = SU->case_end();
i !=
e;) {
5065 if (
i->getCaseSuccessor() !=
BB) {
5069 BB->removePredecessor(SU->getParent());
5070 i = SU.removeCase(
i);
5075 if (DTU &&
SI->getDefaultDest() !=
BB)
5076 Updates.push_back({DominatorTree::Delete, Predecessor,
BB});
5077 }
else if (
auto *II = dyn_cast<InvokeInst>(TI)) {
5080 DTU->applyUpdates(Updates);
5086 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5087 if (CSI->getUnwindDest() ==
BB) {
5089 DTU->applyUpdates(Updates);
5098 E = CSI->handler_end();
5101 CSI->removeHandler(
I);
5108 Updates.push_back({DominatorTree::Delete, Predecessor,
BB});
5109 if (CSI->getNumHandlers() == 0) {
5110 if (CSI->hasUnwindDest()) {
5114 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5116 PredecessorOfPredecessor,
5117 CSI->getUnwindDest()});
5118 Updates.push_back({DominatorTree::Delete,
5119 PredecessorOfPredecessor, Predecessor});
5122 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5126 DTU->applyUpdates(Updates);
5135 CSI->eraseFromParent();
5138 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5140 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() ==
BB &&
5141 "Expected to always have an unwind to BB.");
5143 Updates.push_back({DominatorTree::Delete, Predecessor,
BB});
5151 DTU->applyUpdates(Updates);
5163 assert(Cases.size() >= 1);
5166 for (
size_t I = 1,
E = Cases.size();
I !=
E; ++
I) {
5167 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5176 auto *
BB = Switch->getParent();
5177 auto *OrigDefaultBlock = Switch->getDefaultDest();
5178 OrigDefaultBlock->removePredecessor(
BB);
5179 BasicBlock *NewDefaultBlock = BasicBlock::Create(
5180 BB->getContext(),
BB->getName() +
".unreachabledefault",
BB->getParent(),
5183 Switch->setDefaultDest(&*NewDefaultBlock);
5188 Updates.push_back({DominatorTree::Delete,
BB, &*OrigDefaultBlock});
5196 bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(
SwitchInst *
SI,
5198 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5201 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5203 auto *
BB =
SI->getParent();
5206 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5211 for (
auto Case :
SI->cases()) {
5215 if (Dest == DestA) {
5216 CasesA.push_back(Case.getCaseValue());
5221 if (Dest == DestB) {
5222 CasesB.push_back(Case.getCaseValue());
5231 "Single-destination switch should have been folded.");
5233 assert(DestB !=
SI->getDefaultDest());
5234 assert(!CasesB.empty() &&
"There must be non-default cases.");
5235 assert(!CasesA.empty() || HasDefault);
5242 ContiguousCases = &CasesA;
5243 ContiguousDest = DestA;
5246 ContiguousCases = &CasesB;
5247 ContiguousDest = DestB;
5254 Constant *
Offset = ConstantExpr::getNeg(ContiguousCases->back());
5258 Value *Sub =
SI->getCondition();
5259 if (!
Offset->isNullValue())
5264 if (NumCases->
isNullValue() && !ContiguousCases->empty())
5267 Cmp =
Builder.CreateICmpULT(Sub, NumCases,
"switch");
5274 if (Weights.size() == 1 +
SI->getNumCases()) {
5277 for (
size_t I = 0,
E = Weights.size();
I !=
E; ++
I) {
5278 if (
SI->getSuccessor(
I) == ContiguousDest)
5279 TrueWeight += Weights[
I];
5281 FalseWeight += Weights[
I];
5283 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5292 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5293 unsigned PreviousEdges = ContiguousCases->size();
5294 if (ContiguousDest ==
SI->getDefaultDest())
5296 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5297 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5299 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5300 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->size();
5301 if (OtherDest ==
SI->getDefaultDest())
5303 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5304 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5312 auto *UnreachableDefault =
SI->getDefaultDest();
5315 SI->eraseFromParent();
5317 if (!HasDefault && DTU)
5318 DTU->applyUpdates({{DominatorTree::Delete,
BB, UnreachableDefault}});
5334 unsigned MaxSignificantBitsInCond =