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) {
1626 if (NumSkipped || !AllInstsAreIdentical)
1629 for (
auto &SuccIter : OtherSuccIterRange)
1631 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, Insts) || Changed;
1634 if (AllInstsAreIdentical) {
1635 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1636 AllInstsAreIdentical =
1638 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1640 unsigned SkipFlagsBB2 = Pair.second;
1650 if (AllInstsAreIdentical) {
1652 if (isa<DbgInfoIntrinsic>(I1)) {
1656 I1->moveBeforePreserving(TI);
1657 for (
auto &SuccIter : OtherSuccIterRange) {
1658 auto *I2 = &*SuccIter++;
1659 assert(isa<DbgInfoIntrinsic>(I2));
1666 I1->moveBeforePreserving(TI);
1668 for (
auto &SuccIter : OtherSuccIterRange) {
1682 NumHoistCommonCode += SuccIterPairs.
size();
1684 NumHoistCommonInstrs += SuccIterPairs.
size();
1691 for (
auto &SuccIterPair : SuccIterPairs) {
1700bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1704 auto *BI = dyn_cast<BranchInst>(TI);
1706 bool Changed =
false;
1711 auto *I2 = *OtherSuccTIs.
begin();
1727 if (isa<CallBrInst>(I1))
1732 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1734 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1751 if (!
NT->getType()->isVoidTy()) {
1752 I1->replaceAllUsesWith(NT);
1754 OtherSuccTI->replaceAllUsesWith(NT);
1758 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1764 for (
auto *OtherSuccTI : OtherSuccTIs)
1765 Locs.
push_back(OtherSuccTI->getDebugLoc());
1777 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1780 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1781 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1787 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1791 if (isa<FPMathOperator>(PN))
1792 Builder.setFastMathFlags(PN.getFastMathFlags());
1794 SI = cast<SelectInst>(
Builder.CreateSelect(
1800 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1801 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1802 PN.setIncomingValue(i, SI);
1813 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1818 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1822 DTU->applyUpdates(Updates);
1828 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1829 switch (II->getIntrinsicID()) {
1832 case Intrinsic::lifetime_start:
1833 case Intrinsic::lifetime_end:
1844 return !isa<IntrinsicInst>(
I);
1858 bool HasUse = !Insts.
front()->user_empty();
1859 for (
auto *
I : Insts) {
1861 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1862 I->getType()->isTokenTy())
1867 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1874 if (
const auto *
C = dyn_cast<CallBase>(
I))
1875 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1879 if (HasUse && !
I->hasOneUse())
1881 if (!HasUse && !
I->user_empty())
1886 for (
auto *
I : Insts) {
1887 if (!
I->isSameOperationAs(I0))
1893 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1895 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1904 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1907 auto *U = cast<Instruction>(*
I->user_begin());
1909 PNUse->getParent() == Succ &&
1910 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
1911 U->getParent() ==
I->getParent();
1926 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
1930 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
1934 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
1942 if (isa<CallBase>(I0)) {
1944 return cast<CallBase>(
I)->isIndirectCall();
1946 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
1947 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
1948 if (HaveIndirectCalls) {
1949 if (!AllCallsAreIndirect)
1953 Value *Callee =
nullptr;
1955 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
1957 Callee = CurrCallee;
1958 else if (Callee != CurrCallee)
1964 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
1966 if (
Op->getType()->isTokenTy())
1974 if (!
all_of(Insts, SameAsI0)) {
1979 for (
auto *
I : Insts)
1980 PHIOperands[
I].push_back(
I->getOperand(OI));
1990 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
1995 for (
auto *BB :
Blocks) {
1998 I =
I->getPrevNode();
1999 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2000 if (!isa<DbgInfoIntrinsic>(
I))
2010 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
2012 auto *U = cast<Instruction>(*
I->user_begin());
2038 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2041 PN->insertBefore(BBEnd->begin());
2042 for (
auto *
I : Insts)
2043 PN->addIncoming(
I->getOperand(O),
I->getParent());
2052 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2055 for (
auto *
I : Insts)
2074 PN->replaceAllUsesWith(I0);
2075 PN->eraseFromParent();
2079 for (
auto *
I : Insts) {
2084 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2085 I->replaceAllUsesWith(I0);
2086 I->eraseFromParent();
2102 class LockstepReverseIterator {
2115 for (
auto *BB : Blocks) {
2117 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2135 for (
auto *&Inst : Insts) {
2136 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2149 for (
auto *&Inst : Insts) {
2150 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2213 bool HaveNonUnconditionalPredecessors =
false;
2215 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2216 if (PredBr && PredBr->isUnconditional())
2219 HaveNonUnconditionalPredecessors =
true;
2221 if (UnconditionalPreds.
size() < 2)
2233 LockstepReverseIterator LRI(UnconditionalPreds);
2234 while (LRI.isValid() &&
2236 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2238 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2249 if (!followedByDeoptOrUnreachable) {
2253 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2254 unsigned NumPHIdValues = 0;
2255 for (
auto *
I : *LRI)
2256 for (
auto *V : PHIOperands[
I]) {
2257 if (!InstructionsToSink.
contains(V))
2263 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2264 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.
size();
2265 if ((NumPHIdValues % UnconditionalPreds.
size()) != 0)
2268 return NumPHIInsts <= 1;
2285 while (
Idx < ScanIdx) {
2286 if (!ProfitableToSinkInstruction(LRI)) {
2289 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2292 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2302 if (
Idx < ScanIdx) {
2305 InstructionsToSink = InstructionsProfitableToSink;
2311 !ProfitableToSinkInstruction(LRI) &&
2312 "We already know that the last instruction is unprofitable to sink");
2320 for (
auto *
I : *LRI)
2321 InstructionsProfitableToSink.
erase(
I);
2322 if (!ProfitableToSinkInstruction(LRI)) {
2325 InstructionsToSink = InstructionsProfitableToSink;
2337 bool Changed =
false;
2339 if (HaveNonUnconditionalPredecessors) {
2340 if (!followedByDeoptOrUnreachable) {
2348 bool Profitable =
false;
2349 while (
Idx < ScanIdx) {
2383 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2385 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2395 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2399 NumSinkCommonInstrs++;
2403 ++NumSinkCommonCode;
2409struct CompatibleSets {
2427 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2436 getCompatibleSet(II).emplace_back(II);
2440 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2446 if (
any_of(Invokes, IsIllegalToMerge))
2452 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2453 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2454 if (HaveIndirectCalls) {
2455 if (!AllCallsAreIndirect)
2462 assert(CurrCallee &&
"There is always a called operand.");
2465 else if (Callee != CurrCallee)
2475 if (
any_of(Invokes, HasNormalDest)) {
2478 if (!
all_of(Invokes, HasNormalDest))
2485 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2487 NormalBB = CurrNormalBB;
2488 else if (NormalBB != CurrNormalBB)
2496 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2507 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2509 UnwindBB = CurrUnwindBB;
2511 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2518 Invokes.front()->getUnwindDest(),
2519 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2525 for (
auto *II : Invokes.drop_front())
2530 auto IsIllegalToMergeArguments = [](
auto Ops) {
2531 Use &U0 = std::get<0>(Ops);
2532 Use &U1 = std::get<1>(Ops);
2539 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2540 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2541 IsIllegalToMergeArguments))
2553 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2559 bool HasNormalDest =
2560 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2564 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2573 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2575 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2577 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2579 if (!HasNormalDest) {
2583 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2590 return MergedInvoke;
2604 SuccBBOfMergedInvoke});
2611 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2614 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2617 for (
Use &U : MergedInvoke->operands()) {
2619 if (MergedInvoke->isCallee(&U)) {
2620 if (!IsIndirectCall)
2622 }
else if (!MergedInvoke->isDataOperand(&U))
2634 U->getType(), Invokes.size(),
"", MergedInvoke);
2646 Invokes.front()->getParent());
2654 if (!MergedDebugLoc)
2663 OrigSuccBB->removePredecessor(II->
getParent());
2669 MergedInvoke->setDebugLoc(MergedDebugLoc);
2670 ++NumInvokeSetsFormed;
2673 DTU->applyUpdates(Updates);
2700 bool Changed =
false;
2706 CompatibleSets Grouper;
2712 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2716 if (Invokes.
size() < 2)
2728class EphemeralValueTracker {
2732 if (isa<AssumeInst>(
I))
2734 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2736 return EphValues.count(cast<Instruction>(U));
2742 if (isEphemeral(
I)) {
2781 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2793 unsigned MaxNumInstToLookAt = 9;
2797 if (!MaxNumInstToLookAt)
2799 --MaxNumInstToLookAt;
2802 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2805 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2809 if (SI->getPointerOperand() == StorePtr &&
2810 SI->getValueOperand()->getType() == StoreTy && SI->isSimple())
2812 return SI->getValueOperand();
2816 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2817 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2841 unsigned &SpeculatedInstructions,
2849 bool HaveRewritablePHIs =
false;
2867 HaveRewritablePHIs =
true;
2870 if (!OrigCE && !ThenCE)
2877 if (OrigCost + ThenCost > MaxCost)
2884 ++SpeculatedInstructions;
2885 if (SpeculatedInstructions > 1)
2889 return HaveRewritablePHIs;
2929bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
2936 if (isa<FCmpInst>(BrCond))
2946 bool Invert =
false;
2955 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
2958 (TWeight + FWeight) != 0) {
2959 uint64_t EndWeight = Invert ? TWeight : FWeight;
2963 if (BIEndProb >= Likely)
2977 unsigned SpeculatedInstructions = 0;
2978 Value *SpeculatedStoreValue =
nullptr;
2980 EphemeralValueTracker EphTracker;
2983 if (isa<DbgInfoIntrinsic>(
I)) {
2991 if (isa<PseudoProbeInst>(
I)) {
3001 if (EphTracker.track(&
I))
3006 ++SpeculatedInstructions;
3007 if (SpeculatedInstructions > 1)
3013 &
I, BB, ThenBB, EndBB))))
3015 if (!SpeculatedStoreValue &&
3021 if (SpeculatedStoreValue)
3022 SpeculatedStore = cast<StoreInst>(&
I);
3027 for (
Use &
Op :
I.operands()) {
3032 ++SinkCandidateUseCounts[OpI];
3039 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3041 ++SpeculatedInstructions;
3042 if (SpeculatedInstructions > 1)
3048 bool Convert = SpeculatedStore !=
nullptr;
3051 SpeculatedInstructions,
3053 if (!Convert ||
Cost > Budget)
3057 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3060 if (SpeculatedStoreValue) {
3064 Value *FalseV = SpeculatedStoreValue;
3068 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3099 DAI->replaceVariableLocationOp(OrigV, S);
3110 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3112 if (!isa<DbgAssignIntrinsic>(&
I))
3115 I.dropUBImplyingAttrsAndMetadata();
3118 if (EphTracker.contains(&
I)) {
3120 I.eraseFromParent();
3126 std::prev(ThenBB->
end()));
3143 Value *TrueV = ThenV, *FalseV = OrigV;
3146 Value *
V =
Builder.CreateSelect(BrCond, TrueV, FalseV,
"spec.select", BI);
3157 if (!isa<DbgAssignIntrinsic>(
I))
3158 I->eraseFromParent();
3168 EphemeralValueTracker EphTracker;
3174 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3175 if (CI->cannotDuplicate() || CI->isConvergent())
3181 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3188 for (
User *U :
I.users()) {
3190 if (UI->
getParent() != BB || isa<PHINode>(UI))
3204 auto *
I = dyn_cast<Instruction>(V);
3205 if (
I &&
I->getParent() == To)
3209 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3221static std::optional<bool>
3237 if (
auto *CB = dyn_cast<ConstantInt>(U))
3242 KnownValues[CB].
insert(Pred);
3246 if (KnownValues.
empty())
3255 for (
const auto &Pair : KnownValues) {
3273 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3276 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3284 EdgeBB->setName(RealDest->
getName() +
".critedge");
3285 EdgeBB->moveBefore(RealDest);
3295 TranslateMap[
Cond] = CB;
3297 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3304 N->insertInto(EdgeBB, InsertPt);
3307 N->setName(BBI->getName() +
".c");
3310 for (
Use &
Op :
N->operands()) {
3312 if (PI != TranslateMap.
end())
3318 if (!BBI->use_empty())
3319 TranslateMap[&*BBI] = V;
3320 if (!
N->mayHaveSideEffects()) {
3321 N->eraseFromParent();
3326 if (!BBI->use_empty())
3327 TranslateMap[&*BBI] =
N;
3331 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3338 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3344 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3345 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3356 return std::nullopt;
3366 std::optional<bool> Result;
3367 bool EverChanged =
false;
3371 EverChanged |= Result == std::nullopt || *Result;
3372 }
while (Result == std::nullopt);
3394 if (isa<ConstantInt>(IfCond))
3401 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3404 "Will have either one or two blocks to speculate.");
3411 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3414 (TWeight + FWeight) != 0) {
3419 if (IfBlocks.
size() == 1) {
3421 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3422 if (BIBBProb >= Likely)
3425 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3433 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3434 if (IfCondPhiInst->getParent() == BB)
3442 unsigned NumPhis = 0;
3455 bool Changed =
false;
3457 PHINode *PN = cast<PHINode>(II++);
3474 PN = dyn_cast<PHINode>(BB->
begin());
3480 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3491 auto IsBinOpOrAnd = [](
Value *V) {
3511 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3524 <<
" T: " << IfTrue->
getName()
3525 <<
" F: " << IfFalse->
getName() <<
"\n");
3539 if (isa<FPMathOperator>(PN))
3546 Value *Sel =
Builder.CreateSelect(IfCond, TrueVal, FalseVal,
"", DomBI);
3559 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3577 if (Opc == Instruction::And)
3579 if (Opc == Instruction::Or)
3592 bool PredHasWeights =
3594 bool SuccHasWeights =
3596 if (PredHasWeights || SuccHasWeights) {
3597 if (!PredHasWeights)
3598 PredTrueWeight = PredFalseWeight = 1;
3599 if (!SuccHasWeights)
3600 SuccTrueWeight = SuccFalseWeight = 1;
3610static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3614 "Both blocks must end with a conditional branches.");
3616 "PredBB must be a predecessor of BB.");
3624 (PTWeight + PFWeight) != 0) {
3632 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3633 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3637 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3640 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3641 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3647 return std::nullopt;
3660 bool InvertPredCond;
3661 std::tie(CommonSucc, Opc, InvertPredCond) =
3664 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3671 {LLVMContext::MD_annotation});
3674 if (InvertPredCond) {
3687 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3689 SuccTrueWeight, SuccFalseWeight)) {
3696 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3702 (SuccFalseWeight + SuccTrueWeight) +
3703 PredTrueWeight * SuccFalseWeight);
3709 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3710 PredFalseWeight * SuccTrueWeight);
3712 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3730 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3731 {DominatorTree::Delete, PredBlock, BB}});
3749 if (isa<DbgInfoIntrinsic>(
I)) {
3757 ++NumFoldBranchToCommonDest;
3764 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3765 return U->getType()->isVectorTy();
3775 unsigned BonusInstThreshold) {
3789 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3790 !isa<SelectInst>(
Cond)) ||
3791 Cond->getParent() != BB || !
Cond->hasOneUse())
3801 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3812 bool InvertPredCond;
3814 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3846 unsigned NumBonusInsts = 0;
3847 bool SawVectorOp =
false;
3848 const unsigned PredCount = Preds.
size();
3854 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3865 NumBonusInsts += PredCount;
3873 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3874 auto *UI = cast<Instruction>(U.getUser());
3875 if (
auto *PN = dyn_cast<PHINode>(UI))
3877 return UI->
getParent() == BB &&
I.comesBefore(UI);
3881 if (!
all_of(
I.uses(), IsBCSSAUse))
3885 BonusInstThreshold *
3891 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
3901 for (
auto *BB : {BB1, BB2}) {
3905 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
3917 Value *AlternativeV =
nullptr) {
3935 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
3936 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
3937 PHI = cast<PHINode>(
I);
3943 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
3944 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
3952 if (!AlternativeV &&
3953 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
3958 PHI->addIncoming(V, BB);
3968 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
3977 if (!PStore || !QStore)
3998 if (
I.mayReadOrWriteMemory())
4000 for (
auto &
I : *QFB)
4001 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4004 for (
auto &
I : *QTB)
4005 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4009 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4025 if (
I.isTerminator())
4029 if (
auto *S = dyn_cast<StoreInst>(&
I))
4033 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4043 "When we run out of budget we will eagerly return from within the "
4044 "per-instruction loop.");
4048 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4050 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4051 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4159 bool InvertPCond =
false, InvertQCond =
false;
4165 if (QFB == PostBB) {
4184 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4187 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4195 for (
auto *BB : {PTB, PFB}) {
4200 PStoreAddresses.
insert(SI->getPointerOperand());
4202 for (
auto *BB : {QTB, QFB}) {
4207 QStoreAddresses.
insert(SI->getPointerOperand());
4213 auto &CommonAddresses = PStoreAddresses;
4215 bool Changed =
false;
4216 for (
auto *Address : CommonAddresses)
4219 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4239 if (!IfFalseBB->
phis().empty())
4249 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4260 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4261 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4272 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4273 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4356 unsigned NumPhis = 0;
4378 if (OtherDest == BB) {
4385 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4386 OtherDest = InfLoopBlock;
4398 PBICond =
Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4421 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4422 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4425 SuccTrueWeight, SuccFalseWeight);
4427 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4428 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4429 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4430 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4434 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4435 PredOther * SuccCommon,
4436 PredOther * SuccOther};
4458 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4465 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4466 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4467 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4468 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4471 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4472 PredOther * SuccCommon};
4494bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4505 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4512 if (Succ == KeepEdge1)
4513 KeepEdge1 =
nullptr;
4514 else if (Succ == KeepEdge2)
4515 KeepEdge2 =
nullptr;
4520 if (Succ != TrueBB && Succ != FalseBB)
4521 RemovedSuccessors.
insert(Succ);
4529 if (!KeepEdge1 && !KeepEdge2) {
4530 if (TrueBB == FalseBB) {
4538 if (TrueWeight != FalseWeight)
4541 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4563 for (
auto *RemovedSuccessor : RemovedSuccessors)
4564 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4565 DTU->applyUpdates(Updates);
4575bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4580 if (!TrueVal || !FalseVal)
4585 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4586 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4589 uint32_t TrueWeight = 0, FalseWeight = 0;
4594 if (Weights.
size() == 1 +
SI->getNumCases()) {
4596 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4598 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4603 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4612bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4625 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4646bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4666 if (
SI->getCondition() != V)
4672 if (
SI->getDefaultDest() != BB) {
4674 assert(VVal &&
"Should have a unique destination value");
4682 return requestResimplify();
4688 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4698 return requestResimplify();
4705 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4730 auto W0 = SIW.getSuccessorWeight(0);
4734 SIW.setSuccessorWeight(0, *NewW);
4736 SIW.addCase(Cst, NewBB, NewW);
4738 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4742 Builder.SetInsertPoint(NewBB);
4743 Builder.SetCurrentDebugLocation(
SI->getDebugLoc());
4747 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4748 DTU->applyUpdates(Updates);
4756bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4768 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4771 Value *CompVal = ConstantCompare.CompValue;
4772 unsigned UsedICmps = ConstantCompare.UsedICmps;
4773 Value *ExtraCase = ConstantCompare.Extra;
4792 if (ExtraCase && Values.
size() < 2)
4807 <<
" cases into SWITCH. BB is:\n"
4817 nullptr,
"switch.early.test");
4821 Builder.SetInsertPoint(OldTI);
4831 ExtraCase =
Builder.CreateFreeze(ExtraCase);
4834 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
4836 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
4841 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4847 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4848 <<
"\nEXTRABB = " << *BB);
4855 CompVal =
Builder.CreatePtrToInt(
4856 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4863 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4864 New->addCase(Values[i], EdgeBB);
4870 PHINode *PN = cast<PHINode>(BBI);
4872 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
4879 DTU->applyUpdates(Updates);
4881 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
4887 return simplifyCommonResume(RI);
4891 return simplifySingleResume(RI);
4899 auto *II = dyn_cast<IntrinsicInst>(&
I);
4904 switch (IntrinsicID) {
4905 case Intrinsic::dbg_declare:
4906 case Intrinsic::dbg_value:
4907 case Intrinsic::dbg_label:
4908 case Intrinsic::lifetime_end:
4918bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
4928 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
4931 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
4933 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
4934 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
4938 if (IncomingBB->getUniqueSuccessor() != BB)
4941 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
4943 if (IncomingValue != LandingPad)
4947 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
4948 TrivialUnwindBlocks.
insert(IncomingBB);
4952 if (TrivialUnwindBlocks.
empty())
4956 for (
auto *TrivialBB : TrivialUnwindBlocks) {
4960 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
4974 TrivialBB->getTerminator()->eraseFromParent();
4977 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
4984 return !TrivialUnwindBlocks.empty();
4988bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
4992 "Resume must unwind the exception that caused control to here");
4996 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5032 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5049 int Idx = DestPN.getBasicBlockIndex(BB);
5063 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5064 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5066 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5070 DestPN.addIncoming(Incoming, Pred);
5097 std::vector<DominatorTree::UpdateType> Updates;
5101 if (UnwindDest ==
nullptr) {
5113 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5114 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5141 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5142 if (!SuccessorCleanupPad)
5151 SuccessorCleanupPad->eraseFromParent();
5164 if (isa<UndefValue>(RI->