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 Type *Ty = std::get<0>(Ops)->getType();
2448 assert(Ty == std::get<1>(Ops)->
getType() &&
"Incompatible types?");
2449 return Ty->
isTokenTy() && std::get<0>(Ops) != std::get<1>(Ops);
2451 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2452 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2453 IsIllegalToMergeArguments))
2465 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2471 bool HasNormalDest =
2472 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2476 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2485 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2487 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2489 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2491 if (!HasNormalDest) {
2495 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2502 return MergedInvoke;
2516 SuccBBOfMergedInvoke});
2523 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2526 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2529 for (
Use &U : MergedInvoke->operands()) {
2531 if (MergedInvoke->isCallee(&U)) {
2532 if (!IsIndirectCall)
2534 }
else if (!MergedInvoke->isDataOperand(&U))
2546 U->getType(), Invokes.size(),
"", MergedInvoke);
2558 Invokes.front()->getParent());
2566 if (!MergedDebugLoc)
2575 OrigSuccBB->removePredecessor(II->
getParent());
2581 MergedInvoke->setDebugLoc(MergedDebugLoc);
2582 ++NumInvokeSetsFormed;
2585 DTU->applyUpdates(Updates);
2612 bool Changed =
false;
2618 CompatibleSets Grouper;
2624 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2628 if (Invokes.
size() < 2)
2640class EphemeralValueTracker {
2644 if (isa<AssumeInst>(
I))
2646 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2648 return EphValues.count(cast<Instruction>(U));
2654 if (isEphemeral(
I)) {
2693 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2705 unsigned MaxNumInstToLookAt = 9;
2709 if (!MaxNumInstToLookAt)
2711 --MaxNumInstToLookAt;
2714 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2717 if (
auto *
SI = dyn_cast<StoreInst>(&CurI)) {
2721 if (
SI->getPointerOperand() == StorePtr &&
2722 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple())
2724 return SI->getValueOperand();
2728 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2729 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2753 unsigned &SpeculatedInstructions,
2761 bool HaveRewritablePHIs =
false;
2779 HaveRewritablePHIs =
true;
2782 if (!OrigCE && !ThenCE)
2789 if (OrigCost + ThenCost > MaxCost)
2796 ++SpeculatedInstructions;
2797 if (SpeculatedInstructions > 1)
2801 return HaveRewritablePHIs;
2845 if (isa<FCmpInst>(BrCond))
2855 bool Invert =
false;
2864 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
2867 (TWeight + FWeight) != 0) {
2868 uint64_t EndWeight = Invert ? TWeight : FWeight;
2872 if (BIEndProb >= Likely)
2886 unsigned SpeculatedInstructions = 0;
2887 Value *SpeculatedStoreValue =
nullptr;
2889 EphemeralValueTracker EphTracker;
2892 if (isa<DbgInfoIntrinsic>(
I)) {
2900 if (isa<PseudoProbeInst>(
I)) {
2910 if (EphTracker.track(&
I))
2915 ++SpeculatedInstructions;
2916 if (SpeculatedInstructions > 1)
2922 &
I, BB, ThenBB, EndBB))))
2924 if (!SpeculatedStoreValue &&
2930 if (SpeculatedStoreValue)
2931 SpeculatedStore = cast<StoreInst>(&
I);
2936 for (
Use &Op :
I.operands()) {
2941 ++SinkCandidateUseCounts[OpI];
2948 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
2950 ++SpeculatedInstructions;
2951 if (SpeculatedInstructions > 1)
2957 bool Convert = SpeculatedStore !=
nullptr;
2960 SpeculatedInstructions,
2962 if (!Convert || Cost > Budget)
2966 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
2969 if (SpeculatedStoreValue) {
2973 Value *FalseV = SpeculatedStoreValue;
2977 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3007 if (
any_of(DAI->location_ops(), [&](
Value *V) { return V == OrigV; }))
3008 DAI->replaceVariableLocationOp(OrigV, S);
3019 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3021 if (!isa<DbgAssignIntrinsic>(&
I))
3024 I.dropUndefImplyingAttrsAndUnknownMetadata();
3027 if (EphTracker.contains(&
I)) {
3029 I.eraseFromParent();
3035 std::prev(ThenBB->
end()));
3052 Value *TrueV = ThenV, *FalseV = OrigV;
3055 Value *
V =
Builder.CreateSelect(BrCond, TrueV, FalseV,
"spec.select", BI);
3066 if (!isa<DbgAssignIntrinsic>(
I))
3067 I->eraseFromParent();
3077 EphemeralValueTracker EphTracker;
3083 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3084 if (CI->cannotDuplicate() || CI->isConvergent())
3090 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3097 for (
User *U :
I.users()) {
3099 if (UI->
getParent() != BB || isa<PHINode>(UI))
3113 auto *
I = dyn_cast<Instruction>(V);
3114 if (
I &&
I->getParent() == To)
3118 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3130static std::optional<bool>
3146 if (
auto *CB = dyn_cast<ConstantInt>(U))
3151 KnownValues[CB].
insert(Pred);
3155 if (KnownValues.
empty())
3164 for (
const auto &Pair : KnownValues) {
3182 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3185 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3193 EdgeBB->setName(RealDest->
getName() +
".critedge");
3194 EdgeBB->moveBefore(RealDest);
3204 TranslateMap[
Cond] = CB;
3206 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3213 N->setName(BBI->getName() +
".c");
3216 for (
Use &Op :
N->operands()) {
3218 if (PI != TranslateMap.
end())
3224 if (!BBI->use_empty())
3225 TranslateMap[&*BBI] = V;
3226 if (!
N->mayHaveSideEffects()) {
3231 if (!BBI->use_empty())
3232 TranslateMap[&*BBI] =
N;
3236 N->insertInto(EdgeBB, InsertPt);
3239 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3246 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3252 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3253 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3264 return std::nullopt;
3274 std::optional<bool> Result;
3275 bool EverChanged =
false;
3279 EverChanged |= Result == std::nullopt || *Result;
3280 }
while (Result == std::nullopt);
3302 if (isa<ConstantInt>(IfCond))
3309 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3312 "Will have either one or two blocks to speculate.");
3319 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3322 (TWeight + FWeight) != 0) {
3327 if (IfBlocks.
size() == 1) {
3329 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3330 if (BIBBProb >= Likely)
3333 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3341 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3342 if (IfCondPhiInst->getParent() == BB)
3350 unsigned NumPhis = 0;
3363 bool Changed =
false;
3365 PHINode *PN = cast<PHINode>(II++);
3382 PN = dyn_cast<PHINode>(BB->
begin());
3388 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3399 auto IsBinOpOrAnd = [](
Value *V) {
3419 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3432 <<
" T: " << IfTrue->
getName()
3433 <<
" F: " << IfFalse->
getName() <<
"\n");
3447 if (isa<FPMathOperator>(PN))
3454 Value *Sel =
Builder.CreateSelect(IfCond, TrueVal, FalseVal,
"", DomBI);
3467 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3485 if (Opc == Instruction::And)
3487 if (Opc == Instruction::Or)
3500 bool PredHasWeights =
3502 bool SuccHasWeights =
3504 if (PredHasWeights || SuccHasWeights) {
3505 if (!PredHasWeights)
3506 PredTrueWeight = PredFalseWeight = 1;
3507 if (!SuccHasWeights)
3508 SuccTrueWeight = SuccFalseWeight = 1;
3518static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3522 "Both blocks must end with a conditional branches.");
3524 "PredBB must be a predecessor of BB.");
3532 (PTWeight + PFWeight) != 0) {
3540 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3541 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3545 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3548 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3549 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3555 return std::nullopt;
3568 bool InvertPredCond;
3569 std::tie(CommonSucc, Opc, InvertPredCond) =
3572 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3579 {LLVMContext::MD_annotation});
3582 if (InvertPredCond) {
3584 if (NewCond->
hasOneUse() && isa<CmpInst>(NewCond)) {
3585 CmpInst *CI = cast<CmpInst>(NewCond);
3605 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3607 SuccTrueWeight, SuccFalseWeight)) {
3614 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3620 (SuccFalseWeight + SuccTrueWeight) +
3621 PredTrueWeight * SuccFalseWeight);
3627 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3628 PredFalseWeight * SuccTrueWeight);
3630 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3648 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3649 {DominatorTree::Delete, PredBlock, BB}});
3667 if (isa<DbgInfoIntrinsic>(
I)) {
3675 ++NumFoldBranchToCommonDest;
3682 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3683 return U->getType()->isVectorTy();
3693 unsigned BonusInstThreshold) {
3707 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3708 !isa<SelectInst>(
Cond)) ||
3709 Cond->getParent() != BB || !
Cond->hasOneUse())
3719 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3730 bool InvertPredCond;
3732 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3764 unsigned NumBonusInsts = 0;
3765 bool SawVectorOp =
false;
3766 const unsigned PredCount = Preds.
size();
3772 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3783 NumBonusInsts += PredCount;
3791 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3792 auto *UI = cast<Instruction>(U.getUser());
3793 if (
auto *PN = dyn_cast<PHINode>(UI))
3795 return UI->
getParent() == BB &&
I.comesBefore(UI);
3799 if (!
all_of(
I.uses(), IsBCSSAUse))
3803 BonusInstThreshold *
3809 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
3819 for (
auto *BB : {BB1, BB2}) {
3823 if (
auto *
SI = dyn_cast<StoreInst>(&
I)) {
3835 Value *AlternativeV =
nullptr) {
3853 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
3854 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
3855 PHI = cast<PHINode>(
I);
3861 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
3862 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
3870 if (!AlternativeV &&
3871 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
3875 PHI->addIncoming(V, BB);
3885 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
3894 if (!PStore || !QStore)
3915 if (
I.mayReadOrWriteMemory())
3917 for (
auto &
I : *QFB)
3918 if (&
I != QStore &&
I.mayReadOrWriteMemory())
3921 for (
auto &
I : *QTB)
3922 if (&
I != QStore &&
I.mayReadOrWriteMemory())
3926 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
3942 if (
I.isTerminator())
3946 if (
auto *S = dyn_cast<StoreInst>(&
I))
3950 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
3960 "When we run out of budget we will eagerly return from within the "
3961 "per-instruction loop.");
3965 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
3967 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
3968 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4072 bool InvertPCond =
false, InvertQCond =
false;
4078 if (QFB == PostBB) {
4097 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4100 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4108 for (
auto *BB : {PTB, PFB}) {
4113 PStoreAddresses.
insert(
SI->getPointerOperand());
4115 for (
auto *BB : {QTB, QFB}) {
4120 QStoreAddresses.
insert(
SI->getPointerOperand());
4126 auto &CommonAddresses = PStoreAddresses;
4128 bool Changed =
false;
4129 for (
auto *Address : CommonAddresses)
4132 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4152 if (!IfFalseBB->
phis().empty())
4162 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4173 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4174 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4185 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4186 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4269 unsigned NumPhis = 0;
4291 if (OtherDest == BB) {
4298 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4299 OtherDest = InfLoopBlock;
4311 PBICond =
Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4334 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4335 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4338 SuccTrueWeight, SuccFalseWeight);
4340 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4341 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4342 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4343 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4347 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4348 PredOther * SuccCommon,
4349 PredOther * SuccOther};
4371 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4378 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4379 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4380 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4381 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4384 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4385 PredOther * SuccCommon};
4407bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4418 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4425 if (Succ == KeepEdge1)
4426 KeepEdge1 =
nullptr;
4427 else if (Succ == KeepEdge2)
4428 KeepEdge2 =
nullptr;
4433 if (Succ != TrueBB && Succ != FalseBB)
4434 RemovedSuccessors.
insert(Succ);
4442 if (!KeepEdge1 && !KeepEdge2) {
4443 if (TrueBB == FalseBB) {
4451 if (TrueWeight != FalseWeight)
4454 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4476 for (
auto *RemovedSuccessor : RemovedSuccessors)
4477 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4478 DTU->applyUpdates(Updates);
4488bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4493 if (!TrueVal || !FalseVal)
4498 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4499 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4502 uint32_t TrueWeight = 0, FalseWeight = 0;
4507 if (Weights.
size() == 1 +
SI->getNumCases()) {
4509 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4511 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4516 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4525bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4538 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4559bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4579 if (
SI->getCondition() != V)
4585 if (
SI->getDefaultDest() != BB) {
4587 assert(VVal &&
"Should have a unique destination value");
4595 return requestResimplify();
4601 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4611 return requestResimplify();
4618 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4643 auto W0 = SIW.getSuccessorWeight(0);
4647 SIW.setSuccessorWeight(0, *NewW);
4649 SIW.addCase(Cst, NewBB, NewW);
4651 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4655 Builder.SetInsertPoint(NewBB);
4656 Builder.SetCurrentDebugLocation(
SI->getDebugLoc());
4660 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4661 DTU->applyUpdates(Updates);
4669bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4681 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4684 Value *CompVal = ConstantCompare.CompValue;
4685 unsigned UsedICmps = ConstantCompare.UsedICmps;
4686 Value *ExtraCase = ConstantCompare.Extra;
4705 if (ExtraCase && Values.
size() < 2)
4720 <<
" cases into SWITCH. BB is:\n"
4730 nullptr,
"switch.early.test");
4734 Builder.SetInsertPoint(OldTI);
4744 ExtraCase =
Builder.CreateFreeze(ExtraCase);
4747 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
4749 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
4754 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4760 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4761 <<
"\nEXTRABB = " << *BB);
4768 CompVal =
Builder.CreatePtrToInt(
4769 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4776 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4777 New->addCase(Values[i], EdgeBB);
4783 PHINode *PN = cast<PHINode>(BBI);
4785 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
4792 DTU->applyUpdates(Updates);
4794 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
4800 return simplifyCommonResume(RI);
4804 return simplifySingleResume(RI);
4812 auto *II = dyn_cast<IntrinsicInst>(&
I);
4817 switch (IntrinsicID) {
4818 case Intrinsic::dbg_declare:
4819 case Intrinsic::dbg_value:
4820 case Intrinsic::dbg_label:
4821 case Intrinsic::lifetime_end:
4831bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
4841 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
4844 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues();
Idx != End;
4846 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
4847 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
4851 if (IncomingBB->getUniqueSuccessor() != BB)
4854 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
4856 if (IncomingValue != LandingPad)
4860 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
4861 TrivialUnwindBlocks.
insert(IncomingBB);
4865 if (TrivialUnwindBlocks.
empty())
4869 for (
auto *TrivialBB : TrivialUnwindBlocks) {
4873 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
4887 TrivialBB->getTerminator()->eraseFromParent();
4890 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
4897 return !TrivialUnwindBlocks.empty();
4901bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
4905 "Resume must unwind the exception that caused control to here");
4909 make_range<Instruction *>(LPInst->getNextNode(), RI)))
4945 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
4962 int Idx = DestPN.getBasicBlockIndex(BB);
4976 Value *SrcVal = DestPN.getIncomingValue(
Idx);
4977 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
4979 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
4983 DestPN.addIncoming(Incoming, Pred);
5010 std::vector<DominatorTree::UpdateType> Updates;
5014 if (UnwindDest ==
nullptr) {
5026 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5027 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5054 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5055 if (!SuccessorCleanupPad)
5064 SuccessorCleanupPad->eraseFromParent();
5093 bool Changed =
false;
5113 BBI->eraseFromParent();
5119 if (&BB->
front() != UI)
5122 std::vector<DominatorTree::UpdateType> Updates;
5125 for (
unsigned i = 0, e = Preds.size(); i != e; ++i) {
5126 auto *Predecessor = Preds[i];
5129 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5133 [BB](
auto *
Successor) { return Successor == BB; })) {
5141 "The destinations are guaranteed to be different here.");