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"));
206 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
213STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
215 "Number of switch instructions turned into linear mapping");
217 "Number of switch instructions turned into lookup tables");
219 NumLookupTablesHoles,
220 "Number of switch instructions turned into lookup tables (holes checked)");
221STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
223 "Number of value comparisons folded into predecessor basic blocks");
225 "Number of branches folded into predecessor basic block");
228 "Number of common instruction 'blocks' hoisted up to the begin block");
230 "Number of common instructions hoisted up to the begin block");
232 "Number of common instruction 'blocks' sunk down to the end block");
234 "Number of common instructions sunk down to the end block");
235STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
237 "Number of invokes with empty resume blocks simplified into calls");
238STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
239STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
246using SwitchCaseResultVectorTy =
255struct ValueEqualityComparisonCase {
267 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
270class SimplifyCFGOpt {
271 const TargetTransformInfo &TTI;
273 const DataLayout &DL;
275 const SimplifyCFGOptions &Options;
278 Value *isValueEqualityComparison(Instruction *TI);
280 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
281 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
284 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
287 bool foldValueComparisonIntoPredecessors(Instruction *TI,
290 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
291 bool simplifySingleResume(ResumeInst *RI);
292 bool simplifyCommonResume(ResumeInst *RI);
293 bool simplifyCleanupReturn(CleanupReturnInst *RI);
294 bool simplifyUnreachable(UnreachableInst *UI);
295 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
296 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
297 bool simplifyIndirectBr(IndirectBrInst *IBI);
298 bool simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder);
299 bool simplifyUncondBranch(BranchInst *BI,
IRBuilder<> &Builder);
300 bool simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder);
301 bool foldCondBranchOnValueKnownInPredecessor(BranchInst *BI);
303 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
305 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
308 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
309 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
310 Instruction *TI, Instruction *I1,
311 SmallVectorImpl<Instruction *> &OtherSuccTIs,
313 bool speculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
314 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
315 BasicBlock *TrueBB, BasicBlock *FalseBB,
316 uint32_t TrueWeight, uint32_t FalseWeight);
317 bool simplifyBranchOnICmpChain(BranchInst *BI,
IRBuilder<> &Builder,
318 const DataLayout &DL);
319 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
320 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
321 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
324 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
326 const SimplifyCFGOptions &Opts)
327 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
328 assert((!DTU || !DTU->hasPostDomTree()) &&
329 "SimplifyCFG is not yet capable of maintaining validity of a "
330 "PostDomTree, so don't ask for it.");
333 bool simplifyOnce(BasicBlock *BB);
334 bool run(BasicBlock *BB);
337 bool requestResimplify() {
347isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
367 "Only for a pair of incoming blocks at the time!");
373 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
374 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
377 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
378 EquivalenceSet->contains(IV1))
401 if (!SI1Succs.
count(Succ))
407 FailBlocks->insert(Succ);
423 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
425 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
426 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
488 if (AggressiveInsts.
count(
I))
504 ZeroCostInstructions.
insert(OverflowInst);
506 }
else if (!ZeroCostInstructions.
contains(
I))
522 for (
Use &
Op :
I->operands())
524 TTI, AC, ZeroCostInstructions,
Depth + 1))
541 if (
DL.hasUnstableRepresentation(V->getType()))
550 return ConstantInt::get(IntPtrTy, 0);
555 if (CE->getOpcode() == Instruction::IntToPtr)
579struct ConstantComparesGatherer {
580 const DataLayout &DL;
583 Value *CompValue =
nullptr;
586 Value *Extra =
nullptr;
592 unsigned UsedICmps = 0;
598 bool IgnoreFirstMatch =
false;
599 bool MultipleMatches =
false;
602 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
604 if (CompValue || !MultipleMatches)
609 IgnoreFirstMatch =
true;
613 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
614 ConstantComparesGatherer &
615 operator=(
const ConstantComparesGatherer &) =
delete;
620 bool setValueOnce(
Value *NewVal) {
621 if (IgnoreFirstMatch) {
622 IgnoreFirstMatch =
false;
625 if (CompValue && CompValue != NewVal) {
626 MultipleMatches =
true;
640 bool matchInstruction(Instruction *
I,
bool isEQ) {
647 if (!setValueOnce(Val))
667 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
711 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
713 if (!setValueOnce(RHSVal))
718 ConstantInt::get(
C->getContext(),
719 C->getValue() | Mask));
734 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
736 if (!setValueOnce(RHSVal))
740 Vals.push_back(ConstantInt::get(
C->getContext(),
741 C->getValue() & ~Mask));
762 Value *CandidateVal =
I->getOperand(0);
765 CandidateVal = RHSVal;
780 if (!setValueOnce(CandidateVal))
786 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
798 void gather(
Value *V) {
807 SmallVector<Value *, 8> DFT{Op0, Op1};
808 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
810 while (!DFT.
empty()) {
817 if (Visited.
insert(Op1).second)
819 if (Visited.
insert(Op0).second)
826 if (matchInstruction(
I, IsEq))
853 if (BI->isConditional())
871 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
872 CV =
SI->getCondition();
874 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
879 if (Trunc->hasNoUnsignedWrap())
880 CV = Trunc->getOperand(0);
887 Value *Ptr = PTII->getPointerOperand();
888 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
890 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
899BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
900 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
902 Cases.reserve(
SI->getNumCases());
903 for (
auto Case :
SI->cases())
904 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
905 Case.getCaseSuccessor()));
906 return SI->getDefaultDest();
911 ICmpInst::Predicate Pred;
917 Pred = ICmpInst::ICMP_NE;
922 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
930 std::vector<ValueEqualityComparisonCase> &Cases) {
936 std::vector<ValueEqualityComparisonCase> &C2) {
937 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
940 if (V1->size() > V2->size())
945 if (V1->size() == 1) {
948 for (
const ValueEqualityComparisonCase &
VECC : *V2)
949 if (TheVal ==
VECC.Value)
956 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
957 while (i1 != e1 && i2 != e2) {
973bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
974 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
979 Value *ThisVal = isValueEqualityComparison(TI);
980 assert(ThisVal &&
"This isn't a value comparison!!");
981 if (ThisVal != PredVal)
988 std::vector<ValueEqualityComparisonCase> PredCases;
990 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
994 std::vector<ValueEqualityComparisonCase> ThisCases;
995 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1010 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1016 ThisCases[0].Dest->removePredecessor(PredDef);
1019 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1026 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1033 SmallPtrSet<Constant *, 16> DeadCases;
1034 for (
const ValueEqualityComparisonCase &Case : PredCases)
1035 DeadCases.
insert(Case.Value);
1038 <<
"Through successor TI: " << *TI);
1040 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1043 auto *
Successor = i->getCaseSuccessor();
1046 if (DeadCases.
count(i->getCaseValue())) {
1055 std::vector<DominatorTree::UpdateType> Updates;
1056 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1058 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1068 ConstantInt *TIV =
nullptr;
1070 for (
const auto &[
Value, Dest] : PredCases)
1076 assert(TIV &&
"No edge from pred to succ?");
1081 for (
const auto &[
Value, Dest] : ThisCases)
1089 TheRealDest = ThisDef;
1091 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1096 if (Succ != CheckEdge) {
1097 if (Succ != TheRealDest)
1098 RemovedSuccs.
insert(Succ);
1101 CheckEdge =
nullptr;
1108 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1113 SmallVector<DominatorTree::UpdateType, 2> Updates;
1115 for (
auto *RemovedSucc : RemovedSuccs)
1116 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1127struct ConstantIntOrdering {
1128 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1129 return LHS->getValue().ult(
RHS->getValue());
1141 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1150 assert(MD &&
"Invalid branch-weight metadata");
1175 if (BonusInst.isTerminator())
1205 NewBonusInst->
takeName(&BonusInst);
1206 BonusInst.setName(NewBonusInst->
getName() +
".old");
1207 VMap[&BonusInst] = NewBonusInst;
1216 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1217 "If the user is not a PHI node, then it should be in the same "
1218 "block as, and come after, the original bonus instruction.");
1222 if (PN->getIncomingBlock(U) == BB)
1226 assert(PN->getIncomingBlock(U) == PredBlock &&
1227 "Not in block-closed SSA form?");
1228 U.set(NewBonusInst);
1238 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1239 PredDL.isSameSourceLocation(
DL)) {
1246bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1254 std::vector<ValueEqualityComparisonCase> BBCases;
1255 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1257 std::vector<ValueEqualityComparisonCase> PredCases;
1258 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1263 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1266 SmallVector<uint64_t, 8> Weights;
1270 if (PredHasWeights) {
1273 if (Weights.
size() != 1 + PredCases.size())
1274 PredHasWeights = SuccHasWeights =
false;
1275 }
else if (SuccHasWeights)
1279 Weights.
assign(1 + PredCases.size(), 1);
1281 SmallVector<uint64_t, 8> SuccWeights;
1282 if (SuccHasWeights) {
1285 if (SuccWeights.
size() != 1 + BBCases.size())
1286 PredHasWeights = SuccHasWeights =
false;
1287 }
else if (PredHasWeights)
1288 SuccWeights.
assign(1 + BBCases.size(), 1);
1290 if (PredDefault == BB) {
1293 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1294 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1295 if (PredCases[i].Dest != BB)
1296 PTIHandled.insert(PredCases[i].
Value);
1299 std::swap(PredCases[i], PredCases.back());
1301 if (PredHasWeights || SuccHasWeights) {
1303 Weights[0] += Weights[i + 1];
1308 PredCases.pop_back();
1314 if (PredDefault != BBDefault) {
1316 if (DTU && PredDefault != BB)
1317 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1318 PredDefault = BBDefault;
1319 ++NewSuccessors[BBDefault];
1322 unsigned CasesFromPred = Weights.
size();
1323 uint64_t ValidTotalSuccWeight = 0;
1324 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1325 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1326 PredCases.push_back(BBCases[i]);
1327 ++NewSuccessors[BBCases[i].Dest];
1328 if (SuccHasWeights || PredHasWeights) {
1332 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1333 ValidTotalSuccWeight += SuccWeights[i + 1];
1337 if (SuccHasWeights || PredHasWeights) {
1338 ValidTotalSuccWeight += SuccWeights[0];
1340 for (
unsigned i = 1; i < CasesFromPred; ++i)
1341 Weights[i] *= ValidTotalSuccWeight;
1343 Weights[0] *= SuccWeights[0];
1349 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1350 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1351 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1352 if (PredCases[i].Dest == BB) {
1353 PTIHandled.insert(PredCases[i].
Value);
1355 if (PredHasWeights || SuccHasWeights) {
1356 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1361 std::swap(PredCases[i], PredCases.back());
1362 PredCases.pop_back();
1369 for (
const ValueEqualityComparisonCase &Case : BBCases)
1370 if (PTIHandled.count(Case.Value)) {
1372 if (PredHasWeights || SuccHasWeights)
1373 Weights.
push_back(WeightsForHandled[Case.Value]);
1374 PredCases.push_back(Case);
1375 ++NewSuccessors[Case.Dest];
1376 PTIHandled.erase(Case.Value);
1381 for (ConstantInt *
I : PTIHandled) {
1382 if (PredHasWeights || SuccHasWeights)
1384 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1385 ++NewSuccessors[BBDefault];
1392 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1397 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1399 for (
auto I :
seq(NewSuccessor.second)) {
1403 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1404 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1411 "Should not end up here with unstable pointers");
1417 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1419 for (ValueEqualityComparisonCase &V : PredCases)
1422 if (PredHasWeights || SuccHasWeights)
1434 if (!InfLoopBlock) {
1442 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1449 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1451 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1456 ++NumFoldValueComparisonIntoPredecessors;
1464bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1467 Value *CV = isValueEqualityComparison(TI);
1468 assert(CV &&
"Not a comparison?");
1473 while (!Preds.empty()) {
1482 Value *PCV = isValueEqualityComparison(PTI);
1486 SmallSetVector<BasicBlock *, 4> FailBlocks;
1488 for (
auto *Succ : FailBlocks) {
1494 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1508 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1509 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1510 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1529 if (
I->mayReadFromMemory())
1561 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1569 if (J->getParent() == BB)
1591 if (C1->isMustTailCall() != C2->isMustTailCall())
1594 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1600 if (CB1->cannotMerge() || CB1->isConvergent())
1603 if (CB2->cannotMerge() || CB2->isConvergent())
1618 if (!I1->hasDbgRecords())
1620 using CurrentAndEndIt =
1621 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1627 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1628 return Pair.first == Pair.second;
1634 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1640 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1642 if (!
Other->hasDbgRecords())
1645 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1652 while (
none_of(Itrs, atEnd)) {
1653 bool HoistDVRs = allIdentical(Itrs);
1654 for (CurrentAndEndIt &Pair : Itrs) {
1668 if (I1->isIdenticalToWhenDefined(I2,
true))
1673 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1674 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1675 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1677 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1678 return I1->getOperand(0) == I2->
getOperand(1) &&
1744 auto &Context = BI->
getParent()->getContext();
1749 Value *Mask =
nullptr;
1750 Value *MaskFalse =
nullptr;
1751 Value *MaskTrue =
nullptr;
1752 if (Invert.has_value()) {
1753 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1754 Mask = Builder.CreateBitCast(
1759 MaskFalse = Builder.CreateBitCast(
1761 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1763 auto PeekThroughBitcasts = [](
Value *V) {
1765 V = BitCast->getOperand(0);
1768 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1770 if (!Invert.has_value())
1771 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1776 auto *Op0 =
I->getOperand(0);
1777 CallInst *MaskedLoadStore =
nullptr;
1780 auto *Ty =
I->getType();
1782 Value *PassThru =
nullptr;
1783 if (Invert.has_value())
1784 for (
User *U :
I->users()) {
1786 PassThru = Builder.CreateBitCast(
1795 Builder.SetInsertPoint(Ins);
1798 MaskedLoadStore = Builder.CreateMaskedLoad(
1800 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1803 I->replaceAllUsesWith(NewLoadStore);
1806 auto *StoredVal = Builder.CreateBitCast(
1808 MaskedLoadStore = Builder.CreateMaskedStore(
1819 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1821 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1825 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1826 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1829 I->eraseFromParent();
1836 bool IsStore =
false;
1859bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1860 bool AllInstsEqOnly) {
1876 for (
auto *Succ : UniqueSuccessors) {
1892 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1894 for (
auto *Succ : UniqueSuccessors) {
1898 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1901 if (AllInstsEqOnly) {
1908 none_of(UniqueSuccessors, [&UniqueSuccessors](BasicBlock *Succ) {
1909 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1911 return !
Term->isSameOperationAs(Term0) ||
1913 UniqueSuccessors[0]->size() != Succ->
size();
1918 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1919 while (LRI.isValid()) {
1921 if (
any_of(*LRI, [I0](Instruction *
I) {
1936 unsigned NumSkipped = 0;
1939 if (SuccIterPairs.
size() > 2) {
1942 if (SuccIterPairs.
size() < 2)
1949 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1950 auto &BB1ItrPair = *SuccIterPairBegin++;
1951 auto OtherSuccIterPairRange =
1957 bool AllInstsAreIdentical =
true;
1958 bool HasTerminator =
I1->isTerminator();
1959 for (
auto &SuccIter : OtherSuccIterRange) {
1963 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1964 AllInstsAreIdentical =
false;
1967 SmallVector<Instruction *, 8> OtherInsts;
1968 for (
auto &SuccIter : OtherSuccIterRange)
1973 if (HasTerminator) {
1977 if (NumSkipped || !AllInstsAreIdentical) {
1982 return hoistSuccIdenticalTerminatorToSwitchOrIf(
1983 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
1987 if (AllInstsAreIdentical) {
1988 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1989 AllInstsAreIdentical =
1991 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1993 unsigned SkipFlagsBB2 = Pair.second;
2003 if (AllInstsAreIdentical) {
2013 for (
auto &SuccIter : OtherSuccIterRange) {
2021 assert(
Success &&
"We should not be trying to hoist callbases "
2022 "with non-intersectable attributes");
2034 NumHoistCommonCode += SuccIterPairs.
size();
2036 NumHoistCommonInstrs += SuccIterPairs.
size();
2045 for (
auto &SuccIterPair : SuccIterPairs) {
2054bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2055 Instruction *TI, Instruction *I1,
2056 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2066 auto *I2 = *OtherSuccTIs.
begin();
2086 for (PHINode &PN : Succ->
phis()) {
2087 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2088 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2089 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2109 if (!
NT->getType()->isVoidTy()) {
2110 I1->replaceAllUsesWith(NT);
2111 for (Instruction *OtherSuccTI : OtherSuccTIs)
2112 OtherSuccTI->replaceAllUsesWith(NT);
2116 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2122 for (
auto *OtherSuccTI : OtherSuccTIs)
2123 Locs.
push_back(OtherSuccTI->getDebugLoc());
2135 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2137 for (PHINode &PN : Succ->
phis()) {
2138 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2139 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2145 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2155 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2156 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2157 PN.setIncomingValue(i, SI);
2168 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2174 for (BasicBlock *Succ : UniqueSuccessors)
2175 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2189 if (
I->isIntDivRem())
2204 std::optional<unsigned> NumUses;
2205 for (
auto *
I : Insts) {
2208 I->getType()->isTokenTy())
2213 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2221 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2225 NumUses =
I->getNumUses();
2226 else if (NumUses !=
I->getNumUses())
2232 for (
auto *
I : Insts) {
2246 for (
const Use &U : I0->
uses()) {
2247 auto It = PHIOperands.find(&U);
2248 if (It == PHIOperands.end())
2251 if (!
equal(Insts, It->second))
2263 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2264 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2265 if (HaveIndirectCalls) {
2266 if (!AllCallsAreIndirect)
2270 Value *Callee =
nullptr;
2274 Callee = CurrCallee;
2275 else if (Callee != CurrCallee)
2281 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2287 if (!
all_of(Insts, SameAsI0)) {
2293 for (
auto *
I : Insts)
2294 Ops.push_back(
I->getOperand(OI));
2304 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2309 for (
auto *BB : Blocks) {
2311 I =
I->getPrevNode();
2336 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2339 PN->insertBefore(BBEnd->begin());
2340 for (
auto *
I : Insts)
2341 PN->addIncoming(
I->getOperand(O),
I->getParent());
2350 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2353 for (
auto *
I : Insts)
2367 assert(
Success &&
"We should not be trying to sink callbases "
2368 "with non-intersectable attributes");
2379 PN->replaceAllUsesWith(I0);
2380 PN->eraseFromParent();
2384 for (
auto *
I : Insts) {
2389 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2390 I->replaceAllUsesWith(I0);
2391 I->eraseFromParent();
2441 bool HaveNonUnconditionalPredecessors =
false;
2444 if (PredBr && PredBr->isUnconditional())
2447 HaveNonUnconditionalPredecessors =
true;
2449 if (UnconditionalPreds.
size() < 2)
2462 for (
const Use &U : PN.incoming_values())
2463 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2464 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2466 Ops.push_back(*IncomingVals[Pred]);
2474 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2487 if (!followedByDeoptOrUnreachable) {
2489 auto IsMemOperand = [](
Use &U) {
2502 unsigned NumPHIInsts = 0;
2503 for (
Use &U : (*LRI)[0]->operands()) {
2504 auto It = PHIOperands.
find(&U);
2505 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2506 return InstructionsToSink.contains(V);
2513 if (IsMemOperand(U) &&
2514 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2521 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2522 return NumPHIInsts <= 1;
2539 while (Idx < ScanIdx) {
2540 if (!ProfitableToSinkInstruction(LRI)) {
2543 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2556 if (Idx < ScanIdx) {
2559 InstructionsToSink = InstructionsProfitableToSink;
2565 !ProfitableToSinkInstruction(LRI) &&
2566 "We already know that the last instruction is unprofitable to sink");
2574 for (
auto *
I : *LRI)
2575 InstructionsProfitableToSink.
erase(
I);
2576 if (!ProfitableToSinkInstruction(LRI)) {
2579 InstructionsToSink = InstructionsProfitableToSink;
2593 if (HaveNonUnconditionalPredecessors) {
2594 if (!followedByDeoptOrUnreachable) {
2602 bool Profitable =
false;
2603 while (Idx < ScanIdx) {
2637 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2639 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2647 NumSinkCommonInstrs++;
2651 ++NumSinkCommonCode;
2657struct CompatibleSets {
2658 using SetTy = SmallVector<InvokeInst *, 2>;
2664 SetTy &getCompatibleSet(InvokeInst *
II);
2666 void insert(InvokeInst *
II);
2669CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2674 for (CompatibleSets::SetTy &Set : Sets) {
2675 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2680 return Sets.emplace_back();
2683void CompatibleSets::insert(InvokeInst *
II) {
2684 getCompatibleSet(
II).emplace_back(
II);
2688 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2691 auto IsIllegalToMerge = [](InvokeInst *
II) {
2692 return II->cannotMerge() ||
II->isInlineAsm();
2694 if (
any_of(Invokes, IsIllegalToMerge))
2699 auto IsIndirectCall = [](InvokeInst *
II) {
return II->isIndirectCall(); };
2700 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2701 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2702 if (HaveIndirectCalls) {
2703 if (!AllCallsAreIndirect)
2708 for (InvokeInst *
II : Invokes) {
2709 Value *CurrCallee =
II->getCalledOperand();
2710 assert(CurrCallee &&
"There is always a called operand.");
2713 else if (Callee != CurrCallee)
2720 auto HasNormalDest = [](InvokeInst *
II) {
2723 if (
any_of(Invokes, HasNormalDest)) {
2726 if (!
all_of(Invokes, HasNormalDest))
2731 for (InvokeInst *
II : Invokes) {
2733 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2735 NormalBB = CurrNormalBB;
2736 else if (NormalBB != CurrNormalBB)
2744 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2753 for (InvokeInst *
II : Invokes) {
2755 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2757 UnwindBB = CurrUnwindBB;
2759 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2766 Invokes.front()->getUnwindDest(),
2767 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2772 const InvokeInst *II0 = Invokes.front();
2773 for (
auto *
II : Invokes.drop_front())
2778 auto IsIllegalToMergeArguments = [](
auto Ops) {
2779 Use &U0 = std::get<0>(
Ops);
2780 Use &U1 = std::get<1>(
Ops);
2786 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2787 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2788 IsIllegalToMergeArguments))
2800 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2806 bool HasNormalDest =
2811 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2815 II0->
getParent()->getIterator()->getNextNode();
2820 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2824 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2826 if (!HasNormalDest) {
2830 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2838 return MergedInvoke;
2852 SuccBBOfMergedInvoke});
2862 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2868 if (!IsIndirectCall)
2875 return II->getOperand(U.getOperandNo()) != U.get();
2894 Invokes.
front()->getParent());
2902 if (!MergedDebugLoc)
2903 MergedDebugLoc =
II->getDebugLoc();
2911 OrigSuccBB->removePredecessor(
II->getParent());
2917 assert(
Success &&
"Merged invokes with incompatible attributes");
2920 II->replaceAllUsesWith(MergedInvoke);
2921 II->eraseFromParent();
2925 ++NumInvokeSetsFormed;
2961 CompatibleSets Grouper;
2971 if (Invokes.
size() < 2)
2983class EphemeralValueTracker {
2984 SmallPtrSet<const Instruction *, 32> EphValues;
2986 bool isEphemeral(
const Instruction *
I) {
2989 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2990 all_of(
I->users(), [&](
const User *U) {
2991 return EphValues.count(cast<Instruction>(U));
2996 bool track(
const Instruction *
I) {
2997 if (isEphemeral(
I)) {
3048 unsigned MaxNumInstToLookAt = 9;
3052 if (!MaxNumInstToLookAt)
3054 --MaxNumInstToLookAt;
3064 if (
SI->getPointerOperand() == StorePtr &&
3065 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3068 return SI->getValueOperand();
3073 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3074 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3076 bool ExplicitlyDereferenceableOnly;
3081 (!ExplicitlyDereferenceableOnly ||
3083 LI->getDataLayout()))) {
3099 unsigned &SpeculatedInstructions,
3107 bool HaveRewritablePHIs =
false;
3109 Value *OrigV = PN.getIncomingValueForBlock(BB);
3110 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3117 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3126 HaveRewritablePHIs =
true;
3129 if (!OrigCE && !ThenCE)
3136 if (OrigCost + ThenCost > MaxCost)
3143 ++SpeculatedInstructions;
3144 if (SpeculatedInstructions > 1)
3148 return HaveRewritablePHIs;
3152 std::optional<bool> Invert,
3156 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3163 if (!Invert.has_value())
3166 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3170 return BIEndProb < Likely;
3210bool SimplifyCFGOpt::speculativelyExecuteBB(BranchInst *BI,
3211 BasicBlock *ThenBB) {
3227 bool Invert =
false;
3242 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3244 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3246 unsigned SpeculatedInstructions = 0;
3247 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3248 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3249 Value *SpeculatedStoreValue =
nullptr;
3250 StoreInst *SpeculatedStore =
nullptr;
3251 EphemeralValueTracker EphTracker;
3266 if (EphTracker.track(&
I))
3271 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3273 SpeculatedConditionalLoadsStores.
size() <
3277 if (IsSafeCheapLoadStore)
3278 SpeculatedConditionalLoadsStores.
push_back(&
I);
3280 ++SpeculatedInstructions;
3282 if (SpeculatedInstructions > 1)
3286 if (!IsSafeCheapLoadStore &&
3289 (SpeculatedStoreValue =
3292 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3298 if (!SpeculatedStore && SpeculatedStoreValue)
3304 for (Use &
Op :
I.operands()) {
3309 ++SinkCandidateUseCounts[OpI];
3316 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3317 if (Inst->hasNUses(
Count)) {
3318 ++SpeculatedInstructions;
3319 if (SpeculatedInstructions > 1)
3326 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3329 SpeculatedInstructions,
Cost,
TTI);
3330 if (!Convert ||
Cost > Budget)
3334 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3338 if (SpeculatedStoreValue) {
3342 Value *FalseV = SpeculatedStoreValue;
3346 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3376 for (DbgVariableRecord *DbgAssign :
3379 DbgAssign->replaceVariableLocationOp(OrigV, S);
3389 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3392 I.dropUBImplyingAttrsAndMetadata();
3395 if (EphTracker.contains(&
I)) {
3397 I.eraseFromParent();
3403 for (
auto &It : *ThenBB)
3408 !DVR || !DVR->isDbgAssign())
3409 It.dropOneDbgRecord(&DR);
3411 std::prev(ThenBB->end()));
3413 if (!SpeculatedConditionalLoadsStores.
empty())
3419 for (PHINode &PN : EndBB->
phis()) {
3420 unsigned OrigI = PN.getBasicBlockIndex(BB);
3421 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3422 Value *OrigV = PN.getIncomingValue(OrigI);
3423 Value *ThenV = PN.getIncomingValue(ThenI);
3432 Value *TrueV = ThenV, *FalseV = OrigV;
3436 PN.setIncomingValue(OrigI, V);
3437 PN.setIncomingValue(ThenI, V);
3441 for (Instruction *
I : SpeculatedPseudoProbes)
3442 I->eraseFromParent();
3455 if (!ReachesNonLocalUses.
insert(BB).second)
3470 EphemeralValueTracker EphTracker;
3477 if (CI->cannotDuplicate() || CI->isConvergent())
3490 for (
User *U :
I.users()) {
3493 if (UsedInBB == BB) {
3497 NonLocalUseBlocks.
insert(UsedInBB);
3511 if (
I &&
I->getParent() == To)
3527static std::optional<bool>
3548 KnownValues[CB].
insert(Pred);
3552 if (KnownValues.
empty())
3577 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3580 for (
const auto &Pair : KnownValues) {
3597 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3602 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3605 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3613 EdgeBB->setName(RealDest->
getName() +
".critedge");
3614 EdgeBB->moveBefore(RealDest);
3624 TranslateMap[
Cond] = CB;
3637 N->insertInto(EdgeBB, InsertPt);
3640 N->setName(BBI->getName() +
".c");
3651 if (!BBI->use_empty())
3652 TranslateMap[&*BBI] = V;
3653 if (!
N->mayHaveSideEffects()) {
3654 N->eraseFromParent();
3659 if (!BBI->use_empty())
3660 TranslateMap[&*BBI] =
N;
3666 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3667 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3668 SrcDbgCursor = std::next(BBI);
3670 N->cloneDebugInfoFrom(&*BBI);
3679 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3680 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3681 InsertPt->cloneDebugInfoFrom(BI);
3702 return std::nullopt;
3708bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(BranchInst *BI) {
3715 std::optional<bool>
Result;
3716 bool EverChanged =
false;
3722 }
while (Result == std::nullopt);
3731 bool SpeculateUnpredictables) {
3753 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3756 "Will have either one or two blocks to speculate.");
3763 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3764 if (!IsUnpredictable) {
3767 (TWeight + FWeight) != 0) {
3772 if (IfBlocks.
size() == 1) {
3774 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3775 if (BIBBProb >= Likely)
3778 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3787 if (IfCondPhiInst->getParent() == BB)
3795 unsigned NumPhis = 0;
3808 if (SpeculateUnpredictables && IsUnpredictable)
3809 Budget +=
TTI.getBranchMispredictPenalty();
3822 AggressiveInsts, Cost, Budget,
TTI, AC,
3823 ZeroCostInstructions) ||
3825 AggressiveInsts, Cost, Budget,
TTI, AC,
3826 ZeroCostInstructions))
3838 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3849 auto IsBinOpOrAnd = [](
Value *V) {
3866 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3879 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3881 <<
" F: " << IfFalse->
getName() <<
"\n");
3898 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3903 PN->eraseFromParent();
3909 Builder.CreateBr(BB);
3930 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3931 if (
Opc == Instruction::And)
3932 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3933 if (
Opc == Instruction::Or)
3934 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3946 bool PredHasWeights =
3948 bool SuccHasWeights =
3950 if (PredHasWeights || SuccHasWeights) {
3951 if (!PredHasWeights)
3952 PredTrueWeight = PredFalseWeight = 1;
3953 if (!SuccHasWeights)
3954 SuccTrueWeight = SuccFalseWeight = 1;
3964static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3968 "Both blocks must end with a conditional branches.");
3970 "PredBB must be a predecessor of BB.");
3978 (PTWeight + PFWeight) != 0) {
3981 Likely =
TTI->getPredictableBranchThreshold();
3986 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3987 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3991 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3994 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3995 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4001 return std::nullopt;
4014 bool InvertPredCond;
4015 std::tie(CommonSucc,
Opc, InvertPredCond) =
4018 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4025 {LLVMContext::MD_annotation});
4028 if (InvertPredCond) {
4041 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4044 SuccTrueWeight, SuccFalseWeight)) {
4050 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4055 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4056 PredTrueWeight * SuccFalseWeight);
4062 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4063 PredFalseWeight * SuccTrueWeight);
4065 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4107 if (!MDWeights.
empty()) {
4108 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4113 ++NumFoldBranchToCommonDest;
4120 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4121 return U->getType()->isVectorTy();
4131 unsigned BonusInstThreshold) {
4145 Cond->getParent() != BB || !
Cond->hasOneUse())
4166 bool InvertPredCond;
4168 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4200 unsigned NumBonusInsts = 0;
4201 bool SawVectorOp =
false;
4202 const unsigned PredCount = Preds.
size();
4219 NumBonusInsts += PredCount;
4227 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4230 return PN->getIncomingBlock(U) == BB;
4231 return UI->
getParent() == BB &&
I.comesBefore(UI);
4235 if (!
all_of(
I.uses(), IsBCSSAUse))
4239 BonusInstThreshold *
4255 for (
auto *BB : {BB1, BB2}) {
4271 Value *AlternativeV =
nullptr) {
4297 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4298 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4306 if (!AlternativeV &&
4312 PHI->addIncoming(V, BB);
4322 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4331 if (!PStore || !QStore)
4352 if (
I.mayReadOrWriteMemory())
4354 for (
auto &
I : *QFB)
4355 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4358 for (
auto &
I : *QTB)
4359 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4363 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4379 if (
I.isTerminator())
4397 "When we run out of budget we will eagerly return from within the "
4398 "per-instruction loop.");
4402 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4404 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4405 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4441 InvertPCond ^= (PStore->
getParent() != PTB);
4442 InvertQCond ^= (QStore->
getParent() != QTB);
4463 {CombinedWeights[0], CombinedWeights[1]},
4527 bool InvertPCond =
false, InvertQCond =
false;
4533 if (QFB == PostBB) {
4552 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4555 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4563 for (
auto *BB : {PTB, PFB}) {
4568 PStoreAddresses.
insert(
SI->getPointerOperand());
4570 for (
auto *BB : {QTB, QFB}) {
4575 QStoreAddresses.
insert(
SI->getPointerOperand());
4581 auto &CommonAddresses = PStoreAddresses;
4584 for (
auto *Address : CommonAddresses)
4587 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4605 !BI->
getParent()->getSinglePredecessor())
4607 if (!IfFalseBB->
phis().empty())
4617 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4720 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4722 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4726 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4729 if (CommonDestProb >= Likely)
4739 unsigned NumPhis = 0;
4761 if (OtherDest == BB) {
4769 OtherDest = InfLoopBlock;
4781 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4785 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4789 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4804 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4805 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4808 SuccTrueWeight, SuccFalseWeight);
4810 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4811 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4812 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4813 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4817 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4818 PredOther * SuccCommon,
4819 PredOther * SuccOther};
4827 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4846 Value *BIV = PN.getIncomingValueForBlock(BB);
4847 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4848 Value *PBIV = PN.getIncomingValue(PBBIdx);
4852 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4853 PN.setIncomingValue(PBBIdx, NV);
4857 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4858 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4878bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4880 BasicBlock *FalseBB,
4881 uint32_t TrueWeight,
4882 uint32_t FalseWeight) {
4889 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4891 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4894 for (BasicBlock *Succ :
successors(OldTerm)) {
4896 if (Succ == KeepEdge1)
4897 KeepEdge1 =
nullptr;
4898 else if (Succ == KeepEdge2)
4899 KeepEdge2 =
nullptr;
4904 if (Succ != TrueBB && Succ != FalseBB)
4905 RemovedSuccessors.
insert(Succ);
4913 if (!KeepEdge1 && !KeepEdge2) {
4914 if (TrueBB == FalseBB) {
4925 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4945 SmallVector<DominatorTree::UpdateType, 2> Updates;
4947 for (
auto *RemovedSuccessor : RemovedSuccessors)
4948 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4959bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4964 if (!TrueVal || !FalseVal)
4969 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4970 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4973 uint32_t TrueWeight = 0, FalseWeight = 0;
4974 SmallVector<uint64_t, 8> Weights;
4978 if (Weights.
size() == 1 +
SI->getNumCases()) {
4980 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4982 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4987 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4996bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5010 SmallVector<uint32_t> SelectBranchWeights(2);
5014 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5015 SelectBranchWeights[0],
5016 SelectBranchWeights[1]);
5036bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5040 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5086bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5105 ConstantInt *NewCaseVal;
5113 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5119 SelectTrueVal = Builder.
getTrue();
5120 SelectFalseVal = Builder.
getFalse();
5123 SelectCond =
Select->getCondition();
5125 if (SelectCond != ICI)
5127 SelectTrueVal =
Select->getTrueValue();
5128 SelectFalseVal =
Select->getFalseValue();
5133 if (
SI->getCondition() != IcmpCond)
5139 if (
SI->getDefaultDest() != BB) {
5140 ConstantInt *VVal =
SI->findCaseDest(BB);
5141 assert(VVal &&
"Should have a unique destination value");
5149 return requestResimplify();
5155 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5157 if (Predicate == ICmpInst::ICMP_EQ)
5165 return requestResimplify();
5172 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5178 Value *DefaultCst = SelectFalseVal;
5179 Value *NewCst = SelectTrueVal;
5187 Select->replaceAllUsesWith(DefaultCst);
5188 Select->eraseFromParent();
5194 SmallVector<DominatorTree::UpdateType, 2> Updates;
5201 SwitchInstProfUpdateWrapper SIW(*SI);
5202 auto W0 = SIW.getSuccessorWeight(0);
5205 NewW = ((uint64_t(*W0) + 1) >> 1);
5206 SIW.setSuccessorWeight(0, *NewW);
5208 SIW.addCase(NewCaseVal, NewBB, NewW);
5210 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5219 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5228bool SimplifyCFGOpt::simplifyBranchOnICmpChain(BranchInst *BI,
5230 const DataLayout &
DL) {
5240 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5242 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5243 Value *CompVal = ConstantCompare.CompValue;
5244 unsigned UsedICmps = ConstantCompare.UsedICmps;
5245 Value *ExtraCase = ConstantCompare.Extra;
5246 bool TrueWhenEqual = ConstantCompare.IsEq;
5263 if (ExtraCase && Values.
size() < 2)
5266 SmallVector<uint32_t> BranchWeights;
5273 if (!TrueWhenEqual) {
5276 std::swap(BranchWeights[0], BranchWeights[1]);
5282 <<
" cases into SWITCH. BB is:\n"
5285 SmallVector<DominatorTree::UpdateType, 2> Updates;
5292 nullptr,
"switch.early.test");
5303 AssumptionCache *AC =
Options.AC;
5309 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5316 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5322 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5323 <<
"\nEXTRABB = " << *BB);
5331 "Should not end up here with unstable pointers");
5333 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5338 if (Values.
front()->getValue() - Values.
back()->getValue() ==
5339 Values.
size() - 1) {
5341 Values.
back()->getValue(), Values.
front()->getValue() + 1);
5343 ICmpInst::Predicate Pred;
5361 SmallVector<uint32_t> NewWeights(Values.
size() + 1);
5362 NewWeights[0] = BranchWeights[1];
5365 V = BranchWeights[0] / Values.
size();
5370 for (ConstantInt *Val : Values)
5371 New->addCase(Val, EdgeBB);
5379 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5389 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5393bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5395 return simplifyCommonResume(RI);
5399 return simplifySingleResume(RI);
5412 switch (IntrinsicID) {
5413 case Intrinsic::dbg_declare:
5414 case Intrinsic::dbg_value:
5415 case Intrinsic::dbg_label:
5416 case Intrinsic::lifetime_end:
5426bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5435 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5439 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5441 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5442 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5446 if (IncomingBB->getUniqueSuccessor() != BB)
5451 if (IncomingValue != LandingPad)
5455 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5456 TrivialUnwindBlocks.
insert(IncomingBB);
5460 if (TrivialUnwindBlocks.
empty())
5464 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5468 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5471 for (BasicBlock *Pred :
5482 TrivialBB->getTerminator()->eraseFromParent();
5483 new UnreachableInst(RI->
getContext(), TrivialBB);
5485 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5492 return !TrivialUnwindBlocks.empty();
5496bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5500 "Resume must unwind the exception that caused control to here");
5556 int Idx = DestPN.getBasicBlockIndex(BB);
5570 Value *SrcVal = DestPN.getIncomingValue(Idx);
5573 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5577 DestPN.addIncoming(
Incoming, Pred);
5604 std::vector<DominatorTree::UpdateType> Updates;
5608 if (UnwindDest ==
nullptr) {
5649 if (!SuccessorCleanupPad)
5658 SuccessorCleanupPad->eraseFromParent();
5667bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5684bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5716 BBI->dropDbgRecords();
5720 BBI->eraseFromParent();
5726 if (&BB->
front() != UI)
5729 std::vector<DominatorTree::UpdateType> Updates;
5732 for (BasicBlock *Predecessor : Preds) {
5739 [BB](
auto *
Successor) { return Successor == BB; })) {
5747 "The destinations are guaranteed to be different here.");
5748 CallInst *Assumption;
5764 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5766 SwitchInstProfUpdateWrapper SU(*SI);
5767 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5768 if (i->getCaseSuccessor() != BB) {
5773 i = SU.removeCase(i);
5778 if (DTU &&
SI->getDefaultDest() != BB)
5779 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5781 if (
II->getUnwindDest() == BB) {
5787 if (!CI->doesNotThrow())
5788 CI->setDoesNotThrow();
5792 if (CSI->getUnwindDest() == BB) {
5803 E = CSI->handler_end();
5806 CSI->removeHandler(
I);
5813 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5814 if (CSI->getNumHandlers() == 0) {
5815 if (CSI->hasUnwindDest()) {
5819 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5820 Updates.push_back({DominatorTree::Insert,
5821 PredecessorOfPredecessor,
5822 CSI->getUnwindDest()});
5823 Updates.push_back({DominatorTree::Delete,
5824 PredecessorOfPredecessor, Predecessor});
5827 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5834 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5835 for (BasicBlock *EHPred : EHPreds)
5839 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5840 CSI->eraseFromParent();
5845 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5846 "Expected to always have an unwind to BB.");
5848 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5876static std::optional<ContiguousCasesResult>
5883 const APInt &Min = Cases.
back()->getValue();
5884 const APInt &Max = Cases.
front()->getValue();
5886 size_t ContiguousOffset = Cases.
size() - 1;
5887 if (
Offset == ContiguousOffset) {
5905 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
5906 return L->getValue() != R->getValue() + 1;
5908 if (It == Cases.
end())
5909 return std::nullopt;
5910 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5911 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5915 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5918 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5926 return std::nullopt;
5931 bool RemoveOrigDefaultBlock =
true) {
5933 auto *BB = Switch->getParent();
5934 auto *OrigDefaultBlock = Switch->getDefaultDest();
5935 if (RemoveOrigDefaultBlock)
5936 OrigDefaultBlock->removePredecessor(BB);
5940 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5942 Switch->setDefaultDest(&*NewDefaultBlock);
5946 if (RemoveOrigDefaultBlock &&
5956bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5958 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5960 bool HasDefault = !
SI->defaultDestUnreachable();
5962 auto *BB =
SI->getParent();
5964 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5969 for (
auto Case :
SI->cases()) {
5973 if (Dest == DestA) {
5979 if (Dest == DestB) {
5989 "Single-destination switch should have been folded.");
5991 assert(DestB !=
SI->getDefaultDest());
5992 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5996 std::optional<ContiguousCasesResult> ContiguousCases;
5999 if (!HasDefault && CasesA.
size() == 1)
6000 ContiguousCases = ContiguousCasesResult{
6008 else if (CasesB.
size() == 1)
6009 ContiguousCases = ContiguousCasesResult{
6018 else if (!HasDefault)
6022 if (!ContiguousCases)
6026 if (!ContiguousCases)
6029 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6035 Max->getValue() - Min->getValue() + 1);
6038 assert(
Max->getValue() == Min->getValue());
6043 else if (NumCases->
isNullValue() && !Cases->empty()) {
6047 if (!
Offset->isNullValue())
6055 SmallVector<uint64_t, 8> Weights;
6057 if (Weights.
size() == 1 +
SI->getNumCases()) {
6058 uint64_t TrueWeight = 0;
6059 uint64_t FalseWeight = 0;
6060 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6061 if (
SI->getSuccessor(
I) == Dest)
6062 TrueWeight += Weights[
I];
6064 FalseWeight += Weights[
I];
6066 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6077 unsigned PreviousEdges = Cases->size();
6078 if (Dest ==
SI->getDefaultDest())
6080 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6081 PHI.removeIncomingValue(
SI->getParent());
6084 unsigned PreviousEdges = OtherCases->size();
6085 if (OtherDest ==
SI->getDefaultDest())
6087 unsigned E = PreviousEdges - 1;
6091 for (
unsigned I = 0;
I !=
E; ++
I)
6092 PHI.removeIncomingValue(
SI->getParent());
6100 auto *UnreachableDefault =
SI->getDefaultDest();
6103 SI->eraseFromParent();
6105 if (!HasDefault && DTU)
6106 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
6124 unsigned MaxSignificantBitsInCond =
6131 for (
const auto &Case :
SI->cases()) {
6132 auto *
Successor = Case.getCaseSuccessor();
6143 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6149 }
else if (IsKnownValuesValid)
6150 KnownValues.
erase(CaseC);
6157 bool HasDefault = !
SI->defaultDestUnreachable();
6158 const unsigned NumUnknownBits =
6161 if (HasDefault && DeadCases.
empty()) {
6167 if (NumUnknownBits < 64 ) {
6168 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6169 if (
SI->getNumCases() == AllNumCases) {
6176 if (
SI->getNumCases() == AllNumCases - 1) {
6177 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6184 for (
const auto &Case :
SI->cases())
6185 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6187 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6189 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6199 if (DeadCases.
empty())
6205 assert(CaseI !=
SI->case_default() &&
6206 "Case was not found. Probably mistake in DeadCases forming.");
6208 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6213 std::vector<DominatorTree::UpdateType> Updates;
6214 for (
auto *
Successor : UniqueSuccessors)
6215 if (NumPerSuccessorCases[
Successor] == 0)
6236 if (!Branch || !Branch->isUnconditional())
6242 int Idx =
PHI.getBasicBlockIndex(BB);
6243 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6245 Value *InValue =
PHI.getIncomingValue(Idx);
6246 if (InValue != CaseValue)
6262 ForwardingNodesMap ForwardingNodes;
6265 for (
const auto &Case :
SI->cases()) {
6267 BasicBlock *CaseDest = Case.getCaseSuccessor();
6286 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6287 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6288 count(Phi.blocks(), SwitchBlock) == 1) {
6289 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6297 ForwardingNodes[Phi].push_back(PhiIdx);
6300 for (
auto &ForwardingNode : ForwardingNodes) {
6301 PHINode *Phi = ForwardingNode.first;
6307 for (
int Index : Indexes)
6308 Phi->setIncomingValue(Index,
SI->getCondition());
6318 if (
C->isThreadDependent())
6320 if (
C->isDLLImportDependent())
6336 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6363 if (
A->isAllOnesValue())
6365 if (
A->isNullValue())
6371 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6396 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6398 if (
I.isTerminator()) {
6400 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6403 CaseDest =
I.getSuccessor(0);
6410 for (
auto &
Use :
I.uses()) {
6413 if (
I->getParent() == CaseDest)
6416 if (Phi->getIncomingBlock(
Use) == CaseDest)
6429 *CommonDest = CaseDest;
6431 if (CaseDest != *CommonDest)
6436 int Idx =
PHI.getBasicBlockIndex(Pred);
6449 Res.push_back(std::make_pair(&
PHI, ConstVal));
6452 return Res.
size() > 0;
6458 SwitchCaseResultVectorTy &UniqueResults,
6460 for (
auto &
I : UniqueResults) {
6461 if (
I.first == Result) {
6462 I.second.push_back(CaseVal);
6463 return I.second.size();
6466 UniqueResults.push_back(
6477 SwitchCaseResultVectorTy &UniqueResults,
6481 uintptr_t MaxUniqueResults) {
6482 for (
const auto &
I :
SI->cases()) {
6496 const size_t NumCasesForResult =
6504 if (UniqueResults.size() > MaxUniqueResults)
6520 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6522 return DefaultResult ||
SI->defaultDestUnreachable();
6543 const bool HasBranchWeights =
6546 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6547 ResultVector[1].second.size() == 1) {
6548 ConstantInt *FirstCase = ResultVector[0].second[0];
6549 ConstantInt *SecondCase = ResultVector[1].second[0];
6550 Value *SelectValue = ResultVector[1].first;
6551 if (DefaultResult) {
6552 Value *ValueCompare =
6553 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6554 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6555 DefaultResult,
"switch.select");
6557 SI && HasBranchWeights) {
6564 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6568 Value *ValueCompare =
6569 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6570 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6571 SelectValue,
"switch.select");
6577 size_t FirstCasePos = (Condition !=
nullptr);
6578 size_t SecondCasePos = FirstCasePos + 1;
6579 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6581 {BranchWeights[FirstCasePos],
6582 DefaultCase + BranchWeights[SecondCasePos]},
6589 if (ResultVector.size() == 1 && DefaultResult) {
6591 unsigned CaseCount = CaseValues.
size();
6604 for (
auto *Case : CaseValues) {
6605 if (Case->getValue().slt(MinCaseVal->
getValue()))
6607 AndMask &= Case->getValue();
6617 if (FreeBits ==
Log2_32(CaseCount)) {
6618 Value *
And = Builder.CreateAnd(Condition, AndMask);
6619 Value *Cmp = Builder.CreateICmpEQ(
6622 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6638 for (
auto *Case : CaseValues)
6639 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6645 Condition = Builder.CreateSub(Condition, MinCaseVal);
6646 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6647 Value *Cmp = Builder.CreateICmpEQ(
6650 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6663 if (CaseValues.
size() == 2) {
6664 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6665 "switch.selectcmp.case1");
6666 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6667 "switch.selectcmp.case2");
6668 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6670 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6690 std::vector<DominatorTree::UpdateType> Updates;
6697 Builder.CreateBr(DestBB);
6701 PHI->removeIncomingValueIf(
6702 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6703 PHI->addIncoming(SelectValue, SelectBB);
6706 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6712 if (DTU && RemovedSuccessors.
insert(Succ).second)
6715 SI->eraseFromParent();
6730 SwitchCaseResultVectorTy UniqueResults;
6736 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6737 Builder.SetInsertPoint(
SI);
6740 [[maybe_unused]]
auto HasWeights =
6745 (BranchWeights.
size() >=
6746 UniqueResults.size() + (DefaultResult !=
nullptr)));
6749 Builder,
DL, BranchWeights);
6761class SwitchReplacement {
6768 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6769 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName);
6778 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6785 bool isLookupTable();
6822 ConstantInt *BitMap =
nullptr;
6823 IntegerType *BitMapElementTy =
nullptr;
6826 ConstantInt *LinearOffset =
nullptr;
6827 ConstantInt *LinearMultiplier =
nullptr;
6828 bool LinearMapValWrapped =
false;
6836SwitchReplacement::SwitchReplacement(
6838 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6839 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName)
6840 : DefaultValue(DefaultValue) {
6841 assert(Values.size() &&
"Can't build lookup table without values!");
6842 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6845 SingleValue = Values.begin()->second;
6847 ValueType = Values.begin()->second->getType();
6851 for (
const auto &[CaseVal, CaseRes] : Values) {
6854 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6855 TableContents[Idx] = CaseRes;
6862 if (Values.size() < TableSize) {
6864 "Need a default value to fill the lookup table holes.");
6867 if (!TableContents[
I])
6868 TableContents[
I] = DefaultValue;
6874 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6875 SingleValue =
nullptr;
6881 Kind = SingleValueKind;
6888 bool LinearMappingPossible =
true;
6893 bool NonMonotonic =
false;
6894 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6911 LinearMappingPossible =
false;
6916 APInt Dist = Val - PrevVal;
6919 }
else if (Dist != DistToPrev) {
6920 LinearMappingPossible =
false;
6928 if (LinearMappingPossible) {
6930 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6931 APInt M = LinearMultiplier->getValue();
6932 bool MayWrap =
true;
6933 if (
isIntN(M.getBitWidth(), TableSize - 1))
6934 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6935 LinearMapValWrapped = NonMonotonic || MayWrap;
6936 Kind = LinearMapKind;
6942 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6944 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6946 TableInt <<=
IT->getBitWidth();
6950 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6953 BitMap = ConstantInt::get(M.getContext(), TableInt);
6954 BitMapElementTy =
IT;
6963 Kind = LookupTableKind;
6969 case SingleValueKind:
6971 case LinearMapKind: {
6975 false,
"switch.idx.cast");
6976 if (!LinearMultiplier->
isOne())
6977 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6979 !LinearMapValWrapped);
6981 if (!LinearOffset->
isZero())
6984 !LinearMapValWrapped);
7001 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7002 "switch.shiftamt",
true,
true);
7005 Value *DownShifted =
7006 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7008 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7010 case LookupTableKind: {
7013 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7014 true, GlobalVariable::PrivateLinkage,
7015 Initializer,
"switch.table." +
Func->getName());
7016 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7019 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
7020 Type *IndexTy =
DL.getIndexType(Table->getType());
7023 if (
Index->getType() != IndexTy) {
7024 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7028 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7031 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7034 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7040bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7042 Type *ElementType) {
7050 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7052 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7058 if (
TTI.isTypeLegal(Ty))
7073 DL.fitsInLegalInteger(
IT->getBitWidth());
7076Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7078bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7080bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7091 return NumCases * 100 >= CaseRange * MinDensity;
7112 if (
SI->getNumCases() > TableSize)
7115 bool AllTablesFitInRegister =
true;
7116 bool HasIllegalType =
false;
7117 for (
const auto &Ty : ResultTypes) {
7122 AllTablesFitInRegister =
7123 AllTablesFitInRegister &&
7124 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7129 if (HasIllegalType && !AllTablesFitInRegister)
7134 if (AllTablesFitInRegister)
7151 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7154 return all_of(ResultTypes, [&](
const auto &ResultType) {
7155 return SwitchReplacement::wouldFitInRegister(
7183 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
7205 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7210 for (
auto ValuePair : Values) {
7213 if (!CaseConst || CaseConst == DefaultConst ||
7214 (CaseConst != TrueConst && CaseConst != FalseConst))
7228 if (DefaultConst == FalseConst) {
7231 ++NumTableCmpReuses;
7234 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7235 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7238 ++NumTableCmpReuses;
7248 bool ConvertSwitchToLookupTable) {
7249 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7263 if (
SI->getNumCases() < 3)
7285 MinCaseVal = CaseVal;
7287 MaxCaseVal = CaseVal;
7304 It->second.push_back(std::make_pair(CaseVal,
Value));
7312 bool HasDefaultResults =
7314 DefaultResultsList,
DL,
TTI);
7315 for (
const auto &
I : DefaultResultsList) {
7318 DefaultResults[
PHI] = Result;
7322 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7325 if (UseSwitchConditionAsTableIndex) {
7327 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7332 TableIndexOffset = MinCaseVal;
7339 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7341 bool TableHasHoles = (NumResults < TableSize);
7346 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7354 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7357 if (
SI->getNumCases() < 4)
7359 if (!
DL.fitsInLegalInteger(TableSize))
7368 if (UseSwitchConditionAsTableIndex) {
7369 TableIndex =
SI->getCondition();
7370 if (HasDefaultResults) {
7382 all_of(ResultTypes, [&](
const auto &ResultType) {
7383 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7388 TableSize = std::max(UpperBound, TableSize);
7391 DefaultIsReachable =
false;
7399 const auto &ResultList = ResultLists[
PHI];
7401 Type *ResultType = ResultList.begin()->second->getType();
7406 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7408 PhiToReplacementMap.
insert({
PHI, Replacement});
7411 bool AnyLookupTables =
any_of(
7412 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7413 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7414 [](
auto &KV) {
return KV.second.isBitMap(); });
7422 if (AnyLookupTables &&
7423 (!
TTI.shouldBuildLookupTables() ||
7429 if (!ConvertSwitchToLookupTable &&
7430 (AnyLookupTables || AnyBitMaps || NeedMask))
7433 Builder.SetInsertPoint(
SI);
7436 if (!UseSwitchConditionAsTableIndex) {
7439 bool MayWrap =
true;
7440 if (!DefaultIsReachable) {
7445 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7446 "switch.tableidx",
false,
7450 std::vector<DominatorTree::UpdateType> Updates;
7456 assert(MaxTableSize >= TableSize &&
7457 "It is impossible for a switch to have more entries than the max "
7458 "representable value of its input integer type's size.");
7463 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7468 Builder.SetInsertPoint(
SI);
7469 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7470 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7471 Builder.CreateBr(LookupBB);
7477 Value *Cmp = Builder.CreateICmpULT(
7478 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7480 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7481 CondBranch = RangeCheckBranch;
7487 Builder.SetInsertPoint(LookupBB);
7493 MaskBB->
setName(
"switch.hole_check");
7500 APInt MaskInt(TableSizePowOf2, 0);
7501 APInt One(TableSizePowOf2, 1);
7503 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7504 for (
const auto &Result : ResultList) {
7507 MaskInt |= One << Idx;
7509 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7516 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7517 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7518 Value *LoBit = Builder.CreateTrunc(
7520 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7525 Builder.SetInsertPoint(LookupBB);
7529 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7532 SI->getDefaultDest()->removePredecessor(BB,
7539 const ResultListTy &ResultList = ResultLists[
PHI];
7540 auto Replacement = PhiToReplacementMap.
at(
PHI);
7541 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7544 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7547 for (
auto *
User :
PHI->users()) {
7549 Replacement.getDefaultValue(), ResultList);
7553 PHI->addIncoming(Result, LookupBB);
7556 Builder.CreateBr(CommonDest);
7568 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7571 if (Succ ==
SI->getDefaultDest()) {
7572 if (HasBranchWeights)
7573 ToDefaultWeight += BranchWeights[
I];
7577 if (DTU && RemovedSuccessors.
insert(Succ).second)
7579 if (HasBranchWeights)
7580 ToLookupWeight += BranchWeights[
I];
7582 SI->eraseFromParent();
7583 if (HasBranchWeights)
7590 ++NumLookupTablesHoles;
7606 if (CondTy->getIntegerBitWidth() > 64 ||
7607 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7611 if (
SI->getNumCases() < 4)
7619 for (
const auto &
C :
SI->cases())
7620 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7628 int64_t
Base = Values[0];
7629 for (
auto &V : Values)
7642 unsigned Shift = 64;
7643 for (
auto &V : Values)
7647 for (
auto &V : Values)
7648 V = (int64_t)((
uint64_t)V >> Shift);
7665 Builder.SetInsertPoint(
SI);
7667 Builder.CreateSub(
SI->getCondition(), ConstantInt::get(Ty,
Base));
7668 Value *Rot = Builder.CreateIntrinsic(
7669 Ty, Intrinsic::fshl,
7670 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7671 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7673 for (
auto Case :
SI->cases()) {
7674 auto *Orig = Case.getCaseValue();
7675 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7720 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
7721 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
7737 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
7740 return !Updates.
empty();
7770 Value *Condition =
SI->getCondition();
7774 if (CondTy->getIntegerBitWidth() > 64 ||
7775 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7787 if (
SI->getNumCases() < 4)
7792 for (
const auto &Case :
SI->cases()) {
7793 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7807 Builder.SetInsertPoint(
SI);
7809 if (!
SI->defaultDestUnreachable()) {
7812 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
7813 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
7815 auto *OrigBB =
SI->getParent();
7816 auto *DefaultCaseBB =
SI->getDefaultDest();
7818 auto It = OrigBB->getTerminator()->getIterator();
7823 if (HasWeights &&
any_of(Weights, [](
const auto &V) {
return V != 0; })) {
7831 NewWeights[1] = Weights[0] / 2;
7832 NewWeights[0] = OrigDenominator - NewWeights[1];
7844 Weights[0] = NewWeights[1];
7845 uint64_t CasesDenominator = OrigDenominator - Weights[0];
7847 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
7853 It->eraseFromParent();
7861 for (
auto &Case :
SI->cases()) {
7862 auto *OrigValue = Case.getCaseValue();
7863 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7864 OrigValue->getValue().countr_zero()));
7868 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7871 SI->setCondition(ConditionTrailingZeros);
7881 if (!Cmp || !Cmp->hasOneUse())
7892 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7895 if (
SI->getNumCases() == 2) {
7902 Succ =
SI->getDefaultDest();
7903 SuccWeight = Weights[0];
7905 for (
auto &Case :
SI->cases()) {
7906 std::optional<int64_t> Val =
7910 if (!Missing.erase(*Val))
7915 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7918 assert(Missing.size() == 1 &&
"Should have one case left");
7919 Res = *Missing.begin();
7920 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7922 Unreachable =
SI->getDefaultDest();
7924 for (
auto &Case :
SI->cases()) {
7925 BasicBlock *NewSucc = Case.getCaseSuccessor();
7926 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7929 OtherSuccWeight += Weight;
7932 SuccWeight = Weight;
7933 }
else if (Succ == NewSucc) {
7939 for (
auto &Case :
SI->cases()) {
7940 std::optional<int64_t> Val =
7942 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7944 if (Case.getCaseSuccessor() == Succ) {
7966 if (Cmp->isSigned())
7969 MDNode *NewWeights =
nullptr;
7975 Builder.SetInsertPoint(
SI->getIterator());
7976 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
7977 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
7978 SI->getMetadata(LLVMContext::MD_unpredictable));
7982 SI->eraseFromParent();
7983 Cmp->eraseFromParent();
7984 if (DTU && Unreachable)
8015 "Only supporting unconditional branches for now");
8017 "Expected unconditional branches to have one successor");
8018 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
8039 if (LHS == EKey || RHS == EKey || LHS == TKey || RHS == TKey)
8055 "Only supporting unconditional branches for now");
8062 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8063 if (PredIVs[
A] != PredIVs[
B])
8071bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *
SI,
8085 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
8090 if (BB->
size() != 1)
8100 if (!Seen.
insert(BB).second) {
8101 auto It = BBToSuccessorIndexes.
find(BB);
8102 if (It != BBToSuccessorIndexes.
end())
8103 It->second.emplace_back(
I);
8117 Cases.
emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs});
8118 BBToSuccessorIndexes[BB].emplace_back(
I);
8124 for (PHINode *Phi : Phis) {
8126 PhiPredIVs.
try_emplace(Phi,
Phi->getNumIncomingValues()).first->second;
8127 for (
auto &
IV :
Phi->incoming_values())
8128 IVs.insert({
Phi->getIncomingBlock(
IV),
IV.get()});
8139 DenseSet<const SwitchSuccWrapper *> ReplaceWith;
8144 bool MadeChange =
false;
8145 for (
auto &SSW : Cases) {
8152 Updates.
push_back({DominatorTree::Delete,
SI->getParent(), SSW.Dest});
8153 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
8154 for (
unsigned Idx : Successors)
8155 SI->setSuccessor(Idx, (*It)->Dest);
8166bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8169 if (isValueEqualityComparison(SI)) {
8173 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8174 return requestResimplify();
8178 if (simplifySwitchOnSelect(SI,
Select))
8179 return requestResimplify();
8184 if (foldValueComparisonIntoPredecessors(SI, Builder))
8185 return requestResimplify();
8191 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8192 return requestResimplify();
8196 return requestResimplify();
8199 return requestResimplify();
8202 return requestResimplify();
8205 return requestResimplify();
8210 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8212 Options.ConvertSwitchToLookupTable))
8213 return requestResimplify();
8216 return requestResimplify();
8219 return requestResimplify();
8222 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8223 return requestResimplify();
8225 if (simplifyDuplicateSwitchArms(SI, DTU))
8226 return requestResimplify();
8229 return requestResimplify();
8234bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8237 SmallVector<uint32_t> BranchWeights;
8241 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8242 if (HasBranchWeights)
8247 SmallPtrSet<Value *, 8> Succs;
8248 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8253 RemovedSuccs.
insert(Dest);
8263 std::vector<DominatorTree::UpdateType> Updates;
8264 Updates.reserve(RemovedSuccs.
size());
8265 for (
auto *RemovedSucc : RemovedSuccs)
8266 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8283 if (HasBranchWeights) {
8290 if (simplifyIndirectBrOnSelect(IBI, SI))
8291 return requestResimplify();
8327 if (BB == OtherPred)
8338 std::vector<DominatorTree::UpdateType> Updates;
8345 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8346 "unexpected successor");
8347 II->setUnwindDest(OtherPred);
8362 Builder.CreateUnreachable();
8371bool SimplifyCFGOpt::simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder) {
8372 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
8373 : simplifyCondBranch(
Branch, Builder);
8376bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
8388 bool NeedCanonicalLoop =
8402 if (
I->isTerminator() &&
8403 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8424 if (
Options.SpeculateBlocks &&
8427 return requestResimplify();
8435 if (!PPred || (PredPred && PredPred != PPred))
8472 if (!SuccBI || !SuccBI->isConditional())
8476 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8480 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8506 bool HasWeight =
false;
8511 BBTWeight = BBFWeight = 1;
8516 BB1TWeight = BB1FWeight = 1;
8521 BB2TWeight = BB2FWeight = 1;
8523 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8524 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8531bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder) {
8535 "Tautological conditional branch should have been eliminated already.");
8538 if (!
Options.SimplifyCondBranch ||
8543 if (isValueEqualityComparison(BI)) {
8548 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8549 return requestResimplify();
8555 if (foldValueComparisonIntoPredecessors(BI, Builder))
8556 return requestResimplify();
8559 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8560 return requestResimplify();
8565 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8578 return requestResimplify();
8584 if (
Options.SpeculateBlocks &&
8587 return requestResimplify();
8596 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8597 return requestResimplify();
8599 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8601 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8602 auto CanSpeculateConditionalLoadsStores = [&]() {
8604 for (Instruction &
I : *Succ) {
8605 if (
I.isTerminator()) {
8606 if (
I.getNumSuccessors() > 1)
8610 SpeculatedConditionalLoadsStores.
size() ==
8614 SpeculatedConditionalLoadsStores.
push_back(&
I);
8617 return !SpeculatedConditionalLoadsStores.
empty();
8620 if (CanSpeculateConditionalLoadsStores()) {
8622 std::nullopt,
nullptr);
8623 return requestResimplify();
8633 return requestResimplify();
8642 return requestResimplify();
8648 if (foldCondBranchOnValueKnownInPredecessor(BI))
8649 return requestResimplify();
8654 if (PBI != BI && PBI->isConditional())
8656 return requestResimplify();
8662 if (PBI != BI && PBI->isConditional())
8664 return requestResimplify();
8668 return requestResimplify();
8675 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8687 auto *Use = cast<Instruction>(U.getUser());
8689 switch (Use->getOpcode()) {
8692 case Instruction::GetElementPtr:
8693 case Instruction::Ret:
8694 case Instruction::BitCast:
8695 case Instruction::Load:
8696 case Instruction::Store:
8697 case Instruction::Call:
8698 case Instruction::CallBr:
8699 case Instruction::Invoke:
8700 case Instruction::UDiv:
8701 case Instruction::URem:
8705 case Instruction::SDiv:
8706 case Instruction::SRem:
8710 if (FindUse ==
I->use_end())
8712 auto &
Use = *FindUse;
8717 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8718 User->comesBefore(
I))
8732 if (
GEP->getPointerOperand() ==
I) {
8735 if (
GEP->getType()->isVectorTy())
8743 if (!
GEP->hasAllZeroIndices() &&
8744 (!
GEP->isInBounds() ||
8746 GEP->getPointerAddressSpace())))
8747 PtrValueMayBeModified =
true;
8753 bool HasNoUndefAttr =
8754 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8759 if (
C->isNullValue() && HasNoUndefAttr &&
8760 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8761 return !PtrValueMayBeModified;
8767 if (!LI->isVolatile())
8769 LI->getPointerAddressSpace());
8773 if (!
SI->isVolatile())
8775 SI->getPointerAddressSpace())) &&
8776 SI->getPointerOperand() ==
I;
8781 if (
I == Assume->getArgOperand(0))
8789 if (CB->getCalledOperand() ==
I)
8792 if (CB->isArgOperand(&
Use)) {
8793 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8796 CB->paramHasNonNullAttr(ArgIdx,
false))
8797 return !PtrValueMayBeModified;
8816 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8826 Builder.CreateUnreachable();
8833 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8835 Assumption = Builder.CreateAssumption(
Cond);
8850 Builder.SetInsertPoint(Unreachable);
8852 Builder.CreateUnreachable();
8853 for (
const auto &Case :
SI->cases())
8854 if (Case.getCaseSuccessor() == BB) {
8856 Case.setSuccessor(Unreachable);
8858 if (
SI->getDefaultDest() == BB) {
8860 SI->setDefaultDest(Unreachable);
8874bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8899 return requestResimplify();
8920 if (
Options.SpeculateBlocks &&
8927 Options.SpeculateUnpredictables))
8934 case Instruction::Br:
8937 case Instruction::Resume:
8940 case Instruction::CleanupRet:
8943 case Instruction::Switch:
8946 case Instruction::Unreachable:
8949 case Instruction::IndirectBr:
8957bool SimplifyCFGOpt::run(BasicBlock *BB) {
8967 }
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 Value * getCondition(Instruction *I)
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
unsigned unsigned DefaultVal
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 isProfitableToSpeculate(const BranchInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
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 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 std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static void hoistConditionalLoadsStores(BranchInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
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 performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
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 bool extractPredSuccWeights(BranchInst *PBI, BranchInst *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 Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *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 tryToMergeLandingPad(LandingPadInst *LPad, BranchInst *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 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 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 mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
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 bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool 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...
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *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 size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, 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 void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool 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...
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 TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
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.
LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
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 if the block is well formed or null if the block is not well forme...
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
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() 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.
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.
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
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)
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.
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.
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.
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="")
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="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
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)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
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...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
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.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ 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.
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
LLVM_ABI CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
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.
LLVM_ABI unsigned getIntegerBitWidth() const
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.
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.
iterator_range< user_iterator > users()
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
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.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
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.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
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.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
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.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
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)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
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< PhiNode * > Phi
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)
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.
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"))
LLVM_ABI BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
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)
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 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.
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
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)
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...
static cl::opt< unsigned > MaxJumpThreadingLiveBlocks("max-jump-threading-live-blocks", cl::Hidden, cl::init(24), cl::desc("Limit number of blocks a define in a threaded block is allowed " "to be live in"))
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.
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.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
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.
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...
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
LLVM_ABI bool foldBranchToCommonDest(BranchInst *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 ...
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.
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 cases of SI are equal depends on the contents of the BasicBlock and the incoming...
DenseMap< PHINode *, SmallDenseMap< BasicBlock *, Value *, 8 > > * PhiPredIVs
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const SwitchSuccWrapper * getEmptyKey()
static const SwitchSuccWrapper * getTombstoneKey()
static unsigned getHashValue(const SwitchSuccWrapper *SSW)
static bool isEqual(const SwitchSuccWrapper *LHS, const SwitchSuccWrapper *RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane maks 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.