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 simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
299 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
300 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
302 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
304 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
307 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
308 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
309 Instruction *TI, Instruction *I1,
310 SmallVectorImpl<Instruction *> &OtherSuccTIs,
312 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
313 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
314 BasicBlock *TrueBB, BasicBlock *FalseBB,
315 uint32_t TrueWeight, uint32_t FalseWeight);
316 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
317 const DataLayout &DL);
318 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
319 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
320 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
321 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
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))
870 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
871 CV =
SI->getCondition();
873 if (BI->getCondition()->hasOneUse()) {
878 if (Trunc->hasNoUnsignedWrap())
879 CV = Trunc->getOperand(0);
886 Value *Ptr = PTII->getPointerOperand();
887 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
889 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
898BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
899 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
901 Cases.reserve(
SI->getNumCases());
902 for (
auto Case :
SI->cases())
903 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
904 Case.getCaseSuccessor()));
905 return SI->getDefaultDest();
910 ICmpInst::Predicate Pred;
916 Pred = ICmpInst::ICMP_NE;
921 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
929 std::vector<ValueEqualityComparisonCase> &Cases) {
935 std::vector<ValueEqualityComparisonCase> &C2) {
936 std::vector<ValueEqualityComparisonCase> *
V1 = &C1, *V2 = &C2;
939 if (
V1->size() > V2->size())
944 if (
V1->size() == 1) {
947 for (
const ValueEqualityComparisonCase &
VECC : *V2)
948 if (TheVal ==
VECC.Value)
955 unsigned i1 = 0, i2 = 0, e1 =
V1->size(), e2 = V2->size();
956 while (i1 != e1 && i2 != e2) {
972bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
973 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
978 Value *ThisVal = isValueEqualityComparison(TI);
979 assert(ThisVal &&
"This isn't a value comparison!!");
980 if (ThisVal != PredVal)
987 std::vector<ValueEqualityComparisonCase> PredCases;
989 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
993 std::vector<ValueEqualityComparisonCase> ThisCases;
994 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1009 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1015 ThisCases[0].Dest->removePredecessor(PredDef);
1018 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1025 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1032 SmallPtrSet<Constant *, 16> DeadCases;
1033 for (
const ValueEqualityComparisonCase &Case : PredCases)
1034 DeadCases.
insert(Case.Value);
1037 <<
"Through successor TI: " << *TI);
1039 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1042 auto *
Successor = i->getCaseSuccessor();
1045 if (DeadCases.
count(i->getCaseValue())) {
1054 std::vector<DominatorTree::UpdateType> Updates;
1055 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1057 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1067 ConstantInt *TIV =
nullptr;
1069 for (
const auto &[
Value, Dest] : PredCases)
1075 assert(TIV &&
"No edge from pred to succ?");
1080 for (
const auto &[
Value, Dest] : ThisCases)
1088 TheRealDest = ThisDef;
1090 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1095 if (Succ != CheckEdge) {
1096 if (Succ != TheRealDest)
1097 RemovedSuccs.
insert(Succ);
1100 CheckEdge =
nullptr;
1107 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1112 SmallVector<DominatorTree::UpdateType, 2> Updates;
1114 for (
auto *RemovedSucc : RemovedSuccs)
1115 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1126struct ConstantIntOrdering {
1127 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1128 return LHS->getValue().ult(
RHS->getValue());
1140 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1149 assert(MD &&
"Invalid branch-weight metadata");
1174 if (BonusInst.isTerminator())
1209 NewBonusInst->
takeName(&BonusInst);
1210 BonusInst.setName(NewBonusInst->
getName() +
".old");
1211 VMap[&BonusInst] = NewBonusInst;
1220 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1221 "If the user is not a PHI node, then it should be in the same "
1222 "block as, and come after, the original bonus instruction.");
1226 if (PN->getIncomingBlock(U) == BB)
1230 assert(PN->getIncomingBlock(U) == PredBlock &&
1231 "Not in block-closed SSA form?");
1232 U.set(NewBonusInst);
1242 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1243 PredDL.isSameSourceLocation(
DL)) {
1250bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1258 std::vector<ValueEqualityComparisonCase> BBCases;
1259 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1261 std::vector<ValueEqualityComparisonCase> PredCases;
1262 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1267 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1270 SmallVector<uint64_t, 8> Weights;
1274 if (PredHasWeights) {
1277 if (Weights.
size() != 1 + PredCases.size())
1278 PredHasWeights = SuccHasWeights =
false;
1279 }
else if (SuccHasWeights)
1283 Weights.
assign(1 + PredCases.size(), 1);
1285 SmallVector<uint64_t, 8> SuccWeights;
1286 if (SuccHasWeights) {
1289 if (SuccWeights.
size() != 1 + BBCases.size())
1290 PredHasWeights = SuccHasWeights =
false;
1291 }
else if (PredHasWeights)
1292 SuccWeights.
assign(1 + BBCases.size(), 1);
1294 if (PredDefault == BB) {
1297 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1298 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1299 if (PredCases[i].Dest != BB)
1300 PTIHandled.insert(PredCases[i].
Value);
1303 std::swap(PredCases[i], PredCases.back());
1305 if (PredHasWeights || SuccHasWeights) {
1307 Weights[0] += Weights[i + 1];
1312 PredCases.pop_back();
1318 if (PredDefault != BBDefault) {
1320 if (DTU && PredDefault != BB)
1321 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1322 PredDefault = BBDefault;
1323 ++NewSuccessors[BBDefault];
1326 unsigned CasesFromPred = Weights.
size();
1327 uint64_t ValidTotalSuccWeight = 0;
1328 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1329 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1330 PredCases.push_back(BBCases[i]);
1331 ++NewSuccessors[BBCases[i].Dest];
1332 if (SuccHasWeights || PredHasWeights) {
1336 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1337 ValidTotalSuccWeight += SuccWeights[i + 1];
1341 if (SuccHasWeights || PredHasWeights) {
1342 ValidTotalSuccWeight += SuccWeights[0];
1344 for (
unsigned i = 1; i < CasesFromPred; ++i)
1345 Weights[i] *= ValidTotalSuccWeight;
1347 Weights[0] *= SuccWeights[0];
1353 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1354 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1355 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1356 if (PredCases[i].Dest == BB) {
1357 PTIHandled.insert(PredCases[i].
Value);
1359 if (PredHasWeights || SuccHasWeights) {
1360 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1365 std::swap(PredCases[i], PredCases.back());
1366 PredCases.pop_back();
1373 for (
const ValueEqualityComparisonCase &Case : BBCases)
1374 if (PTIHandled.count(Case.Value)) {
1376 if (PredHasWeights || SuccHasWeights)
1377 Weights.
push_back(WeightsForHandled[Case.Value]);
1378 PredCases.push_back(Case);
1379 ++NewSuccessors[Case.Dest];
1380 PTIHandled.erase(Case.Value);
1385 for (ConstantInt *
I : PTIHandled) {
1386 if (PredHasWeights || SuccHasWeights)
1388 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1389 ++NewSuccessors[BBDefault];
1396 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1401 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1403 for (
auto I :
seq(NewSuccessor.second)) {
1407 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1408 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1415 "Should not end up here with unstable pointers");
1421 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1423 for (ValueEqualityComparisonCase &V : PredCases)
1426 if (PredHasWeights || SuccHasWeights)
1438 if (!InfLoopBlock) {
1446 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1453 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1455 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1460 ++NumFoldValueComparisonIntoPredecessors;
1468bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1471 Value *CV = isValueEqualityComparison(TI);
1472 assert(CV &&
"Not a comparison?");
1477 while (!Preds.empty()) {
1486 Value *PCV = isValueEqualityComparison(PTI);
1490 SmallSetVector<BasicBlock *, 4> FailBlocks;
1492 for (
auto *Succ : FailBlocks) {
1498 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1512 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1513 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1514 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1536 if (
I->mayReadFromMemory())
1568 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1576 if (J->getParent() == BB)
1598 if (C1->isMustTailCall() != C2->isMustTailCall())
1601 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1607 if (CB1->cannotMerge() || CB1->isConvergent())
1610 if (CB2->cannotMerge() || CB2->isConvergent())
1625 if (!I1->hasDbgRecords())
1627 using CurrentAndEndIt =
1628 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1634 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1635 return Pair.first == Pair.second;
1641 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1647 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1649 if (!
Other->hasDbgRecords())
1652 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1659 while (
none_of(Itrs, atEnd)) {
1660 bool HoistDVRs = allIdentical(Itrs);
1661 for (CurrentAndEndIt &Pair : Itrs) {
1675 if (I1->isIdenticalToWhenDefined(I2,
true))
1680 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1681 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1682 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1684 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1685 return I1->getOperand(0) == I2->
getOperand(1) &&
1751 auto &Context = BI->
getParent()->getContext();
1756 Value *Mask =
nullptr;
1757 Value *MaskFalse =
nullptr;
1758 Value *MaskTrue =
nullptr;
1759 if (Invert.has_value()) {
1760 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1761 Mask = Builder.CreateBitCast(
1766 MaskFalse = Builder.CreateBitCast(
1768 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1770 auto PeekThroughBitcasts = [](
Value *V) {
1772 V = BitCast->getOperand(0);
1775 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1777 if (!Invert.has_value())
1778 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1783 auto *Op0 =
I->getOperand(0);
1784 CallInst *MaskedLoadStore =
nullptr;
1787 auto *Ty =
I->getType();
1789 Value *PassThru =
nullptr;
1790 if (Invert.has_value())
1791 for (
User *U :
I->users()) {
1793 PassThru = Builder.CreateBitCast(
1802 Builder.SetInsertPoint(Ins);
1805 MaskedLoadStore = Builder.CreateMaskedLoad(
1807 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1810 I->replaceAllUsesWith(NewLoadStore);
1813 auto *StoredVal = Builder.CreateBitCast(
1815 MaskedLoadStore = Builder.CreateMaskedStore(
1826 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1828 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1832 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1833 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1836 I->eraseFromParent();
1843 bool IsStore =
false;
1866bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1867 bool AllInstsEqOnly) {
1883 for (
auto *Succ : UniqueSuccessors) {
1899 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1901 for (
auto *Succ : UniqueSuccessors) {
1905 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1908 if (AllInstsEqOnly) {
1914 unsigned Size0 = UniqueSuccessors[0]->size();
1915 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1919 Succ->
size() == Size0;
1923 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1924 while (LRI.isValid()) {
1926 if (
any_of(*LRI, [I0](Instruction *
I) {
1940 unsigned NumSkipped = 0;
1943 if (SuccIterPairs.
size() > 2) {
1946 if (SuccIterPairs.
size() < 2)
1953 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1954 auto &BB1ItrPair = *SuccIterPairBegin++;
1955 auto OtherSuccIterPairRange =
1961 bool AllInstsAreIdentical =
true;
1962 bool HasTerminator =
I1->isTerminator();
1963 for (
auto &SuccIter : OtherSuccIterRange) {
1967 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1968 AllInstsAreIdentical =
false;
1971 SmallVector<Instruction *, 8> OtherInsts;
1972 for (
auto &SuccIter : OtherSuccIterRange)
1977 if (HasTerminator) {
1981 if (NumSkipped || !AllInstsAreIdentical) {
1986 return hoistSuccIdenticalTerminatorToSwitchOrIf(
1987 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
1991 if (AllInstsAreIdentical) {
1992 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1993 AllInstsAreIdentical =
1995 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1997 unsigned SkipFlagsBB2 = Pair.second;
2012 AllInstsAreIdentical && CI && CI->isMustTailCall()) {
2013 AllInstsAreIdentical =
2014 NumSkipped == 0 &&
all_of(SuccIterPairs, [](
const SuccIterPair &
P) {
2019 if (AllInstsAreIdentical) {
2029 for (
auto &SuccIter : OtherSuccIterRange) {
2037 assert(
Success &&
"We should not be trying to hoist callbases "
2038 "with non-intersectable attributes");
2050 NumHoistCommonCode += SuccIterPairs.
size();
2052 NumHoistCommonInstrs += SuccIterPairs.
size();
2061 for (
auto &SuccIterPair : SuccIterPairs) {
2070bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2071 Instruction *TI, Instruction *I1,
2072 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2082 auto *I2 = *OtherSuccTIs.
begin();
2102 for (PHINode &PN : Succ->
phis()) {
2103 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2104 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2105 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2125 if (!
NT->getType()->isVoidTy()) {
2126 I1->replaceAllUsesWith(NT);
2127 for (Instruction *OtherSuccTI : OtherSuccTIs)
2128 OtherSuccTI->replaceAllUsesWith(NT);
2132 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2138 for (
auto *OtherSuccTI : OtherSuccTIs)
2139 Locs.
push_back(OtherSuccTI->getDebugLoc());
2151 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2153 for (PHINode &PN : Succ->
phis()) {
2154 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2155 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2161 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2171 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2172 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2173 PN.setIncomingValue(i, SI);
2181 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
2185 if (DTU && VisitedSuccs.
insert(Succ).second)
2186 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2192 for (BasicBlock *Succ : UniqueSuccessors)
2193 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2207 if (
I->isIntDivRem())
2222 std::optional<unsigned> NumUses;
2223 for (
auto *
I : Insts) {
2226 I->getType()->isTokenTy())
2231 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2239 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2243 NumUses =
I->getNumUses();
2244 else if (NumUses !=
I->getNumUses())
2250 for (
auto *
I : Insts) {
2264 for (
const Use &U : I0->
uses()) {
2265 auto It = PHIOperands.find(&U);
2266 if (It == PHIOperands.end())
2269 if (!
equal(Insts, It->second))
2283 if (HaveIndirectCalls) {
2284 if (!AllCallsAreIndirect)
2288 Value *Callee =
nullptr;
2292 Callee = CurrCallee;
2293 else if (Callee != CurrCallee)
2299 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2305 if (!
all_of(Insts, SameAsI0)) {
2311 for (
auto *
I : Insts)
2312 Ops.push_back(
I->getOperand(OI));
2322 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2327 for (
auto *BB : Blocks) {
2329 I =
I->getPrevNode();
2354 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2357 PN->insertBefore(BBEnd->begin());
2358 for (
auto *
I : Insts)
2359 PN->addIncoming(
I->getOperand(O),
I->getParent());
2368 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2371 for (
auto *
I : Insts)
2385 assert(
Success &&
"We should not be trying to sink callbases "
2386 "with non-intersectable attributes");
2397 PN->replaceAllUsesWith(I0);
2398 PN->eraseFromParent();
2402 for (
auto *
I : Insts) {
2407 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2408 I->replaceAllUsesWith(I0);
2409 I->eraseFromParent();
2459 bool HaveNonUnconditionalPredecessors =
false;
2465 HaveNonUnconditionalPredecessors =
true;
2467 if (UnconditionalPreds.
size() < 2)
2480 for (
const Use &U : PN.incoming_values())
2481 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2482 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2484 Ops.push_back(*IncomingVals[Pred]);
2492 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2505 if (!followedByDeoptOrUnreachable) {
2507 auto IsMemOperand = [](
Use &U) {
2520 unsigned NumPHIInsts = 0;
2521 for (
Use &U : (*LRI)[0]->operands()) {
2522 auto It = PHIOperands.
find(&U);
2523 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2524 return InstructionsToSink.contains(V);
2531 if (IsMemOperand(U) &&
2532 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2539 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2540 return NumPHIInsts <= 1;
2557 while (Idx < ScanIdx) {
2558 if (!ProfitableToSinkInstruction(LRI)) {
2561 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2574 if (Idx < ScanIdx) {
2577 InstructionsToSink = InstructionsProfitableToSink;
2583 !ProfitableToSinkInstruction(LRI) &&
2584 "We already know that the last instruction is unprofitable to sink");
2592 for (
auto *
I : *LRI)
2593 InstructionsProfitableToSink.
erase(
I);
2594 if (!ProfitableToSinkInstruction(LRI)) {
2597 InstructionsToSink = InstructionsProfitableToSink;
2611 if (HaveNonUnconditionalPredecessors) {
2612 if (!followedByDeoptOrUnreachable) {
2620 bool Profitable =
false;
2621 while (Idx < ScanIdx) {
2655 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2657 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2665 NumSinkCommonInstrs++;
2669 ++NumSinkCommonCode;
2675struct CompatibleSets {
2676 using SetTy = SmallVector<InvokeInst *, 2>;
2682 SetTy &getCompatibleSet(InvokeInst *
II);
2684 void insert(InvokeInst *
II);
2687CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2692 for (CompatibleSets::SetTy &Set : Sets) {
2693 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2698 return Sets.emplace_back();
2701void CompatibleSets::insert(InvokeInst *
II) {
2702 getCompatibleSet(
II).emplace_back(
II);
2706 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2709 auto IsIllegalToMerge = [](InvokeInst *
II) {
2710 return II->cannotMerge() ||
II->isInlineAsm();
2712 if (
any_of(Invokes, IsIllegalToMerge))
2720 if (HaveIndirectCalls) {
2721 if (!AllCallsAreIndirect)
2726 for (InvokeInst *
II : Invokes) {
2727 Value *CurrCallee =
II->getCalledOperand();
2728 assert(CurrCallee &&
"There is always a called operand.");
2731 else if (Callee != CurrCallee)
2738 auto HasNormalDest = [](InvokeInst *
II) {
2741 if (
any_of(Invokes, HasNormalDest)) {
2744 if (!
all_of(Invokes, HasNormalDest))
2749 for (InvokeInst *
II : Invokes) {
2751 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2753 NormalBB = CurrNormalBB;
2754 else if (NormalBB != CurrNormalBB)
2762 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2771 for (InvokeInst *
II : Invokes) {
2773 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2775 UnwindBB = CurrUnwindBB;
2777 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2784 Invokes.front()->getUnwindDest(),
2785 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2790 const InvokeInst *II0 = Invokes.front();
2791 for (
auto *
II : Invokes.drop_front())
2796 auto IsIllegalToMergeArguments = [](
auto Ops) {
2797 Use &U0 = std::get<0>(
Ops);
2798 Use &U1 = std::get<1>(
Ops);
2804 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2805 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2806 IsIllegalToMergeArguments))
2818 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2824 bool HasNormalDest =
2829 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2833 II0->
getParent()->getIterator()->getNextNode();
2838 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2842 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2844 if (!HasNormalDest) {
2848 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2856 return MergedInvoke;
2870 SuccBBOfMergedInvoke});
2893 return II->getOperand(U.getOperandNo()) != U.get();
2912 Invokes.
front()->getParent());
2920 if (!MergedDebugLoc)
2921 MergedDebugLoc =
II->getDebugLoc();
2929 OrigSuccBB->removePredecessor(
II->getParent());
2935 assert(
Success &&
"Merged invokes with incompatible attributes");
2938 II->replaceAllUsesWith(MergedInvoke);
2939 II->eraseFromParent();
2943 ++NumInvokeSetsFormed;
2979 CompatibleSets Grouper;
2989 if (Invokes.
size() < 2)
3001class EphemeralValueTracker {
3002 SmallPtrSet<const Instruction *, 32> EphValues;
3004 bool isEphemeral(
const Instruction *
I) {
3007 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3008 all_of(
I->users(), [&](
const User *U) {
3009 return EphValues.count(cast<Instruction>(U));
3014 bool track(
const Instruction *
I) {
3015 if (isEphemeral(
I)) {
3066 unsigned MaxNumInstToLookAt = 9;
3070 if (!MaxNumInstToLookAt)
3072 --MaxNumInstToLookAt;
3085 if (
SI->getPointerOperand() == StorePtr &&
3086 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3089 return SI->getValueOperand();
3094 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3095 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3097 bool ExplicitlyDereferenceableOnly;
3105 (!ExplicitlyDereferenceableOnly ||
3123 unsigned &SpeculatedInstructions,
3131 bool HaveRewritablePHIs =
false;
3133 Value *OrigV = PN.getIncomingValueForBlock(BB);
3134 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3141 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3150 HaveRewritablePHIs =
true;
3153 if (!OrigCE && !ThenCE)
3160 if (OrigCost + ThenCost > MaxCost)
3167 ++SpeculatedInstructions;
3168 if (SpeculatedInstructions > 1)
3172 return HaveRewritablePHIs;
3176 std::optional<bool> Invert,
3180 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3187 if (!Invert.has_value())
3190 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3194 return BIEndProb < Likely;
3234bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3235 BasicBlock *ThenBB) {
3251 bool Invert =
false;
3266 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3268 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3270 unsigned SpeculatedInstructions = 0;
3271 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3272 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3273 Value *SpeculatedStoreValue =
nullptr;
3274 StoreInst *SpeculatedStore =
nullptr;
3275 EphemeralValueTracker EphTracker;
3290 if (EphTracker.track(&
I))
3295 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3297 SpeculatedConditionalLoadsStores.
size() <
3301 if (IsSafeCheapLoadStore)
3302 SpeculatedConditionalLoadsStores.
push_back(&
I);
3304 ++SpeculatedInstructions;
3306 if (SpeculatedInstructions > 1)
3310 if (!IsSafeCheapLoadStore &&
3313 (SpeculatedStoreValue =
3316 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3322 if (!SpeculatedStore && SpeculatedStoreValue)
3328 for (Use &
Op :
I.operands()) {
3333 ++SinkCandidateUseCounts[OpI];
3340 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3341 if (Inst->hasNUses(
Count)) {
3342 ++SpeculatedInstructions;
3343 if (SpeculatedInstructions > 1)
3350 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3353 SpeculatedInstructions,
Cost,
TTI);
3354 if (!Convert ||
Cost > Budget)
3358 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3362 if (SpeculatedStoreValue) {
3366 Value *FalseV = SpeculatedStoreValue;
3370 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3400 for (DbgVariableRecord *DbgAssign :
3403 DbgAssign->replaceVariableLocationOp(OrigV, S);
3413 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3416 I.dropUBImplyingAttrsAndMetadata();
3419 if (EphTracker.contains(&
I)) {
3421 I.eraseFromParent();
3427 for (
auto &It : *ThenBB)
3432 !DVR || !DVR->isDbgAssign())
3433 It.dropOneDbgRecord(&DR);
3435 std::prev(ThenBB->end()));
3437 if (!SpeculatedConditionalLoadsStores.
empty())
3443 for (PHINode &PN : EndBB->
phis()) {
3444 unsigned OrigI = PN.getBasicBlockIndex(BB);
3445 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3446 Value *OrigV = PN.getIncomingValue(OrigI);
3447 Value *ThenV = PN.getIncomingValue(ThenI);
3456 Value *TrueV = ThenV, *FalseV = OrigV;
3460 PN.setIncomingValue(OrigI, V);
3461 PN.setIncomingValue(ThenI, V);
3465 for (Instruction *
I : SpeculatedPseudoProbes)
3466 I->eraseFromParent();
3479 if (!ReachesNonLocalUses.
insert(BB).second)
3494 EphemeralValueTracker EphTracker;
3501 if (CI->cannotDuplicate() || CI->isConvergent())
3514 for (
User *U :
I.users()) {
3517 if (UsedInBB == BB) {
3521 NonLocalUseBlocks.
insert(UsedInBB);
3535 if (
I &&
I->getParent() == To)
3551static std::optional<bool>
3572 KnownValues[CB].
insert(Pred);
3576 if (KnownValues.
empty())
3601 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3604 for (
const auto &Pair : KnownValues) {
3621 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3626 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3629 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3639 EdgeBB->setName(RealDest->
getName() +
".critedge");
3640 EdgeBB->moveBefore(RealDest);
3650 TranslateMap[
Cond] = CB;
3663 N->insertInto(EdgeBB, InsertPt);
3666 N->setName(BBI->getName() +
".c");
3677 if (!BBI->use_empty())
3678 TranslateMap[&*BBI] = V;
3679 if (!
N->mayHaveSideEffects()) {
3680 N->eraseFromParent();
3685 if (!BBI->use_empty())
3686 TranslateMap[&*BBI] =
N;
3692 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3693 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3694 SrcDbgCursor = std::next(BBI);
3696 N->cloneDebugInfoFrom(&*BBI);
3705 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3706 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3707 InsertPt->cloneDebugInfoFrom(BI);
3728 return std::nullopt;
3734bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3741 std::optional<bool>
Result;
3742 bool EverChanged =
false;
3748 }
while (Result == std::nullopt);
3757 bool SpeculateUnpredictables) {
3779 return isa<UncondBrInst>(IfBlock->getTerminator());
3782 "Will have either one or two blocks to speculate.");
3789 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3790 if (!IsUnpredictable) {
3793 (TWeight + FWeight) != 0) {
3798 if (IfBlocks.
size() == 1) {
3800 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3801 if (BIBBProb >= Likely)
3804 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3813 if (IfCondPhiInst->getParent() == BB)
3821 unsigned NumPhis = 0;
3834 if (SpeculateUnpredictables && IsUnpredictable)
3835 Budget +=
TTI.getBranchMispredictPenalty();
3848 AggressiveInsts, Cost, Budget,
TTI, AC,
3849 ZeroCostInstructions) ||
3851 AggressiveInsts, Cost, Budget,
TTI, AC,
3852 ZeroCostInstructions))
3865 auto IsBinOpOrAndEq = [](
Value *V) {
3888 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3901 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3903 <<
" F: " << IfFalse->
getName() <<
"\n");
3920 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3925 PN->eraseFromParent();
3931 Builder.CreateBr(BB);
3952 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3953 if (
Opc == Instruction::And)
3954 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3955 if (
Opc == Instruction::Or)
3956 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3968 bool PredHasWeights =
3970 bool SuccHasWeights =
3972 if (PredHasWeights || SuccHasWeights) {
3973 if (!PredHasWeights)
3974 PredTrueWeight = PredFalseWeight = 1;
3975 if (!SuccHasWeights)
3976 SuccTrueWeight = SuccFalseWeight = 1;
3986static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3989 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
3991 "PredBB must be a predecessor of BB.");
3999 (PTWeight + PFWeight) != 0) {
4002 Likely =
TTI->getPredictableBranchThreshold();
4007 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4008 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4012 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4015 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4016 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4022 return std::nullopt;
4035 bool InvertPredCond;
4036 std::tie(CommonSucc,
Opc, InvertPredCond) =
4039 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4047 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4052 if (InvertPredCond) {
4065 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4068 SuccTrueWeight, SuccFalseWeight)) {
4074 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4079 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4080 PredTrueWeight * SuccFalseWeight);
4086 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4087 PredFalseWeight * SuccTrueWeight);
4089 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4131 if (!MDWeights.
empty()) {
4132 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4137 ++NumFoldBranchToCommonDest;
4144 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4145 return U->getType()->isVectorTy();
4156 unsigned BonusInstThreshold) {
4165 Cond->getParent() != BB || !
Cond->hasOneUse())
4186 bool InvertPredCond;
4188 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4220 unsigned NumBonusInsts = 0;
4221 bool SawVectorOp =
false;
4222 const unsigned PredCount = Preds.
size();
4226 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4246 NumBonusInsts += PredCount;
4254 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4257 return PN->getIncomingBlock(U) == BB;
4258 return UI->
getParent() == BB &&
I.comesBefore(UI);
4262 if (!
all_of(
I.uses(), IsBCSSAUse))
4266 BonusInstThreshold *
4282 for (
auto *BB : {BB1, BB2}) {
4298 Value *AlternativeV =
nullptr) {
4324 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4325 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4333 if (!AlternativeV &&
4339 PHI->addIncoming(V, BB);
4349 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4358 if (!PStore || !QStore)
4381 if (
I.mayReadOrWriteMemory())
4383 for (
auto &
I : *QFB)
4384 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4387 for (
auto &
I : *QTB)
4388 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4392 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4406 for (
auto &
I : *BB) {
4408 if (
I.isTerminator())
4426 "When we run out of budget we will eagerly return from within the "
4427 "per-instruction loop.");
4431 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4433 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4434 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4470 InvertPCond ^= (PStore->
getParent() != PTB);
4471 InvertQCond ^= (QStore->
getParent() != QTB);
4492 {CombinedWeights[0], CombinedWeights[1]},
4499 SI->copyMetadata(*QStore);
4505 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4508 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4571 bool InvertPCond =
false, InvertQCond =
false;
4577 if (QFB == PostBB) {
4596 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4599 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4607 for (
auto *BB : {PTB, PFB}) {
4612 PStoreAddresses.
insert(
SI->getPointerOperand());
4614 for (
auto *BB : {QTB, QFB}) {
4619 QStoreAddresses.
insert(
SI->getPointerOperand());
4625 auto &CommonAddresses = PStoreAddresses;
4628 for (
auto *Address : CommonAddresses)
4631 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4649 !BI->
getParent()->getSinglePredecessor())
4651 if (!IfFalseBB->
phis().empty())
4661 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4735 if (&*BB->
begin() != BI)
4763 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4765 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4769 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4772 if (CommonDestProb >= Likely)
4782 unsigned NumPhis = 0;
4804 if (OtherDest == BB) {
4812 OtherDest = InfLoopBlock;
4824 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4828 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4832 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4847 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4848 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4851 SuccTrueWeight, SuccFalseWeight);
4853 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4854 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4855 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4856 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4860 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4861 PredOther * SuccCommon,
4862 PredOther * SuccOther};
4870 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4872 assert(
SI->getCondition() == PBICond);
4889 Value *BIV = PN.getIncomingValueForBlock(BB);
4890 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4891 Value *PBIV = PN.getIncomingValue(PBBIdx);
4895 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4896 PN.setIncomingValue(PBBIdx, NV);
4900 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4901 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4921bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4923 BasicBlock *FalseBB,
4924 uint32_t TrueWeight,
4925 uint32_t FalseWeight) {
4932 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4934 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4937 for (BasicBlock *Succ :
successors(OldTerm)) {
4939 if (Succ == KeepEdge1)
4940 KeepEdge1 =
nullptr;
4941 else if (Succ == KeepEdge2)
4942 KeepEdge2 =
nullptr;
4947 if (Succ != TrueBB && Succ != FalseBB)
4948 RemovedSuccessors.
insert(Succ);
4956 if (!KeepEdge1 && !KeepEdge2) {
4957 if (TrueBB == FalseBB) {
4968 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4988 SmallVector<DominatorTree::UpdateType, 2> Updates;
4990 for (
auto *RemovedSuccessor : RemovedSuccessors)
4991 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
5002bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
5007 if (!TrueVal || !FalseVal)
5012 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
5013 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5016 uint32_t TrueWeight = 0, FalseWeight = 0;
5017 SmallVector<uint64_t, 8> Weights;
5021 if (Weights.
size() == 1 +
SI->getNumCases()) {
5023 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5025 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5030 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5039bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5053 SmallVector<uint32_t> SelectBranchWeights(2);
5057 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5058 SelectBranchWeights[0],
5059 SelectBranchWeights[1]);
5079bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5083 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5129bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5148 ConstantInt *NewCaseVal;
5156 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5162 SelectTrueVal = Builder.
getTrue();
5163 SelectFalseVal = Builder.
getFalse();
5166 SelectCond =
Select->getCondition();
5168 if (SelectCond != ICI)
5170 SelectTrueVal =
Select->getTrueValue();
5171 SelectFalseVal =
Select->getFalseValue();
5176 if (
SI->getCondition() != IcmpCond)
5182 if (
SI->getDefaultDest() != BB) {
5183 ConstantInt *VVal =
SI->findCaseDest(BB);
5184 assert(VVal &&
"Should have a unique destination value");
5192 return requestResimplify();
5198 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5200 if (Predicate == ICmpInst::ICMP_EQ)
5208 return requestResimplify();
5215 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5221 Value *DefaultCst = SelectFalseVal;
5222 Value *NewCst = SelectTrueVal;
5230 Select->replaceAllUsesWith(DefaultCst);
5231 Select->eraseFromParent();
5237 SmallVector<DominatorTree::UpdateType, 2> Updates;
5244 SwitchInstProfUpdateWrapper SIW(*SI);
5245 auto W0 = SIW.getSuccessorWeight(0);
5248 NewW = ((uint64_t(*W0) + 1) >> 1);
5249 SIW.setSuccessorWeight(0, *NewW);
5251 SIW.addCase(NewCaseVal, NewBB, NewW);
5253 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5262 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5270bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5272 const DataLayout &
DL) {
5282 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5284 SmallVectorImpl<ConstantInt *> &
Values = ConstantCompare.Vals;
5285 Value *CompVal = ConstantCompare.CompValue;
5286 unsigned UsedICmps = ConstantCompare.UsedICmps;
5287 Value *ExtraCase = ConstantCompare.Extra;
5288 bool TrueWhenEqual = ConstantCompare.IsEq;
5305 if (ExtraCase &&
Values.size() < 2)
5308 SmallVector<uint32_t> BranchWeights;
5315 if (!TrueWhenEqual) {
5318 std::swap(BranchWeights[0], BranchWeights[1]);
5324 <<
" cases into SWITCH. BB is:\n"
5327 SmallVector<DominatorTree::UpdateType, 2> Updates;
5334 nullptr,
"switch.early.test");
5345 AssumptionCache *AC =
Options.AC;
5351 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5358 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5364 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5365 <<
"\nEXTRABB = " << *BB);
5373 "Should not end up here with unstable pointers");
5375 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5380 if (
Values.front()->getValue() -
Values.back()->getValue() ==
5383 Values.back()->getValue(),
Values.front()->getValue() + 1);
5385 ICmpInst::Predicate Pred;
5403 SmallVector<uint32_t> NewWeights(
Values.size() + 1);
5404 NewWeights[0] = BranchWeights[1];
5407 V = BranchWeights[0] /
Values.size();
5412 for (ConstantInt *Val :
Values)
5413 New->addCase(Val, EdgeBB);
5421 for (
unsigned i = 0, e =
Values.size() - 1; i != e; ++i)
5431 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5435bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5437 return simplifyCommonResume(RI);
5441 return simplifySingleResume(RI);
5454 switch (IntrinsicID) {
5455 case Intrinsic::dbg_declare:
5456 case Intrinsic::dbg_value:
5457 case Intrinsic::dbg_label:
5458 case Intrinsic::lifetime_end:
5468bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5477 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5481 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5483 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5484 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5488 if (IncomingBB->getUniqueSuccessor() != BB)
5493 if (IncomingValue != LandingPad)
5497 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5498 TrivialUnwindBlocks.
insert(IncomingBB);
5502 if (TrivialUnwindBlocks.
empty())
5506 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5510 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5513 for (BasicBlock *Pred :
5524 TrivialBB->getTerminator()->eraseFromParent();
5525 new UnreachableInst(RI->
getContext(), TrivialBB);
5527 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5534 return !TrivialUnwindBlocks.empty();
5538bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5542 "Resume must unwind the exception that caused control to here");
5598 int Idx = DestPN.getBasicBlockIndex(BB);
5612 Value *SrcVal = DestPN.getIncomingValue(Idx);
5615 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5619 DestPN.addIncoming(Incoming, Pred);
5646 std::vector<DominatorTree::UpdateType> Updates;
5650 if (UnwindDest ==
nullptr) {
5691 if (!SuccessorCleanupPad)
5700 SuccessorCleanupPad->eraseFromParent();
5709bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5726bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5758 BBI->dropDbgRecords();
5762 BBI->eraseFromParent();
5768 if (&BB->
front() != UI)
5771 std::vector<DominatorTree::UpdateType> Updates;
5774 for (BasicBlock *Predecessor : Preds) {
5782 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5793 "The destinations are guaranteed to be different here.");
5794 CallInst *Assumption;
5810 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5812 SwitchInstProfUpdateWrapper SU(*SI);
5813 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5814 if (i->getCaseSuccessor() != BB) {
5819 i = SU.removeCase(i);
5824 if (DTU &&
SI->getDefaultDest() != BB)
5825 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5827 if (
II->getUnwindDest() == BB) {
5833 if (!CI->doesNotThrow())
5834 CI->setDoesNotThrow();
5838 if (CSI->getUnwindDest() == BB) {
5849 E = CSI->handler_end();
5852 CSI->removeHandler(
I);
5859 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5860 if (CSI->getNumHandlers() == 0) {
5861 if (CSI->hasUnwindDest()) {
5865 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5866 Updates.push_back({DominatorTree::Insert,
5867 PredecessorOfPredecessor,
5868 CSI->getUnwindDest()});
5869 Updates.push_back({DominatorTree::Delete,
5870 PredecessorOfPredecessor, Predecessor});
5873 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5880 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5881 for (BasicBlock *EHPred : EHPreds)
5885 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5886 CSI->eraseFromParent();
5891 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5892 "Expected to always have an unwind to BB.");
5894 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5922static std::optional<ContiguousCasesResult>
5929 const APInt &Min = Cases.
back()->getValue();
5930 const APInt &Max = Cases.
front()->getValue();
5932 size_t ContiguousOffset = Cases.
size() - 1;
5933 if (
Offset == ContiguousOffset) {
5952 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
5953 return L->getValue() != R->getValue() + 1;
5955 if (It == Cases.
end())
5956 return std::nullopt;
5957 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5958 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5962 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5965 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5973 return std::nullopt;
5978 bool RemoveOrigDefaultBlock =
true) {
5980 auto *BB = Switch->getParent();
5981 auto *OrigDefaultBlock = Switch->getDefaultDest();
5982 if (RemoveOrigDefaultBlock)
5983 OrigDefaultBlock->removePredecessor(BB);
5987 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5989 Switch->setDefaultDest(&*NewDefaultBlock);
5993 if (RemoveOrigDefaultBlock &&
6003bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
6005 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6007 bool HasDefault = !
SI->defaultDestUnreachable();
6009 auto *BB =
SI->getParent();
6011 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6016 for (
auto Case :
SI->cases()) {
6020 if (Dest == DestA) {
6026 if (Dest == DestB) {
6036 "Single-destination switch should have been folded.");
6038 assert(DestB !=
SI->getDefaultDest());
6039 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6043 std::optional<ContiguousCasesResult> ContiguousCases;
6046 if (!HasDefault && CasesA.
size() == 1)
6047 ContiguousCases = ContiguousCasesResult{
6055 else if (CasesB.
size() == 1)
6056 ContiguousCases = ContiguousCasesResult{
6065 else if (!HasDefault)
6069 if (!ContiguousCases)
6073 if (!ContiguousCases)
6076 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6082 Max->getValue() - Min->getValue() + 1);
6085 assert(
Max->getValue() == Min->getValue());
6090 else if (NumCases->
isNullValue() && !Cases->empty()) {
6094 if (!
Offset->isNullValue())
6102 SmallVector<uint64_t, 8> Weights;
6104 if (Weights.
size() == 1 +
SI->getNumCases()) {
6105 uint64_t TrueWeight = 0;
6106 uint64_t FalseWeight = 0;
6107 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6108 if (
SI->getSuccessor(
I) == Dest)
6109 TrueWeight += Weights[
I];
6111 FalseWeight += Weights[
I];
6113 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6124 unsigned PreviousEdges = Cases->size();
6125 if (Dest ==
SI->getDefaultDest())
6127 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6128 PHI.removeIncomingValue(
SI->getParent());
6131 unsigned PreviousEdges = OtherCases->size();
6132 if (OtherDest ==
SI->getDefaultDest())
6134 unsigned E = PreviousEdges - 1;
6138 for (
unsigned I = 0;
I !=
E; ++
I)
6139 PHI.removeIncomingValue(
SI->getParent());
6143 SmallVector<DominatorTree::UpdateType, 2> Updates;
6147 Updates.
push_back({DominatorTree::Delete, BB, OrigDefaultBlock});
6151 SI->eraseFromParent();
6154 Updates.
push_back({DominatorTree::Delete, BB, OtherDest});
6174 unsigned MaxSignificantBitsInCond =
6181 for (
const auto &Case :
SI->cases()) {
6182 auto *
Successor = Case.getCaseSuccessor();
6191 if (
Known.Zero.intersects(CaseVal) || !
Known.One.isSubsetOf(CaseVal) ||
6193 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6199 }
else if (IsKnownValuesValid)
6200 KnownValues.
erase(CaseC);
6207 bool HasDefault = !
SI->defaultDestUnreachable();
6208 const unsigned NumUnknownBits =
6211 if (HasDefault && DeadCases.
empty()) {
6217 if (NumUnknownBits < 64 ) {
6218 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6219 if (
SI->getNumCases() == AllNumCases) {
6226 if (
SI->getNumCases() == AllNumCases - 1) {
6227 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6229 if (CondTy->getIntegerBitWidth() > 64 ||
6230 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6234 for (
const auto &Case :
SI->cases())
6235 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6237 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6239 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6249 if (DeadCases.
empty())
6255 assert(CaseI !=
SI->case_default() &&
6256 "Case was not found. Probably mistake in DeadCases forming.");
6258 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6263 std::vector<DominatorTree::UpdateType> Updates;
6264 for (
auto *
Successor : UniqueSuccessors)
6265 if (NumPerSuccessorCases[
Successor] == 0)
6292 int Idx =
PHI.getBasicBlockIndex(BB);
6293 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6295 Value *InValue =
PHI.getIncomingValue(Idx);
6296 if (InValue != CaseValue)
6312 ForwardingNodesMap ForwardingNodes;
6315 for (
const auto &Case :
SI->cases()) {
6317 BasicBlock *CaseDest = Case.getCaseSuccessor();
6336 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6337 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6338 count(Phi.blocks(), SwitchBlock) == 1) {
6339 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6347 ForwardingNodes[Phi].push_back(PhiIdx);
6350 for (
auto &ForwardingNode : ForwardingNodes) {
6351 PHINode *Phi = ForwardingNode.first;
6357 for (
int Index : Indexes)
6358 Phi->setIncomingValue(Index,
SI->getCondition());
6368 if (
C->isThreadDependent())
6370 if (
C->isDLLImportDependent())
6378 if (
C->getType()->isScalableTy())
6389 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6416 if (
A->isAllOnesValue())
6418 if (
A->isNullValue())
6424 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6449 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6451 if (
I.isTerminator()) {
6453 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6456 CaseDest =
I.getSuccessor(0);
6463 for (
auto &
Use :
I.uses()) {
6466 if (
I->getParent() == CaseDest)
6469 if (Phi->getIncomingBlock(
Use) == CaseDest)
6482 *CommonDest = CaseDest;
6484 if (CaseDest != *CommonDest)
6489 int Idx =
PHI.getBasicBlockIndex(Pred);
6502 Res.push_back(std::make_pair(&
PHI, ConstVal));
6505 return Res.
size() > 0;
6511 SwitchCaseResultVectorTy &UniqueResults,
6513 for (
auto &
I : UniqueResults) {
6514 if (
I.first == Result) {
6515 I.second.push_back(CaseVal);
6516 return I.second.size();
6519 UniqueResults.push_back(
6530 SwitchCaseResultVectorTy &UniqueResults,
6535 for (
const auto &
I :
SI->cases()) {
6549 const size_t NumCasesForResult =
6557 if (UniqueResults.size() > MaxUniqueResults)
6573 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6575 return DefaultResult ||
SI->defaultDestUnreachable();
6596 const bool HasBranchWeights =
6599 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6600 ResultVector[1].second.size() == 1) {
6601 ConstantInt *FirstCase = ResultVector[0].second[0];
6602 ConstantInt *SecondCase = ResultVector[1].second[0];
6603 Value *SelectValue = ResultVector[1].first;
6604 if (DefaultResult) {
6605 Value *ValueCompare =
6606 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6607 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6608 DefaultResult,
"switch.select");
6610 SI && HasBranchWeights) {
6617 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6621 Value *ValueCompare =
6622 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6623 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6624 SelectValue,
"switch.select");
6630 size_t FirstCasePos = (Condition !=
nullptr);
6631 size_t SecondCasePos = FirstCasePos + 1;
6632 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6634 {BranchWeights[FirstCasePos],
6635 DefaultCase + BranchWeights[SecondCasePos]},
6642 if (ResultVector.size() == 1 && DefaultResult) {
6644 unsigned CaseCount = CaseValues.
size();
6657 for (
auto *Case : CaseValues) {
6658 if (Case->getValue().slt(MinCaseVal->
getValue()))
6660 AndMask &= Case->getValue();
6664 if (!AndMask.
isZero() &&
Known.getMaxValue().uge(AndMask)) {
6666 unsigned FreeBits =
Known.countMaxActiveBits() - AndMask.
popcount();
6670 if (FreeBits ==
Log2_32(CaseCount)) {
6671 Value *
And = Builder.CreateAnd(Condition, AndMask);
6672 Value *Cmp = Builder.CreateICmpEQ(
6675 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6691 for (
auto *Case : CaseValues)
6692 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6698 Condition = Builder.CreateSub(Condition, MinCaseVal);
6699 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6700 Value *Cmp = Builder.CreateICmpEQ(
6703 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6716 if (CaseValues.
size() == 2) {
6717 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6718 "switch.selectcmp.case1");
6719 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6720 "switch.selectcmp.case2");
6721 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6723 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6743 std::vector<DominatorTree::UpdateType> Updates;
6750 Builder.CreateBr(DestBB);
6754 PHI->removeIncomingValueIf(
6755 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6756 PHI->addIncoming(SelectValue, SelectBB);
6759 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6765 if (DTU && RemovedSuccessors.
insert(Succ).second)
6768 SI->eraseFromParent();
6783 SwitchCaseResultVectorTy UniqueResults;
6789 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6790 Builder.SetInsertPoint(
SI);
6793 [[maybe_unused]]
auto HasWeights =
6798 (BranchWeights.
size() >=
6799 UniqueResults.size() + (DefaultResult !=
nullptr)));
6802 Builder,
DL, BranchWeights);
6814class SwitchReplacement {
6821 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
6822 Constant *DefaultValue,
const DataLayout &
DL,
6823 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
6832 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6839 bool isLookupTable();
6876 ConstantInt *BitMap =
nullptr;
6877 IntegerType *BitMapElementTy =
nullptr;
6880 ConstantInt *LinearOffset =
nullptr;
6881 ConstantInt *LinearMultiplier =
nullptr;
6882 bool LinearMapValWrapped =
false;
6890SwitchReplacement::SwitchReplacement(
6892 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
6893 Constant *DefaultValue,
const DataLayout &
DL,
6894 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
6895 : DefaultValue(DefaultValue) {
6896 assert(
Values.size() &&
"Can't build lookup table without values!");
6897 assert(TableSize >=
Values.size() &&
"Can't fit values in table!");
6900 SingleValue =
Values.begin()->second;
6906 for (
const auto &[CaseVal, CaseRes] :
Values) {
6909 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6910 TableContents[Idx] = CaseRes;
6917 if (
Values.size() < TableSize) {
6919 "Need a default value to fill the lookup table holes.");
6922 if (!TableContents[
I])
6923 TableContents[
I] = DefaultValue;
6929 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6930 SingleValue =
nullptr;
6936 Kind = SingleValueKind;
6943 bool LinearMappingPossible =
true;
6948 bool NonMonotonic =
false;
6949 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6966 LinearMappingPossible =
false;
6971 APInt Dist = Val - PrevVal;
6974 }
else if (Dist != DistToPrev) {
6975 LinearMappingPossible =
false;
6983 if (LinearMappingPossible) {
6985 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6986 APInt M = LinearMultiplier->getValue();
6987 bool MayWrap =
true;
6988 if (
isIntN(M.getBitWidth(), TableSize - 1))
6989 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6990 LinearMapValWrapped = NonMonotonic || MayWrap;
6991 Kind = LinearMapKind;
6997 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6999 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
7001 TableInt <<=
IT->getBitWidth();
7005 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
7008 BitMap = ConstantInt::get(M.getContext(), TableInt);
7009 BitMapElementTy =
IT;
7020 unsigned NeededBitWidth =
7021 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7034 Kind = LookupTableKind;
7040 case SingleValueKind:
7042 case LinearMapKind: {
7046 false,
"switch.idx.cast");
7047 if (!LinearMultiplier->
isOne())
7048 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7050 !LinearMapValWrapped);
7052 if (!LinearOffset->
isZero())
7055 !LinearMapValWrapped);
7072 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7073 "switch.shiftamt",
true,
true);
7076 Value *DownShifted =
7077 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7079 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7081 case LookupTableKind: {
7084 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7085 true, GlobalVariable::PrivateLinkage,
7086 Initializer,
"switch.table." +
Func->getName());
7087 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7091 Type *IndexTy =
DL.getIndexType(
Table->getType());
7094 if (
Index->getType() != IndexTy) {
7095 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7099 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7102 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7106 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7115bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7117 Type *ElementType) {
7125 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7127 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7133 if (
TTI.isTypeLegal(Ty))
7148 DL.fitsInLegalInteger(
IT->getBitWidth());
7151Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7153bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7155bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7162 const uint64_t MinDensity = OptSize ? 40 : 10;
7167 return NumCases * 100 >= CaseRange * MinDensity;
7179static std::optional<unsigned>
7182 assert(
Values.size() > 1 &&
"expected multiple switch cases");
7184 return std::nullopt;
7189 for (
auto &V : ReducedValues) {
7191 ReducedValuesOr |= Reduced;
7192 V = (int64_t)Reduced;
7205 for (
auto &V : ReducedValues)
7206 V = (int64_t)((
uint64_t)V >> Shift);
7209 return std::nullopt;
7223 if (
SI->getNumCases() > TableSize)
7226 bool AllTablesFitInRegister =
true;
7227 bool HasIllegalType =
false;
7228 for (
const auto &Ty : ResultTypes) {
7233 AllTablesFitInRegister =
7234 AllTablesFitInRegister &&
7235 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7240 if (HasIllegalType && !AllTablesFitInRegister)
7245 if (AllTablesFitInRegister)
7253 SI->getFunction()->hasOptSize());
7263 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7266 return all_of(ResultTypes, [&](
const auto &ResultType) {
7267 return SwitchReplacement::wouldFitInRegister(
7317 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7322 for (
auto ValuePair :
Values) {
7325 if (!CaseConst || CaseConst == DefaultConst ||
7326 (CaseConst != TrueConst && CaseConst != FalseConst))
7340 if (DefaultConst == FalseConst) {
7343 ++NumTableCmpReuses;
7346 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7347 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7350 ++NumTableCmpReuses;
7360 bool ConvertSwitchToLookupTable) {
7361 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7375 if (
SI->getNumCases() < 3)
7397 MinCaseVal = CaseVal;
7399 MaxCaseVal = CaseVal;
7416 It->second.push_back(std::make_pair(CaseVal,
Value));
7424 bool HasDefaultResults =
7426 DefaultResultsList,
DL,
TTI);
7427 for (
const auto &
I : DefaultResultsList) {
7430 DefaultResults[
PHI] = Result;
7434 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7437 if (UseSwitchConditionAsTableIndex) {
7439 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7444 TableIndexOffset = MinCaseVal;
7451 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7453 bool TableHasHoles = (NumResults < TableSize);
7458 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7466 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7469 if (
SI->getNumCases() < 4)
7471 if (!
DL.fitsInLegalInteger(TableSize))
7480 if (UseSwitchConditionAsTableIndex) {
7481 TableIndex =
SI->getCondition();
7482 if (HasDefaultResults) {
7494 all_of(ResultTypes, [&](
const auto &ResultType) {
7495 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7500 TableSize = std::max(UpperBound, TableSize);
7503 DefaultIsReachable =
false;
7511 const auto &ResultList = ResultLists[
PHI];
7513 Type *ResultType = ResultList.begin()->second->getType();
7518 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7519 ResultList, DefaultVal,
DL,
TTI, FuncName);
7520 PhiToReplacementMap.
insert({
PHI, Replacement});
7523 bool AnyLookupTables =
any_of(
7524 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7525 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7526 [](
auto &KV) {
return KV.second.isBitMap(); });
7534 if (AnyLookupTables &&
7535 (!
TTI.shouldBuildLookupTables() ||
7541 if (!ConvertSwitchToLookupTable &&
7542 (AnyLookupTables || AnyBitMaps || NeedMask))
7545 Builder.SetInsertPoint(
SI);
7548 if (!UseSwitchConditionAsTableIndex) {
7551 bool MayWrap =
true;
7552 if (!DefaultIsReachable) {
7557 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7558 "switch.tableidx",
false,
7562 std::vector<DominatorTree::UpdateType> Updates;
7568 assert(MaxTableSize >= TableSize &&
7569 "It is impossible for a switch to have more entries than the max "
7570 "representable value of its input integer type's size.");
7575 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7580 Builder.SetInsertPoint(
SI);
7581 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7582 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7583 Builder.CreateBr(LookupBB);
7589 Value *Cmp = Builder.CreateICmpULT(
7590 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7592 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7593 CondBranch = RangeCheckBranch;
7599 Builder.SetInsertPoint(LookupBB);
7605 MaskBB->
setName(
"switch.hole_check");
7612 APInt MaskInt(TableSizePowOf2, 0);
7613 APInt One(TableSizePowOf2, 1);
7615 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7616 for (
const auto &Result : ResultList) {
7619 MaskInt |= One << Idx;
7621 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7628 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7629 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7630 Value *LoBit = Builder.CreateTrunc(
7632 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7637 Builder.SetInsertPoint(LookupBB);
7641 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7644 SI->getDefaultDest()->removePredecessor(BB,
7651 const ResultListTy &ResultList = ResultLists[
PHI];
7652 auto Replacement = PhiToReplacementMap.
at(
PHI);
7653 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7656 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7659 for (
auto *
User :
PHI->users()) {
7661 Replacement.getDefaultValue(), ResultList);
7665 PHI->addIncoming(Result, LookupBB);
7668 Builder.CreateBr(CommonDest);
7680 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7683 if (Succ ==
SI->getDefaultDest()) {
7684 if (HasBranchWeights)
7685 ToDefaultWeight += BranchWeights[
I];
7689 if (DTU && RemovedSuccessors.
insert(Succ).second)
7691 if (HasBranchWeights)
7692 ToLookupWeight += BranchWeights[
I];
7694 SI->eraseFromParent();
7695 if (HasBranchWeights)
7702 ++NumLookupTablesHoles;
7718 if (CondTy->getIntegerBitWidth() > 64 ||
7719 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7723 if (
SI->getNumCases() < 4)
7731 for (
const auto &
C :
SI->cases())
7732 Values.push_back(
C.getCaseValue()->getValue().getSExtValue());
7736 bool OptSize =
SI->getFunction()->hasOptSize();
7743 std::optional<unsigned> Shift;
7773 Builder.SetInsertPoint(
SI);
7777 Value *Rot = Builder.CreateIntrinsic(
7778 Ty, Intrinsic::fshl,
7779 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - *Shift)});
7780 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7782 for (
auto Case :
SI->cases()) {
7783 auto *Orig = Case.getCaseValue();
7784 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7829 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
7830 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
7847 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
7850 return !Updates.
empty();
7870 if (
SI->defaultDestUnreachable())
7881 if (!
Known.isConstant())
7888 ConstantInt::get(
SI->getContext(),
Known.getConstant());
7890 if (CaseIt ==
SI->case_default()) {
7899 SI->case_default());
7901 assert(
SI->getNumCases() > 0 &&
"Switch should have at least one case");
7902 assert(
SI->findCaseValue(CaseVal) !=
SI->case_default() &&
7903 "Proven value should have a dedicated case");
7904 assert(
SI->defaultDestUnreachable());
7922 Value *Condition =
SI->getCondition();
7926 if (CondTy->getIntegerBitWidth() > 64 ||
7927 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7939 if (
SI->getNumCases() < 4)
7944 for (
const auto &Case :
SI->cases()) {
7945 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7947 Values.push_back(CaseValue);
7957 SI->getFunction()->hasOptSize()))
7961 Builder.SetInsertPoint(
SI);
7963 if (!
SI->defaultDestUnreachable()) {
7966 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
7967 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
7969 auto *OrigBB =
SI->getParent();
7970 auto *DefaultCaseBB =
SI->getDefaultDest();
7972 auto It = OrigBB->getTerminator()->getIterator();
7985 NewWeights[1] = Weights[0] / 2;
7986 NewWeights[0] = OrigDenominator - NewWeights[1];
7998 Weights[0] = NewWeights[1];
7999 uint64_t CasesDenominator = OrigDenominator - Weights[0];
8001 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
8007 It->eraseFromParent();
8015 for (
auto &Case :
SI->cases()) {
8016 auto *OrigValue = Case.getCaseValue();
8017 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
8018 OrigValue->getValue().countr_zero()));
8022 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
8025 SI->setCondition(ConditionTrailingZeros);
8035 if (!Cmp || !Cmp->hasOneUse())
8046 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
8049 if (
SI->getNumCases() == 2) {
8056 Succ =
SI->getDefaultDest();
8057 SuccWeight = Weights[0];
8059 for (
auto &Case :
SI->cases()) {
8060 std::optional<int64_t> Val =
8064 if (!Missing.erase(*Val))
8069 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
8072 assert(Missing.size() == 1 &&
"Should have one case left");
8073 Res = *Missing.begin();
8074 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
8076 Unreachable =
SI->getDefaultDest();
8078 for (
auto &Case :
SI->cases()) {
8079 BasicBlock *NewSucc = Case.getCaseSuccessor();
8080 uint32_t Weight = Weights[Case.getSuccessorIndex()];
8083 OtherSuccWeight += Weight;
8086 SuccWeight = Weight;
8087 }
else if (Succ == NewSucc) {
8093 for (
auto &Case :
SI->cases()) {
8094 std::optional<int64_t> Val =
8096 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8098 if (Case.getCaseSuccessor() == Succ) {
8120 if (Cmp->isSigned())
8123 MDNode *NewWeights =
nullptr;
8129 Builder.SetInsertPoint(
SI->getIterator());
8130 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
8131 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8132 SI->getMetadata(LLVMContext::MD_unpredictable));
8136 SI->eraseFromParent();
8137 Cmp->eraseFromParent();
8138 if (DTU && Unreachable)
8163 assert(
BB &&
"Expected non-null BB");
8165 if (
BB->isEntryBlock())
8178 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8183 if (&
BB->front() != &
BB->back())
8198 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8209 return (*EBW->PhiPredIVs)[&Phi][BB];
8231 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8234 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8235 return PredIVs[
A] == PredIVs[
B];
8244 if (Candidates.
size() < 2)
8259 assert(Succ &&
"Expected unconditional BB");
8269 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8272 for (
auto &
IV : Phi->incoming_values())
8273 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8291 bool MadeChange =
false;
8305 if (!LivePreds.
contains(PredOfDead))
8312 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8313 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8318 T->replaceSuccessorWith(
Dead, Live);
8323 for (
const auto &EBW : BBs2Merge) {
8326 const auto &[It, Inserted] =
Keep.insert(&EBW);
8335 if (KeepBB == DeadBB)
8339 RedirectIncomingEdges(DeadBB, KeepBB);
8348 if (DTU && !Updates.
empty())
8354bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8355 DomTreeUpdater *DTU) {
8357 SmallSetVector<BasicBlock *, 16> FilteredArms(
8363bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8364 DomTreeUpdater *DTU) {
8375 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8381bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8384 if (isValueEqualityComparison(SI)) {
8388 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8389 return requestResimplify();
8393 if (simplifySwitchOnSelect(SI,
Select))
8394 return requestResimplify();
8398 if (SI == &*BB->
begin())
8399 if (foldValueComparisonIntoPredecessors(SI, Builder))
8400 return requestResimplify();
8406 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8407 return requestResimplify();
8411 return requestResimplify();
8414 return requestResimplify();
8417 return requestResimplify();
8420 return requestResimplify();
8425 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8427 Options.ConvertSwitchToLookupTable))
8428 return requestResimplify();
8431 return requestResimplify();
8434 return requestResimplify();
8437 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8438 return requestResimplify();
8442 if (simplifyDuplicateSwitchArms(SI, DTU))
8443 return requestResimplify();
8446 return requestResimplify();
8449 return requestResimplify();
8454bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8457 SmallVector<uint32_t> BranchWeights;
8461 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8462 if (HasBranchWeights)
8467 SmallPtrSet<Value *, 8> Succs;
8468 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8473 RemovedSuccs.
insert(Dest);
8483 std::vector<DominatorTree::UpdateType> Updates;
8484 Updates.reserve(RemovedSuccs.
size());
8485 for (
auto *RemovedSucc : RemovedSuccs)
8486 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8503 if (HasBranchWeights) {
8510 if (simplifyIndirectBrOnSelect(IBI, SI))
8511 return requestResimplify();
8547 if (BB == OtherPred)
8558 std::vector<DominatorTree::UpdateType> Updates;
8565 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8566 "unexpected successor");
8567 II->setUnwindDest(OtherPred);
8582 Builder.CreateUnreachable();
8591bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8603 bool NeedCanonicalLoop =
8617 if (
I->isTerminator() &&
8618 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8642 if (!PPred || (PredPred && PredPred != PPred))
8683 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8687 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8717 bool HasWeight =
false;
8722 BBTWeight = BBFWeight = 1;
8727 BB1TWeight = BB1FWeight = 1;
8732 BB2TWeight = BB2FWeight = 1;
8734 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8735 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8742bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
8746 "Tautological conditional branch should have been eliminated already.");
8749 if (!
Options.SimplifyCondBranch ||
8754 if (isValueEqualityComparison(BI)) {
8759 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8760 return requestResimplify();
8764 for (
auto &
I : *BB) {
8769 if (foldValueComparisonIntoPredecessors(BI, Builder))
8770 return requestResimplify();
8776 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8789 return requestResimplify();
8795 if (
Options.SpeculateBlocks &&
8798 return requestResimplify();
8807 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8808 return requestResimplify();
8810 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8812 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8813 auto CanSpeculateConditionalLoadsStores = [&]() {
8815 for (Instruction &
I : *Succ) {
8816 if (
I.isTerminator()) {
8817 if (
I.getNumSuccessors() > 1)
8821 SpeculatedConditionalLoadsStores.
size() ==
8825 SpeculatedConditionalLoadsStores.
push_back(&
I);
8828 return !SpeculatedConditionalLoadsStores.
empty();
8831 if (CanSpeculateConditionalLoadsStores()) {
8833 std::nullopt,
nullptr);
8834 return requestResimplify();
8844 return requestResimplify();
8853 return requestResimplify();
8859 if (foldCondBranchOnValueKnownInPredecessor(BI))
8860 return requestResimplify();
8867 return requestResimplify();
8875 return requestResimplify();
8879 return requestResimplify();
8886 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8898 auto *Use = cast<Instruction>(U.getUser());
8901 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
8904 switch (Use->getOpcode()) {
8907 case Instruction::GetElementPtr:
8908 case Instruction::Ret:
8909 case Instruction::BitCast:
8910 case Instruction::Load:
8911 case Instruction::Store:
8912 case Instruction::Call:
8913 case Instruction::CallBr:
8914 case Instruction::Invoke:
8915 case Instruction::UDiv:
8916 case Instruction::URem:
8920 case Instruction::SDiv:
8921 case Instruction::SRem:
8925 if (FindUse ==
I->use_end())
8927 auto &
Use = *FindUse;
8941 if (
GEP->getPointerOperand() ==
I) {
8944 if (
GEP->getType()->isVectorTy())
8952 if (!
GEP->hasAllZeroIndices() &&
8953 (!
GEP->isInBounds() ||
8955 GEP->getPointerAddressSpace())))
8956 PtrValueMayBeModified =
true;
8962 bool HasNoUndefAttr =
8963 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8968 if (
C->isNullValue() && HasNoUndefAttr &&
8969 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8970 return !PtrValueMayBeModified;
8976 if (!LI->isVolatile())
8978 LI->getPointerAddressSpace());
8982 if (!
SI->isVolatile())
8984 SI->getPointerAddressSpace())) &&
8985 SI->getPointerOperand() ==
I;
8990 if (
I == Assume->getArgOperand(0))
8998 if (CB->getCalledOperand() ==
I)
9001 if (CB->isArgOperand(&
Use)) {
9002 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
9005 CB->paramHasNonNullAttr(ArgIdx,
false))
9006 return !PtrValueMayBeModified;
9025 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
9033 Builder.CreateUnreachable();
9034 T->eraseFromParent();
9046 Builder.CreateUnreachable();
9053 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
9055 Assumption = Builder.CreateAssumption(
Cond);
9070 Builder.SetInsertPoint(Unreachable);
9072 Builder.CreateUnreachable();
9073 for (
const auto &Case :
SI->cases())
9074 if (Case.getCaseSuccessor() == BB) {
9076 Case.setSuccessor(Unreachable);
9078 if (
SI->getDefaultDest() == BB) {
9080 SI->setDefaultDest(Unreachable);
9094bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9119 return requestResimplify();
9138 if (simplifyDuplicatePredecessors(BB, DTU))
9142 if (
Options.SpeculateBlocks &&
9149 Options.SpeculateUnpredictables))
9157 case Instruction::UncondBr:
9160 case Instruction::CondBr:
9163 case Instruction::Resume:
9166 case Instruction::CleanupRet:
9169 case Instruction::Switch:
9172 case Instruction::Unreachable:
9175 case Instruction::IndirectBr:
9183bool SimplifyCFGOpt::run(BasicBlock *BB) {
9193 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static bool IsIndirectCall(const MachineInstr *MI)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
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
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange, bool OptSize)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool isProfitableToSpeculate(const CondBrInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(CondBrInst *BI, CondBrInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static void hoistConditionalLoadsStores(CondBrInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool simplifySwitchDefaultBranch(SwitchInst *SI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool extractPredSuccWeights(CondBrInst *PBI, CondBrInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static bool performBranchToCommonDestFolding(CondBrInst *BI, CondBrInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static std::optional< unsigned > getDenseSwitchRangeReductionShift(ArrayRef< int64_t > Values, int64_t Base, bool OptSize)
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool mergeConditionalStores(CondBrInst *PBI, CondBrInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeNestedCondBranch(CondBrInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool tryWidenCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool mergeIdenticalBBs(ArrayRef< BasicBlock * > Candidates, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static bool tryToMergeLandingPad(LandingPadInst *LPad, UncondBrInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool SimplifyCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, CondBrInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & front() const
Get the first element.
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
bool isEquality() const
Determine if this is an equals/not equals predicate.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Conditional Branch instruction.
static CondBrInst * Create(Value *Cond, BasicBlock *IfTrue, BasicBlock *IfFalse, InsertPosition InsertBefore=nullptr)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setCondition(Value *V)
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
ConstantFP - Floating Point Values [float, double].
ConstantFolder - Create constants with minimum, target independent, folding.
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
A constant pointer value that points to null.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Implements a dense probed hash-table based set.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
LLVM_ABI CallInst * CreateAssumption(Value *Cond)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
UncondBrInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
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 bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
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 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.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
void insert_range(Range &&R)
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
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.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this store instruction.
Value * getPointerOperand()
Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Unconditional Branch instruction.
void setSuccessor(BasicBlock *NewSucc)
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i=0) const
'undef' values are things that do not have specified contents.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
auto m_UMin(const Opnd0 &Op0, const Opnd1 &Op1)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
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_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
DXILDebugInfoMap run(Module &M)
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
LLVM_ABI bool foldBranchToCommonDest(CondBrInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, AssumptionCache *AC=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 ...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
RelativeUniformCounterPtr Values
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"))
@ Known
Known to have no common set bits.
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)
@ Load
The value being inserted comes from a load (InsertElement only).
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr detail::StaticCastFunc< To > StaticCastTo
Function objects corresponding to the Cast types defined above.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI CondBrInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
LLVM_ABI void InvertBranch(CondBrInst *PBI, IRBuilderBase &Builder)
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible immediate values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
auto succ_size(const MachineBasicBlock *BB)
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
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...
LLVM_ABI bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
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 isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
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...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Constant * ConstantFoldCastInstruction(unsigned opcode, Constant *V, Type *DestTy)
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...
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.
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const SimplifyQuery &Q, bool IgnoreFree=false)
Equivalent to isDereferenceableAndAlignedPointer with an alignment of 1.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
@ Keep
No function return thunk.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, const SimplifyQuery &SQ, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two BBs are equal depends on the contents of the BasicBlock and the incoming values ...
SmallDenseMap< BasicBlock *, Value *, 8 > BB2ValueMap
DenseMap< PHINode *, BB2ValueMap > Phi2IVsMap
static bool canBeMerged(const BasicBlock *BB)
static bool isEqual(const EqualBBWrapper *LHS, const EqualBBWrapper *RHS)
static unsigned getHashValue(const EqualBBWrapper *EBW)
An information struct used to provide DenseMap with the various necessary components for a given valu...
A MapVector that performs no allocations if smaller than a certain size.