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,
274 bool hoistCommonCodeFromSuccessors(
BasicBlock *BB,
bool EqTermsOnly);
275 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
294 "SimplifyCFG is not yet capable of maintaining validity of a "
295 "PostDomTree, so don't ask for it.");
302 bool requestResimplify() {
321 "Only for a pair of incoming blocks at the time!");
327 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
328 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
331 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
332 EquivalenceSet->contains(IV1))
355 if (!SI1Succs.
count(Succ))
361 FailBlocks->insert(Succ);
377 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
379 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
380 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
389 assert((!isa<Instruction>(
I) ||
391 "Instruction is not safe to speculatively execute!");
417 unsigned Depth = 0) {
446 if (AggressiveInsts.
count(
I))
470 for (
Use &
Op :
I->operands())
484 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
485 DL.isNonIntegralPointerType(V->getType()))
490 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
493 if (isa<ConstantPointerNull>(V))
498 if (CE->getOpcode() == Instruction::IntToPtr)
499 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
504 return cast<ConstantInt>(
522struct ConstantComparesGatherer {
526 Value *CompValue =
nullptr;
529 Value *Extra =
nullptr;
535 unsigned UsedICmps = 0;
542 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
543 ConstantComparesGatherer &
544 operator=(
const ConstantComparesGatherer &) =
delete;
549 bool setValueOnce(
Value *NewVal) {
550 if (CompValue && CompValue != NewVal)
553 return (CompValue !=
nullptr);
567 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
578 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
622 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
624 if (!setValueOnce(RHSVal))
630 C->getValue() | Mask));
645 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
647 if (!setValueOnce(RHSVal))
652 C->getValue() & ~Mask));
673 Value *CandidateVal =
I->getOperand(0);
676 CandidateVal = RHSVal;
691 if (!setValueOnce(CandidateVal))
707 void gather(
Value *V) {
718 while (!DFT.
empty()) {
726 if (Visited.
insert(Op1).second)
728 if (Visited.
insert(Op0).second)
735 if (matchInstruction(
I, isEQ))
759 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
760 Cond = dyn_cast<Instruction>(SI->getCondition());
761 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
762 if (BI->isConditional())
763 Cond = dyn_cast<Instruction>(BI->getCondition());
765 Cond = dyn_cast<Instruction>(IBI->getAddress());
777 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
780 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
781 CV =
SI->getCondition();
782 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
783 if (BI->isConditional() && BI->getCondition()->hasOneUse())
784 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
792 Value *
Ptr = PTII->getPointerOperand();
793 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
802BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
803 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
804 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
805 Cases.reserve(
SI->getNumCases());
806 for (
auto Case :
SI->cases())
807 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
808 Case.getCaseSuccessor()));
809 return SI->getDefaultDest();
815 Cases.push_back(ValueEqualityComparisonCase(
824 std::vector<ValueEqualityComparisonCase> &Cases) {
830 std::vector<ValueEqualityComparisonCase> &C2) {
831 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
834 if (V1->size() > V2->size())
839 if (V1->size() == 1) {
842 for (
const ValueEqualityComparisonCase &VECC : *V2)
843 if (TheVal == VECC.
Value)
850 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
851 while (i1 != e1 && i2 != e2) {
870 SI->setMetadata(LLVMContext::MD_prof,
N);
877 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
881 if (TrueWeight || FalseWeight)
884 I->setMetadata(LLVMContext::MD_prof,
N);
892bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
898 Value *ThisVal = isValueEqualityComparison(TI);
899 assert(ThisVal &&
"This isn't a value comparison!!");
900 if (ThisVal != PredVal)
907 std::vector<ValueEqualityComparisonCase> PredCases;
909 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
913 std::vector<ValueEqualityComparisonCase> ThisCases;
914 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
926 if (isa<BranchInst>(TI)) {
929 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
935 ThisCases[0].Dest->removePredecessor(PredDef);
938 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
945 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
953 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
957 <<
"Through successor TI: " << *TI);
965 if (DeadCases.
count(i->getCaseValue())) {
974 std::vector<DominatorTree::UpdateType> Updates;
975 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
977 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
978 DTU->applyUpdates(Updates);
989 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
990 if (PredCases[i].Dest == TIBB) {
993 TIV = PredCases[i].
Value;
995 assert(TIV &&
"No edge from pred to succ?");
1000 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1001 if (ThisCases[i].
Value == TIV) {
1002 TheRealDest = ThisCases[i].Dest;
1008 TheRealDest = ThisDef;
1015 if (Succ != CheckEdge) {
1016 if (Succ != TheRealDest)
1017 RemovedSuccs.
insert(Succ);
1020 CheckEdge =
nullptr;
1027 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1034 for (
auto *RemovedSucc : RemovedSuccs)
1035 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1036 DTU->applyUpdates(Updates);
1046struct ConstantIntOrdering {
1048 return LHS->getValue().ult(
RHS->getValue());
1060 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1078 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1089 if (Max > UINT_MAX) {
1104 if (isa<DbgInfoIntrinsic>(BonusInst) || BonusInst.isTerminator())
1119 VMap[&BonusInst] = NewBonusInst;
1129 NewBonusInst->
takeName(&BonusInst);
1130 BonusInst.setName(NewBonusInst->
getName() +
".old");
1136 auto *UI = cast<Instruction>(U.getUser());
1137 auto *PN = dyn_cast<PHINode>(UI);
1139 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1140 "If the user is not a PHI node, then it should be in the same "
1141 "block as, and come after, the original bonus instruction.");
1145 if (PN->getIncomingBlock(U) == BB)
1149 assert(PN->getIncomingBlock(U) == PredBlock &&
1150 "Not in block-closed SSA form?");
1151 U.set(NewBonusInst);
1156bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1164 std::vector<ValueEqualityComparisonCase> BBCases;
1165 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1167 std::vector<ValueEqualityComparisonCase> PredCases;
1168 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1180 if (PredHasWeights) {
1183 if (Weights.
size() != 1 + PredCases.size())
1184 PredHasWeights = SuccHasWeights =
false;
1185 }
else if (SuccHasWeights)
1189 Weights.
assign(1 + PredCases.size(), 1);
1192 if (SuccHasWeights) {
1195 if (SuccWeights.
size() != 1 + BBCases.size())
1196 PredHasWeights = SuccHasWeights =
false;
1197 }
else if (PredHasWeights)
1198 SuccWeights.
assign(1 + BBCases.size(), 1);
1200 if (PredDefault == BB) {
1203 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1204 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1205 if (PredCases[i].Dest != BB)
1206 PTIHandled.insert(PredCases[i].
Value);
1209 std::swap(PredCases[i], PredCases.back());
1211 if (PredHasWeights || SuccHasWeights) {
1213 Weights[0] += Weights[i + 1];
1218 PredCases.pop_back();
1224 if (PredDefault != BBDefault) {
1226 if (DTU && PredDefault != BB)
1227 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1228 PredDefault = BBDefault;
1229 ++NewSuccessors[BBDefault];
1232 unsigned CasesFromPred = Weights.
size();
1234 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1235 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1236 PredCases.push_back(BBCases[i]);
1237 ++NewSuccessors[BBCases[i].Dest];
1238 if (SuccHasWeights || PredHasWeights) {
1242 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1243 ValidTotalSuccWeight += SuccWeights[i + 1];
1247 if (SuccHasWeights || PredHasWeights) {
1248 ValidTotalSuccWeight += SuccWeights[0];
1250 for (
unsigned i = 1; i < CasesFromPred; ++i)
1251 Weights[i] *= ValidTotalSuccWeight;
1253 Weights[0] *= SuccWeights[0];
1259 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1260 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1261 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1262 if (PredCases[i].Dest == BB) {
1265 if (PredHasWeights || SuccHasWeights) {
1266 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1271 std::swap(PredCases[i], PredCases.back());
1272 PredCases.pop_back();
1279 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1280 if (PTIHandled.count(BBCases[i].Value)) {
1282 if (PredHasWeights || SuccHasWeights)
1284 PredCases.push_back(BBCases[i]);
1285 ++NewSuccessors[BBCases[i].Dest];
1292 if (PredHasWeights || SuccHasWeights)
1294 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1295 ++NewSuccessors[BBDefault];
1307 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1309 for (
auto I :
seq(NewSuccessor.second)) {
1313 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1314 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1327 for (ValueEqualityComparisonCase &V : PredCases)
1330 if (PredHasWeights || SuccHasWeights) {
1347 if (!InfLoopBlock) {
1355 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1362 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1364 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1366 DTU->applyUpdates(Updates);
1369 ++NumFoldValueComparisonIntoPredecessors;
1377bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1380 Value *CV = isValueEqualityComparison(TI);
1381 assert(CV &&
"Not a comparison?");
1383 bool Changed =
false;
1386 while (!Preds.empty()) {
1395 Value *PCV = isValueEqualityComparison(PTI);
1401 for (
auto *Succ : FailBlocks) {
1407 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1421 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1422 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1423 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1442 if (
I->mayReadFromMemory())
1446 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1463 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1473 if (
auto *CB = dyn_cast<CallBase>(
I))
1474 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1481 if (
auto *J = dyn_cast<Instruction>(
Op))
1482 if (J->getParent() == BB)
1501 auto *C1 = dyn_cast<CallInst>(I1);
1502 auto *C2 = dyn_cast<CallInst>(I2);
1504 if (C1->isMustTailCall() != C2->isMustTailCall())
1512 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1513 if (CB1->cannotMerge() || CB1->isConvergent())
1515 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1516 if (CB2->cannotMerge() || CB2->isConvergent())
1527bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1549 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1553 if (isa<PHINode>(*SuccItr))
1555 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1564 if (!INonDbg->isTerminator())
1574 unsigned NumSkipped = 0;
1577 if (SuccIterPairs.
size() > 2) {
1579 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1580 if (SuccIterPairs.
size() < 2)
1584 bool Changed =
false;
1587 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1588 auto &BB1ItrPair = *SuccIterPairBegin++;
1589 auto OtherSuccIterPairRange =
1594 auto *BB1 =
I1->getParent();
1597 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1599 return I1->isIdenticalToWhenDefined(I2);
1601 if (!AllDbgInstsAreIdentical) {
1602 while (isa<DbgInfoIntrinsic>(I1))
1603 I1 = &*++BB1ItrPair.first;
1604 for (
auto &SuccIter : OtherSuccIterRange) {
1606 while (isa<DbgInfoIntrinsic>(I2))
1611 bool AllInstsAreIdentical =
true;
1612 bool HasTerminator =
I1->isTerminator();
1613 for (
auto &SuccIter : OtherSuccIterRange) {
1616 if (AllInstsAreIdentical && !
I1->isIdenticalToWhenDefined(I2))
1617 AllInstsAreIdentical =
false;
1622 if (HasTerminator) {
1624 if (NumSkipped || SuccSize != SuccIterPairs.
size() ||
1625 !AllInstsAreIdentical)
1628 for (
auto &SuccIter : OtherSuccIterRange)
1630 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, Insts) || Changed;
1633 if (AllInstsAreIdentical) {
1634 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1635 AllInstsAreIdentical =
1637 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1639 unsigned SkipFlagsBB2 = Pair.second;
1649 if (AllInstsAreIdentical) {
1651 if (isa<DbgInfoIntrinsic>(I1)) {
1655 I1->moveBeforePreserving(TI);
1656 for (
auto &SuccIter : OtherSuccIterRange) {
1657 auto *I2 = &*SuccIter++;
1658 assert(isa<DbgInfoIntrinsic>(I2));
1665 I1->moveBeforePreserving(TI);
1667 for (
auto &SuccIter : OtherSuccIterRange) {
1681 NumHoistCommonCode += SuccIterPairs.
size();
1683 NumHoistCommonInstrs += SuccIterPairs.
size();
1690 for (
auto &SuccIterPair : SuccIterPairs) {
1699bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1703 auto *BI = dyn_cast<BranchInst>(TI);
1705 bool Changed =
false;
1710 auto *I2 = *OtherSuccTIs.
begin();
1726 if (isa<CallBrInst>(I1))
1731 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1733 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1750 if (!
NT->getType()->isVoidTy()) {
1751 I1->replaceAllUsesWith(NT);
1753 OtherSuccTI->replaceAllUsesWith(NT);
1757 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1763 for (
auto *OtherSuccTI : OtherSuccTIs)
1764 Locs.
push_back(OtherSuccTI->getDebugLoc());
1776 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1779 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1780 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1786 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1790 if (isa<FPMathOperator>(PN))
1791 Builder.setFastMathFlags(PN.getFastMathFlags());
1793 SI = cast<SelectInst>(
Builder.CreateSelect(
1799 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1800 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1801 PN.setIncomingValue(i, SI);
1812 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1817 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1821 DTU->applyUpdates(Updates);
1827 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1828 switch (II->getIntrinsicID()) {
1831 case Intrinsic::lifetime_start:
1832 case Intrinsic::lifetime_end:
1843 return !isa<IntrinsicInst>(
I);
1857 bool HasUse = !Insts.
front()->user_empty();
1858 for (
auto *
I : Insts) {
1860 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1861 I->getType()->isTokenTy())
1866 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1873 if (
const auto *
C = dyn_cast<CallBase>(
I))
1874 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1878 if (HasUse && !
I->hasOneUse())
1880 if (!HasUse && !
I->user_empty())
1885 for (
auto *
I : Insts) {
1886 if (!
I->isSameOperationAs(I0))
1892 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1894 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1903 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1906 auto *U = cast<Instruction>(*
I->user_begin());
1908 PNUse->getParent() == Succ &&
1909 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
1910 U->getParent() ==
I->getParent();
1925 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
1929 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
1933 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
1941 if (isa<CallBase>(I0)) {
1943 return cast<CallBase>(
I)->isIndirectCall();
1945 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
1946 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
1947 if (HaveIndirectCalls) {
1948 if (!AllCallsAreIndirect)
1952 Value *Callee =
nullptr;
1954 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
1956 Callee = CurrCallee;
1957 else if (Callee != CurrCallee)
1963 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
1965 if (
Op->getType()->isTokenTy())
1973 if (!
all_of(Insts, SameAsI0)) {
1978 for (
auto *
I : Insts)
1979 PHIOperands[
I].push_back(
I->getOperand(OI));
1989 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
1994 for (
auto *BB :
Blocks) {
1997 I =
I->getPrevNode();
1998 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
1999 if (!isa<DbgInfoIntrinsic>(
I))
2009 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
2011 auto *U = cast<Instruction>(*
I->user_begin());
2037 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2040 PN->insertBefore(BBEnd->begin());
2041 for (
auto *
I : Insts)
2042 PN->addIncoming(
I->getOperand(O),
I->getParent());
2051 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2054 for (
auto *
I : Insts)
2073 PN->replaceAllUsesWith(I0);
2074 PN->eraseFromParent();
2078 for (
auto *
I : Insts) {
2083 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2084 I->replaceAllUsesWith(I0);
2085 I->eraseFromParent();
2101 class LockstepReverseIterator {
2114 for (
auto *BB : Blocks) {
2116 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2134 for (
auto *&Inst : Insts) {
2135 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2148 for (
auto *&Inst : Insts) {
2149 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2212 bool HaveNonUnconditionalPredecessors =
false;
2214 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2215 if (PredBr && PredBr->isUnconditional())
2218 HaveNonUnconditionalPredecessors =
true;
2220 if (UnconditionalPreds.
size() < 2)
2232 LockstepReverseIterator LRI(UnconditionalPreds);
2233 while (LRI.isValid() &&
2235 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2237 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2248 if (!followedByDeoptOrUnreachable) {
2252 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2253 unsigned NumPHIdValues = 0;
2254 for (
auto *
I : *LRI)
2255 for (
auto *V : PHIOperands[
I]) {
2256 if (!InstructionsToSink.
contains(V))
2262 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2263 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.
size();
2264 if ((NumPHIdValues % UnconditionalPreds.
size()) != 0)
2267 return NumPHIInsts <= 1;
2284 while (
Idx < ScanIdx) {
2285 if (!ProfitableToSinkInstruction(LRI)) {
2288 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2291 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2301 if (
Idx < ScanIdx) {
2304 InstructionsToSink = InstructionsProfitableToSink;
2310 !ProfitableToSinkInstruction(LRI) &&
2311 "We already know that the last instruction is unprofitable to sink");
2319 for (
auto *
I : *LRI)
2320 InstructionsProfitableToSink.
erase(
I);
2321 if (!ProfitableToSinkInstruction(LRI)) {
2324 InstructionsToSink = InstructionsProfitableToSink;
2336 bool Changed =
false;
2338 if (HaveNonUnconditionalPredecessors) {
2339 if (!followedByDeoptOrUnreachable) {
2347 bool Profitable =
false;
2348 while (
Idx < ScanIdx) {
2382 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2384 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2394 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2398 NumSinkCommonInstrs++;
2402 ++NumSinkCommonCode;
2408struct CompatibleSets {
2426 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2435 getCompatibleSet(II).emplace_back(II);
2439 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2445 if (
any_of(Invokes, IsIllegalToMerge))
2451 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2452 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2453 if (HaveIndirectCalls) {
2454 if (!AllCallsAreIndirect)
2461 assert(CurrCallee &&
"There is always a called operand.");
2464 else if (Callee != CurrCallee)
2474 if (
any_of(Invokes, HasNormalDest)) {
2477 if (!
all_of(Invokes, HasNormalDest))
2484 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2486 NormalBB = CurrNormalBB;
2487 else if (NormalBB != CurrNormalBB)
2495 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2506 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2508 UnwindBB = CurrUnwindBB;
2510 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2517 Invokes.front()->getUnwindDest(),
2518 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2524 for (
auto *II : Invokes.drop_front())
2529 auto IsIllegalToMergeArguments = [](
auto Ops) {
2530 Use &U0 = std::get<0>(Ops);
2531 Use &U1 = std::get<1>(Ops);
2538 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2539 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2540 IsIllegalToMergeArguments))
2552 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2558 bool HasNormalDest =
2559 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2563 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2572 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2574 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2576 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2578 if (!HasNormalDest) {
2582 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2589 return MergedInvoke;
2603 SuccBBOfMergedInvoke});
2610 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2613 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2616 for (
Use &U : MergedInvoke->operands()) {
2618 if (MergedInvoke->isCallee(&U)) {
2619 if (!IsIndirectCall)
2621 }
else if (!MergedInvoke->isDataOperand(&U))
2633 U->getType(), Invokes.size(),
"", MergedInvoke);
2645 Invokes.front()->getParent());
2653 if (!MergedDebugLoc)
2662 OrigSuccBB->removePredecessor(II->
getParent());
2668 MergedInvoke->setDebugLoc(MergedDebugLoc);
2669 ++NumInvokeSetsFormed;
2672 DTU->applyUpdates(Updates);
2699 bool Changed =
false;
2705 CompatibleSets Grouper;
2711 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2715 if (Invokes.
size() < 2)
2727class EphemeralValueTracker {
2731 if (isa<AssumeInst>(
I))
2733 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2735 return EphValues.count(cast<Instruction>(U));
2741 if (isEphemeral(
I)) {
2780 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2792 unsigned MaxNumInstToLookAt = 9;
2796 if (!MaxNumInstToLookAt)
2798 --MaxNumInstToLookAt;
2801 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2804 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2808 if (SI->getPointerOperand() == StorePtr &&
2809 SI->getValueOperand()->getType() == StoreTy && SI->isSimple())
2811 return SI->getValueOperand();
2815 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2816 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2840 unsigned &SpeculatedInstructions,
2848 bool HaveRewritablePHIs =
false;
2866 HaveRewritablePHIs =
true;
2869 if (!OrigCE && !ThenCE)
2876 if (OrigCost + ThenCost > MaxCost)
2883 ++SpeculatedInstructions;
2884 if (SpeculatedInstructions > 1)
2888 return HaveRewritablePHIs;
2928bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
2935 if (isa<FCmpInst>(BrCond))
2945 bool Invert =
false;
2954 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
2957 (TWeight + FWeight) != 0) {
2958 uint64_t EndWeight = Invert ? TWeight : FWeight;
2962 if (BIEndProb >= Likely)
2976 unsigned SpeculatedInstructions = 0;
2977 Value *SpeculatedStoreValue =
nullptr;
2979 EphemeralValueTracker EphTracker;
2982 if (isa<DbgInfoIntrinsic>(
I)) {
2990 if (isa<PseudoProbeInst>(
I)) {
3000 if (EphTracker.track(&
I))
3005 ++SpeculatedInstructions;
3006 if (SpeculatedInstructions > 1)
3012 &
I, BB, ThenBB, EndBB))))
3014 if (!SpeculatedStoreValue &&
3020 if (SpeculatedStoreValue)
3021 SpeculatedStore = cast<StoreInst>(&
I);
3026 for (
Use &
Op :
I.operands()) {
3031 ++SinkCandidateUseCounts[OpI];
3038 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3040 ++SpeculatedInstructions;
3041 if (SpeculatedInstructions > 1)
3047 bool Convert = SpeculatedStore !=
nullptr;
3050 SpeculatedInstructions,
3052 if (!Convert ||
Cost > Budget)
3056 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3059 if (SpeculatedStoreValue) {
3063 Value *FalseV = SpeculatedStoreValue;
3067 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3098 DAI->replaceVariableLocationOp(OrigV, S);
3109 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3111 if (!isa<DbgAssignIntrinsic>(&
I))
3114 I.dropUBImplyingAttrsAndMetadata();
3117 if (EphTracker.contains(&
I)) {
3119 I.eraseFromParent();
3125 std::prev(ThenBB->
end()));
3142 Value *TrueV = ThenV, *FalseV = OrigV;
3145 Value *
V =
Builder.CreateSelect(BrCond, TrueV, FalseV,
"spec.select", BI);
3156 if (!isa<DbgAssignIntrinsic>(
I))
3157 I->eraseFromParent();
3167 EphemeralValueTracker EphTracker;
3173 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3174 if (CI->cannotDuplicate() || CI->isConvergent())
3180 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3187 for (
User *U :
I.users()) {
3189 if (UI->
getParent() != BB || isa<PHINode>(UI))
3203 auto *
I = dyn_cast<Instruction>(V);
3204 if (
I &&
I->getParent() == To)
3208 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3220static std::optional<bool>
3236 if (
auto *CB = dyn_cast<ConstantInt>(U))
3241 KnownValues[CB].
insert(Pred);
3245 if (KnownValues.
empty())
3254 for (
const auto &Pair : KnownValues) {
3272 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3275 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3283 EdgeBB->setName(RealDest->
getName() +
".critedge");
3284 EdgeBB->moveBefore(RealDest);
3294 TranslateMap[
Cond] = CB;
3296 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3303 N->insertInto(EdgeBB, InsertPt);
3306 N->setName(BBI->getName() +
".c");
3309 for (
Use &
Op :
N->operands()) {
3311 if (PI != TranslateMap.
end())
3317 if (!BBI->use_empty())
3318 TranslateMap[&*BBI] = V;
3319 if (!
N->mayHaveSideEffects()) {
3320 N->eraseFromParent();
3325 if (!BBI->use_empty())
3326 TranslateMap[&*BBI] =
N;
3330 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3337 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3343 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3344 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3355 return std::nullopt;
3365 std::optional<bool> Result;
3366 bool EverChanged =
false;
3370 EverChanged |= Result == std::nullopt || *Result;
3371 }
while (Result == std::nullopt);
3393 if (isa<ConstantInt>(IfCond))
3400 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3403 "Will have either one or two blocks to speculate.");
3410 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3413 (TWeight + FWeight) != 0) {
3418 if (IfBlocks.
size() == 1) {
3420 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3421 if (BIBBProb >= Likely)
3424 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3432 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3433 if (IfCondPhiInst->getParent() == BB)
3441 unsigned NumPhis = 0;
3454 bool Changed =
false;
3456 PHINode *PN = cast<PHINode>(II++);
3473 PN = dyn_cast<PHINode>(BB->
begin());
3479 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3490 auto IsBinOpOrAnd = [](
Value *V) {
3510 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3523 <<
" T: " << IfTrue->
getName()
3524 <<
" F: " << IfFalse->
getName() <<
"\n");
3538 if (isa<FPMathOperator>(PN))
3545 Value *Sel =
Builder.CreateSelect(IfCond, TrueVal, FalseVal,
"", DomBI);
3558 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3576 if (Opc == Instruction::And)
3578 if (Opc == Instruction::Or)
3591 bool PredHasWeights =
3593 bool SuccHasWeights =
3595 if (PredHasWeights || SuccHasWeights) {
3596 if (!PredHasWeights)
3597 PredTrueWeight = PredFalseWeight = 1;
3598 if (!SuccHasWeights)
3599 SuccTrueWeight = SuccFalseWeight = 1;
3609static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3613 "Both blocks must end with a conditional branches.");
3615 "PredBB must be a predecessor of BB.");
3623 (PTWeight + PFWeight) != 0) {
3631 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3632 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3636 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3639 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3640 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3646 return std::nullopt;
3659 bool InvertPredCond;
3660 std::tie(CommonSucc, Opc, InvertPredCond) =
3663 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3670 {LLVMContext::MD_annotation});
3673 if (InvertPredCond) {
3686 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3688 SuccTrueWeight, SuccFalseWeight)) {
3695 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3701 (SuccFalseWeight + SuccTrueWeight) +
3702 PredTrueWeight * SuccFalseWeight);
3708 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3709 PredFalseWeight * SuccTrueWeight);
3711 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3729 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3730 {DominatorTree::Delete, PredBlock, BB}});
3748 if (isa<DbgInfoIntrinsic>(
I)) {
3756 ++NumFoldBranchToCommonDest;
3763 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3764 return U->getType()->isVectorTy();
3774 unsigned BonusInstThreshold) {
3788 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3789 !isa<SelectInst>(
Cond)) ||
3790 Cond->getParent() != BB || !
Cond->hasOneUse())
3800 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3811 bool InvertPredCond;
3813 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3845 unsigned NumBonusInsts = 0;
3846 bool SawVectorOp =
false;
3847 const unsigned PredCount = Preds.
size();
3853 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3864 NumBonusInsts += PredCount;
3872 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3873 auto *UI = cast<Instruction>(U.getUser());
3874 if (
auto *PN = dyn_cast<PHINode>(UI))
3876 return UI->
getParent() == BB &&
I.comesBefore(UI);
3880 if (!
all_of(
I.uses(), IsBCSSAUse))
3884 BonusInstThreshold *
3890 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
3900 for (
auto *BB : {BB1, BB2}) {
3904 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
3916 Value *AlternativeV =
nullptr) {
3934 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
3935 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
3936 PHI = cast<PHINode>(
I);
3942 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
3943 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
3951 if (!AlternativeV &&
3952 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
3957 PHI->addIncoming(V, BB);
3967 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
3976 if (!PStore || !QStore)
3997 if (
I.mayReadOrWriteMemory())
3999 for (
auto &
I : *QFB)
4000 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4003 for (
auto &
I : *QTB)
4004 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4008 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4024 if (
I.isTerminator())
4028 if (
auto *S = dyn_cast<StoreInst>(&
I))
4032 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4042 "When we run out of budget we will eagerly return from within the "
4043 "per-instruction loop.");
4047 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4049 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4050 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4158 bool InvertPCond =
false, InvertQCond =
false;
4164 if (QFB == PostBB) {
4183 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4186 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4194 for (
auto *BB : {PTB, PFB}) {
4199 PStoreAddresses.
insert(SI->getPointerOperand());
4201 for (
auto *BB : {QTB, QFB}) {
4206 QStoreAddresses.
insert(SI->getPointerOperand());
4212 auto &CommonAddresses = PStoreAddresses;
4214 bool Changed =
false;
4215 for (
auto *Address : CommonAddresses)
4218 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4238 if (!IfFalseBB->
phis().empty())
4248 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4259 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4260 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4271 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4272 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4355 unsigned NumPhis = 0;
4377 if (OtherDest == BB) {
4384 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4385 OtherDest = InfLoopBlock;
4397 PBICond =
Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4420 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4421 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4424 SuccTrueWeight, SuccFalseWeight);
4426 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4427 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4428 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4429 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4433 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4434 PredOther * SuccCommon,
4435 PredOther * SuccOther};
4457 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4464 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4465 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4466 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4467 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4470 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4471 PredOther * SuccCommon};
4493bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4504 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4511 if (Succ == KeepEdge1)
4512 KeepEdge1 =
nullptr;
4513 else if (Succ == KeepEdge2)
4514 KeepEdge2 =
nullptr;
4519 if (Succ != TrueBB && Succ != FalseBB)
4520 RemovedSuccessors.
insert(Succ);
4528 if (!KeepEdge1 && !KeepEdge2) {
4529 if (TrueBB == FalseBB) {
4537 if (TrueWeight != FalseWeight)
4540 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4562 for (
auto *RemovedSuccessor : RemovedSuccessors)
4563 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4564 DTU->applyUpdates(Updates);
4574bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4579 if (!TrueVal || !FalseVal)
4584 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4585 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4588 uint32_t TrueWeight = 0, FalseWeight = 0;
4593 if (Weights.
size() == 1 +
SI->getNumCases()) {
4595 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4597 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4602 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4611bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4624 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4645bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4665 if (
SI->getCondition() != V)
4671 if (
SI->getDefaultDest() != BB) {
4673 assert(VVal &&
"Should have a unique destination value");
4681 return requestResimplify();
4687 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4697 return requestResimplify();
4704 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4729 auto W0 = SIW.getSuccessorWeight(0);
4733 SIW.setSuccessorWeight(0, *NewW);
4735 SIW.addCase(Cst, NewBB, NewW);
4737 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4741 Builder.SetInsertPoint(NewBB);
4742 Builder.SetCurrentDebugLocation(
SI->getDebugLoc());
4746 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4747 DTU->applyUpdates(Updates);
4755bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4767 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4770 Value *CompVal = ConstantCompare.CompValue;
4771 unsigned UsedICmps = ConstantCompare.UsedICmps;
4772 Value *ExtraCase = ConstantCompare.Extra;
4791 if (ExtraCase && Values.
size() < 2)
4806 <<
" cases into SWITCH. BB is:\n"
4816 nullptr,
"switch.early.test");
4820 Builder.SetInsertPoint(OldTI);
4830 ExtraCase =
Builder.CreateFreeze(ExtraCase);
4833 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
4835 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
4840 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4846 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4847 <<
"\nEXTRABB = " << *BB);
4854 CompVal =
Builder.CreatePtrToInt(
4855 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4862 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4863 New->addCase(Values[i], EdgeBB);
4869 PHINode *PN = cast<PHINode>(BBI);
4871 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
4878 DTU->applyUpdates(Updates);
4880 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
4886 return simplifyCommonResume(RI);
4890 return simplifySingleResume(RI);
4898 auto *II = dyn_cast<IntrinsicInst>(&
I);
4903 switch (IntrinsicID) {
4904 case Intrinsic::dbg_declare:
4905 case Intrinsic::dbg_value:
4906 case Intrinsic::dbg_label:
4907 case Intrinsic::lifetime_end:
4917bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
4927 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
4930 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
4932 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
4933 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
4937 if (IncomingBB->getUniqueSuccessor() != BB)
4940 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
4942 if (IncomingValue != LandingPad)
4946 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
4947 TrivialUnwindBlocks.
insert(IncomingBB);
4951 if (TrivialUnwindBlocks.
empty())
4955 for (
auto *TrivialBB : TrivialUnwindBlocks) {
4959 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
4973 TrivialBB->getTerminator()->eraseFromParent();
4976 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
4983 return !TrivialUnwindBlocks.empty();
4987bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
4991 "Resume must unwind the exception that caused control to here");
4995 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5031 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5048 int Idx = DestPN.getBasicBlockIndex(BB);
5062 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5063 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5065 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5069 DestPN.addIncoming(Incoming, Pred);
5096 std::vector<DominatorTree::UpdateType> Updates;
5100 if (UnwindDest ==
nullptr) {
5112 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5113 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5140 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5141 if (!SuccessorCleanupPad)
5150 SuccessorCleanupPad->eraseFromParent();