97#define DEBUG_TYPE "simplifycfg"
102 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
105 "Temporary development switch used to gradually uplift SimplifyCFG "
106 "into preserving DomTree,"));
115 "Control the amount of phi node folding to perform (default = 2)"));
119 cl::desc(
"Control the maximal total instruction cost that we are willing "
120 "to speculatively execute to fold a 2-entry PHI node into a "
121 "select (default = 4)"));
125 cl::desc(
"Hoist common instructions up to the parent block"));
129 cl::desc(
"Hoist loads if the target supports conditional faulting"));
133 cl::desc(
"Hoist stores if the target supports conditional faulting"));
137 cl::desc(
"Control the maximal conditional load/store that we are willing "
138 "to speculatively execute to eliminate conditional branch "
144 cl::desc(
"Allow reordering across at most this many "
145 "instructions when hoisting"));
149 cl::desc(
"Sink common instructions down to the end block"));
153 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
157 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
158 "precede - hoist multiple conditional stores into a single "
159 "predicated store"));
163 cl::desc(
"When merging conditional stores, do so even if the resultant "
164 "basic blocks are unlikely to be if-converted as a result"));
168 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
173 cl::desc(
"Limit maximum recursion depth when calculating costs of "
174 "speculatively executed instructions"));
179 cl::desc(
"Max size of a block which is still considered "
180 "small enough to thread through"));
186 cl::desc(
"Maximum cost of combining conditions when "
187 "folding branches"));
190 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
192 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
193 "to fold branch to common destination when vector operations are "
198 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
202 cl::desc(
"Limit cases to analyze when converting a switch to select"));
208STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
210 "Number of switch instructions turned into linear mapping");
212 "Number of switch instructions turned into lookup tables");
214 NumLookupTablesHoles,
215 "Number of switch instructions turned into lookup tables (holes checked)");
216STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
218 "Number of value comparisons folded into predecessor basic blocks");
220 "Number of branches folded into predecessor basic block");
223 "Number of common instruction 'blocks' hoisted up to the begin block");
225 "Number of common instructions hoisted up to the begin block");
227 "Number of common instruction 'blocks' sunk down to the end block");
229 "Number of common instructions sunk down to the end block");
230STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
232 "Number of invokes with empty resume blocks simplified into calls");
233STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
234STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
241using SwitchCaseResultVectorTy =
250struct ValueEqualityComparisonCase {
262 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
265class SimplifyCFGOpt {
266 const TargetTransformInfo &TTI;
268 const DataLayout &DL;
270 const SimplifyCFGOptions &Options;
273 Value *isValueEqualityComparison(Instruction *TI);
275 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
276 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
279 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
282 bool foldValueComparisonIntoPredecessors(Instruction *TI,
285 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
286 bool simplifySingleResume(ResumeInst *RI);
287 bool simplifyCommonResume(ResumeInst *RI);
288 bool simplifyCleanupReturn(CleanupReturnInst *RI);
289 bool simplifyUnreachable(UnreachableInst *UI);
290 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
291 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
292 bool simplifyIndirectBr(IndirectBrInst *IBI);
293 bool simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
294 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
295 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
297 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
299 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
302 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
303 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
304 Instruction *TI, Instruction *I1,
305 SmallVectorImpl<Instruction *> &OtherSuccTIs,
307 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
308 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
309 BasicBlock *TrueBB, BasicBlock *FalseBB,
310 uint32_t TrueWeight, uint32_t FalseWeight);
311 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
312 const DataLayout &DL);
313 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
314 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
315 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
316 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
319 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
321 const SimplifyCFGOptions &Opts)
322 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
323 assert((!DTU || !DTU->hasPostDomTree()) &&
324 "SimplifyCFG is not yet capable of maintaining validity of a "
325 "PostDomTree, so don't ask for it.");
328 bool simplifyOnce(BasicBlock *BB);
329 bool run(BasicBlock *BB);
332 bool requestResimplify() {
342isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
362 "Only for a pair of incoming blocks at the time!");
368 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
369 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
372 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
373 EquivalenceSet->contains(IV1))
396 if (!SI1Succs.
count(Succ))
402 FailBlocks->insert(Succ);
418 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
420 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
421 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
483 if (AggressiveInsts.
count(
I))
499 ZeroCostInstructions.
insert(OverflowInst);
501 }
else if (!ZeroCostInstructions.
contains(
I))
517 for (
Use &
Op :
I->operands())
519 TTI, AC, ZeroCostInstructions,
Depth + 1))
536 if (
DL.hasUnstableRepresentation(V->getType()))
545 return ConstantInt::get(IntPtrTy, 0);
550 if (CE->getOpcode() == Instruction::IntToPtr)
574struct ConstantComparesGatherer {
575 const DataLayout &DL;
578 Value *CompValue =
nullptr;
581 Value *Extra =
nullptr;
587 unsigned UsedICmps = 0;
593 bool IgnoreFirstMatch =
false;
594 bool MultipleMatches =
false;
597 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
599 if (CompValue || !MultipleMatches)
604 IgnoreFirstMatch =
true;
608 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
609 ConstantComparesGatherer &
610 operator=(
const ConstantComparesGatherer &) =
delete;
615 bool setValueOnce(
Value *NewVal) {
616 if (IgnoreFirstMatch) {
617 IgnoreFirstMatch =
false;
620 if (CompValue && CompValue != NewVal) {
621 MultipleMatches =
true;
635 bool matchInstruction(Instruction *
I,
bool isEQ) {
642 if (!setValueOnce(Val))
662 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
706 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
708 if (!setValueOnce(RHSVal))
713 ConstantInt::get(
C->getContext(),
714 C->getValue() | Mask));
729 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
731 if (!setValueOnce(RHSVal))
735 Vals.push_back(ConstantInt::get(
C->getContext(),
736 C->getValue() & ~Mask));
757 Value *CandidateVal =
I->getOperand(0);
760 CandidateVal = RHSVal;
775 if (!setValueOnce(CandidateVal))
781 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
793 void gather(
Value *V) {
802 SmallVector<Value *, 8> DFT{Op0, Op1};
803 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
805 while (!DFT.
empty()) {
812 if (Visited.
insert(Op1).second)
814 if (Visited.
insert(Op0).second)
821 if (matchInstruction(
I, IsEq))
865 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
866 CV =
SI->getCondition();
868 if (BI->getCondition()->hasOneUse()) {
873 if (Trunc->hasNoUnsignedWrap())
874 CV = Trunc->getOperand(0);
881 Value *Ptr = PTII->getPointerOperand();
882 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
884 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
893BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
894 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
896 Cases.reserve(
SI->getNumCases());
897 for (
auto Case :
SI->cases())
898 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
899 Case.getCaseSuccessor()));
900 return SI->getDefaultDest();
905 ICmpInst::Predicate Pred;
911 Pred = ICmpInst::ICMP_NE;
916 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
924 std::vector<ValueEqualityComparisonCase> &Cases) {
930 std::vector<ValueEqualityComparisonCase> &C2) {
931 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
934 if (V1->size() > V2->size())
939 if (V1->size() == 1) {
942 for (
const ValueEqualityComparisonCase &
VECC : *V2)
943 if (TheVal ==
VECC.Value)
950 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
951 while (i1 != e1 && i2 != e2) {
967bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
968 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
973 Value *ThisVal = isValueEqualityComparison(TI);
974 assert(ThisVal &&
"This isn't a value comparison!!");
975 if (ThisVal != PredVal)
982 std::vector<ValueEqualityComparisonCase> PredCases;
984 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
988 std::vector<ValueEqualityComparisonCase> ThisCases;
989 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1004 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1010 ThisCases[0].Dest->removePredecessor(PredDef);
1013 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1020 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1027 SmallPtrSet<Constant *, 16> DeadCases;
1028 for (
const ValueEqualityComparisonCase &Case : PredCases)
1029 DeadCases.
insert(Case.Value);
1032 <<
"Through successor TI: " << *TI);
1034 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1037 auto *
Successor = i->getCaseSuccessor();
1040 if (DeadCases.
count(i->getCaseValue())) {
1049 std::vector<DominatorTree::UpdateType> Updates;
1050 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1052 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1062 ConstantInt *TIV =
nullptr;
1064 for (
const auto &[
Value, Dest] : PredCases)
1070 assert(TIV &&
"No edge from pred to succ?");
1075 for (
const auto &[
Value, Dest] : ThisCases)
1083 TheRealDest = ThisDef;
1085 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1090 if (Succ != CheckEdge) {
1091 if (Succ != TheRealDest)
1092 RemovedSuccs.
insert(Succ);
1095 CheckEdge =
nullptr;
1102 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1107 SmallVector<DominatorTree::UpdateType, 2> Updates;
1109 for (
auto *RemovedSucc : RemovedSuccs)
1110 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1121struct ConstantIntOrdering {
1122 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1123 return LHS->getValue().ult(
RHS->getValue());
1135 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1144 assert(MD &&
"Invalid branch-weight metadata");
1169 if (BonusInst.isTerminator())
1199 NewBonusInst->
takeName(&BonusInst);
1200 BonusInst.setName(NewBonusInst->
getName() +
".old");
1201 VMap[&BonusInst] = NewBonusInst;
1210 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1211 "If the user is not a PHI node, then it should be in the same "
1212 "block as, and come after, the original bonus instruction.");
1216 if (PN->getIncomingBlock(U) == BB)
1220 assert(PN->getIncomingBlock(U) == PredBlock &&
1221 "Not in block-closed SSA form?");
1222 U.set(NewBonusInst);
1232 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1233 PredDL.isSameSourceLocation(
DL)) {
1240bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1248 std::vector<ValueEqualityComparisonCase> BBCases;
1249 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1251 std::vector<ValueEqualityComparisonCase> PredCases;
1252 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1257 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1260 SmallVector<uint64_t, 8> Weights;
1264 if (PredHasWeights) {
1267 if (Weights.
size() != 1 + PredCases.size())
1268 PredHasWeights = SuccHasWeights =
false;
1269 }
else if (SuccHasWeights)
1273 Weights.
assign(1 + PredCases.size(), 1);
1275 SmallVector<uint64_t, 8> SuccWeights;
1276 if (SuccHasWeights) {
1279 if (SuccWeights.
size() != 1 + BBCases.size())
1280 PredHasWeights = SuccHasWeights =
false;
1281 }
else if (PredHasWeights)
1282 SuccWeights.
assign(1 + BBCases.size(), 1);
1284 if (PredDefault == BB) {
1287 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1288 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1289 if (PredCases[i].Dest != BB)
1290 PTIHandled.insert(PredCases[i].
Value);
1293 std::swap(PredCases[i], PredCases.back());
1295 if (PredHasWeights || SuccHasWeights) {
1297 Weights[0] += Weights[i + 1];
1302 PredCases.pop_back();
1308 if (PredDefault != BBDefault) {
1310 if (DTU && PredDefault != BB)
1311 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1312 PredDefault = BBDefault;
1313 ++NewSuccessors[BBDefault];
1316 unsigned CasesFromPred = Weights.
size();
1317 uint64_t ValidTotalSuccWeight = 0;
1318 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1319 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1320 PredCases.push_back(BBCases[i]);
1321 ++NewSuccessors[BBCases[i].Dest];
1322 if (SuccHasWeights || PredHasWeights) {
1326 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1327 ValidTotalSuccWeight += SuccWeights[i + 1];
1331 if (SuccHasWeights || PredHasWeights) {
1332 ValidTotalSuccWeight += SuccWeights[0];
1334 for (
unsigned i = 1; i < CasesFromPred; ++i)
1335 Weights[i] *= ValidTotalSuccWeight;
1337 Weights[0] *= SuccWeights[0];
1343 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1344 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1345 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1346 if (PredCases[i].Dest == BB) {
1347 PTIHandled.insert(PredCases[i].
Value);
1349 if (PredHasWeights || SuccHasWeights) {
1350 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1355 std::swap(PredCases[i], PredCases.back());
1356 PredCases.pop_back();
1363 for (
const ValueEqualityComparisonCase &Case : BBCases)
1364 if (PTIHandled.count(Case.Value)) {
1366 if (PredHasWeights || SuccHasWeights)
1367 Weights.
push_back(WeightsForHandled[Case.Value]);
1368 PredCases.push_back(Case);
1369 ++NewSuccessors[Case.Dest];
1370 PTIHandled.erase(Case.Value);
1375 for (ConstantInt *
I : PTIHandled) {
1376 if (PredHasWeights || SuccHasWeights)
1378 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1379 ++NewSuccessors[BBDefault];
1386 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1391 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1393 for (
auto I :
seq(NewSuccessor.second)) {
1397 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1398 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1405 "Should not end up here with unstable pointers");
1411 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1413 for (ValueEqualityComparisonCase &V : PredCases)
1416 if (PredHasWeights || SuccHasWeights)
1428 if (!InfLoopBlock) {
1436 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1443 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1445 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1450 ++NumFoldValueComparisonIntoPredecessors;
1458bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1461 Value *CV = isValueEqualityComparison(TI);
1462 assert(CV &&
"Not a comparison?");
1467 while (!Preds.empty()) {
1476 Value *PCV = isValueEqualityComparison(PTI);
1480 SmallSetVector<BasicBlock *, 4> FailBlocks;
1482 for (
auto *Succ : FailBlocks) {
1488 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1502 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1503 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1504 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1523 if (
I->mayReadFromMemory())
1555 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1563 if (J->getParent() == BB)
1585 if (C1->isMustTailCall() != C2->isMustTailCall())
1588 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1594 if (CB1->cannotMerge() || CB1->isConvergent())
1597 if (CB2->cannotMerge() || CB2->isConvergent())
1612 if (!I1->hasDbgRecords())
1614 using CurrentAndEndIt =
1615 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1621 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1622 return Pair.first == Pair.second;
1628 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1634 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1636 if (!
Other->hasDbgRecords())
1639 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1646 while (
none_of(Itrs, atEnd)) {
1647 bool HoistDVRs = allIdentical(Itrs);
1648 for (CurrentAndEndIt &Pair : Itrs) {
1662 if (I1->isIdenticalToWhenDefined(I2,
true))
1667 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1668 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1669 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1671 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1672 return I1->getOperand(0) == I2->
getOperand(1) &&
1738 auto &Context = BI->getParent()->getContext();
1743 Value *Mask =
nullptr;
1744 Value *MaskFalse =
nullptr;
1745 Value *MaskTrue =
nullptr;
1746 if (Invert.has_value()) {
1747 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1748 Mask = Builder.CreateBitCast(
1753 MaskFalse = Builder.CreateBitCast(
1755 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1757 auto PeekThroughBitcasts = [](
Value *V) {
1759 V = BitCast->getOperand(0);
1762 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1764 if (!Invert.has_value())
1765 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1770 auto *Op0 =
I->getOperand(0);
1771 CallInst *MaskedLoadStore =
nullptr;
1774 auto *Ty =
I->getType();
1776 Value *PassThru =
nullptr;
1777 if (Invert.has_value())
1778 for (
User *U :
I->users()) {
1780 PassThru = Builder.CreateBitCast(
1789 Builder.SetInsertPoint(Ins);
1792 MaskedLoadStore = Builder.CreateMaskedLoad(
1794 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1797 I->replaceAllUsesWith(NewLoadStore);
1800 auto *StoredVal = Builder.CreateBitCast(
1802 MaskedLoadStore = Builder.CreateMaskedStore(
1813 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1815 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1819 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1820 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1823 I->eraseFromParent();
1830 bool IsStore =
false;
1853bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1854 bool AllInstsEqOnly) {
1870 for (
auto *Succ : UniqueSuccessors) {
1886 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1888 for (
auto *Succ : UniqueSuccessors) {
1892 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1895 if (AllInstsEqOnly) {
1901 unsigned Size0 = UniqueSuccessors[0]->size();
1902 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1906 Succ->
size() == Size0;
1910 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1911 while (LRI.isValid()) {
1913 if (
any_of(*LRI, [I0](Instruction *
I) {
1927 unsigned NumSkipped = 0;
1930 if (SuccIterPairs.
size() > 2) {
1933 if (SuccIterPairs.
size() < 2)
1940 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1941 auto &BB1ItrPair = *SuccIterPairBegin++;
1942 auto OtherSuccIterPairRange =
1948 bool AllInstsAreIdentical =
true;
1949 bool HasTerminator =
I1->isTerminator();
1950 for (
auto &SuccIter : OtherSuccIterRange) {
1954 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1955 AllInstsAreIdentical =
false;
1958 SmallVector<Instruction *, 8> OtherInsts;
1959 for (
auto &SuccIter : OtherSuccIterRange)
1964 if (HasTerminator) {
1968 if (NumSkipped || !AllInstsAreIdentical) {
1973 return hoistSuccIdenticalTerminatorToSwitchOrIf(
1974 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
1978 if (AllInstsAreIdentical) {
1979 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1980 AllInstsAreIdentical =
1982 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1984 unsigned SkipFlagsBB2 = Pair.second;
1994 if (AllInstsAreIdentical) {
2004 for (
auto &SuccIter : OtherSuccIterRange) {
2012 assert(
Success &&
"We should not be trying to hoist callbases "
2013 "with non-intersectable attributes");
2025 NumHoistCommonCode += SuccIterPairs.
size();
2027 NumHoistCommonInstrs += SuccIterPairs.
size();
2036 for (
auto &SuccIterPair : SuccIterPairs) {
2045bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2046 Instruction *TI, Instruction *I1,
2047 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2057 auto *I2 = *OtherSuccTIs.
begin();
2077 for (PHINode &PN : Succ->
phis()) {
2078 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2079 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2080 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2100 if (!
NT->getType()->isVoidTy()) {
2101 I1->replaceAllUsesWith(NT);
2102 for (Instruction *OtherSuccTI : OtherSuccTIs)
2103 OtherSuccTI->replaceAllUsesWith(NT);
2107 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2113 for (
auto *OtherSuccTI : OtherSuccTIs)
2114 Locs.
push_back(OtherSuccTI->getDebugLoc());
2126 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2128 for (PHINode &PN : Succ->
phis()) {
2129 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2130 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2136 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2146 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2147 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2148 PN.setIncomingValue(i, SI);
2159 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2165 for (BasicBlock *Succ : UniqueSuccessors)
2166 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2180 if (
I->isIntDivRem())
2195 std::optional<unsigned> NumUses;
2196 for (
auto *
I : Insts) {
2199 I->getType()->isTokenTy())
2204 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2212 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2216 NumUses =
I->getNumUses();
2217 else if (NumUses !=
I->getNumUses())
2223 for (
auto *
I : Insts) {
2237 for (
const Use &U : I0->
uses()) {
2238 auto It = PHIOperands.find(&U);
2239 if (It == PHIOperands.end())
2242 if (!
equal(Insts, It->second))
2256 if (HaveIndirectCalls) {
2257 if (!AllCallsAreIndirect)
2261 Value *Callee =
nullptr;
2265 Callee = CurrCallee;
2266 else if (Callee != CurrCallee)
2272 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2278 if (!
all_of(Insts, SameAsI0)) {
2284 for (
auto *
I : Insts)
2285 Ops.push_back(
I->getOperand(OI));
2295 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2300 for (
auto *BB : Blocks) {
2302 I =
I->getPrevNode();
2327 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2330 PN->insertBefore(BBEnd->begin());
2331 for (
auto *
I : Insts)
2332 PN->addIncoming(
I->getOperand(O),
I->getParent());
2341 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2344 for (
auto *
I : Insts)
2358 assert(
Success &&
"We should not be trying to sink callbases "
2359 "with non-intersectable attributes");
2370 PN->replaceAllUsesWith(I0);
2371 PN->eraseFromParent();
2375 for (
auto *
I : Insts) {
2380 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2381 I->replaceAllUsesWith(I0);
2382 I->eraseFromParent();
2432 bool HaveNonUnconditionalPredecessors =
false;
2438 HaveNonUnconditionalPredecessors =
true;
2440 if (UnconditionalPreds.
size() < 2)
2453 for (
const Use &U : PN.incoming_values())
2454 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2455 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2457 Ops.push_back(*IncomingVals[Pred]);
2465 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2478 if (!followedByDeoptOrUnreachable) {
2480 auto IsMemOperand = [](
Use &U) {
2493 unsigned NumPHIInsts = 0;
2494 for (
Use &U : (*LRI)[0]->operands()) {
2495 auto It = PHIOperands.
find(&U);
2496 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2497 return InstructionsToSink.contains(V);
2504 if (IsMemOperand(U) &&
2505 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2512 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2513 return NumPHIInsts <= 1;
2530 while (Idx < ScanIdx) {
2531 if (!ProfitableToSinkInstruction(LRI)) {
2534 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2547 if (Idx < ScanIdx) {
2550 InstructionsToSink = InstructionsProfitableToSink;
2556 !ProfitableToSinkInstruction(LRI) &&
2557 "We already know that the last instruction is unprofitable to sink");
2565 for (
auto *
I : *LRI)
2566 InstructionsProfitableToSink.
erase(
I);
2567 if (!ProfitableToSinkInstruction(LRI)) {
2570 InstructionsToSink = InstructionsProfitableToSink;
2584 if (HaveNonUnconditionalPredecessors) {
2585 if (!followedByDeoptOrUnreachable) {
2593 bool Profitable =
false;
2594 while (Idx < ScanIdx) {
2628 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2630 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2638 NumSinkCommonInstrs++;
2642 ++NumSinkCommonCode;
2648struct CompatibleSets {
2649 using SetTy = SmallVector<InvokeInst *, 2>;
2655 SetTy &getCompatibleSet(InvokeInst *
II);
2657 void insert(InvokeInst *
II);
2660CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2665 for (CompatibleSets::SetTy &Set : Sets) {
2666 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2671 return Sets.emplace_back();
2674void CompatibleSets::insert(InvokeInst *
II) {
2675 getCompatibleSet(
II).emplace_back(
II);
2679 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2682 auto IsIllegalToMerge = [](InvokeInst *
II) {
2683 return II->cannotMerge() ||
II->isInlineAsm();
2685 if (
any_of(Invokes, IsIllegalToMerge))
2693 if (HaveIndirectCalls) {
2694 if (!AllCallsAreIndirect)
2699 for (InvokeInst *
II : Invokes) {
2700 Value *CurrCallee =
II->getCalledOperand();
2701 assert(CurrCallee &&
"There is always a called operand.");
2704 else if (Callee != CurrCallee)
2711 auto HasNormalDest = [](InvokeInst *
II) {
2714 if (
any_of(Invokes, HasNormalDest)) {
2717 if (!
all_of(Invokes, HasNormalDest))
2722 for (InvokeInst *
II : Invokes) {
2724 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2726 NormalBB = CurrNormalBB;
2727 else if (NormalBB != CurrNormalBB)
2735 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2744 for (InvokeInst *
II : Invokes) {
2746 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2748 UnwindBB = CurrUnwindBB;
2750 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2757 Invokes.front()->getUnwindDest(),
2758 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2763 const InvokeInst *II0 = Invokes.front();
2764 for (
auto *
II : Invokes.drop_front())
2769 auto IsIllegalToMergeArguments = [](
auto Ops) {
2770 Use &U0 = std::get<0>(
Ops);
2771 Use &U1 = std::get<1>(
Ops);
2777 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2778 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2779 IsIllegalToMergeArguments))
2791 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2797 bool HasNormalDest =
2802 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2806 II0->
getParent()->getIterator()->getNextNode();
2811 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2815 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2817 if (!HasNormalDest) {
2821 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2829 return MergedInvoke;
2843 SuccBBOfMergedInvoke});
2866 return II->getOperand(U.getOperandNo()) != U.get();
2885 Invokes.
front()->getParent());
2893 if (!MergedDebugLoc)
2894 MergedDebugLoc =
II->getDebugLoc();
2902 OrigSuccBB->removePredecessor(
II->getParent());
2906 BI->setDebugLoc(
II->getDebugLoc());
2908 assert(
Success &&
"Merged invokes with incompatible attributes");
2911 II->replaceAllUsesWith(MergedInvoke);
2912 II->eraseFromParent();
2916 ++NumInvokeSetsFormed;
2952 CompatibleSets Grouper;
2962 if (Invokes.
size() < 2)
2974class EphemeralValueTracker {
2975 SmallPtrSet<const Instruction *, 32> EphValues;
2977 bool isEphemeral(
const Instruction *
I) {
2980 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2981 all_of(
I->users(), [&](
const User *U) {
2982 return EphValues.count(cast<Instruction>(U));
2987 bool track(
const Instruction *
I) {
2988 if (isEphemeral(
I)) {
3039 unsigned MaxNumInstToLookAt = 9;
3043 if (!MaxNumInstToLookAt)
3045 --MaxNumInstToLookAt;
3058 if (
SI->getPointerOperand() == StorePtr &&
3059 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3062 return SI->getValueOperand();
3067 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3068 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3070 bool ExplicitlyDereferenceableOnly;
3075 (!ExplicitlyDereferenceableOnly ||
3077 LI->getDataLayout()))) {
3093 unsigned &SpeculatedInstructions,
3101 bool HaveRewritablePHIs =
false;
3103 Value *OrigV = PN.getIncomingValueForBlock(BB);
3104 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3111 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3120 HaveRewritablePHIs =
true;
3123 if (!OrigCE && !ThenCE)
3130 if (OrigCost + ThenCost > MaxCost)
3137 ++SpeculatedInstructions;
3138 if (SpeculatedInstructions > 1)
3142 return HaveRewritablePHIs;
3146 std::optional<bool> Invert,
3150 if (BI->getMetadata(LLVMContext::MD_unpredictable))
3157 if (!Invert.has_value())
3160 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3164 return BIEndProb < Likely;
3204bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3205 BasicBlock *ThenBB) {
3221 bool Invert =
false;
3236 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3238 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3240 unsigned SpeculatedInstructions = 0;
3241 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3242 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3243 Value *SpeculatedStoreValue =
nullptr;
3244 StoreInst *SpeculatedStore =
nullptr;
3245 EphemeralValueTracker EphTracker;
3260 if (EphTracker.track(&
I))
3265 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3267 SpeculatedConditionalLoadsStores.
size() <
3271 if (IsSafeCheapLoadStore)
3272 SpeculatedConditionalLoadsStores.
push_back(&
I);
3274 ++SpeculatedInstructions;
3276 if (SpeculatedInstructions > 1)
3280 if (!IsSafeCheapLoadStore &&
3283 (SpeculatedStoreValue =
3286 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3292 if (!SpeculatedStore && SpeculatedStoreValue)
3298 for (Use &
Op :
I.operands()) {
3303 ++SinkCandidateUseCounts[OpI];
3310 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3311 if (Inst->hasNUses(
Count)) {
3312 ++SpeculatedInstructions;
3313 if (SpeculatedInstructions > 1)
3320 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3323 SpeculatedInstructions,
Cost,
TTI);
3324 if (!Convert ||
Cost > Budget)
3328 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3332 if (SpeculatedStoreValue) {
3336 Value *FalseV = SpeculatedStoreValue;
3340 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3370 for (DbgVariableRecord *DbgAssign :
3373 DbgAssign->replaceVariableLocationOp(OrigV, S);
3383 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3386 I.dropUBImplyingAttrsAndMetadata();
3389 if (EphTracker.contains(&
I)) {
3391 I.eraseFromParent();
3397 for (
auto &It : *ThenBB)
3402 !DVR || !DVR->isDbgAssign())
3403 It.dropOneDbgRecord(&DR);
3404 BB->
splice(BI->getIterator(), ThenBB, ThenBB->begin(),
3405 std::prev(ThenBB->end()));
3407 if (!SpeculatedConditionalLoadsStores.
empty())
3413 for (PHINode &PN : EndBB->
phis()) {
3414 unsigned OrigI = PN.getBasicBlockIndex(BB);
3415 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3416 Value *OrigV = PN.getIncomingValue(OrigI);
3417 Value *ThenV = PN.getIncomingValue(ThenI);
3426 Value *TrueV = ThenV, *FalseV = OrigV;
3430 PN.setIncomingValue(OrigI, V);
3431 PN.setIncomingValue(ThenI, V);
3435 for (Instruction *
I : SpeculatedPseudoProbes)
3436 I->eraseFromParent();
3445 EphemeralValueTracker EphTracker;
3452 if (CI->cannotDuplicate() || CI->isConvergent())
3465 for (
User *U :
I.users()) {
3482 if (
I &&
I->getParent() == To)
3498static std::optional<bool>
3519 KnownValues[CB].
insert(Pred);
3523 if (KnownValues.
empty())
3532 for (
const auto &Pair : KnownValues) {
3550 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3553 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3563 EdgeBB->setName(RealDest->
getName() +
".critedge");
3564 EdgeBB->moveBefore(RealDest);
3574 TranslateMap[
Cond] = CB;
3587 N->insertInto(EdgeBB, InsertPt);
3590 N->setName(BBI->getName() +
".c");
3601 if (!BBI->use_empty())
3602 TranslateMap[&*BBI] = V;
3603 if (!
N->mayHaveSideEffects()) {
3604 N->eraseFromParent();
3609 if (!BBI->use_empty())
3610 TranslateMap[&*BBI] =
N;
3616 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3617 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3618 SrcDbgCursor = std::next(BBI);
3620 N->cloneDebugInfoFrom(&*BBI);
3629 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3630 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3631 InsertPt->cloneDebugInfoFrom(BI);
3636 EdgeBI->setDebugLoc(BI->getDebugLoc());
3652 return std::nullopt;
3658bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3665 std::optional<bool>
Result;
3666 bool EverChanged =
false;
3672 }
while (Result == std::nullopt);
3681 bool SpeculateUnpredictables) {
3703 return isa<UncondBrInst>(IfBlock->getTerminator());
3706 "Will have either one or two blocks to speculate.");
3713 bool IsUnpredictable = DomBI->getMetadata(LLVMContext::MD_unpredictable);
3714 if (!IsUnpredictable) {
3717 (TWeight + FWeight) != 0) {
3722 if (IfBlocks.
size() == 1) {
3724 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3725 if (BIBBProb >= Likely)
3728 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3737 if (IfCondPhiInst->getParent() == BB)
3745 unsigned NumPhis = 0;
3758 if (SpeculateUnpredictables && IsUnpredictable)
3759 Budget +=
TTI.getBranchMispredictPenalty();
3772 AggressiveInsts, Cost, Budget,
TTI, AC,
3773 ZeroCostInstructions) ||
3775 AggressiveInsts, Cost, Budget,
TTI, AC,
3776 ZeroCostInstructions))
3789 auto IsBinOpOrAndEq = [](
Value *V) {
3812 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3825 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3827 <<
" F: " << IfFalse->
getName() <<
"\n");
3844 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3849 PN->eraseFromParent();
3855 Builder.CreateBr(BB);
3864 DomBI->eraseFromParent();
3876 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3877 if (
Opc == Instruction::And)
3878 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3879 if (
Opc == Instruction::Or)
3880 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3892 bool PredHasWeights =
3894 bool SuccHasWeights =
3896 if (PredHasWeights || SuccHasWeights) {
3897 if (!PredHasWeights)
3898 PredTrueWeight = PredFalseWeight = 1;
3899 if (!SuccHasWeights)
3900 SuccTrueWeight = SuccFalseWeight = 1;
3910static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3913 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
3915 "PredBB must be a predecessor of BB.");
3921 if (
TTI && !PBI->getMetadata(LLVMContext::MD_unpredictable) &&
3923 (PTWeight + PFWeight) != 0) {
3926 Likely =
TTI->getPredictableBranchThreshold();
3931 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3932 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3936 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3939 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3940 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3946 return std::nullopt;
3959 bool InvertPredCond;
3960 std::tie(CommonSucc,
Opc, InvertPredCond) =
3963 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3970 {LLVMContext::MD_annotation});
3973 if (InvertPredCond) {
3986 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3989 SuccTrueWeight, SuccFalseWeight)) {
3995 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4000 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4001 PredTrueWeight * SuccFalseWeight);
4007 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4008 PredFalseWeight * SuccTrueWeight);
4010 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4019 PBI->setMetadata(LLVMContext::MD_prof,
nullptr);
4030 if (
MDNode *LoopMD = BI->getMetadata(LLVMContext::MD_loop))
4031 PBI->setMetadata(LLVMContext::MD_loop, LoopMD);
4052 if (!MDWeights.
empty()) {
4053 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4058 ++NumFoldBranchToCommonDest;
4065 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4066 return U->getType()->isVectorTy();
4076 unsigned BonusInstThreshold) {
4085 Cond->getParent() != BB || !
Cond->hasOneUse())
4106 bool InvertPredCond;
4108 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4140 unsigned NumBonusInsts = 0;
4141 bool SawVectorOp =
false;
4142 const unsigned PredCount = Preds.
size();
4159 NumBonusInsts += PredCount;
4167 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4170 return PN->getIncomingBlock(U) == BB;
4171 return UI->
getParent() == BB &&
I.comesBefore(UI);
4175 if (!
all_of(
I.uses(), IsBCSSAUse))
4179 BonusInstThreshold *
4195 for (
auto *BB : {BB1, BB2}) {
4211 Value *AlternativeV =
nullptr) {
4237 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4238 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4246 if (!AlternativeV &&
4252 PHI->addIncoming(V, BB);
4262 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4271 if (!PStore || !QStore)
4292 if (
I.mayReadOrWriteMemory())
4294 for (
auto &
I : *QFB)
4295 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4298 for (
auto &
I : *QTB)
4299 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4303 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4317 for (
auto &
I : *BB) {
4319 if (
I.isTerminator())
4337 "When we run out of budget we will eagerly return from within the "
4338 "per-instruction loop.");
4342 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4344 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4345 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4381 InvertPCond ^= (PStore->
getParent() != PTB);
4382 InvertQCond ^= (QStore->
getParent() != QTB);
4403 {CombinedWeights[0], CombinedWeights[1]},
4467 bool InvertPCond =
false, InvertQCond =
false;
4469 if (PFB == QBI->getParent()) {
4473 if (QFB == PostBB) {
4480 if (PTB == QBI->getParent())
4491 if (!HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) ||
4492 !HasOnePredAndOneSucc(QFB, QBI->getParent(), PostBB))
4494 if ((PTB && !HasOnePredAndOneSucc(PTB, PBI->getParent(), QBI->getParent())) ||
4495 (QTB && !HasOnePredAndOneSucc(QTB, QBI->getParent(), PostBB)))
4497 if (!QBI->getParent()->hasNUses(2))
4503 for (
auto *BB : {PTB, PFB}) {
4508 PStoreAddresses.
insert(
SI->getPointerOperand());
4510 for (
auto *BB : {QTB, QFB}) {
4515 QStoreAddresses.
insert(
SI->getPointerOperand());
4521 auto &CommonAddresses = PStoreAddresses;
4524 for (
auto *Address : CommonAddresses)
4527 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4545 !BI->getParent()->getSinglePredecessor())
4547 if (!IfFalseBB->
phis().empty())
4557 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4562 NoSideEffects(*BI->getParent())) {
4574 NoSideEffects(*BI->getParent())) {
4631 if (&*BB->
begin() != BI)
4659 if (!PBI->getMetadata(LLVMContext::MD_unpredictable) &&
4661 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4665 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4668 if (CommonDestProb >= Likely)
4678 unsigned NumPhis = 0;
4689 <<
"AND: " << *BI->getParent());
4700 if (OtherDest == BB) {
4708 OtherDest = InfLoopBlock;
4720 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4724 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4728 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4743 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4744 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4747 SuccTrueWeight, SuccFalseWeight);
4749 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4750 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4751 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4752 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4756 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4757 PredOther * SuccCommon,
4758 PredOther * SuccOther};
4766 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4768 assert(
SI->getCondition() == PBICond);
4785 Value *BIV = PN.getIncomingValueForBlock(BB);
4786 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->getParent());
4787 Value *PBIV = PN.getIncomingValue(PBBIdx);
4791 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4792 PN.setIncomingValue(PBBIdx, NV);
4796 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4797 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4817bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4819 BasicBlock *FalseBB,
4820 uint32_t TrueWeight,
4821 uint32_t FalseWeight) {
4828 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4830 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4833 for (BasicBlock *Succ :
successors(OldTerm)) {
4835 if (Succ == KeepEdge1)
4836 KeepEdge1 =
nullptr;
4837 else if (Succ == KeepEdge2)
4838 KeepEdge2 =
nullptr;
4843 if (Succ != TrueBB && Succ != FalseBB)
4844 RemovedSuccessors.
insert(Succ);
4852 if (!KeepEdge1 && !KeepEdge2) {
4853 if (TrueBB == FalseBB) {
4864 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4884 SmallVector<DominatorTree::UpdateType, 2> Updates;
4886 for (
auto *RemovedSuccessor : RemovedSuccessors)
4887 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4898bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4903 if (!TrueVal || !FalseVal)
4908 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4909 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4912 uint32_t TrueWeight = 0, FalseWeight = 0;
4913 SmallVector<uint64_t, 8> Weights;
4917 if (Weights.
size() == 1 +
SI->getNumCases()) {
4919 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4921 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4926 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4935bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
4949 SmallVector<uint32_t> SelectBranchWeights(2);
4953 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
4954 SelectBranchWeights[0],
4955 SelectBranchWeights[1]);
4975bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4979 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5025bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5044 ConstantInt *NewCaseVal;
5052 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5058 SelectTrueVal = Builder.
getTrue();
5059 SelectFalseVal = Builder.
getFalse();
5062 SelectCond =
Select->getCondition();
5064 if (SelectCond != ICI)
5066 SelectTrueVal =
Select->getTrueValue();
5067 SelectFalseVal =
Select->getFalseValue();
5072 if (
SI->getCondition() != IcmpCond)
5078 if (
SI->getDefaultDest() != BB) {
5079 ConstantInt *VVal =
SI->findCaseDest(BB);
5080 assert(VVal &&
"Should have a unique destination value");
5088 return requestResimplify();
5094 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5096 if (Predicate == ICmpInst::ICMP_EQ)
5104 return requestResimplify();
5111 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5117 Value *DefaultCst = SelectFalseVal;
5118 Value *NewCst = SelectTrueVal;
5126 Select->replaceAllUsesWith(DefaultCst);
5127 Select->eraseFromParent();
5133 SmallVector<DominatorTree::UpdateType, 2> Updates;
5140 SwitchInstProfUpdateWrapper SIW(*SI);
5141 auto W0 = SIW.getSuccessorWeight(0);
5144 NewW = ((uint64_t(*W0) + 1) >> 1);
5145 SIW.setSuccessorWeight(0, *NewW);
5147 SIW.addCase(NewCaseVal, NewBB, NewW);
5149 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5158 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5166bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5168 const DataLayout &
DL) {
5178 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5180 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5181 Value *CompVal = ConstantCompare.CompValue;
5182 unsigned UsedICmps = ConstantCompare.UsedICmps;
5183 Value *ExtraCase = ConstantCompare.Extra;
5184 bool TrueWhenEqual = ConstantCompare.IsEq;
5201 if (ExtraCase && Values.
size() < 2)
5204 SmallVector<uint32_t> BranchWeights;
5211 if (!TrueWhenEqual) {
5214 std::swap(BranchWeights[0], BranchWeights[1]);
5220 <<
" cases into SWITCH. BB is:\n"
5223 SmallVector<DominatorTree::UpdateType, 2> Updates;
5230 nullptr,
"switch.early.test");
5241 AssumptionCache *AC =
Options.AC;
5247 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5254 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5260 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5261 <<
"\nEXTRABB = " << *BB);
5269 "Should not end up here with unstable pointers");
5271 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5276 if (Values.
front()->getValue() - Values.
back()->getValue() ==
5277 Values.
size() - 1) {
5279 Values.
back()->getValue(), Values.
front()->getValue() + 1);
5281 ICmpInst::Predicate Pred;
5299 SmallVector<uint32_t> NewWeights(Values.
size() + 1);
5300 NewWeights[0] = BranchWeights[1];
5303 V = BranchWeights[0] / Values.
size();
5308 for (ConstantInt *Val : Values)
5309 New->addCase(Val, EdgeBB);
5317 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5327 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5331bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5333 return simplifyCommonResume(RI);
5337 return simplifySingleResume(RI);
5350 switch (IntrinsicID) {
5351 case Intrinsic::dbg_declare:
5352 case Intrinsic::dbg_value:
5353 case Intrinsic::dbg_label:
5354 case Intrinsic::lifetime_end:
5364bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5373 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5377 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5379 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5380 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5384 if (IncomingBB->getUniqueSuccessor() != BB)
5389 if (IncomingValue != LandingPad)
5393 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5394 TrivialUnwindBlocks.
insert(IncomingBB);
5398 if (TrivialUnwindBlocks.
empty())
5402 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5406 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5409 for (BasicBlock *Pred :
5420 TrivialBB->getTerminator()->eraseFromParent();
5421 new UnreachableInst(RI->
getContext(), TrivialBB);
5423 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5430 return !TrivialUnwindBlocks.empty();
5434bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5438 "Resume must unwind the exception that caused control to here");
5494 int Idx = DestPN.getBasicBlockIndex(BB);
5508 Value *SrcVal = DestPN.getIncomingValue(Idx);
5511 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5515 DestPN.addIncoming(
Incoming, Pred);
5542 std::vector<DominatorTree::UpdateType> Updates;
5546 if (UnwindDest ==
nullptr) {
5587 if (!SuccessorCleanupPad)
5596 SuccessorCleanupPad->eraseFromParent();
5605bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5622bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5654 BBI->dropDbgRecords();
5658 BBI->eraseFromParent();
5664 if (&BB->
front() != UI)
5667 std::vector<DominatorTree::UpdateType> Updates;
5670 for (BasicBlock *Predecessor : Preds) {
5678 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5689 "The destinations are guaranteed to be different here.");
5690 CallInst *Assumption;
5706 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5708 SwitchInstProfUpdateWrapper SU(*SI);
5709 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5710 if (i->getCaseSuccessor() != BB) {
5715 i = SU.removeCase(i);
5720 if (DTU &&
SI->getDefaultDest() != BB)
5721 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5723 if (
II->getUnwindDest() == BB) {
5729 if (!CI->doesNotThrow())
5730 CI->setDoesNotThrow();
5734 if (CSI->getUnwindDest() == BB) {
5745 E = CSI->handler_end();
5748 CSI->removeHandler(
I);
5755 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5756 if (CSI->getNumHandlers() == 0) {
5757 if (CSI->hasUnwindDest()) {
5761 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5762 Updates.push_back({DominatorTree::Insert,
5763 PredecessorOfPredecessor,
5764 CSI->getUnwindDest()});
5765 Updates.push_back({DominatorTree::Delete,
5766 PredecessorOfPredecessor, Predecessor});
5769 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5776 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5777 for (BasicBlock *EHPred : EHPreds)
5781 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5782 CSI->eraseFromParent();
5787 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5788 "Expected to always have an unwind to BB.");
5790 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5818static std::optional<ContiguousCasesResult>
5825 const APInt &Min = Cases.
back()->getValue();
5826 const APInt &Max = Cases.
front()->getValue();
5828 size_t ContiguousOffset = Cases.
size() - 1;
5829 if (
Offset == ContiguousOffset) {
5847 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
5848 return L->getValue() != R->getValue() + 1;
5850 if (It == Cases.
end())
5851 return std::nullopt;
5852 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5853 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5857 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5860 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5868 return std::nullopt;
5873 bool RemoveOrigDefaultBlock =
true) {
5875 auto *BB = Switch->getParent();
5876 auto *OrigDefaultBlock = Switch->getDefaultDest();
5877 if (RemoveOrigDefaultBlock)
5878 OrigDefaultBlock->removePredecessor(BB);
5882 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5884 Switch->setDefaultDest(&*NewDefaultBlock);
5888 if (RemoveOrigDefaultBlock &&
5898bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5900 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5902 bool HasDefault = !
SI->defaultDestUnreachable();
5904 auto *BB =
SI->getParent();
5906 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5911 for (
auto Case :
SI->cases()) {
5915 if (Dest == DestA) {
5921 if (Dest == DestB) {
5931 "Single-destination switch should have been folded.");
5933 assert(DestB !=
SI->getDefaultDest());
5934 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5938 std::optional<ContiguousCasesResult> ContiguousCases;
5941 if (!HasDefault && CasesA.
size() == 1)
5942 ContiguousCases = ContiguousCasesResult{
5950 else if (CasesB.
size() == 1)
5951 ContiguousCases = ContiguousCasesResult{
5960 else if (!HasDefault)
5964 if (!ContiguousCases)
5968 if (!ContiguousCases)
5971 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
5977 Max->getValue() - Min->getValue() + 1);
5980 assert(
Max->getValue() == Min->getValue());
5985 else if (NumCases->
isNullValue() && !Cases->empty()) {
5989 if (!
Offset->isNullValue())
5997 SmallVector<uint64_t, 8> Weights;
5999 if (Weights.
size() == 1 +
SI->getNumCases()) {
6000 uint64_t TrueWeight = 0;
6001 uint64_t FalseWeight = 0;
6002 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6003 if (
SI->getSuccessor(
I) == Dest)
6004 TrueWeight += Weights[
I];
6006 FalseWeight += Weights[
I];
6008 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6019 unsigned PreviousEdges = Cases->size();
6020 if (Dest ==
SI->getDefaultDest())
6022 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6023 PHI.removeIncomingValue(
SI->getParent());
6026 unsigned PreviousEdges = OtherCases->size();
6027 if (OtherDest ==
SI->getDefaultDest())
6029 unsigned E = PreviousEdges - 1;
6033 for (
unsigned I = 0;
I !=
E; ++
I)
6034 PHI.removeIncomingValue(
SI->getParent());
6042 auto *UnreachableDefault =
SI->getDefaultDest();
6045 SI->eraseFromParent();
6047 if (!HasDefault && DTU)
6048 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
6066 unsigned MaxSignificantBitsInCond =
6073 for (
const auto &Case :
SI->cases()) {
6074 auto *
Successor = Case.getCaseSuccessor();
6085 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6091 }
else if (IsKnownValuesValid)
6092 KnownValues.
erase(CaseC);
6099 bool HasDefault = !
SI->defaultDestUnreachable();
6100 const unsigned NumUnknownBits =
6103 if (HasDefault && DeadCases.
empty()) {
6109 if (NumUnknownBits < 64 ) {
6110 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6111 if (
SI->getNumCases() == AllNumCases) {
6118 if (
SI->getNumCases() == AllNumCases - 1) {
6119 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6121 if (CondTy->getIntegerBitWidth() > 64 ||
6122 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6126 for (
const auto &Case :
SI->cases())
6127 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6129 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6131 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6141 if (DeadCases.
empty())
6147 assert(CaseI !=
SI->case_default() &&
6148 "Case was not found. Probably mistake in DeadCases forming.");
6150 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6155 std::vector<DominatorTree::UpdateType> Updates;
6156 for (
auto *
Successor : UniqueSuccessors)
6157 if (NumPerSuccessorCases[
Successor] == 0)
6184 int Idx =
PHI.getBasicBlockIndex(BB);
6185 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6187 Value *InValue =
PHI.getIncomingValue(Idx);
6188 if (InValue != CaseValue)
6204 ForwardingNodesMap ForwardingNodes;
6207 for (
const auto &Case :
SI->cases()) {
6209 BasicBlock *CaseDest = Case.getCaseSuccessor();
6228 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6229 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6230 count(Phi.blocks(), SwitchBlock) == 1) {
6231 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6239 ForwardingNodes[Phi].push_back(PhiIdx);
6242 for (
auto &ForwardingNode : ForwardingNodes) {
6243 PHINode *Phi = ForwardingNode.first;
6249 for (
int Index : Indexes)
6250 Phi->setIncomingValue(Index,
SI->getCondition());
6260 if (
C->isThreadDependent())
6262 if (
C->isDLLImportDependent())
6270 if (
C->getType()->isScalableTy())
6281 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6308 if (
A->isAllOnesValue())
6310 if (
A->isNullValue())
6316 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6341 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6343 if (
I.isTerminator()) {
6345 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6348 CaseDest =
I.getSuccessor(0);
6355 for (
auto &
Use :
I.uses()) {
6358 if (
I->getParent() == CaseDest)
6361 if (Phi->getIncomingBlock(
Use) == CaseDest)
6374 *CommonDest = CaseDest;
6376 if (CaseDest != *CommonDest)
6381 int Idx =
PHI.getBasicBlockIndex(Pred);
6394 Res.push_back(std::make_pair(&
PHI, ConstVal));
6397 return Res.
size() > 0;
6403 SwitchCaseResultVectorTy &UniqueResults,
6405 for (
auto &
I : UniqueResults) {
6406 if (
I.first == Result) {
6407 I.second.push_back(CaseVal);
6408 return I.second.size();
6411 UniqueResults.push_back(
6422 SwitchCaseResultVectorTy &UniqueResults,
6426 uintptr_t MaxUniqueResults) {
6427 for (
const auto &
I :
SI->cases()) {
6441 const size_t NumCasesForResult =
6449 if (UniqueResults.size() > MaxUniqueResults)
6465 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6467 return DefaultResult ||
SI->defaultDestUnreachable();
6488 const bool HasBranchWeights =
6491 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6492 ResultVector[1].second.size() == 1) {
6493 ConstantInt *FirstCase = ResultVector[0].second[0];
6494 ConstantInt *SecondCase = ResultVector[1].second[0];
6495 Value *SelectValue = ResultVector[1].first;
6496 if (DefaultResult) {
6497 Value *ValueCompare =
6498 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6499 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6500 DefaultResult,
"switch.select");
6502 SI && HasBranchWeights) {
6509 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6513 Value *ValueCompare =
6514 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6515 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6516 SelectValue,
"switch.select");
6522 size_t FirstCasePos = (Condition !=
nullptr);
6523 size_t SecondCasePos = FirstCasePos + 1;
6524 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6526 {BranchWeights[FirstCasePos],
6527 DefaultCase + BranchWeights[SecondCasePos]},
6534 if (ResultVector.size() == 1 && DefaultResult) {
6536 unsigned CaseCount = CaseValues.
size();
6549 for (
auto *Case : CaseValues) {
6550 if (Case->getValue().slt(MinCaseVal->
getValue()))
6552 AndMask &= Case->getValue();
6562 if (FreeBits ==
Log2_32(CaseCount)) {
6563 Value *
And = Builder.CreateAnd(Condition, AndMask);
6564 Value *Cmp = Builder.CreateICmpEQ(
6567 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6583 for (
auto *Case : CaseValues)
6584 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6590 Condition = Builder.CreateSub(Condition, MinCaseVal);
6591 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6592 Value *Cmp = Builder.CreateICmpEQ(
6595 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6608 if (CaseValues.
size() == 2) {
6609 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6610 "switch.selectcmp.case1");
6611 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6612 "switch.selectcmp.case2");
6613 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6615 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6635 std::vector<DominatorTree::UpdateType> Updates;
6642 Builder.CreateBr(DestBB);
6646 PHI->removeIncomingValueIf(
6647 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6648 PHI->addIncoming(SelectValue, SelectBB);
6651 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6657 if (DTU && RemovedSuccessors.
insert(Succ).second)
6660 SI->eraseFromParent();
6675 SwitchCaseResultVectorTy UniqueResults;
6681 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6682 Builder.SetInsertPoint(
SI);
6685 [[maybe_unused]]
auto HasWeights =
6690 (BranchWeights.
size() >=
6691 UniqueResults.size() + (DefaultResult !=
nullptr)));
6694 Builder,
DL, BranchWeights);
6706class SwitchReplacement {
6713 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6714 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName);
6723 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6730 bool isLookupTable();
6767 ConstantInt *BitMap =
nullptr;
6768 IntegerType *BitMapElementTy =
nullptr;
6771 ConstantInt *LinearOffset =
nullptr;
6772 ConstantInt *LinearMultiplier =
nullptr;
6773 bool LinearMapValWrapped =
false;
6781SwitchReplacement::SwitchReplacement(
6783 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6784 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName)
6785 : DefaultValue(DefaultValue) {
6786 assert(Values.size() &&
"Can't build lookup table without values!");
6787 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6790 SingleValue = Values.begin()->second;
6792 ValueType = Values.begin()->second->getType();
6796 for (
const auto &[CaseVal, CaseRes] : Values) {
6799 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6800 TableContents[Idx] = CaseRes;
6807 if (Values.size() < TableSize) {
6809 "Need a default value to fill the lookup table holes.");
6812 if (!TableContents[
I])
6813 TableContents[
I] = DefaultValue;
6819 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6820 SingleValue =
nullptr;
6826 Kind = SingleValueKind;
6833 bool LinearMappingPossible =
true;
6838 bool NonMonotonic =
false;
6839 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6856 LinearMappingPossible =
false;
6861 APInt Dist = Val - PrevVal;
6864 }
else if (Dist != DistToPrev) {
6865 LinearMappingPossible =
false;
6873 if (LinearMappingPossible) {
6875 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6876 APInt M = LinearMultiplier->getValue();
6877 bool MayWrap =
true;
6878 if (
isIntN(M.getBitWidth(), TableSize - 1))
6879 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6880 LinearMapValWrapped = NonMonotonic || MayWrap;
6881 Kind = LinearMapKind;
6887 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6889 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6891 TableInt <<=
IT->getBitWidth();
6895 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6898 BitMap = ConstantInt::get(M.getContext(), TableInt);
6899 BitMapElementTy =
IT;
6908 Kind = LookupTableKind;
6914 case SingleValueKind:
6916 case LinearMapKind: {
6920 false,
"switch.idx.cast");
6921 if (!LinearMultiplier->
isOne())
6922 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6924 !LinearMapValWrapped);
6926 if (!LinearOffset->
isZero())
6929 !LinearMapValWrapped);
6946 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
6947 "switch.shiftamt",
true,
true);
6950 Value *DownShifted =
6951 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6953 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6955 case LookupTableKind: {
6958 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
6959 true, GlobalVariable::PrivateLinkage,
6960 Initializer,
"switch.table." +
Func->getName());
6961 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6964 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
6965 Type *IndexTy =
DL.getIndexType(Table->getType());
6968 if (
Index->getType() != IndexTy) {
6969 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
6973 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
6976 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
6979 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
6985bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
6987 Type *ElementType) {
6995 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6997 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7003 if (
TTI.isTypeLegal(Ty))
7018 DL.fitsInLegalInteger(
IT->getBitWidth());
7021Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7023bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7025bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7036 return NumCases * 100 >= CaseRange * MinDensity;
7057 if (
SI->getNumCases() > TableSize)
7060 bool AllTablesFitInRegister =
true;
7061 bool HasIllegalType =
false;
7062 for (
const auto &Ty : ResultTypes) {
7067 AllTablesFitInRegister =
7068 AllTablesFitInRegister &&
7069 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7074 if (HasIllegalType && !AllTablesFitInRegister)
7079 if (AllTablesFitInRegister)
7096 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7099 return all_of(ResultTypes, [&](
const auto &ResultType) {
7100 return SwitchReplacement::wouldFitInRegister(
7128 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
7150 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7155 for (
auto ValuePair : Values) {
7158 if (!CaseConst || CaseConst == DefaultConst ||
7159 (CaseConst != TrueConst && CaseConst != FalseConst))
7167 BasicBlock *BranchBlock = RangeCheckBranch->getParent();
7173 if (DefaultConst == FalseConst) {
7176 ++NumTableCmpReuses;
7179 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7180 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7181 RangeCheckBranch->getIterator());
7183 ++NumTableCmpReuses;
7193 bool ConvertSwitchToLookupTable) {
7194 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7208 if (
SI->getNumCases() < 3)
7230 MinCaseVal = CaseVal;
7232 MaxCaseVal = CaseVal;
7249 It->second.push_back(std::make_pair(CaseVal,
Value));
7257 bool HasDefaultResults =
7259 DefaultResultsList,
DL,
TTI);
7260 for (
const auto &
I : DefaultResultsList) {
7263 DefaultResults[
PHI] = Result;
7267 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7270 if (UseSwitchConditionAsTableIndex) {
7272 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7277 TableIndexOffset = MinCaseVal;
7284 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7286 bool TableHasHoles = (NumResults < TableSize);
7291 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7299 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7302 if (
SI->getNumCases() < 4)
7304 if (!
DL.fitsInLegalInteger(TableSize))
7313 if (UseSwitchConditionAsTableIndex) {
7314 TableIndex =
SI->getCondition();
7315 if (HasDefaultResults) {
7327 all_of(ResultTypes, [&](
const auto &ResultType) {
7328 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7333 TableSize = std::max(UpperBound, TableSize);
7336 DefaultIsReachable =
false;
7344 const auto &ResultList = ResultLists[
PHI];
7346 Type *ResultType = ResultList.begin()->second->getType();
7351 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7352 ResultList, DefaultVal,
DL, FuncName);
7353 PhiToReplacementMap.
insert({
PHI, Replacement});
7356 bool AnyLookupTables =
any_of(
7357 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7358 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7359 [](
auto &KV) {
return KV.second.isBitMap(); });
7367 if (AnyLookupTables &&
7368 (!
TTI.shouldBuildLookupTables() ||
7374 if (!ConvertSwitchToLookupTable &&
7375 (AnyLookupTables || AnyBitMaps || NeedMask))
7378 Builder.SetInsertPoint(
SI);
7381 if (!UseSwitchConditionAsTableIndex) {
7384 bool MayWrap =
true;
7385 if (!DefaultIsReachable) {
7390 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7391 "switch.tableidx",
false,
7395 std::vector<DominatorTree::UpdateType> Updates;
7401 assert(MaxTableSize >= TableSize &&
7402 "It is impossible for a switch to have more entries than the max "
7403 "representable value of its input integer type's size.");
7408 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7413 Builder.SetInsertPoint(
SI);
7414 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7415 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7416 Builder.CreateBr(LookupBB);
7422 Value *Cmp = Builder.CreateICmpULT(
7423 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7425 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7426 CondBranch = RangeCheckBranch;
7432 Builder.SetInsertPoint(LookupBB);
7438 MaskBB->
setName(
"switch.hole_check");
7445 APInt MaskInt(TableSizePowOf2, 0);
7446 APInt One(TableSizePowOf2, 1);
7448 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7449 for (
const auto &Result : ResultList) {
7452 MaskInt |= One << Idx;
7454 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7461 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7462 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7463 Value *LoBit = Builder.CreateTrunc(
7465 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7470 Builder.SetInsertPoint(LookupBB);
7474 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7477 SI->getDefaultDest()->removePredecessor(BB,
7484 const ResultListTy &ResultList = ResultLists[
PHI];
7485 auto Replacement = PhiToReplacementMap.
at(
PHI);
7486 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7489 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7492 for (
auto *
User :
PHI->users()) {
7494 Replacement.getDefaultValue(), ResultList);
7498 PHI->addIncoming(Result, LookupBB);
7501 Builder.CreateBr(CommonDest);
7513 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7516 if (Succ ==
SI->getDefaultDest()) {
7517 if (HasBranchWeights)
7518 ToDefaultWeight += BranchWeights[
I];
7522 if (DTU && RemovedSuccessors.
insert(Succ).second)
7524 if (HasBranchWeights)
7525 ToLookupWeight += BranchWeights[
I];
7527 SI->eraseFromParent();
7528 if (HasBranchWeights)
7535 ++NumLookupTablesHoles;
7551 if (CondTy->getIntegerBitWidth() > 64 ||
7552 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7556 if (
SI->getNumCases() < 4)
7564 for (
const auto &
C :
SI->cases())
7565 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7573 int64_t
Base = Values[0];
7574 for (
auto &V : Values)
7587 unsigned Shift = 64;
7588 for (
auto &V : Values)
7592 for (
auto &V : Values)
7593 V = (int64_t)((
uint64_t)V >> Shift);
7610 Builder.SetInsertPoint(
SI);
7613 Value *Rot = Builder.CreateIntrinsic(
7614 Ty, Intrinsic::fshl,
7615 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7616 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7618 for (
auto Case :
SI->cases()) {
7619 auto *Orig = Case.getCaseValue();
7620 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7665 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
7666 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
7682 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
7685 return !Updates.
empty();
7715 Value *Condition =
SI->getCondition();
7719 if (CondTy->getIntegerBitWidth() > 64 ||
7720 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7732 if (
SI->getNumCases() < 4)
7737 for (
const auto &Case :
SI->cases()) {
7738 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7752 Builder.SetInsertPoint(
SI);
7754 if (!
SI->defaultDestUnreachable()) {
7757 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
7758 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
7760 auto *OrigBB =
SI->getParent();
7761 auto *DefaultCaseBB =
SI->getDefaultDest();
7763 auto It = OrigBB->getTerminator()->getIterator();
7776 NewWeights[1] = Weights[0] / 2;
7777 NewWeights[0] = OrigDenominator - NewWeights[1];
7789 Weights[0] = NewWeights[1];
7790 uint64_t CasesDenominator = OrigDenominator - Weights[0];
7792 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
7797 BI->setDebugLoc(
SI->getDebugLoc());
7798 It->eraseFromParent();
7806 for (
auto &Case :
SI->cases()) {
7807 auto *OrigValue = Case.getCaseValue();
7808 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7809 OrigValue->getValue().countr_zero()));
7813 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7816 SI->setCondition(ConditionTrailingZeros);
7826 if (!Cmp || !Cmp->hasOneUse())
7837 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7840 if (
SI->getNumCases() == 2) {
7847 Succ =
SI->getDefaultDest();
7848 SuccWeight = Weights[0];
7850 for (
auto &Case :
SI->cases()) {
7851 std::optional<int64_t> Val =
7855 if (!Missing.erase(*Val))
7860 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7863 assert(Missing.size() == 1 &&
"Should have one case left");
7864 Res = *Missing.begin();
7865 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7867 Unreachable =
SI->getDefaultDest();
7869 for (
auto &Case :
SI->cases()) {
7870 BasicBlock *NewSucc = Case.getCaseSuccessor();
7871 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7874 OtherSuccWeight += Weight;
7877 SuccWeight = Weight;
7878 }
else if (Succ == NewSucc) {
7884 for (
auto &Case :
SI->cases()) {
7885 std::optional<int64_t> Val =
7887 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7889 if (Case.getCaseSuccessor() == Succ) {
7911 if (Cmp->isSigned())
7914 MDNode *NewWeights =
nullptr;
7920 Builder.SetInsertPoint(
SI->getIterator());
7921 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
7922 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
7923 SI->getMetadata(LLVMContext::MD_unpredictable));
7927 SI->eraseFromParent();
7928 Cmp->eraseFromParent();
7929 if (DTU && Unreachable)
7954 assert(
BB &&
"Expected non-null BB");
7956 if (
BB->isEntryBlock())
7969 if (
BB->hasAddressTaken() ||
BB->isEHPad())
7974 if (&
BB->front() != &
BB->back())
7996 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8007 return (*EBW->PhiPredIVs)[&Phi][BB];
8014 if (LHS == EKey || RHS == EKey || LHS == TKey || RHS == TKey)
8034 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8037 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8038 return PredIVs[
A] == PredIVs[
B];
8047 if (Candidates.
size() < 2)
8062 assert(Succ &&
"Expected unconditional BB");
8072 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8075 for (
auto &
IV : Phi->incoming_values())
8076 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8094 bool MadeChange =
false;
8108 if (!LivePreds.
contains(PredOfDead))
8115 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8116 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8121 T->replaceSuccessorWith(
Dead, Live);
8126 for (
const auto &EBW : BBs2Merge) {
8129 const auto &[It, Inserted] =
Keep.insert(&EBW);
8138 if (KeepBB == DeadBB)
8142 RedirectIncomingEdges(DeadBB, KeepBB);
8151 if (DTU && !Updates.
empty())
8157bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8158 DomTreeUpdater *DTU) {
8160 SmallSetVector<BasicBlock *, 16> FilteredArms(
8166bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8167 DomTreeUpdater *DTU) {
8178 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8184bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8187 if (isValueEqualityComparison(SI)) {
8191 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8192 return requestResimplify();
8196 if (simplifySwitchOnSelect(SI,
Select))
8197 return requestResimplify();
8201 if (SI == &*BB->
begin())
8202 if (foldValueComparisonIntoPredecessors(SI, Builder))
8203 return requestResimplify();
8209 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8210 return requestResimplify();
8214 return requestResimplify();
8217 return requestResimplify();
8220 return requestResimplify();
8223 return requestResimplify();
8228 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8230 Options.ConvertSwitchToLookupTable))
8231 return requestResimplify();
8234 return requestResimplify();
8237 return requestResimplify();
8240 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8241 return requestResimplify();
8245 if (simplifyDuplicateSwitchArms(SI, DTU))
8246 return requestResimplify();
8249 return requestResimplify();
8254bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8257 SmallVector<uint32_t> BranchWeights;
8261 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8262 if (HasBranchWeights)
8267 SmallPtrSet<Value *, 8> Succs;
8268 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8273 RemovedSuccs.
insert(Dest);
8283 std::vector<DominatorTree::UpdateType> Updates;
8284 Updates.reserve(RemovedSuccs.
size());
8285 for (
auto *RemovedSucc : RemovedSuccs)
8286 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8303 if (HasBranchWeights) {
8310 if (simplifyIndirectBrOnSelect(IBI, SI))
8311 return requestResimplify();
8347 if (BB == OtherPred)
8355 if (!BI2 || !BI2->isIdenticalTo(BI))
8358 std::vector<DominatorTree::UpdateType> Updates;
8365 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8366 "unexpected successor");
8367 II->setUnwindDest(OtherPred);
8382 Builder.CreateUnreachable();
8383 BI->eraseFromParent();
8391bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8403 bool NeedCanonicalLoop =
8417 if (
I->isTerminator() &&
8418 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8442 if (!PPred || (PredPred && PredPred != PPred))
8483 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8487 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8513 bool HasWeight =
false;
8518 BBTWeight = BBFWeight = 1;
8523 BB1TWeight = BB1FWeight = 1;
8528 BB2TWeight = BB2FWeight = 1;
8530 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8531 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8538bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
8542 "Tautological conditional branch should have been eliminated already.");
8545 if (!
Options.SimplifyCondBranch ||
8546 BI->getFunction()->hasFnAttribute(Attribute::OptForFuzzing))
8550 if (isValueEqualityComparison(BI)) {
8555 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8556 return requestResimplify();
8560 for (
auto &
I : *BB) {
8565 if (foldValueComparisonIntoPredecessors(BI, Builder))
8566 return requestResimplify();
8572 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8585 return requestResimplify();
8591 if (
Options.SpeculateBlocks &&
8594 return requestResimplify();
8603 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8604 return requestResimplify();
8606 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8608 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8609 auto CanSpeculateConditionalLoadsStores = [&]() {
8611 for (Instruction &
I : *Succ) {
8612 if (
I.isTerminator()) {
8613 if (
I.getNumSuccessors() > 1)
8617 SpeculatedConditionalLoadsStores.
size() ==
8621 SpeculatedConditionalLoadsStores.
push_back(&
I);
8624 return !SpeculatedConditionalLoadsStores.
empty();
8627 if (CanSpeculateConditionalLoadsStores()) {
8629 std::nullopt,
nullptr);
8630 return requestResimplify();
8640 return requestResimplify();
8649 return requestResimplify();
8655 if (foldCondBranchOnValueKnownInPredecessor(BI))
8656 return requestResimplify();
8663 return requestResimplify();
8671 return requestResimplify();
8675 return requestResimplify();
8682 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8694 auto *Use = cast<Instruction>(U.getUser());
8696 switch (Use->getOpcode()) {
8699 case Instruction::GetElementPtr:
8700 case Instruction::Ret:
8701 case Instruction::BitCast:
8702 case Instruction::Load:
8703 case Instruction::Store:
8704 case Instruction::Call:
8705 case Instruction::CallBr:
8706 case Instruction::Invoke:
8707 case Instruction::UDiv:
8708 case Instruction::URem:
8712 case Instruction::SDiv:
8713 case Instruction::SRem:
8717 if (FindUse ==
I->use_end())
8719 auto &
Use = *FindUse;
8724 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8725 User->comesBefore(
I))
8739 if (
GEP->getPointerOperand() ==
I) {
8742 if (
GEP->getType()->isVectorTy())
8750 if (!
GEP->hasAllZeroIndices() &&
8751 (!
GEP->isInBounds() ||
8753 GEP->getPointerAddressSpace())))
8754 PtrValueMayBeModified =
true;
8760 bool HasNoUndefAttr =
8761 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8766 if (
C->isNullValue() && HasNoUndefAttr &&
8767 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8768 return !PtrValueMayBeModified;
8774 if (!LI->isVolatile())
8776 LI->getPointerAddressSpace());
8780 if (!
SI->isVolatile())
8782 SI->getPointerAddressSpace())) &&
8783 SI->getPointerOperand() ==
I;
8788 if (
I == Assume->getArgOperand(0))
8796 if (CB->getCalledOperand() ==
I)
8799 if (CB->isArgOperand(&
Use)) {
8800 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8803 CB->paramHasNonNullAttr(ArgIdx,
false))
8804 return !PtrValueMayBeModified;
8823 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8831 Builder.CreateUnreachable();
8832 T->eraseFromParent();
8843 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8845 Assumption = Builder.CreateAssumption(
Cond);
8850 BI->eraseFromParent();
8859 Builder.SetInsertPoint(Unreachable);
8861 Builder.CreateUnreachable();
8862 for (
const auto &Case :
SI->cases())
8863 if (Case.getCaseSuccessor() == BB) {
8865 Case.setSuccessor(Unreachable);
8867 if (
SI->getDefaultDest() == BB) {
8869 SI->setDefaultDest(Unreachable);
8883bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8908 return requestResimplify();
8927 if (simplifyDuplicatePredecessors(BB, DTU))
8931 if (
Options.SpeculateBlocks &&
8938 Options.SpeculateUnpredictables))
8946 case Instruction::UncondBr:
8949 case Instruction::CondBr:
8952 case Instruction::Resume:
8955 case Instruction::CleanupRet:
8958 case Instruction::Switch:
8961 case Instruction::Unreachable:
8964 case Instruction::IndirectBr:
8972bool SimplifyCFGOpt::run(BasicBlock *BB) {
8982 }
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< 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.
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...
MachineInstr unsigned OpIdx
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
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 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 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 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 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 isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
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 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 std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
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 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 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 blockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
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 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 intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
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 isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
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
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
bool empty() const
empty - 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
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 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].
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...
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.
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
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)
at - 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)
LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
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="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
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...
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.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
void insert_range(Range &&R)
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Unconditional Branch instruction.
void setSuccessor(BasicBlock *NewSucc)
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i=0) const
'undef' values are things that do not have specified contents.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr detail::StaticCastFunc< To > StaticCastTo
Function objects corresponding to the Cast types defined above.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI CondBrInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
LLVM_ABI void InvertBranch(CondBrInst *PBI, IRBuilderBase &Builder)
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible immediate values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
FunctionAddr VTableAddr Count
auto succ_size(const MachineBasicBlock *BB)
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
LLVM_ABI bool foldBranchToCommonDest(CondBrInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< T1, 2 > &B1, const SmallVector< T2, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
@ Keep
No function return thunk.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two BBs are equal depends on the contents of the BasicBlock and the incoming values ...
SmallDenseMap< BasicBlock *, Value *, 8 > BB2ValueMap
DenseMap< PHINode *, BB2ValueMap > Phi2IVsMap
static bool canBeMerged(const BasicBlock *BB)
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const EqualBBWrapper * getEmptyKey()
static bool isEqual(const EqualBBWrapper *LHS, const EqualBBWrapper *RHS)
static unsigned getHashValue(const EqualBBWrapper *EBW)
static const EqualBBWrapper * getTombstoneKey()
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane mask phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.