96#define DEBUG_TYPE "simplifycfg"
101 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
104 "Temporary development switch used to gradually uplift SimplifyCFG "
105 "into preserving DomTree,"));
114 "Control the amount of phi node folding to perform (default = 2)"));
118 cl::desc(
"Control the maximal total instruction cost that we are willing "
119 "to speculatively execute to fold a 2-entry PHI node into a "
120 "select (default = 4)"));
124 cl::desc(
"Hoist common instructions up to the parent block"));
128 cl::desc(
"Hoist loads if the target supports conditional faulting"));
132 cl::desc(
"Hoist stores if the target supports conditional faulting"));
136 cl::desc(
"Control the maximal conditional load/store that we are willing "
137 "to speculatively execute to eliminate conditional branch "
143 cl::desc(
"Allow reordering across at most this many "
144 "instructions when hoisting"));
148 cl::desc(
"Sink common instructions down to the end block"));
152 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
156 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
157 "precede - hoist multiple conditional stores into a single "
158 "predicated store"));
162 cl::desc(
"When merging conditional stores, do so even if the resultant "
163 "basic blocks are unlikely to be if-converted as a result"));
167 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
172 cl::desc(
"Limit maximum recursion depth when calculating costs of "
173 "speculatively executed instructions"));
178 cl::desc(
"Max size of a block which is still considered "
179 "small enough to thread through"));
185 cl::desc(
"Maximum cost of combining conditions when "
186 "folding branches"));
189 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
191 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
192 "to fold branch to common destination when vector operations are "
197 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
201 cl::desc(
"Limit cases to analyze when converting a switch to select"));
205 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
212STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
214 "Number of switch instructions turned into linear mapping");
216 "Number of switch instructions turned into lookup tables");
218 NumLookupTablesHoles,
219 "Number of switch instructions turned into lookup tables (holes checked)");
220STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
222 "Number of value comparisons folded into predecessor basic blocks");
224 "Number of branches folded into predecessor basic block");
227 "Number of common instruction 'blocks' hoisted up to the begin block");
229 "Number of common instructions hoisted up to the begin block");
231 "Number of common instruction 'blocks' sunk down to the end block");
233 "Number of common instructions sunk down to the end block");
234STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
236 "Number of invokes with empty resume blocks simplified into calls");
237STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
238STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
245using SwitchCaseResultVectorTy =
254struct ValueEqualityComparisonCase {
266 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
269class SimplifyCFGOpt {
270 const TargetTransformInfo &TTI;
272 const DataLayout &DL;
274 const SimplifyCFGOptions &Options;
277 Value *isValueEqualityComparison(Instruction *TI);
279 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
280 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
283 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
286 bool foldValueComparisonIntoPredecessors(Instruction *TI,
289 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
290 bool simplifySingleResume(ResumeInst *RI);
291 bool simplifyCommonResume(ResumeInst *RI);
292 bool simplifyCleanupReturn(CleanupReturnInst *RI);
293 bool simplifyUnreachable(UnreachableInst *UI);
294 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
295 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
296 bool simplifyIndirectBr(IndirectBrInst *IBI);
297 bool simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
298 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
299 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
301 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
303 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
306 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
307 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
308 Instruction *TI, Instruction *I1,
309 SmallVectorImpl<Instruction *> &OtherSuccTIs,
311 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
312 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
313 BasicBlock *TrueBB, BasicBlock *FalseBB,
314 uint32_t TrueWeight, uint32_t FalseWeight);
315 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
316 const DataLayout &DL);
317 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
318 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
319 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
320 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
323 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
325 const SimplifyCFGOptions &Opts)
326 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
327 assert((!DTU || !DTU->hasPostDomTree()) &&
328 "SimplifyCFG is not yet capable of maintaining validity of a "
329 "PostDomTree, so don't ask for it.");
332 bool simplifyOnce(BasicBlock *BB);
333 bool run(BasicBlock *BB);
336 bool requestResimplify() {
346isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
366 "Only for a pair of incoming blocks at the time!");
372 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
373 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
376 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
377 EquivalenceSet->contains(IV1))
400 if (!SI1Succs.
count(Succ))
406 FailBlocks->insert(Succ);
422 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
424 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
425 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
487 if (AggressiveInsts.
count(
I))
503 ZeroCostInstructions.
insert(OverflowInst);
505 }
else if (!ZeroCostInstructions.
contains(
I))
521 for (
Use &
Op :
I->operands())
523 TTI, AC, ZeroCostInstructions,
Depth + 1))
540 if (
DL.hasUnstableRepresentation(V->getType()))
549 return ConstantInt::get(
IntPtrTy, 0);
554 if (CE->getOpcode() == Instruction::IntToPtr)
578struct ConstantComparesGatherer {
579 const DataLayout &DL;
582 Value *CompValue =
nullptr;
585 Value *Extra =
nullptr;
591 unsigned UsedICmps = 0;
597 bool IgnoreFirstMatch =
false;
598 bool MultipleMatches =
false;
601 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
603 if (CompValue || !MultipleMatches)
608 IgnoreFirstMatch =
true;
612 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
613 ConstantComparesGatherer &
614 operator=(
const ConstantComparesGatherer &) =
delete;
619 bool setValueOnce(
Value *NewVal) {
620 if (IgnoreFirstMatch) {
621 IgnoreFirstMatch =
false;
624 if (CompValue && CompValue != NewVal) {
625 MultipleMatches =
true;
639 bool matchInstruction(Instruction *
I,
bool isEQ) {
646 if (!setValueOnce(Val))
666 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
710 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
712 if (!setValueOnce(RHSVal))
717 ConstantInt::get(
C->getContext(),
718 C->getValue() | Mask));
733 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
735 if (!setValueOnce(RHSVal))
739 Vals.push_back(ConstantInt::get(
C->getContext(),
740 C->getValue() & ~Mask));
761 Value *CandidateVal =
I->getOperand(0);
764 CandidateVal = RHSVal;
779 if (!setValueOnce(CandidateVal))
785 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
797 void gather(
Value *V) {
806 SmallVector<Value *, 8> DFT{Op0, Op1};
807 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
809 while (!DFT.
empty()) {
816 if (Visited.
insert(Op1).second)
818 if (Visited.
insert(Op0).second)
825 if (matchInstruction(
I, IsEq))
869 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
870 CV =
SI->getCondition();
872 if (BI->getCondition()->hasOneUse()) {
877 if (Trunc->hasNoUnsignedWrap())
878 CV = Trunc->getOperand(0);
885 Value *Ptr = PTII->getPointerOperand();
886 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
888 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
897BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
898 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
900 Cases.reserve(
SI->getNumCases());
901 for (
auto Case :
SI->cases())
902 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
903 Case.getCaseSuccessor()));
904 return SI->getDefaultDest();
909 ICmpInst::Predicate Pred;
915 Pred = ICmpInst::ICMP_NE;
920 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
928 std::vector<ValueEqualityComparisonCase> &Cases) {
934 std::vector<ValueEqualityComparisonCase> &C2) {
935 std::vector<ValueEqualityComparisonCase> *
V1 = &C1, *V2 = &C2;
938 if (
V1->size() > V2->size())
943 if (
V1->size() == 1) {
946 for (
const ValueEqualityComparisonCase &
VECC : *V2)
947 if (TheVal ==
VECC.Value)
954 unsigned i1 = 0, i2 = 0, e1 =
V1->size(), e2 = V2->size();
955 while (i1 != e1 && i2 != e2) {
971bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
972 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
977 Value *ThisVal = isValueEqualityComparison(TI);
978 assert(ThisVal &&
"This isn't a value comparison!!");
979 if (ThisVal != PredVal)
986 std::vector<ValueEqualityComparisonCase> PredCases;
988 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
992 std::vector<ValueEqualityComparisonCase> ThisCases;
993 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1008 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1014 ThisCases[0].Dest->removePredecessor(PredDef);
1017 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1024 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1031 SmallPtrSet<Constant *, 16> DeadCases;
1032 for (
const ValueEqualityComparisonCase &Case : PredCases)
1033 DeadCases.
insert(Case.Value);
1036 <<
"Through successor TI: " << *TI);
1038 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1041 auto *
Successor = i->getCaseSuccessor();
1044 if (DeadCases.
count(i->getCaseValue())) {
1053 std::vector<DominatorTree::UpdateType> Updates;
1054 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1056 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1066 ConstantInt *TIV =
nullptr;
1068 for (
const auto &[
Value, Dest] : PredCases)
1074 assert(TIV &&
"No edge from pred to succ?");
1079 for (
const auto &[
Value, Dest] : ThisCases)
1087 TheRealDest = ThisDef;
1089 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1094 if (Succ != CheckEdge) {
1095 if (Succ != TheRealDest)
1096 RemovedSuccs.
insert(Succ);
1099 CheckEdge =
nullptr;
1106 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1111 SmallVector<DominatorTree::UpdateType, 2> Updates;
1113 for (
auto *RemovedSucc : RemovedSuccs)
1114 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1125struct ConstantIntOrdering {
1126 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1127 return LHS->getValue().ult(
RHS->getValue());
1139 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1148 assert(MD &&
"Invalid branch-weight metadata");
1173 if (BonusInst.isTerminator())
1208 NewBonusInst->
takeName(&BonusInst);
1209 BonusInst.setName(NewBonusInst->
getName() +
".old");
1210 VMap[&BonusInst] = NewBonusInst;
1219 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1220 "If the user is not a PHI node, then it should be in the same "
1221 "block as, and come after, the original bonus instruction.");
1225 if (PN->getIncomingBlock(U) == BB)
1229 assert(PN->getIncomingBlock(U) == PredBlock &&
1230 "Not in block-closed SSA form?");
1231 U.set(NewBonusInst);
1241 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1242 PredDL.isSameSourceLocation(
DL)) {
1249bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1257 std::vector<ValueEqualityComparisonCase> BBCases;
1258 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1260 std::vector<ValueEqualityComparisonCase> PredCases;
1261 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1266 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1269 SmallVector<uint64_t, 8> Weights;
1273 if (PredHasWeights) {
1276 if (Weights.
size() != 1 + PredCases.size())
1277 PredHasWeights = SuccHasWeights =
false;
1278 }
else if (SuccHasWeights)
1282 Weights.
assign(1 + PredCases.size(), 1);
1284 SmallVector<uint64_t, 8> SuccWeights;
1285 if (SuccHasWeights) {
1288 if (SuccWeights.
size() != 1 + BBCases.size())
1289 PredHasWeights = SuccHasWeights =
false;
1290 }
else if (PredHasWeights)
1291 SuccWeights.
assign(1 + BBCases.size(), 1);
1293 if (PredDefault == BB) {
1296 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1297 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1298 if (PredCases[i].Dest != BB)
1299 PTIHandled.insert(PredCases[i].
Value);
1302 std::swap(PredCases[i], PredCases.back());
1304 if (PredHasWeights || SuccHasWeights) {
1306 Weights[0] += Weights[i + 1];
1311 PredCases.pop_back();
1317 if (PredDefault != BBDefault) {
1319 if (DTU && PredDefault != BB)
1320 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1321 PredDefault = BBDefault;
1322 ++NewSuccessors[BBDefault];
1325 unsigned CasesFromPred = Weights.
size();
1327 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1328 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1329 PredCases.push_back(BBCases[i]);
1330 ++NewSuccessors[BBCases[i].Dest];
1331 if (SuccHasWeights || PredHasWeights) {
1335 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1336 ValidTotalSuccWeight += SuccWeights[i + 1];
1340 if (SuccHasWeights || PredHasWeights) {
1341 ValidTotalSuccWeight += SuccWeights[0];
1343 for (
unsigned i = 1; i < CasesFromPred; ++i)
1344 Weights[i] *= ValidTotalSuccWeight;
1346 Weights[0] *= SuccWeights[0];
1352 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1353 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1354 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1355 if (PredCases[i].Dest == BB) {
1356 PTIHandled.insert(PredCases[i].
Value);
1358 if (PredHasWeights || SuccHasWeights) {
1359 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1364 std::swap(PredCases[i], PredCases.back());
1365 PredCases.pop_back();
1372 for (
const ValueEqualityComparisonCase &Case : BBCases)
1373 if (PTIHandled.count(Case.Value)) {
1375 if (PredHasWeights || SuccHasWeights)
1376 Weights.
push_back(WeightsForHandled[Case.Value]);
1377 PredCases.push_back(Case);
1378 ++NewSuccessors[Case.Dest];
1379 PTIHandled.erase(Case.Value);
1384 for (ConstantInt *
I : PTIHandled) {
1385 if (PredHasWeights || SuccHasWeights)
1387 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1388 ++NewSuccessors[BBDefault];
1395 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1400 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1402 for (
auto I :
seq(NewSuccessor.second)) {
1406 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1407 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1414 "Should not end up here with unstable pointers");
1420 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1422 for (ValueEqualityComparisonCase &V : PredCases)
1425 if (PredHasWeights || SuccHasWeights)
1437 if (!InfLoopBlock) {
1445 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1452 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1454 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1459 ++NumFoldValueComparisonIntoPredecessors;
1467bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1470 Value *CV = isValueEqualityComparison(TI);
1471 assert(CV &&
"Not a comparison?");
1476 while (!Preds.empty()) {
1485 Value *PCV = isValueEqualityComparison(PTI);
1489 SmallSetVector<BasicBlock *, 4> FailBlocks;
1491 for (
auto *Succ : FailBlocks) {
1497 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1511 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1512 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1513 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1535 if (
I->mayReadFromMemory())
1567 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1575 if (J->getParent() == BB)
1597 if (C1->isMustTailCall() != C2->isMustTailCall())
1600 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1606 if (CB1->cannotMerge() || CB1->isConvergent())
1609 if (CB2->cannotMerge() || CB2->isConvergent())
1624 if (!I1->hasDbgRecords())
1626 using CurrentAndEndIt =
1627 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1633 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1634 return Pair.first == Pair.second;
1640 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1646 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1648 if (!
Other->hasDbgRecords())
1651 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1658 while (
none_of(Itrs, atEnd)) {
1659 bool HoistDVRs = allIdentical(Itrs);
1660 for (CurrentAndEndIt &Pair : Itrs) {
1674 if (I1->isIdenticalToWhenDefined(I2,
true))
1679 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1680 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1681 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1683 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1684 return I1->getOperand(0) == I2->
getOperand(1) &&
1750 auto &Context = BI->
getParent()->getContext();
1755 Value *Mask =
nullptr;
1756 Value *MaskFalse =
nullptr;
1757 Value *MaskTrue =
nullptr;
1758 if (Invert.has_value()) {
1759 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1760 Mask = Builder.CreateBitCast(
1765 MaskFalse = Builder.CreateBitCast(
1767 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1769 auto PeekThroughBitcasts = [](
Value *V) {
1771 V = BitCast->getOperand(0);
1774 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1776 if (!Invert.has_value())
1777 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1782 auto *Op0 =
I->getOperand(0);
1783 CallInst *MaskedLoadStore =
nullptr;
1786 auto *Ty =
I->getType();
1788 Value *PassThru =
nullptr;
1789 if (Invert.has_value())
1790 for (
User *U :
I->users()) {
1792 PassThru = Builder.CreateBitCast(
1801 Builder.SetInsertPoint(Ins);
1804 MaskedLoadStore = Builder.CreateMaskedLoad(
1806 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1809 I->replaceAllUsesWith(NewLoadStore);
1812 auto *StoredVal = Builder.CreateBitCast(
1814 MaskedLoadStore = Builder.CreateMaskedStore(
1825 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1827 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1831 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1832 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1835 I->eraseFromParent();
1842 bool IsStore =
false;
1865bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1866 bool AllInstsEqOnly) {
1882 for (
auto *Succ : UniqueSuccessors) {
1898 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1900 for (
auto *Succ : UniqueSuccessors) {
1904 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1907 if (AllInstsEqOnly) {
1913 unsigned Size0 = UniqueSuccessors[0]->size();
1914 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1918 Succ->
size() == Size0;
1922 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1923 while (LRI.isValid()) {
1925 if (
any_of(*LRI, [I0](Instruction *
I) {
1939 unsigned NumSkipped = 0;
1942 if (SuccIterPairs.
size() > 2) {
1945 if (SuccIterPairs.
size() < 2)
1952 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1953 auto &BB1ItrPair = *SuccIterPairBegin++;
1954 auto OtherSuccIterPairRange =
1960 bool AllInstsAreIdentical =
true;
1961 bool HasTerminator =
I1->isTerminator();
1962 for (
auto &SuccIter : OtherSuccIterRange) {
1966 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1967 AllInstsAreIdentical =
false;
1970 SmallVector<Instruction *, 8> OtherInsts;
1971 for (
auto &SuccIter : OtherSuccIterRange)
1976 if (HasTerminator) {
1980 if (NumSkipped || !AllInstsAreIdentical) {
1985 return hoistSuccIdenticalTerminatorToSwitchOrIf(
1986 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
1990 if (AllInstsAreIdentical) {
1991 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1992 AllInstsAreIdentical =
1994 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1996 unsigned SkipFlagsBB2 = Pair.second;
2011 AllInstsAreIdentical && CI && CI->isMustTailCall()) {
2012 AllInstsAreIdentical =
2013 NumSkipped == 0 &&
all_of(SuccIterPairs, [](
const SuccIterPair &
P) {
2018 if (AllInstsAreIdentical) {
2028 for (
auto &SuccIter : OtherSuccIterRange) {
2036 assert(
Success &&
"We should not be trying to hoist callbases "
2037 "with non-intersectable attributes");
2049 NumHoistCommonCode += SuccIterPairs.
size();
2051 NumHoistCommonInstrs += SuccIterPairs.
size();
2060 for (
auto &SuccIterPair : SuccIterPairs) {
2069bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2070 Instruction *TI, Instruction *I1,
2071 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2081 auto *I2 = *OtherSuccTIs.
begin();
2101 for (PHINode &PN : Succ->
phis()) {
2102 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2103 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2104 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2124 if (!
NT->getType()->isVoidTy()) {
2125 I1->replaceAllUsesWith(NT);
2126 for (Instruction *OtherSuccTI : OtherSuccTIs)
2127 OtherSuccTI->replaceAllUsesWith(NT);
2131 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2137 for (
auto *OtherSuccTI : OtherSuccTIs)
2138 Locs.
push_back(OtherSuccTI->getDebugLoc());
2150 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2152 for (PHINode &PN : Succ->
phis()) {
2153 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2154 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2160 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2170 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2171 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2172 PN.setIncomingValue(i, SI);
2180 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
2184 if (DTU && VisitedSuccs.
insert(Succ).second)
2185 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2191 for (BasicBlock *Succ : UniqueSuccessors)
2192 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2206 if (
I->isIntDivRem())
2221 std::optional<unsigned> NumUses;
2222 for (
auto *
I : Insts) {
2225 I->getType()->isTokenTy())
2230 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2238 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2242 NumUses =
I->getNumUses();
2243 else if (NumUses !=
I->getNumUses())
2249 for (
auto *
I : Insts) {
2263 for (
const Use &U : I0->
uses()) {
2264 auto It = PHIOperands.find(&U);
2265 if (It == PHIOperands.end())
2268 if (!
equal(Insts, It->second))
2282 if (HaveIndirectCalls) {
2283 if (!AllCallsAreIndirect)
2287 Value *Callee =
nullptr;
2291 Callee = CurrCallee;
2292 else if (Callee != CurrCallee)
2298 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2304 if (!
all_of(Insts, SameAsI0)) {
2309 !
all_of(Insts, CanReplaceOperand))
2313 for (
auto *
I : Insts)
2314 Ops.push_back(
I->getOperand(OI));
2324 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2329 for (
auto *BB : Blocks) {
2331 I =
I->getPrevNode();
2356 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2359 PN->insertBefore(BBEnd->begin());
2360 for (
auto *
I : Insts)
2361 PN->addIncoming(
I->getOperand(O),
I->getParent());
2370 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2373 for (
auto *
I : Insts)
2387 assert(
Success &&
"We should not be trying to sink callbases "
2388 "with non-intersectable attributes");
2399 PN->replaceAllUsesWith(I0);
2400 PN->eraseFromParent();
2404 for (
auto *
I : Insts) {
2409 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2410 I->replaceAllUsesWith(I0);
2411 I->eraseFromParent();
2461 bool HaveNonUnconditionalPredecessors =
false;
2467 HaveNonUnconditionalPredecessors =
true;
2469 if (UnconditionalPreds.
size() < 2)
2482 for (
const Use &U : PN.incoming_values())
2483 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2484 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2486 Ops.push_back(*IncomingVals[Pred]);
2494 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2507 if (!followedByDeoptOrUnreachable) {
2509 auto IsMemOperand = [](
Use &U) {
2522 unsigned NumPHIInsts = 0;
2523 for (
Use &U : (*LRI)[0]->operands()) {
2524 auto It = PHIOperands.
find(&U);
2525 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2526 return InstructionsToSink.contains(V);
2533 if (IsMemOperand(U) &&
2534 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2541 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2542 return NumPHIInsts <= 1;
2559 while (Idx < ScanIdx) {
2560 if (!ProfitableToSinkInstruction(LRI)) {
2563 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2576 if (Idx < ScanIdx) {
2579 InstructionsToSink = InstructionsProfitableToSink;
2585 !ProfitableToSinkInstruction(LRI) &&
2586 "We already know that the last instruction is unprofitable to sink");
2594 for (
auto *
I : *LRI)
2595 InstructionsProfitableToSink.
erase(
I);
2596 if (!ProfitableToSinkInstruction(LRI)) {
2599 InstructionsToSink = InstructionsProfitableToSink;
2613 if (HaveNonUnconditionalPredecessors) {
2614 if (!followedByDeoptOrUnreachable) {
2622 bool Profitable =
false;
2623 while (Idx < ScanIdx) {
2657 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2659 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2667 NumSinkCommonInstrs++;
2671 ++NumSinkCommonCode;
2677struct CompatibleSets {
2678 using SetTy = SmallVector<InvokeInst *, 2>;
2684 SetTy &getCompatibleSet(InvokeInst *
II);
2686 void insert(InvokeInst *
II);
2689CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2694 for (CompatibleSets::SetTy &Set : Sets) {
2695 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2700 return Sets.emplace_back();
2703void CompatibleSets::insert(InvokeInst *
II) {
2704 getCompatibleSet(
II).emplace_back(
II);
2708 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2711 auto IsIllegalToMerge = [](InvokeInst *
II) {
2712 return II->cannotMerge() ||
II->isInlineAsm();
2714 if (
any_of(Invokes, IsIllegalToMerge))
2722 if (HaveIndirectCalls) {
2723 if (!AllCallsAreIndirect)
2728 for (InvokeInst *
II : Invokes) {
2729 Value *CurrCallee =
II->getCalledOperand();
2730 assert(CurrCallee &&
"There is always a called operand.");
2733 else if (Callee != CurrCallee)
2740 auto HasNormalDest = [](InvokeInst *
II) {
2743 if (
any_of(Invokes, HasNormalDest)) {
2746 if (!
all_of(Invokes, HasNormalDest))
2751 for (InvokeInst *
II : Invokes) {
2753 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2755 NormalBB = CurrNormalBB;
2756 else if (NormalBB != CurrNormalBB)
2764 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2773 for (InvokeInst *
II : Invokes) {
2775 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2777 UnwindBB = CurrUnwindBB;
2779 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2786 Invokes.front()->getUnwindDest(),
2787 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2792 const InvokeInst *II0 = Invokes.front();
2793 for (
auto *
II : Invokes.drop_front())
2798 auto IsIllegalToMergeArguments = [](
auto Ops) {
2799 Use &U0 = std::get<0>(
Ops);
2800 Use &U1 = std::get<1>(
Ops);
2806 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2807 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2808 IsIllegalToMergeArguments))
2820 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2826 bool HasNormalDest =
2831 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2835 II0->
getParent()->getIterator()->getNextNode();
2840 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2844 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2846 if (!HasNormalDest) {
2850 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2858 return MergedInvoke;
2872 SuccBBOfMergedInvoke});
2895 return II->getOperand(U.getOperandNo()) != U.get();
2914 Invokes.
front()->getParent());
2922 if (!MergedDebugLoc)
2923 MergedDebugLoc =
II->getDebugLoc();
2931 OrigSuccBB->removePredecessor(
II->getParent());
2937 assert(
Success &&
"Merged invokes with incompatible attributes");
2940 II->replaceAllUsesWith(MergedInvoke);
2941 II->eraseFromParent();
2945 ++NumInvokeSetsFormed;
2981 CompatibleSets Grouper;
2991 if (Invokes.
size() < 2)
3003class EphemeralValueTracker {
3004 SmallPtrSet<const Instruction *, 32> EphValues;
3006 bool isEphemeral(
const Instruction *
I) {
3009 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3010 all_of(
I->users(), [&](
const User *U) {
3011 return EphValues.count(cast<Instruction>(U));
3016 bool track(
const Instruction *
I) {
3017 if (isEphemeral(
I)) {
3068 unsigned MaxNumInstToLookAt = 9;
3072 if (!MaxNumInstToLookAt)
3074 --MaxNumInstToLookAt;
3087 if (
SI->getPointerOperand() == StorePtr &&
3088 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3091 return SI->getValueOperand();
3096 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3097 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3099 bool ExplicitlyDereferenceableOnly;
3107 (!ExplicitlyDereferenceableOnly ||
3125 unsigned &SpeculatedInstructions,
3133 bool HaveRewritablePHIs =
false;
3135 Value *OrigV = PN.getIncomingValueForBlock(BB);
3136 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3143 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3152 HaveRewritablePHIs =
true;
3155 if (!OrigCE && !ThenCE)
3162 if (OrigCost + ThenCost > MaxCost)
3169 ++SpeculatedInstructions;
3170 if (SpeculatedInstructions > 1)
3174 return HaveRewritablePHIs;
3178 std::optional<bool> Invert,
3182 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3189 if (!Invert.has_value())
3192 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3196 return BIEndProb < Likely;
3236bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3237 BasicBlock *ThenBB) {
3248 bool Invert =
false;
3263 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3265 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3267 unsigned SpeculatedInstructions = 0;
3268 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3269 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3270 Value *SpeculatedStoreValue =
nullptr;
3271 StoreInst *SpeculatedStore =
nullptr;
3272 EphemeralValueTracker EphTracker;
3287 if (EphTracker.track(&
I))
3292 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3294 SpeculatedConditionalLoadsStores.
size() <
3298 if (IsSafeCheapLoadStore)
3299 SpeculatedConditionalLoadsStores.
push_back(&
I);
3301 ++SpeculatedInstructions;
3303 if (SpeculatedInstructions > 1)
3307 if (!IsSafeCheapLoadStore &&
3310 (SpeculatedStoreValue =
3313 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3319 if (!SpeculatedStore && SpeculatedStoreValue)
3325 for (Use &
Op :
I.operands()) {
3330 ++SinkCandidateUseCounts[OpI];
3337 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3338 if (Inst->hasNUses(
Count)) {
3339 ++SpeculatedInstructions;
3340 if (SpeculatedInstructions > 1)
3347 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3350 SpeculatedInstructions,
Cost,
TTI);
3351 if (!Convert ||
Cost > Budget)
3355 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3360 if (SpeculatedStoreValue) {
3364 Value *FalseV = SpeculatedStoreValue;
3368 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3398 for (DbgVariableRecord *DbgAssign :
3401 DbgAssign->replaceVariableLocationOp(OrigV, S);
3411 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3414 I.dropUBImplyingAttrsAndMetadata();
3417 if (EphTracker.contains(&
I)) {
3419 I.eraseFromParent();
3425 for (
auto &It : *ThenBB)
3430 !DVR || !DVR->isDbgAssign())
3431 It.dropOneDbgRecord(&DR);
3433 std::prev(ThenBB->end()));
3435 if (!SpeculatedConditionalLoadsStores.
empty())
3441 for (PHINode &PN : EndBB->
phis()) {
3442 unsigned OrigI = PN.getBasicBlockIndex(BB);
3443 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3444 Value *OrigV = PN.getIncomingValue(OrigI);
3445 Value *ThenV = PN.getIncomingValue(ThenI);
3454 Value *TrueV = ThenV, *FalseV = OrigV;
3459 BrCond, TrueV, FalseV, PN.getFastMathFlagsOrNone(),
"spec.select", BI);
3460 PN.setIncomingValue(OrigI, V);
3461 PN.setIncomingValue(ThenI, V);
3465 for (Instruction *
I : SpeculatedPseudoProbes)
3466 I->eraseFromParent();
3479 if (!ReachesNonLocalUses.
insert(BB).second)
3494 EphemeralValueTracker EphTracker;
3501 if (CI->cannotDuplicate() || CI->isConvergent())
3514 for (
User *U :
I.users()) {
3517 if (UsedInBB == BB) {
3521 NonLocalUseBlocks.
insert(UsedInBB);
3535 if (
I &&
I->getParent() == To)
3555 static constexpr unsigned MaxInstructionsToScan = 512;
3569 unsigned NumScannedInstructions = 0;
3570 while (!Worklist.
empty()) {
3574 if (!CanReachStop.
insert(BB).second)
3578 if (++NumScannedInstructions > MaxInstructionsToScan)
3582 BlocksWithUncontrolledConvergentCalls.
insert(BB);
3596 while (!Worklist.
empty()) {
3598 if (BB == StopBB || !CanReachStop.
contains(BB))
3601 if (!Visited.
insert(BB).second)
3604 if (BlocksWithUncontrolledConvergentCalls.
contains(BB))
3636 KnownValues[CB].
insert(Pred);
3640 if (KnownValues.
empty())
3665 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3668 for (
const auto &Pair : KnownValues) {
3685 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3698 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3701 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3711 EdgeBB->setName(RealDest->
getName() +
".critedge");
3712 EdgeBB->moveBefore(RealDest);
3722 TranslateMap[
Cond] = CB;
3735 N->insertInto(EdgeBB, InsertPt);
3738 N->setName(BBI->getName() +
".c");
3749 if (!BBI->use_empty())
3750 TranslateMap[&*BBI] = V;
3751 if (!
N->mayHaveSideEffects()) {
3752 N->eraseFromParent();
3757 if (!BBI->use_empty())
3758 TranslateMap[&*BBI] =
N;
3764 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3765 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3766 SrcDbgCursor = std::next(BBI);
3768 N->cloneDebugInfoFrom(&*BBI);
3777 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3778 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3779 InsertPt->cloneDebugInfoFrom(BI);
3800 return std::nullopt;
3806bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3813 std::optional<bool>
Result;
3814 bool EverChanged =
false;
3820 }
while (Result == std::nullopt);
3829 bool SpeculateUnpredictables) {
3851 return isa<UncondBrInst>(IfBlock->getTerminator());
3854 "Will have either one or two blocks to speculate.");
3861 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3862 if (!IsUnpredictable) {
3865 (TWeight + FWeight) != 0) {
3870 if (IfBlocks.
size() == 1) {
3872 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3873 if (BIBBProb >= Likely)
3876 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3885 if (IfCondPhiInst->getParent() == BB)
3893 unsigned NumPhis = 0;
3906 if (SpeculateUnpredictables && IsUnpredictable)
3907 Budget +=
TTI.getBranchMispredictPenalty();
3920 AggressiveInsts, Cost, Budget,
TTI, AC,
3921 ZeroCostInstructions) ||
3923 AggressiveInsts, Cost, Budget,
TTI, AC,
3924 ZeroCostInstructions))
3937 auto IsBinOpOrAndEq = [](
Value *V) {
3960 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3973 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3975 <<
" F: " << IfFalse->
getName() <<
"\n");
3992 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3997 PN->eraseFromParent();
4003 Builder.CreateBr(BB);
4024 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
4025 if (
Opc == Instruction::And)
4026 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
4027 if (
Opc == Instruction::Or)
4028 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
4040 bool PredHasWeights =
4042 bool SuccHasWeights =
4044 if (PredHasWeights || SuccHasWeights) {
4045 if (!PredHasWeights)
4046 PredTrueWeight = PredFalseWeight = 1;
4047 if (!SuccHasWeights)
4048 SuccTrueWeight = SuccFalseWeight = 1;
4058static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
4061 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
4063 "PredBB must be a predecessor of BB.");
4071 (PTWeight + PFWeight) != 0) {
4074 Likely =
TTI->getPredictableBranchThreshold();
4079 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4080 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4084 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4087 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4088 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4094 return std::nullopt;
4107 bool InvertPredCond;
4108 std::tie(CommonSucc,
Opc, InvertPredCond) =
4111 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4119 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4124 if (InvertPredCond) {
4137 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4140 SuccTrueWeight, SuccFalseWeight)) {
4146 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4151 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4152 PredTrueWeight * SuccFalseWeight);
4158 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4159 PredFalseWeight * SuccTrueWeight);
4161 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4203 if (!MDWeights.
empty()) {
4204 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4209 ++NumFoldBranchToCommonDest;
4216 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4217 return U->getType()->isVectorTy();
4228 unsigned BonusInstThreshold) {
4237 Cond->getParent() != BB || !
Cond->hasOneUse())
4258 bool InvertPredCond;
4260 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4292 unsigned NumBonusInsts = 0;
4293 bool SawVectorOp =
false;
4294 const unsigned PredCount = Preds.
size();
4298 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4318 NumBonusInsts += PredCount;
4326 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4329 return PN->getIncomingBlock(U) == BB;
4330 return UI->
getParent() == BB &&
I.comesBefore(UI);
4334 if (!
all_of(
I.uses(), IsBCSSAUse))
4338 BonusInstThreshold *
4354 for (
auto *BB : {BB1, BB2}) {
4370 Value *AlternativeV =
nullptr) {
4396 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4397 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4405 if (!AlternativeV &&
4411 PHI->addIncoming(V, BB);
4421 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4430 if (!PStore || !QStore)
4453 if (
I.mayReadOrWriteMemory())
4455 for (
auto &
I : *QFB)
4456 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4459 for (
auto &
I : *QTB)
4460 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4464 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4478 for (
auto &
I : *BB) {
4480 if (
I.isTerminator())
4498 "When we run out of budget we will eagerly return from within the "
4499 "per-instruction loop.");
4503 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4505 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4506 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4542 InvertPCond ^= (PStore->
getParent() != PTB);
4543 InvertQCond ^= (QStore->
getParent() != QTB);
4564 {CombinedWeights[0], CombinedWeights[1]},
4571 SI->copyMetadata(*QStore);
4577 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4580 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4643 bool InvertPCond =
false, InvertQCond =
false;
4649 if (QFB == PostBB) {
4668 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4671 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4679 for (
auto *BB : {PTB, PFB}) {
4684 PStoreAddresses.
insert(
SI->getPointerOperand());
4686 for (
auto *BB : {QTB, QFB}) {
4691 QStoreAddresses.
insert(
SI->getPointerOperand());
4697 auto &CommonAddresses = PStoreAddresses;
4700 for (
auto *Address : CommonAddresses)
4703 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4721 !BI->
getParent()->getSinglePredecessor())
4723 if (!IfFalseBB->
phis().empty())
4733 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4807 if (&*BB->
begin() != BI)
4835 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4837 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4841 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4844 if (CommonDestProb >= Likely)
4854 unsigned NumPhis = 0;
4876 if (OtherDest == BB) {
4884 OtherDest = InfLoopBlock;
4896 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4900 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4904 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4919 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4920 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4923 SuccTrueWeight, SuccFalseWeight);
4925 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4926 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4927 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4928 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4932 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4933 PredOther * SuccCommon,
4934 PredOther * SuccOther};
4942 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4944 assert(
SI->getCondition() == PBICond);
4961 Value *BIV = PN.getIncomingValueForBlock(BB);
4962 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4963 Value *PBIV = PN.getIncomingValue(PBBIdx);
4967 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4968 PN.setIncomingValue(PBBIdx, NV);
4972 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4973 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4993bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4995 BasicBlock *FalseBB,
4996 uint32_t TrueWeight,
4997 uint32_t FalseWeight) {
5004 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
5006 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
5009 for (BasicBlock *Succ :
successors(OldTerm)) {
5011 if (Succ == KeepEdge1)
5012 KeepEdge1 =
nullptr;
5013 else if (Succ == KeepEdge2)
5014 KeepEdge2 =
nullptr;
5019 if (Succ != TrueBB && Succ != FalseBB)
5020 RemovedSuccessors.
insert(Succ);
5028 if (!KeepEdge1 && !KeepEdge2) {
5029 if (TrueBB == FalseBB) {
5040 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
5060 SmallVector<DominatorTree::UpdateType, 2> Updates;
5062 for (
auto *RemovedSuccessor : RemovedSuccessors)
5063 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
5074bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
5079 if (!TrueVal || !FalseVal)
5084 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
5085 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5088 uint32_t TrueWeight = 0, FalseWeight = 0;
5089 SmallVector<uint64_t, 8> Weights;
5093 if (Weights.
size() == 1 +
SI->getNumCases()) {
5095 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5097 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5102 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5111bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5125 SmallVector<uint32_t> SelectBranchWeights(2);
5129 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5130 SelectBranchWeights[0],
5131 SelectBranchWeights[1]);
5151bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5155 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5201bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5220 ConstantInt *NewCaseVal;
5228 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5234 SelectTrueVal = Builder.
getTrue();
5235 SelectFalseVal = Builder.
getFalse();
5238 SelectCond =
Select->getCondition();
5240 if (SelectCond != ICI)
5242 SelectTrueVal =
Select->getTrueValue();
5243 SelectFalseVal =
Select->getFalseValue();
5248 if (
SI->getCondition() != IcmpCond)
5254 if (
SI->getDefaultDest() != BB) {
5255 ConstantInt *VVal =
SI->findCaseDest(BB);
5256 assert(VVal &&
"Should have a unique destination value");
5264 return requestResimplify();
5270 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5272 if (Predicate == ICmpInst::ICMP_EQ)
5280 return requestResimplify();
5287 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5293 Value *DefaultCst = SelectFalseVal;
5294 Value *NewCst = SelectTrueVal;
5302 Select->replaceAllUsesWith(DefaultCst);
5303 Select->eraseFromParent();
5309 SmallVector<DominatorTree::UpdateType, 2> Updates;
5316 SwitchInstProfUpdateWrapper SIW(*SI);
5317 auto W0 = SIW.getSuccessorWeight(0);
5321 SIW.setSuccessorWeight(0, *NewW);
5323 SIW.addCase(NewCaseVal, NewBB, NewW);
5325 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5334 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5342bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5344 const DataLayout &
DL) {
5354 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5356 SmallVectorImpl<ConstantInt *> &
Values = ConstantCompare.Vals;
5357 Value *CompVal = ConstantCompare.CompValue;
5358 unsigned UsedICmps = ConstantCompare.UsedICmps;
5359 Value *ExtraCase = ConstantCompare.Extra;
5360 bool TrueWhenEqual = ConstantCompare.IsEq;
5377 if (ExtraCase &&
Values.size() < 2)
5380 SmallVector<uint32_t> BranchWeights;
5387 if (!TrueWhenEqual) {
5390 std::swap(BranchWeights[0], BranchWeights[1]);
5396 <<
" cases into SWITCH. BB is:\n"
5399 SmallVector<DominatorTree::UpdateType, 2> Updates;
5406 nullptr,
"switch.early.test");
5417 AssumptionCache *AC =
Options.AC;
5423 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5430 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5436 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5437 <<
"\nEXTRABB = " << *BB);
5445 "Should not end up here with unstable pointers");
5447 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5452 if (
Values.front()->getValue() -
Values.back()->getValue() ==
5455 Values.back()->getValue(),
Values.front()->getValue() + 1);
5457 ICmpInst::Predicate Pred;
5475 SmallVector<uint32_t> NewWeights(
Values.size() + 1);
5476 NewWeights[0] = BranchWeights[1];
5479 V = BranchWeights[0] /
Values.size();
5484 for (ConstantInt *Val :
Values)
5485 New->addCase(Val, EdgeBB);
5493 for (
unsigned i = 0, e =
Values.size() - 1; i != e; ++i)
5503 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5507bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5509 return simplifyCommonResume(RI);
5513 return simplifySingleResume(RI);
5526 switch (IntrinsicID) {
5527 case Intrinsic::dbg_declare:
5528 case Intrinsic::dbg_value:
5529 case Intrinsic::dbg_label:
5530 case Intrinsic::lifetime_end:
5540bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5549 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5553 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5555 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5556 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5560 if (IncomingBB->getUniqueSuccessor() != BB)
5565 if (IncomingValue != LandingPad)
5569 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5570 TrivialUnwindBlocks.
insert(IncomingBB);
5574 if (TrivialUnwindBlocks.
empty())
5578 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5582 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5585 for (BasicBlock *Pred :
5596 TrivialBB->getTerminator()->eraseFromParent();
5597 new UnreachableInst(RI->
getContext(), TrivialBB);
5599 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5606 return !TrivialUnwindBlocks.empty();
5610bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5614 "Resume must unwind the exception that caused control to here");
5670 int Idx = DestPN.getBasicBlockIndex(BB);
5684 Value *SrcVal = DestPN.getIncomingValue(Idx);
5687 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5691 DestPN.addIncoming(Incoming, Pred);
5718 std::vector<DominatorTree::UpdateType> Updates;
5722 if (UnwindDest ==
nullptr) {
5763 if (!SuccessorCleanupPad)
5772 SuccessorCleanupPad->eraseFromParent();
5781bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5798bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5830 BBI->dropDbgRecords();
5834 BBI->eraseFromParent();
5840 if (&BB->
front() != UI)
5843 std::vector<DominatorTree::UpdateType> Updates;
5846 for (BasicBlock *Predecessor : Preds) {
5854 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5865 "The destinations are guaranteed to be different here.");
5866 CallInst *Assumption;
5882 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5884 SwitchInstProfUpdateWrapper SU(*SI);
5885 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5886 if (i->getCaseSuccessor() != BB) {
5891 i = SU.removeCase(i);
5896 if (DTU &&
SI->getDefaultDest() != BB)
5897 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5899 if (
II->getUnwindDest() == BB) {
5905 if (!CI->doesNotThrow())
5906 CI->setDoesNotThrow();
5910 if (CSI->getUnwindDest() == BB) {
5921 E = CSI->handler_end();
5924 CSI->removeHandler(
I);
5931 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5932 if (CSI->getNumHandlers() == 0) {
5933 if (CSI->hasUnwindDest()) {
5937 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5938 Updates.push_back({DominatorTree::Insert,
5939 PredecessorOfPredecessor,
5940 CSI->getUnwindDest()});
5941 Updates.push_back({DominatorTree::Delete,
5942 PredecessorOfPredecessor, Predecessor});
5945 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5952 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5953 for (BasicBlock *EHPred : EHPreds)
5957 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5958 CSI->eraseFromParent();
5963 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5964 "Expected to always have an unwind to BB.");
5966 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5994static std::optional<ContiguousCasesResult>
6001 const APInt &Min = Cases.
back()->getValue();
6002 const APInt &Max = Cases.
front()->getValue();
6004 size_t ContiguousOffset = Cases.
size() - 1;
6005 if (
Offset == ContiguousOffset) {
6024 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
6025 return L->getValue() != R->getValue() + 1;
6027 if (It == Cases.
end())
6028 return std::nullopt;
6029 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
6030 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
6034 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
6037 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
6045 return std::nullopt;
6050 bool RemoveOrigDefaultBlock =
true) {
6052 auto *BB = Switch->getParent();
6053 auto *OrigDefaultBlock = Switch->getDefaultDest();
6054 if (RemoveOrigDefaultBlock)
6055 OrigDefaultBlock->removePredecessor(BB);
6059 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
6061 Switch->setDefaultDest(&*NewDefaultBlock);
6065 if (RemoveOrigDefaultBlock &&
6075bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
6077 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6079 bool HasDefault = !
SI->defaultDestUnreachable();
6081 auto *BB =
SI->getParent();
6083 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6088 for (
auto Case :
SI->cases()) {
6092 if (Dest == DestA) {
6098 if (Dest == DestB) {
6108 "Single-destination switch should have been folded.");
6110 assert(DestB !=
SI->getDefaultDest());
6111 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6115 std::optional<ContiguousCasesResult> ContiguousCases;
6118 if (!HasDefault && CasesA.
size() == 1)
6119 ContiguousCases = ContiguousCasesResult{
6127 else if (CasesB.
size() == 1)
6128 ContiguousCases = ContiguousCasesResult{
6137 else if (!HasDefault)
6141 if (!ContiguousCases)
6145 if (!ContiguousCases)
6148 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6154 Max->getValue() - Min->getValue() + 1);
6157 assert(
Max->getValue() == Min->getValue());
6162 else if (NumCases->
isNullValue() && !Cases->empty()) {
6166 if (!
Offset->isNullValue())
6174 SmallVector<uint64_t, 8> Weights;
6176 if (Weights.
size() == 1 +
SI->getNumCases()) {
6179 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6180 if (
SI->getSuccessor(
I) == Dest)
6181 TrueWeight += Weights[
I];
6183 FalseWeight += Weights[
I];
6185 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6196 unsigned PreviousEdges = Cases->size();
6197 if (Dest ==
SI->getDefaultDest())
6199 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6200 PHI.removeIncomingValue(
SI->getParent());
6203 unsigned PreviousEdges = OtherCases->size();
6204 if (OtherDest ==
SI->getDefaultDest())
6206 unsigned E = PreviousEdges - 1;
6210 for (
unsigned I = 0;
I !=
E; ++
I)
6211 PHI.removeIncomingValue(
SI->getParent());
6215 SmallVector<DominatorTree::UpdateType, 2> Updates;
6219 Updates.
push_back({DominatorTree::Delete, BB, OrigDefaultBlock});
6223 SI->eraseFromParent();
6226 Updates.
push_back({DominatorTree::Delete, BB, OtherDest});
6246 unsigned MaxSignificantBitsInCond =
6253 for (
const auto &Case :
SI->cases()) {
6254 auto *
Successor = Case.getCaseSuccessor();
6263 if (
Known.Zero.intersects(CaseVal) || !
Known.One.isSubsetOf(CaseVal) ||
6265 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6271 }
else if (IsKnownValuesValid)
6272 KnownValues.
erase(CaseC);
6279 bool HasDefault = !
SI->defaultDestUnreachable();
6280 const unsigned NumUnknownBits =
6283 if (HasDefault && DeadCases.
empty()) {
6289 if (NumUnknownBits < 64 ) {
6290 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6291 if (
SI->getNumCases() == AllNumCases) {
6298 if (
SI->getNumCases() == AllNumCases - 1) {
6299 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6301 if (CondTy->getIntegerBitWidth() > 64 ||
6302 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6306 for (
const auto &Case :
SI->cases())
6307 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6309 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6311 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6321 if (DeadCases.
empty())
6327 assert(CaseI !=
SI->case_default() &&
6328 "Case was not found. Probably mistake in DeadCases forming.");
6330 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6335 std::vector<DominatorTree::UpdateType> Updates;
6336 for (
auto *
Successor : UniqueSuccessors)
6337 if (NumPerSuccessorCases[
Successor] == 0)
6364 int Idx =
PHI.getBasicBlockIndex(BB);
6365 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6367 Value *InValue =
PHI.getIncomingValue(Idx);
6368 if (InValue != CaseValue)
6384 ForwardingNodesMap ForwardingNodes;
6387 for (
const auto &Case :
SI->cases()) {
6389 BasicBlock *CaseDest = Case.getCaseSuccessor();
6408 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6409 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6410 count(Phi.blocks(), SwitchBlock) == 1) {
6411 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6419 ForwardingNodes[Phi].push_back(PhiIdx);
6422 for (
auto &ForwardingNode : ForwardingNodes) {
6423 PHINode *Phi = ForwardingNode.first;
6429 for (
int Index : Indexes)
6430 Phi->setIncomingValue(Index,
SI->getCondition());
6440 if (
C->isThreadDependent())
6442 if (
C->isDLLImportDependent())
6450 if (
C->getType()->isScalableTy())
6461 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6488 if (
A->isAllOnesValue())
6490 if (
A->isNullValue())
6496 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6521 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6523 if (
I.isTerminator()) {
6525 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6528 CaseDest =
I.getSuccessor(0);
6535 for (
auto &
Use :
I.uses()) {
6538 if (
I->getParent() == CaseDest)
6541 if (Phi->getIncomingBlock(
Use) == CaseDest)
6554 *CommonDest = CaseDest;
6556 if (CaseDest != *CommonDest)
6561 int Idx =
PHI.getBasicBlockIndex(Pred);
6574 Res.push_back(std::make_pair(&
PHI, ConstVal));
6577 return Res.
size() > 0;
6583 SwitchCaseResultVectorTy &UniqueResults,
6585 for (
auto &
I : UniqueResults) {
6586 if (
I.first == Result) {
6587 I.second.push_back(CaseVal);
6588 return I.second.size();
6591 UniqueResults.push_back(
6602 SwitchCaseResultVectorTy &UniqueResults,
6607 for (
const auto &
I :
SI->cases()) {
6621 const size_t NumCasesForResult =
6629 if (UniqueResults.size() > MaxUniqueResults)
6645 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6647 return DefaultResult ||
SI->defaultDestUnreachable();
6668 const bool HasBranchWeights =
6671 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6672 ResultVector[1].second.size() == 1) {
6673 ConstantInt *FirstCase = ResultVector[0].second[0];
6674 ConstantInt *SecondCase = ResultVector[1].second[0];
6675 Value *SelectValue = ResultVector[1].first;
6676 if (DefaultResult) {
6677 Value *ValueCompare =
6678 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6679 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6680 DefaultResult,
"switch.select");
6682 SI && HasBranchWeights) {
6689 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6693 Value *ValueCompare =
6694 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6695 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6696 SelectValue,
"switch.select");
6702 size_t FirstCasePos = (Condition !=
nullptr);
6703 size_t SecondCasePos = FirstCasePos + 1;
6704 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6706 {BranchWeights[FirstCasePos],
6707 DefaultCase + BranchWeights[SecondCasePos]},
6714 if (ResultVector.size() == 1 && DefaultResult) {
6716 unsigned CaseCount = CaseValues.
size();
6729 for (
auto *Case : CaseValues) {
6730 if (Case->getValue().slt(MinCaseVal->
getValue()))
6732 AndMask &= Case->getValue();
6736 if (!AndMask.
isZero() &&
Known.getMaxValue().uge(AndMask)) {
6738 unsigned FreeBits =
Known.countMaxActiveBits() - AndMask.
popcount();
6742 if (FreeBits ==
Log2_32(CaseCount)) {
6743 Value *
And = Builder.CreateAnd(Condition, AndMask);
6744 Value *Cmp = Builder.CreateICmpEQ(
6747 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6763 for (
auto *Case : CaseValues)
6764 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6770 Condition = Builder.CreateSub(Condition, MinCaseVal);
6771 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6772 Value *Cmp = Builder.CreateICmpEQ(
6775 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6788 if (CaseValues.
size() == 2) {
6789 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6790 "switch.selectcmp.case1");
6791 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6792 "switch.selectcmp.case2");
6793 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6795 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6815 std::vector<DominatorTree::UpdateType> Updates;
6822 Builder.CreateBr(DestBB);
6826 PHI->removeIncomingValueIf(
6827 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6828 PHI->addIncoming(SelectValue, SelectBB);
6831 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6837 if (DTU && RemovedSuccessors.
insert(Succ).second)
6840 SI->eraseFromParent();
6855 SwitchCaseResultVectorTy UniqueResults;
6861 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6862 Builder.SetInsertPoint(
SI);
6865 [[maybe_unused]]
auto HasWeights =
6870 (BranchWeights.
size() >=
6871 UniqueResults.size() + (DefaultResult !=
nullptr)));
6874 Builder,
DL, BranchWeights);
6886class SwitchReplacement {
6893 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
6894 Constant *DefaultValue,
const DataLayout &
DL,
6895 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
6904 static bool wouldFitInRegister(
const DataLayout &
DL,
uint64_t TableSize,
6911 bool isLookupTable();
6948 ConstantInt *BitMap =
nullptr;
6949 IntegerType *BitMapElementTy =
nullptr;
6952 ConstantInt *LinearOffset =
nullptr;
6953 ConstantInt *LinearMultiplier =
nullptr;
6954 bool LinearMapValWrapped =
false;
6962SwitchReplacement::SwitchReplacement(
6964 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
6965 Constant *DefaultValue,
const DataLayout &
DL,
6966 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
6967 : DefaultValue(DefaultValue) {
6968 assert(
Values.size() &&
"Can't build lookup table without values!");
6969 assert(TableSize >=
Values.size() &&
"Can't fit values in table!");
6972 SingleValue =
Values.begin()->second;
6978 for (
const auto &[CaseVal, CaseRes] :
Values) {
6981 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6982 TableContents[Idx] = CaseRes;
6989 if (
Values.size() < TableSize) {
6991 "Need a default value to fill the lookup table holes.");
6994 if (!TableContents[
I])
6995 TableContents[
I] = DefaultValue;
7001 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
7002 SingleValue =
nullptr;
7008 Kind = SingleValueKind;
7015 bool LinearMappingPossible =
true;
7020 bool NonMonotonic =
false;
7021 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
7038 LinearMappingPossible =
false;
7043 APInt Dist = Val - PrevVal;
7046 }
else if (Dist != DistToPrev) {
7047 LinearMappingPossible =
false;
7055 if (LinearMappingPossible) {
7057 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
7058 APInt M = LinearMultiplier->getValue();
7059 bool MayWrap =
true;
7060 if (
isIntN(M.getBitWidth(), TableSize - 1))
7061 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
7062 LinearMapValWrapped = NonMonotonic || MayWrap;
7063 Kind = LinearMapKind;
7069 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
7071 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
7073 TableInt <<=
IT->getBitWidth();
7077 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
7080 BitMap = ConstantInt::get(M.getContext(), TableInt);
7081 BitMapElementTy =
IT;
7092 unsigned NeededBitWidth =
7093 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7106 Kind = LookupTableKind;
7112 case SingleValueKind:
7114 case LinearMapKind: {
7118 false,
"switch.idx.cast");
7119 if (!LinearMultiplier->
isOne())
7120 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7122 !LinearMapValWrapped);
7124 if (!LinearOffset->
isZero())
7127 !LinearMapValWrapped);
7144 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7145 "switch.shiftamt",
true,
true);
7148 Value *DownShifted =
7149 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7151 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7153 case LookupTableKind: {
7156 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7157 true, GlobalVariable::PrivateLinkage,
7158 Initializer,
"switch.table." +
Func->getName());
7159 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7163 Type *IndexTy =
DL.getIndexType(
Table->getType());
7166 if (
Index->getType() != IndexTy) {
7167 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7171 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7174 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7178 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7187bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7189 Type *ElementType) {
7197 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7199 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7205 if (
TTI.isTypeLegal(Ty))
7220 DL.fitsInLegalInteger(
IT->getBitWidth());
7223Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7225bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7227bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7234 const uint64_t MinDensity = OptSize ? 40 : 10;
7239 return NumCases * 100 >= CaseRange * MinDensity;
7251static std::optional<unsigned>
7254 assert(
Values.size() > 1 &&
"expected multiple switch cases");
7256 return std::nullopt;
7261 for (
auto &V : ReducedValues) {
7263 ReducedValuesOr |= Reduced;
7264 V = (int64_t)Reduced;
7277 for (
auto &V : ReducedValues)
7278 V = (int64_t)((
uint64_t)V >> Shift);
7281 return std::nullopt;
7295 if (
SI->getNumCases() > TableSize)
7298 bool AllTablesFitInRegister =
true;
7299 bool HasIllegalType =
false;
7300 for (
const auto &Ty : ResultTypes) {
7305 AllTablesFitInRegister =
7306 AllTablesFitInRegister &&
7307 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7312 if (HasIllegalType && !AllTablesFitInRegister)
7317 if (AllTablesFitInRegister)
7325 SI->getFunction()->hasOptSize());
7335 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7338 return all_of(ResultTypes, [&](
const auto &ResultType) {
7339 return SwitchReplacement::wouldFitInRegister(
7389 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7394 for (
auto ValuePair :
Values) {
7397 if (!CaseConst || CaseConst == DefaultConst ||
7398 (CaseConst != TrueConst && CaseConst != FalseConst))
7412 if (DefaultConst == FalseConst) {
7415 ++NumTableCmpReuses;
7418 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7419 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7422 ++NumTableCmpReuses;
7432 bool ConvertSwitchToLookupTable) {
7433 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7447 if (
SI->getNumCases() < 3)
7469 MinCaseVal = CaseVal;
7471 MaxCaseVal = CaseVal;
7488 It->second.push_back(std::make_pair(CaseVal,
Value));
7496 bool HasDefaultResults =
7498 DefaultResultsList,
DL,
TTI);
7499 for (
const auto &
I : DefaultResultsList) {
7502 DefaultResults[
PHI] = Result;
7506 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7509 if (UseSwitchConditionAsTableIndex) {
7511 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7516 TableIndexOffset = MinCaseVal;
7523 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7525 bool TableHasHoles = (NumResults < TableSize);
7530 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7538 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7541 if (
SI->getNumCases() < 4)
7543 if (!
DL.fitsInLegalInteger(TableSize))
7552 if (UseSwitchConditionAsTableIndex) {
7553 TableIndex =
SI->getCondition();
7554 if (HasDefaultResults) {
7566 all_of(ResultTypes, [&](
const auto &ResultType) {
7567 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7572 TableSize = std::max(UpperBound, TableSize);
7575 DefaultIsReachable =
false;
7583 const auto &ResultList = ResultLists[
PHI];
7585 Type *ResultType = ResultList.begin()->second->getType();
7590 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7591 ResultList, DefaultVal,
DL,
TTI, FuncName);
7592 PhiToReplacementMap.
insert({
PHI, Replacement});
7595 bool AnyLookupTables =
any_of(
7596 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7597 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7598 [](
auto &KV) {
return KV.second.isBitMap(); });
7606 if (AnyLookupTables &&
7607 (!
TTI.shouldBuildLookupTables() ||
7613 if (!ConvertSwitchToLookupTable &&
7614 (AnyLookupTables || AnyBitMaps || NeedMask))
7617 Builder.SetInsertPoint(
SI);
7620 if (!UseSwitchConditionAsTableIndex) {
7623 bool MayWrap =
true;
7624 if (!DefaultIsReachable) {
7629 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7630 "switch.tableidx",
false,
7634 std::vector<DominatorTree::UpdateType> Updates;
7640 assert(MaxTableSize >= TableSize &&
7641 "It is impossible for a switch to have more entries than the max "
7642 "representable value of its input integer type's size.");
7647 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7652 Builder.SetInsertPoint(
SI);
7653 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7654 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7655 Builder.CreateBr(LookupBB);
7661 Value *Cmp = Builder.CreateICmpULT(
7662 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7664 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7665 CondBranch = RangeCheckBranch;
7671 Builder.SetInsertPoint(LookupBB);
7677 MaskBB->
setName(
"switch.hole_check");
7684 APInt MaskInt(TableSizePowOf2, 0);
7685 APInt One(TableSizePowOf2, 1);
7687 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7688 for (
const auto &Result : ResultList) {
7691 MaskInt |= One << Idx;
7693 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7700 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7701 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7702 Value *LoBit = Builder.CreateTrunc(
7704 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7709 Builder.SetInsertPoint(LookupBB);
7713 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7716 SI->getDefaultDest()->removePredecessor(BB,
7723 const ResultListTy &ResultList = ResultLists[
PHI];
7724 auto Replacement = PhiToReplacementMap.
at(
PHI);
7725 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7728 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7731 for (
auto *
User :
PHI->users()) {
7733 Replacement.getDefaultValue(), ResultList);
7737 PHI->addIncoming(Result, LookupBB);
7740 Builder.CreateBr(CommonDest);
7752 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7755 if (Succ ==
SI->getDefaultDest()) {
7756 if (HasBranchWeights)
7757 ToDefaultWeight += BranchWeights[
I];
7761 if (DTU && RemovedSuccessors.
insert(Succ).second)
7763 if (HasBranchWeights)
7764 ToLookupWeight += BranchWeights[
I];
7766 SI->eraseFromParent();
7767 if (HasBranchWeights)
7774 ++NumLookupTablesHoles;
7790 if (CondTy->getIntegerBitWidth() > 64 ||
7791 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7795 if (
SI->getNumCases() < 4)
7803 for (
const auto &
C :
SI->cases())
7804 Values.push_back(
C.getCaseValue()->getValue().getSExtValue());
7808 bool OptSize =
SI->getFunction()->hasOptSize();
7815 std::optional<unsigned> Shift;
7845 Builder.SetInsertPoint(
SI);
7849 Value *Rot = Builder.CreateIntrinsic(
7850 Ty, Intrinsic::fshl,
7851 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - *Shift)});
7852 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7854 for (
auto Case :
SI->cases()) {
7855 auto *Orig = Case.getCaseValue();
7856 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7901 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
7902 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
7919 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
7922 return !Updates.
empty();
7942 if (
SI->defaultDestUnreachable())
7953 if (!
Known.isConstant())
7960 ConstantInt::get(
SI->getContext(),
Known.getConstant());
7962 if (CaseIt ==
SI->case_default()) {
7971 SI->case_default());
7973 assert(
SI->getNumCases() > 0 &&
"Switch should have at least one case");
7974 assert(
SI->findCaseValue(CaseVal) !=
SI->case_default() &&
7975 "Proven value should have a dedicated case");
7976 assert(
SI->defaultDestUnreachable());
7994 Value *Condition =
SI->getCondition();
7998 if (CondTy->getIntegerBitWidth() > 64 ||
7999 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8011 if (
SI->getNumCases() < 4)
8016 for (
const auto &Case :
SI->cases()) {
8017 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
8019 Values.push_back(CaseValue);
8029 SI->getFunction()->hasOptSize()))
8033 Builder.SetInsertPoint(
SI);
8035 if (!
SI->defaultDestUnreachable()) {
8038 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
8039 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
8041 auto *OrigBB =
SI->getParent();
8042 auto *DefaultCaseBB =
SI->getDefaultDest();
8044 auto It = OrigBB->getTerminator()->getIterator();
8057 NewWeights[1] = Weights[0] / 2;
8058 NewWeights[0] = OrigDenominator - NewWeights[1];
8070 Weights[0] = NewWeights[1];
8071 uint64_t CasesDenominator = OrigDenominator - Weights[0];
8073 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
8079 It->eraseFromParent();
8087 for (
auto &Case :
SI->cases()) {
8088 auto *OrigValue = Case.getCaseValue();
8089 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
8090 OrigValue->getValue().countr_zero()));
8094 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
8097 SI->setCondition(ConditionTrailingZeros);
8107 if (!Cmp || !Cmp->hasOneUse())
8118 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
8121 if (
SI->getNumCases() == 2) {
8128 Succ =
SI->getDefaultDest();
8129 SuccWeight = Weights[0];
8131 for (
auto &Case :
SI->cases()) {
8132 std::optional<int64_t> Val =
8136 if (!Missing.erase(*Val))
8141 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
8144 assert(Missing.size() == 1 &&
"Should have one case left");
8145 Res = *Missing.begin();
8146 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
8148 Unreachable =
SI->getDefaultDest();
8150 for (
auto &Case :
SI->cases()) {
8151 BasicBlock *NewSucc = Case.getCaseSuccessor();
8152 uint32_t Weight = Weights[Case.getSuccessorIndex()];
8155 OtherSuccWeight += Weight;
8158 SuccWeight = Weight;
8159 }
else if (Succ == NewSucc) {
8165 for (
auto &Case :
SI->cases()) {
8166 std::optional<int64_t> Val =
8168 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8170 if (Case.getCaseSuccessor() == Succ) {
8192 if (Cmp->isSigned())
8195 MDNode *NewWeights =
nullptr;
8201 Builder.SetInsertPoint(
SI->getIterator());
8202 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
8203 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8204 SI->getMetadata(LLVMContext::MD_unpredictable));
8208 SI->eraseFromParent();
8209 Cmp->eraseFromParent();
8210 if (DTU && Unreachable)
8235 assert(
BB &&
"Expected non-null BB");
8237 if (
BB->isEntryBlock())
8250 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8255 if (&
BB->front() != &
BB->back())
8270 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8281 return (*EBW->PhiPredIVs)[&Phi][BB];
8303 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8306 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8307 return PredIVs[
A] == PredIVs[
B];
8316 if (Candidates.
size() < 2)
8331 assert(Succ &&
"Expected unconditional BB");
8341 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8344 for (
auto &
IV : Phi->incoming_values())
8345 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8363 bool MadeChange =
false;
8377 if (!LivePreds.
contains(PredOfDead))
8384 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8385 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8390 T->replaceSuccessorWith(
Dead, Live);
8395 for (
const auto &EBW : BBs2Merge) {
8398 const auto &[It, Inserted] =
Keep.insert(&EBW);
8407 if (KeepBB == DeadBB)
8411 RedirectIncomingEdges(DeadBB, KeepBB);
8420 if (DTU && !Updates.
empty())
8426bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8427 DomTreeUpdater *DTU) {
8429 SmallSetVector<BasicBlock *, 16> FilteredArms(
8435bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8436 DomTreeUpdater *DTU) {
8447 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8453bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8456 if (isValueEqualityComparison(SI)) {
8460 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8461 return requestResimplify();
8465 if (simplifySwitchOnSelect(SI,
Select))
8466 return requestResimplify();
8470 if (SI == &*BB->
begin())
8471 if (foldValueComparisonIntoPredecessors(SI, Builder))
8472 return requestResimplify();
8478 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8479 return requestResimplify();
8483 return requestResimplify();
8486 return requestResimplify();
8489 return requestResimplify();
8492 return requestResimplify();
8497 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8499 Options.ConvertSwitchToLookupTable))
8500 return requestResimplify();
8503 return requestResimplify();
8506 return requestResimplify();
8509 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8510 return requestResimplify();
8514 if (simplifyDuplicateSwitchArms(SI, DTU))
8515 return requestResimplify();
8518 return requestResimplify();
8521 return requestResimplify();
8526bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8529 SmallVector<uint32_t> BranchWeights;
8533 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8534 if (HasBranchWeights)
8539 SmallPtrSet<Value *, 8> Succs;
8540 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8545 RemovedSuccs.
insert(Dest);
8555 std::vector<DominatorTree::UpdateType> Updates;
8556 Updates.reserve(RemovedSuccs.
size());
8557 for (
auto *RemovedSucc : RemovedSuccs)
8558 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8575 if (HasBranchWeights) {
8582 if (simplifyIndirectBrOnSelect(IBI, SI))
8583 return requestResimplify();
8619 if (BB == OtherPred)
8630 std::vector<DominatorTree::UpdateType> Updates;
8637 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8638 "unexpected successor");
8639 II->setUnwindDest(OtherPred);
8654 Builder.CreateUnreachable();
8663bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8675 bool NeedCanonicalLoop =
8689 if (
I->isTerminator() &&
8690 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8714 if (!PPred || (PredPred && PredPred != PPred))
8755 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8759 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8789 bool HasWeight =
false;
8794 BBTWeight = BBFWeight = 1;
8799 BB1TWeight = BB1FWeight = 1;
8804 BB2TWeight = BB2FWeight = 1;
8806 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8807 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8814bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
8818 "Tautological conditional branch should have been eliminated already.");
8821 if (!
Options.SimplifyCondBranch ||
8826 if (isValueEqualityComparison(BI)) {
8831 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8832 return requestResimplify();
8836 for (
auto &
I : *BB) {
8841 if (foldValueComparisonIntoPredecessors(BI, Builder))
8842 return requestResimplify();
8848 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8861 return requestResimplify();
8867 if (
Options.SpeculateBlocks &&
8870 return requestResimplify();
8879 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8880 return requestResimplify();
8882 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8884 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8885 auto CanSpeculateConditionalLoadsStores = [&]() {
8887 for (Instruction &
I : *Succ) {
8888 if (
I.isTerminator()) {
8889 if (
I.getNumSuccessors() > 1)
8893 SpeculatedConditionalLoadsStores.
size() ==
8897 SpeculatedConditionalLoadsStores.
push_back(&
I);
8900 return !SpeculatedConditionalLoadsStores.
empty();
8903 if (CanSpeculateConditionalLoadsStores()) {
8905 std::nullopt,
nullptr);
8906 return requestResimplify();
8916 return requestResimplify();
8925 return requestResimplify();
8931 if (foldCondBranchOnValueKnownInPredecessor(BI))
8932 return requestResimplify();
8939 return requestResimplify();
8947 return requestResimplify();
8951 return requestResimplify();
8958 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8970 auto *Use = cast<Instruction>(U.getUser());
8973 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
8976 switch (Use->getOpcode()) {
8979 case Instruction::GetElementPtr:
8980 case Instruction::Ret:
8981 case Instruction::BitCast:
8982 case Instruction::Load:
8983 case Instruction::Store:
8984 case Instruction::Call:
8985 case Instruction::CallBr:
8986 case Instruction::Invoke:
8987 case Instruction::UDiv:
8988 case Instruction::URem:
8992 case Instruction::SDiv:
8993 case Instruction::SRem:
8997 if (FindUse ==
I->use_end())
8999 auto &
Use = *FindUse;
9013 if (
GEP->getPointerOperand() ==
I) {
9016 if (
GEP->getType()->isVectorTy())
9024 if (!
GEP->hasAllZeroIndices() &&
9025 (!
GEP->isInBounds() ||
9027 GEP->getPointerAddressSpace())))
9028 PtrValueMayBeModified =
true;
9034 bool HasNoUndefAttr =
9035 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
9040 if (
C->isNullValue() && HasNoUndefAttr &&
9041 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
9042 return !PtrValueMayBeModified;
9048 if (!LI->isVolatile())
9050 LI->getPointerAddressSpace());
9054 if (!
SI->isVolatile())
9056 SI->getPointerAddressSpace())) &&
9057 SI->getPointerOperand() ==
I;
9062 if (
I == Assume->getArgOperand(0))
9070 if (CB->getCalledOperand() ==
I)
9073 if (CB->isArgOperand(&
Use)) {
9074 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
9077 CB->paramHasNonNullAttr(ArgIdx,
false))
9078 return !PtrValueMayBeModified;
9097 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
9105 Builder.CreateUnreachable();
9106 T->eraseFromParent();
9118 Builder.CreateUnreachable();
9125 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
9127 Assumption = Builder.CreateAssumption(
Cond);
9142 Builder.SetInsertPoint(Unreachable);
9144 Builder.CreateUnreachable();
9145 for (
const auto &Case :
SI->cases())
9146 if (Case.getCaseSuccessor() == BB) {
9148 Case.setSuccessor(Unreachable);
9150 if (
SI->getDefaultDest() == BB) {
9152 SI->setDefaultDest(Unreachable);
9166bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9191 return requestResimplify();
9210 if (simplifyDuplicatePredecessors(BB, DTU))
9214 if (
Options.SpeculateBlocks &&
9221 Options.SpeculateUnpredictables))
9229 case Instruction::UncondBr:
9232 case Instruction::CondBr:
9235 case Instruction::Resume:
9238 case Instruction::CleanupRet:
9241 case Instruction::Switch:
9244 case Instruction::Unreachable:
9247 case Instruction::IndirectBr:
9255bool SimplifyCFGOpt::run(BasicBlock *BB) {
9265 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static bool IsIndirectCall(const MachineInstr *MI)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange, bool OptSize)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool isProfitableToSpeculate(const CondBrInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(CondBrInst *BI, CondBrInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool reachesUncontrolledConvergentCallBeforeBlock(BasicBlock *From, BasicBlock *StopBB)
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static void hoistConditionalLoadsStores(CondBrInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool simplifySwitchDefaultBranch(SwitchInst *SI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool extractPredSuccWeights(CondBrInst *PBI, CondBrInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static bool performBranchToCommonDestFolding(CondBrInst *BI, CondBrInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static std::optional< unsigned > getDenseSwitchRangeReductionShift(ArrayRef< int64_t > Values, int64_t Base, bool OptSize)
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool mergeConditionalStores(CondBrInst *PBI, CondBrInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeNestedCondBranch(CondBrInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool tryWidenCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool mergeIdenticalBBs(ArrayRef< BasicBlock * > Candidates, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static bool tryToMergeLandingPad(LandingPadInst *LPad, UncondBrInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool SimplifyCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isUncontrolledConvergentCall(CallBase *CB)
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, CondBrInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & front() const
Get the first element.
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isConvergent() const
Determine if the invoke is convergent.
Value * getConvergenceControlToken() const
Return the convergence control token for this call, if it exists.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
bool isEquality() const
Determine if this is an equals/not equals predicate.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Conditional Branch instruction.
static CondBrInst * Create(Value *Cond, BasicBlock *IfTrue, BasicBlock *IfFalse, InsertPosition InsertBefore=nullptr)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setCondition(Value *V)
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
ConstantFP - Floating Point Values [float, double].
ConstantFolder - Create constants with minimum, target independent, folding.
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
A constant pointer value that points to null.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Implements a dense probed hash-table based set.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
LLVM_ABI CallInst * CreateAssumption(Value *Cond)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
UncondBrInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getFalse()
Get the constant value for i1 false.