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;
2007 if (AllInstsAreIdentical) {
2017 for (
auto &SuccIter : OtherSuccIterRange) {
2025 assert(
Success &&
"We should not be trying to hoist callbases "
2026 "with non-intersectable attributes");
2038 NumHoistCommonCode += SuccIterPairs.
size();
2040 NumHoistCommonInstrs += SuccIterPairs.
size();
2049 for (
auto &SuccIterPair : SuccIterPairs) {
2058bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2059 Instruction *TI, Instruction *I1,
2060 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2070 auto *I2 = *OtherSuccTIs.
begin();
2090 for (PHINode &PN : Succ->
phis()) {
2091 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2092 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2093 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2113 if (!
NT->getType()->isVoidTy()) {
2114 I1->replaceAllUsesWith(NT);
2115 for (Instruction *OtherSuccTI : OtherSuccTIs)
2116 OtherSuccTI->replaceAllUsesWith(NT);
2120 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2126 for (
auto *OtherSuccTI : OtherSuccTIs)
2127 Locs.
push_back(OtherSuccTI->getDebugLoc());
2139 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2141 for (PHINode &PN : Succ->
phis()) {
2142 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2143 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2149 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2159 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2160 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2161 PN.setIncomingValue(i, SI);
2172 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2178 for (BasicBlock *Succ : UniqueSuccessors)
2179 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2193 if (
I->isIntDivRem())
2208 std::optional<unsigned> NumUses;
2209 for (
auto *
I : Insts) {
2212 I->getType()->isTokenTy())
2217 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2225 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2229 NumUses =
I->getNumUses();
2230 else if (NumUses !=
I->getNumUses())
2236 for (
auto *
I : Insts) {
2250 for (
const Use &U : I0->
uses()) {
2251 auto It = PHIOperands.find(&U);
2252 if (It == PHIOperands.end())
2255 if (!
equal(Insts, It->second))
2269 if (HaveIndirectCalls) {
2270 if (!AllCallsAreIndirect)
2274 Value *Callee =
nullptr;
2278 Callee = CurrCallee;
2279 else if (Callee != CurrCallee)
2285 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2291 if (!
all_of(Insts, SameAsI0)) {
2297 for (
auto *
I : Insts)
2298 Ops.push_back(
I->getOperand(OI));
2308 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2313 for (
auto *BB : Blocks) {
2315 I =
I->getPrevNode();
2340 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2343 PN->insertBefore(BBEnd->begin());
2344 for (
auto *
I : Insts)
2345 PN->addIncoming(
I->getOperand(O),
I->getParent());
2354 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2357 for (
auto *
I : Insts)
2371 assert(
Success &&
"We should not be trying to sink callbases "
2372 "with non-intersectable attributes");
2383 PN->replaceAllUsesWith(I0);
2384 PN->eraseFromParent();
2388 for (
auto *
I : Insts) {
2393 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2394 I->replaceAllUsesWith(I0);
2395 I->eraseFromParent();
2445 bool HaveNonUnconditionalPredecessors =
false;
2451 HaveNonUnconditionalPredecessors =
true;
2453 if (UnconditionalPreds.
size() < 2)
2466 for (
const Use &U : PN.incoming_values())
2467 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2468 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2470 Ops.push_back(*IncomingVals[Pred]);
2478 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2491 if (!followedByDeoptOrUnreachable) {
2493 auto IsMemOperand = [](
Use &U) {
2506 unsigned NumPHIInsts = 0;
2507 for (
Use &U : (*LRI)[0]->operands()) {
2508 auto It = PHIOperands.
find(&U);
2509 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2510 return InstructionsToSink.contains(V);
2517 if (IsMemOperand(U) &&
2518 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2525 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2526 return NumPHIInsts <= 1;
2543 while (Idx < ScanIdx) {
2544 if (!ProfitableToSinkInstruction(LRI)) {
2547 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2560 if (Idx < ScanIdx) {
2563 InstructionsToSink = InstructionsProfitableToSink;
2569 !ProfitableToSinkInstruction(LRI) &&
2570 "We already know that the last instruction is unprofitable to sink");
2578 for (
auto *
I : *LRI)
2579 InstructionsProfitableToSink.
erase(
I);
2580 if (!ProfitableToSinkInstruction(LRI)) {
2583 InstructionsToSink = InstructionsProfitableToSink;
2597 if (HaveNonUnconditionalPredecessors) {
2598 if (!followedByDeoptOrUnreachable) {
2606 bool Profitable =
false;
2607 while (Idx < ScanIdx) {
2641 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2643 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2651 NumSinkCommonInstrs++;
2655 ++NumSinkCommonCode;
2661struct CompatibleSets {
2662 using SetTy = SmallVector<InvokeInst *, 2>;
2668 SetTy &getCompatibleSet(InvokeInst *
II);
2670 void insert(InvokeInst *
II);
2673CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2678 for (CompatibleSets::SetTy &Set : Sets) {
2679 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2684 return Sets.emplace_back();
2687void CompatibleSets::insert(InvokeInst *
II) {
2688 getCompatibleSet(
II).emplace_back(
II);
2692 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2695 auto IsIllegalToMerge = [](InvokeInst *
II) {
2696 return II->cannotMerge() ||
II->isInlineAsm();
2698 if (
any_of(Invokes, IsIllegalToMerge))
2706 if (HaveIndirectCalls) {
2707 if (!AllCallsAreIndirect)
2712 for (InvokeInst *
II : Invokes) {
2713 Value *CurrCallee =
II->getCalledOperand();
2714 assert(CurrCallee &&
"There is always a called operand.");
2717 else if (Callee != CurrCallee)
2724 auto HasNormalDest = [](InvokeInst *
II) {
2727 if (
any_of(Invokes, HasNormalDest)) {
2730 if (!
all_of(Invokes, HasNormalDest))
2735 for (InvokeInst *
II : Invokes) {
2737 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2739 NormalBB = CurrNormalBB;
2740 else if (NormalBB != CurrNormalBB)
2748 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2757 for (InvokeInst *
II : Invokes) {
2759 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2761 UnwindBB = CurrUnwindBB;
2763 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2770 Invokes.front()->getUnwindDest(),
2771 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2776 const InvokeInst *II0 = Invokes.front();
2777 for (
auto *
II : Invokes.drop_front())
2782 auto IsIllegalToMergeArguments = [](
auto Ops) {
2783 Use &U0 = std::get<0>(
Ops);
2784 Use &U1 = std::get<1>(
Ops);
2790 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2791 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2792 IsIllegalToMergeArguments))
2804 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2810 bool HasNormalDest =
2815 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2819 II0->
getParent()->getIterator()->getNextNode();
2824 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2828 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2830 if (!HasNormalDest) {
2834 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2842 return MergedInvoke;
2856 SuccBBOfMergedInvoke});
2879 return II->getOperand(U.getOperandNo()) != U.get();
2898 Invokes.
front()->getParent());
2906 if (!MergedDebugLoc)
2907 MergedDebugLoc =
II->getDebugLoc();
2915 OrigSuccBB->removePredecessor(
II->getParent());
2919 BI->setDebugLoc(
II->getDebugLoc());
2921 assert(
Success &&
"Merged invokes with incompatible attributes");
2924 II->replaceAllUsesWith(MergedInvoke);
2925 II->eraseFromParent();
2929 ++NumInvokeSetsFormed;
2965 CompatibleSets Grouper;
2975 if (Invokes.
size() < 2)
2987class EphemeralValueTracker {
2988 SmallPtrSet<const Instruction *, 32> EphValues;
2990 bool isEphemeral(
const Instruction *
I) {
2993 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2994 all_of(
I->users(), [&](
const User *U) {
2995 return EphValues.count(cast<Instruction>(U));
3000 bool track(
const Instruction *
I) {
3001 if (isEphemeral(
I)) {
3052 unsigned MaxNumInstToLookAt = 9;
3056 if (!MaxNumInstToLookAt)
3058 --MaxNumInstToLookAt;
3071 if (
SI->getPointerOperand() == StorePtr &&
3072 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3075 return SI->getValueOperand();
3080 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3081 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3083 bool ExplicitlyDereferenceableOnly;
3091 (!ExplicitlyDereferenceableOnly ||
3109 unsigned &SpeculatedInstructions,
3117 bool HaveRewritablePHIs =
false;
3119 Value *OrigV = PN.getIncomingValueForBlock(BB);
3120 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3127 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3136 HaveRewritablePHIs =
true;
3139 if (!OrigCE && !ThenCE)
3146 if (OrigCost + ThenCost > MaxCost)
3153 ++SpeculatedInstructions;
3154 if (SpeculatedInstructions > 1)
3158 return HaveRewritablePHIs;
3162 std::optional<bool> Invert,
3166 if (BI->getMetadata(LLVMContext::MD_unpredictable))
3173 if (!Invert.has_value())
3176 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3180 return BIEndProb < Likely;
3220bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3221 BasicBlock *ThenBB) {
3237 bool Invert =
false;
3252 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3254 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3256 unsigned SpeculatedInstructions = 0;
3257 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3258 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3259 Value *SpeculatedStoreValue =
nullptr;
3260 StoreInst *SpeculatedStore =
nullptr;
3261 EphemeralValueTracker EphTracker;
3276 if (EphTracker.track(&
I))
3281 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3283 SpeculatedConditionalLoadsStores.
size() <
3287 if (IsSafeCheapLoadStore)
3288 SpeculatedConditionalLoadsStores.
push_back(&
I);
3290 ++SpeculatedInstructions;
3292 if (SpeculatedInstructions > 1)
3296 if (!IsSafeCheapLoadStore &&
3299 (SpeculatedStoreValue =
3302 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3308 if (!SpeculatedStore && SpeculatedStoreValue)
3314 for (Use &
Op :
I.operands()) {
3319 ++SinkCandidateUseCounts[OpI];
3326 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3327 if (Inst->hasNUses(
Count)) {
3328 ++SpeculatedInstructions;
3329 if (SpeculatedInstructions > 1)
3336 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3339 SpeculatedInstructions,
Cost,
TTI);
3340 if (!Convert ||
Cost > Budget)
3344 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3348 if (SpeculatedStoreValue) {
3352 Value *FalseV = SpeculatedStoreValue;
3356 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3386 for (DbgVariableRecord *DbgAssign :
3389 DbgAssign->replaceVariableLocationOp(OrigV, S);
3399 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3402 I.dropUBImplyingAttrsAndMetadata();
3405 if (EphTracker.contains(&
I)) {
3407 I.eraseFromParent();
3413 for (
auto &It : *ThenBB)
3418 !DVR || !DVR->isDbgAssign())
3419 It.dropOneDbgRecord(&DR);
3420 BB->
splice(BI->getIterator(), ThenBB, ThenBB->begin(),
3421 std::prev(ThenBB->end()));
3423 if (!SpeculatedConditionalLoadsStores.
empty())
3429 for (PHINode &PN : EndBB->
phis()) {
3430 unsigned OrigI = PN.getBasicBlockIndex(BB);
3431 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3432 Value *OrigV = PN.getIncomingValue(OrigI);
3433 Value *ThenV = PN.getIncomingValue(ThenI);
3442 Value *TrueV = ThenV, *FalseV = OrigV;
3446 PN.setIncomingValue(OrigI, V);
3447 PN.setIncomingValue(ThenI, V);
3451 for (Instruction *
I : SpeculatedPseudoProbes)
3452 I->eraseFromParent();
3465 if (!ReachesNonLocalUses.
insert(BB).second)
3480 EphemeralValueTracker EphTracker;
3487 if (CI->cannotDuplicate() || CI->isConvergent())
3500 for (
User *U :
I.users()) {
3503 if (UsedInBB == BB) {
3507 NonLocalUseBlocks.
insert(UsedInBB);
3521 if (
I &&
I->getParent() == To)
3537static std::optional<bool>
3558 KnownValues[CB].
insert(Pred);
3562 if (KnownValues.
empty())
3587 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3590 for (
const auto &Pair : KnownValues) {
3607 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3612 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3615 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3625 EdgeBB->setName(RealDest->
getName() +
".critedge");
3626 EdgeBB->moveBefore(RealDest);
3636 TranslateMap[
Cond] = CB;
3649 N->insertInto(EdgeBB, InsertPt);
3652 N->setName(BBI->getName() +
".c");
3663 if (!BBI->use_empty())
3664 TranslateMap[&*BBI] = V;
3665 if (!
N->mayHaveSideEffects()) {
3666 N->eraseFromParent();
3671 if (!BBI->use_empty())
3672 TranslateMap[&*BBI] =
N;
3678 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3679 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3680 SrcDbgCursor = std::next(BBI);
3682 N->cloneDebugInfoFrom(&*BBI);
3691 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3692 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3693 InsertPt->cloneDebugInfoFrom(BI);
3698 EdgeBI->setDebugLoc(BI->getDebugLoc());
3714 return std::nullopt;
3720bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3727 std::optional<bool>
Result;
3728 bool EverChanged =
false;
3734 }
while (Result == std::nullopt);
3743 bool SpeculateUnpredictables) {
3765 return isa<UncondBrInst>(IfBlock->getTerminator());
3768 "Will have either one or two blocks to speculate.");
3775 bool IsUnpredictable = DomBI->getMetadata(LLVMContext::MD_unpredictable);
3776 if (!IsUnpredictable) {
3779 (TWeight + FWeight) != 0) {
3784 if (IfBlocks.
size() == 1) {
3786 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3787 if (BIBBProb >= Likely)
3790 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3799 if (IfCondPhiInst->getParent() == BB)
3807 unsigned NumPhis = 0;
3820 if (SpeculateUnpredictables && IsUnpredictable)
3821 Budget +=
TTI.getBranchMispredictPenalty();
3834 AggressiveInsts, Cost, Budget,
TTI, AC,
3835 ZeroCostInstructions) ||
3837 AggressiveInsts, Cost, Budget,
TTI, AC,
3838 ZeroCostInstructions))
3851 auto IsBinOpOrAndEq = [](
Value *V) {
3874 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3887 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3889 <<
" F: " << IfFalse->
getName() <<
"\n");
3906 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3911 PN->eraseFromParent();
3917 Builder.CreateBr(BB);
3926 DomBI->eraseFromParent();
3938 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3939 if (
Opc == Instruction::And)
3940 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3941 if (
Opc == Instruction::Or)
3942 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3954 bool PredHasWeights =
3956 bool SuccHasWeights =
3958 if (PredHasWeights || SuccHasWeights) {
3959 if (!PredHasWeights)
3960 PredTrueWeight = PredFalseWeight = 1;
3961 if (!SuccHasWeights)
3962 SuccTrueWeight = SuccFalseWeight = 1;
3972static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3975 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
3977 "PredBB must be a predecessor of BB.");
3983 if (
TTI && !PBI->getMetadata(LLVMContext::MD_unpredictable) &&
3985 (PTWeight + PFWeight) != 0) {
3988 Likely =
TTI->getPredictableBranchThreshold();
3993 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3994 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3998 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4001 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4002 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4008 return std::nullopt;
4021 bool InvertPredCond;
4022 std::tie(CommonSucc,
Opc, InvertPredCond) =
4025 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4033 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4038 if (InvertPredCond) {
4051 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4054 SuccTrueWeight, SuccFalseWeight)) {
4060 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4065 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4066 PredTrueWeight * SuccFalseWeight);
4072 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4073 PredFalseWeight * SuccTrueWeight);
4075 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4084 PBI->setMetadata(LLVMContext::MD_prof,
nullptr);
4095 if (
MDNode *LoopMD = BI->getMetadata(LLVMContext::MD_loop))
4096 PBI->setMetadata(LLVMContext::MD_loop, LoopMD);
4117 if (!MDWeights.
empty()) {
4118 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4123 ++NumFoldBranchToCommonDest;
4130 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4131 return U->getType()->isVectorTy();
4142 unsigned BonusInstThreshold) {
4151 Cond->getParent() != BB || !
Cond->hasOneUse())
4172 bool InvertPredCond;
4174 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4206 unsigned NumBonusInsts = 0;
4207 bool SawVectorOp =
false;
4208 const unsigned PredCount = Preds.
size();
4212 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4232 NumBonusInsts += PredCount;
4240 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4243 return PN->getIncomingBlock(U) == BB;
4244 return UI->
getParent() == BB &&
I.comesBefore(UI);
4248 if (!
all_of(
I.uses(), IsBCSSAUse))
4252 BonusInstThreshold *
4268 for (
auto *BB : {BB1, BB2}) {
4284 Value *AlternativeV =
nullptr) {
4310 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4311 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4319 if (!AlternativeV &&
4325 PHI->addIncoming(V, BB);
4335 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4344 if (!PStore || !QStore)
4367 if (
I.mayReadOrWriteMemory())
4369 for (
auto &
I : *QFB)
4370 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4373 for (
auto &
I : *QTB)
4374 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4378 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4392 for (
auto &
I : *BB) {
4394 if (
I.isTerminator())
4412 "When we run out of budget we will eagerly return from within the "
4413 "per-instruction loop.");
4417 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4419 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4420 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4456 InvertPCond ^= (PStore->
getParent() != PTB);
4457 InvertQCond ^= (QStore->
getParent() != QTB);
4478 {CombinedWeights[0], CombinedWeights[1]},
4485 SI->copyMetadata(*QStore);
4491 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4494 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4557 bool InvertPCond =
false, InvertQCond =
false;
4559 if (PFB == QBI->getParent()) {
4563 if (QFB == PostBB) {
4570 if (PTB == QBI->getParent())
4581 if (!HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) ||
4582 !HasOnePredAndOneSucc(QFB, QBI->getParent(), PostBB))
4584 if ((PTB && !HasOnePredAndOneSucc(PTB, PBI->getParent(), QBI->getParent())) ||
4585 (QTB && !HasOnePredAndOneSucc(QTB, QBI->getParent(), PostBB)))
4587 if (!QBI->getParent()->hasNUses(2))
4593 for (
auto *BB : {PTB, PFB}) {
4598 PStoreAddresses.
insert(
SI->getPointerOperand());
4600 for (
auto *BB : {QTB, QFB}) {
4605 QStoreAddresses.
insert(
SI->getPointerOperand());
4611 auto &CommonAddresses = PStoreAddresses;
4614 for (
auto *Address : CommonAddresses)
4617 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4635 !BI->getParent()->getSinglePredecessor())
4637 if (!IfFalseBB->
phis().empty())
4647 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4652 NoSideEffects(*BI->getParent())) {
4664 NoSideEffects(*BI->getParent())) {
4721 if (&*BB->
begin() != BI)
4749 if (!PBI->getMetadata(LLVMContext::MD_unpredictable) &&
4751 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4755 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4758 if (CommonDestProb >= Likely)
4768 unsigned NumPhis = 0;
4779 <<
"AND: " << *BI->getParent());
4790 if (OtherDest == BB) {
4798 OtherDest = InfLoopBlock;
4810 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4814 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4818 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4833 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4834 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4837 SuccTrueWeight, SuccFalseWeight);
4839 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4840 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4841 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4842 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4846 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4847 PredOther * SuccCommon,
4848 PredOther * SuccOther};
4856 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4858 assert(
SI->getCondition() == PBICond);
4875 Value *BIV = PN.getIncomingValueForBlock(BB);
4876 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->getParent());
4877 Value *PBIV = PN.getIncomingValue(PBBIdx);
4881 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4882 PN.setIncomingValue(PBBIdx, NV);
4886 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4887 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4907bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4909 BasicBlock *FalseBB,
4910 uint32_t TrueWeight,
4911 uint32_t FalseWeight) {
4918 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4920 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4923 for (BasicBlock *Succ :
successors(OldTerm)) {
4925 if (Succ == KeepEdge1)
4926 KeepEdge1 =
nullptr;
4927 else if (Succ == KeepEdge2)
4928 KeepEdge2 =
nullptr;
4933 if (Succ != TrueBB && Succ != FalseBB)
4934 RemovedSuccessors.
insert(Succ);
4942 if (!KeepEdge1 && !KeepEdge2) {
4943 if (TrueBB == FalseBB) {
4954 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4974 SmallVector<DominatorTree::UpdateType, 2> Updates;
4976 for (
auto *RemovedSuccessor : RemovedSuccessors)
4977 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4988bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4993 if (!TrueVal || !FalseVal)
4998 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4999 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5002 uint32_t TrueWeight = 0, FalseWeight = 0;
5003 SmallVector<uint64_t, 8> Weights;
5007 if (Weights.
size() == 1 +
SI->getNumCases()) {
5009 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5011 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5016 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5025bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5039 SmallVector<uint32_t> SelectBranchWeights(2);
5043 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5044 SelectBranchWeights[0],
5045 SelectBranchWeights[1]);
5065bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5069 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5115bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5134 ConstantInt *NewCaseVal;
5142 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5148 SelectTrueVal = Builder.
getTrue();
5149 SelectFalseVal = Builder.
getFalse();
5152 SelectCond =
Select->getCondition();
5154 if (SelectCond != ICI)
5156 SelectTrueVal =
Select->getTrueValue();
5157 SelectFalseVal =
Select->getFalseValue();
5162 if (
SI->getCondition() != IcmpCond)
5168 if (
SI->getDefaultDest() != BB) {
5169 ConstantInt *VVal =
SI->findCaseDest(BB);
5170 assert(VVal &&
"Should have a unique destination value");
5178 return requestResimplify();
5184 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5186 if (Predicate == ICmpInst::ICMP_EQ)
5194 return requestResimplify();
5201 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5207 Value *DefaultCst = SelectFalseVal;
5208 Value *NewCst = SelectTrueVal;
5216 Select->replaceAllUsesWith(DefaultCst);
5217 Select->eraseFromParent();
5223 SmallVector<DominatorTree::UpdateType, 2> Updates;
5230 SwitchInstProfUpdateWrapper SIW(*SI);
5231 auto W0 = SIW.getSuccessorWeight(0);
5234 NewW = ((uint64_t(*W0) + 1) >> 1);
5235 SIW.setSuccessorWeight(0, *NewW);
5237 SIW.addCase(NewCaseVal, NewBB, NewW);
5239 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5248 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5256bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5258 const DataLayout &
DL) {
5268 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5270 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5271 Value *CompVal = ConstantCompare.CompValue;
5272 unsigned UsedICmps = ConstantCompare.UsedICmps;
5273 Value *ExtraCase = ConstantCompare.Extra;
5274 bool TrueWhenEqual = ConstantCompare.IsEq;
5291 if (ExtraCase && Values.
size() < 2)
5294 SmallVector<uint32_t> BranchWeights;
5301 if (!TrueWhenEqual) {
5304 std::swap(BranchWeights[0], BranchWeights[1]);
5310 <<
" cases into SWITCH. BB is:\n"
5313 SmallVector<DominatorTree::UpdateType, 2> Updates;
5320 nullptr,
"switch.early.test");
5331 AssumptionCache *AC =
Options.AC;
5337 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5344 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5350 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5351 <<
"\nEXTRABB = " << *BB);
5359 "Should not end up here with unstable pointers");
5361 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5366 if (Values.
front()->getValue() - Values.
back()->getValue() ==
5367 Values.
size() - 1) {
5369 Values.
back()->getValue(), Values.
front()->getValue() + 1);
5371 ICmpInst::Predicate Pred;
5389 SmallVector<uint32_t> NewWeights(Values.
size() + 1);
5390 NewWeights[0] = BranchWeights[1];
5393 V = BranchWeights[0] / Values.
size();
5398 for (ConstantInt *Val : Values)
5399 New->addCase(Val, EdgeBB);
5407 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5417 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5421bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5423 return simplifyCommonResume(RI);
5427 return simplifySingleResume(RI);
5440 switch (IntrinsicID) {
5441 case Intrinsic::dbg_declare:
5442 case Intrinsic::dbg_value:
5443 case Intrinsic::dbg_label:
5444 case Intrinsic::lifetime_end:
5454bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5463 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5467 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5469 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5470 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5474 if (IncomingBB->getUniqueSuccessor() != BB)
5479 if (IncomingValue != LandingPad)
5483 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5484 TrivialUnwindBlocks.
insert(IncomingBB);
5488 if (TrivialUnwindBlocks.
empty())
5492 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5496 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5499 for (BasicBlock *Pred :
5510 TrivialBB->getTerminator()->eraseFromParent();
5511 new UnreachableInst(RI->
getContext(), TrivialBB);
5513 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5520 return !TrivialUnwindBlocks.empty();
5524bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5528 "Resume must unwind the exception that caused control to here");
5584 int Idx = DestPN.getBasicBlockIndex(BB);
5598 Value *SrcVal = DestPN.getIncomingValue(Idx);
5601 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5605 DestPN.addIncoming(Incoming, Pred);
5632 std::vector<DominatorTree::UpdateType> Updates;
5636 if (UnwindDest ==
nullptr) {
5677 if (!SuccessorCleanupPad)
5686 SuccessorCleanupPad->eraseFromParent();
5695bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5712bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5744 BBI->dropDbgRecords();
5748 BBI->eraseFromParent();
5754 if (&BB->
front() != UI)
5757 std::vector<DominatorTree::UpdateType> Updates;
5760 for (BasicBlock *Predecessor : Preds) {
5768 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5779 "The destinations are guaranteed to be different here.");
5780 CallInst *Assumption;
5796 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5798 SwitchInstProfUpdateWrapper SU(*SI);
5799 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5800 if (i->getCaseSuccessor() != BB) {
5805 i = SU.removeCase(i);
5810 if (DTU &&
SI->getDefaultDest() != BB)
5811 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5813 if (
II->getUnwindDest() == BB) {
5819 if (!CI->doesNotThrow())
5820 CI->setDoesNotThrow();
5824 if (CSI->getUnwindDest() == BB) {
5835 E = CSI->handler_end();
5838 CSI->removeHandler(
I);
5845 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5846 if (CSI->getNumHandlers() == 0) {
5847 if (CSI->hasUnwindDest()) {
5851 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5852 Updates.push_back({DominatorTree::Insert,
5853 PredecessorOfPredecessor,
5854 CSI->getUnwindDest()});
5855 Updates.push_back({DominatorTree::Delete,
5856 PredecessorOfPredecessor, Predecessor});
5859 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5866 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5867 for (BasicBlock *EHPred : EHPreds)
5871 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5872 CSI->eraseFromParent();
5877 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5878 "Expected to always have an unwind to BB.");
5880 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5908static std::optional<ContiguousCasesResult>
5915 const APInt &Min = Cases.
back()->getValue();
5916 const APInt &Max = Cases.
front()->getValue();
5918 size_t ContiguousOffset = Cases.
size() - 1;
5919 if (
Offset == ContiguousOffset) {
5938 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
5939 return L->getValue() != R->getValue() + 1;
5941 if (It == Cases.
end())
5942 return std::nullopt;
5943 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5944 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5948 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5951 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5959 return std::nullopt;
5964 bool RemoveOrigDefaultBlock =
true) {
5966 auto *BB = Switch->getParent();
5967 auto *OrigDefaultBlock = Switch->getDefaultDest();
5968 if (RemoveOrigDefaultBlock)
5969 OrigDefaultBlock->removePredecessor(BB);
5973 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5975 Switch->setDefaultDest(&*NewDefaultBlock);
5979 if (RemoveOrigDefaultBlock &&
5989bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5991 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5993 bool HasDefault = !
SI->defaultDestUnreachable();
5995 auto *BB =
SI->getParent();
5997 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6002 for (
auto Case :
SI->cases()) {
6006 if (Dest == DestA) {
6012 if (Dest == DestB) {
6022 "Single-destination switch should have been folded.");
6024 assert(DestB !=
SI->getDefaultDest());
6025 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6029 std::optional<ContiguousCasesResult> ContiguousCases;
6032 if (!HasDefault && CasesA.
size() == 1)
6033 ContiguousCases = ContiguousCasesResult{
6041 else if (CasesB.
size() == 1)
6042 ContiguousCases = ContiguousCasesResult{
6051 else if (!HasDefault)
6055 if (!ContiguousCases)
6059 if (!ContiguousCases)
6062 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6068 Max->getValue() - Min->getValue() + 1);
6071 assert(
Max->getValue() == Min->getValue());
6076 else if (NumCases->
isNullValue() && !Cases->empty()) {
6080 if (!
Offset->isNullValue())
6088 SmallVector<uint64_t, 8> Weights;
6090 if (Weights.
size() == 1 +
SI->getNumCases()) {
6091 uint64_t TrueWeight = 0;
6092 uint64_t FalseWeight = 0;
6093 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6094 if (
SI->getSuccessor(
I) == Dest)
6095 TrueWeight += Weights[
I];
6097 FalseWeight += Weights[
I];
6099 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6110 unsigned PreviousEdges = Cases->size();
6111 if (Dest ==
SI->getDefaultDest())
6113 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6114 PHI.removeIncomingValue(
SI->getParent());
6117 unsigned PreviousEdges = OtherCases->size();
6118 if (OtherDest ==
SI->getDefaultDest())
6120 unsigned E = PreviousEdges - 1;
6124 for (
unsigned I = 0;
I !=
E; ++
I)
6125 PHI.removeIncomingValue(
SI->getParent());
6133 auto *UnreachableDefault =
SI->getDefaultDest();
6136 SI->eraseFromParent();
6138 if (!HasDefault && DTU)
6139 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
6157 unsigned MaxSignificantBitsInCond =
6164 for (
const auto &Case :
SI->cases()) {
6165 auto *
Successor = Case.getCaseSuccessor();
6176 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6182 }
else if (IsKnownValuesValid)
6183 KnownValues.
erase(CaseC);
6190 bool HasDefault = !
SI->defaultDestUnreachable();
6191 const unsigned NumUnknownBits =
6194 if (HasDefault && DeadCases.
empty()) {
6200 if (NumUnknownBits < 64 ) {
6201 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6202 if (
SI->getNumCases() == AllNumCases) {
6209 if (
SI->getNumCases() == AllNumCases - 1) {
6210 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6212 if (CondTy->getIntegerBitWidth() > 64 ||
6213 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6217 for (
const auto &Case :
SI->cases())
6218 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6220 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6222 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6232 if (DeadCases.
empty())
6238 assert(CaseI !=
SI->case_default() &&
6239 "Case was not found. Probably mistake in DeadCases forming.");
6241 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6246 std::vector<DominatorTree::UpdateType> Updates;
6247 for (
auto *
Successor : UniqueSuccessors)
6248 if (NumPerSuccessorCases[
Successor] == 0)
6275 int Idx =
PHI.getBasicBlockIndex(BB);
6276 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6278 Value *InValue =
PHI.getIncomingValue(Idx);
6279 if (InValue != CaseValue)
6295 ForwardingNodesMap ForwardingNodes;
6298 for (
const auto &Case :
SI->cases()) {
6300 BasicBlock *CaseDest = Case.getCaseSuccessor();
6319 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6320 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6321 count(Phi.blocks(), SwitchBlock) == 1) {
6322 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6330 ForwardingNodes[Phi].push_back(PhiIdx);
6333 for (
auto &ForwardingNode : ForwardingNodes) {
6334 PHINode *Phi = ForwardingNode.first;
6340 for (
int Index : Indexes)
6341 Phi->setIncomingValue(Index,
SI->getCondition());
6351 if (
C->isThreadDependent())
6353 if (
C->isDLLImportDependent())
6361 if (
C->getType()->isScalableTy())
6372 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6399 if (
A->isAllOnesValue())
6401 if (
A->isNullValue())
6407 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6432 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6434 if (
I.isTerminator()) {
6436 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6439 CaseDest =
I.getSuccessor(0);
6446 for (
auto &
Use :
I.uses()) {
6449 if (
I->getParent() == CaseDest)
6452 if (Phi->getIncomingBlock(
Use) == CaseDest)
6465 *CommonDest = CaseDest;
6467 if (CaseDest != *CommonDest)
6472 int Idx =
PHI.getBasicBlockIndex(Pred);
6485 Res.push_back(std::make_pair(&
PHI, ConstVal));
6488 return Res.
size() > 0;
6494 SwitchCaseResultVectorTy &UniqueResults,
6496 for (
auto &
I : UniqueResults) {
6497 if (
I.first == Result) {
6498 I.second.push_back(CaseVal);
6499 return I.second.size();
6502 UniqueResults.push_back(
6513 SwitchCaseResultVectorTy &UniqueResults,
6518 for (
const auto &
I :
SI->cases()) {
6532 const size_t NumCasesForResult =
6540 if (UniqueResults.size() > MaxUniqueResults)
6556 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6558 return DefaultResult ||
SI->defaultDestUnreachable();
6579 const bool HasBranchWeights =
6582 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6583 ResultVector[1].second.size() == 1) {
6584 ConstantInt *FirstCase = ResultVector[0].second[0];
6585 ConstantInt *SecondCase = ResultVector[1].second[0];
6586 Value *SelectValue = ResultVector[1].first;
6587 if (DefaultResult) {
6588 Value *ValueCompare =
6589 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6590 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6591 DefaultResult,
"switch.select");
6593 SI && HasBranchWeights) {
6600 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6604 Value *ValueCompare =
6605 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6606 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6607 SelectValue,
"switch.select");
6613 size_t FirstCasePos = (Condition !=
nullptr);
6614 size_t SecondCasePos = FirstCasePos + 1;
6615 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6617 {BranchWeights[FirstCasePos],
6618 DefaultCase + BranchWeights[SecondCasePos]},
6625 if (ResultVector.size() == 1 && DefaultResult) {
6627 unsigned CaseCount = CaseValues.
size();
6640 for (
auto *Case : CaseValues) {
6641 if (Case->getValue().slt(MinCaseVal->
getValue()))
6643 AndMask &= Case->getValue();
6653 if (FreeBits ==
Log2_32(CaseCount)) {
6654 Value *
And = Builder.CreateAnd(Condition, AndMask);
6655 Value *Cmp = Builder.CreateICmpEQ(
6658 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6674 for (
auto *Case : CaseValues)
6675 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6681 Condition = Builder.CreateSub(Condition, MinCaseVal);
6682 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6683 Value *Cmp = Builder.CreateICmpEQ(
6686 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6699 if (CaseValues.
size() == 2) {
6700 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6701 "switch.selectcmp.case1");
6702 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6703 "switch.selectcmp.case2");
6704 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6706 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6726 std::vector<DominatorTree::UpdateType> Updates;
6733 Builder.CreateBr(DestBB);
6737 PHI->removeIncomingValueIf(
6738 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6739 PHI->addIncoming(SelectValue, SelectBB);
6742 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6748 if (DTU && RemovedSuccessors.
insert(Succ).second)
6751 SI->eraseFromParent();
6766 SwitchCaseResultVectorTy UniqueResults;
6772 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6773 Builder.SetInsertPoint(
SI);
6776 [[maybe_unused]]
auto HasWeights =
6781 (BranchWeights.
size() >=
6782 UniqueResults.size() + (DefaultResult !=
nullptr)));
6785 Builder,
DL, BranchWeights);
6797class SwitchReplacement {
6804 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6805 Constant *DefaultValue,
const DataLayout &
DL,
6806 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
6815 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6822 bool isLookupTable();
6859 ConstantInt *BitMap =
nullptr;
6860 IntegerType *BitMapElementTy =
nullptr;
6863 ConstantInt *LinearOffset =
nullptr;
6864 ConstantInt *LinearMultiplier =
nullptr;
6865 bool LinearMapValWrapped =
false;
6873SwitchReplacement::SwitchReplacement(
6875 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6876 Constant *DefaultValue,
const DataLayout &
DL,
6877 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
6878 : DefaultValue(DefaultValue) {
6879 assert(Values.size() &&
"Can't build lookup table without values!");
6880 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6883 SingleValue = Values.begin()->second;
6885 ValueType = Values.begin()->second->getType();
6889 for (
const auto &[CaseVal, CaseRes] : Values) {
6892 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6893 TableContents[Idx] = CaseRes;
6900 if (Values.size() < TableSize) {
6902 "Need a default value to fill the lookup table holes.");
6905 if (!TableContents[
I])
6906 TableContents[
I] = DefaultValue;
6912 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6913 SingleValue =
nullptr;
6919 Kind = SingleValueKind;
6926 bool LinearMappingPossible =
true;
6931 bool NonMonotonic =
false;
6932 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6949 LinearMappingPossible =
false;
6954 APInt Dist = Val - PrevVal;
6957 }
else if (Dist != DistToPrev) {
6958 LinearMappingPossible =
false;
6966 if (LinearMappingPossible) {
6968 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6969 APInt M = LinearMultiplier->getValue();
6970 bool MayWrap =
true;
6971 if (
isIntN(M.getBitWidth(), TableSize - 1))
6972 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6973 LinearMapValWrapped = NonMonotonic || MayWrap;
6974 Kind = LinearMapKind;
6980 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6982 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6984 TableInt <<=
IT->getBitWidth();
6988 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6991 BitMap = ConstantInt::get(M.getContext(), TableInt);
6992 BitMapElementTy =
IT;
7003 unsigned NeededBitWidth =
7004 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7017 Kind = LookupTableKind;
7023 case SingleValueKind:
7025 case LinearMapKind: {
7029 false,
"switch.idx.cast");
7030 if (!LinearMultiplier->
isOne())
7031 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7033 !LinearMapValWrapped);
7035 if (!LinearOffset->
isZero())
7038 !LinearMapValWrapped);
7055 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7056 "switch.shiftamt",
true,
true);
7059 Value *DownShifted =
7060 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7062 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7064 case LookupTableKind: {
7067 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7068 true, GlobalVariable::PrivateLinkage,
7069 Initializer,
"switch.table." +
Func->getName());
7070 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7073 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
7074 Type *IndexTy =
DL.getIndexType(Table->getType());
7077 if (
Index->getType() != IndexTy) {
7078 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7082 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7085 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7089 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7098bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7100 Type *ElementType) {
7108 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7110 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7116 if (
TTI.isTypeLegal(Ty))
7131 DL.fitsInLegalInteger(
IT->getBitWidth());
7134Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7136bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7138bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7145 const uint64_t MinDensity = OptSize ? 40 : 10;
7150 return NumCases * 100 >= CaseRange * MinDensity;
7171 if (
SI->getNumCases() > TableSize)
7174 bool AllTablesFitInRegister =
true;
7175 bool HasIllegalType =
false;
7176 for (
const auto &Ty : ResultTypes) {
7181 AllTablesFitInRegister =
7182 AllTablesFitInRegister &&
7183 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7188 if (HasIllegalType && !AllTablesFitInRegister)
7193 if (AllTablesFitInRegister)
7201 SI->getFunction()->hasOptSize());
7211 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7214 return all_of(ResultTypes, [&](
const auto &ResultType) {
7215 return SwitchReplacement::wouldFitInRegister(
7243 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
7265 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7270 for (
auto ValuePair : Values) {
7273 if (!CaseConst || CaseConst == DefaultConst ||
7274 (CaseConst != TrueConst && CaseConst != FalseConst))
7282 BasicBlock *BranchBlock = RangeCheckBranch->getParent();
7288 if (DefaultConst == FalseConst) {
7291 ++NumTableCmpReuses;
7294 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7295 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7296 RangeCheckBranch->getIterator());
7298 ++NumTableCmpReuses;
7308 bool ConvertSwitchToLookupTable) {
7309 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7323 if (
SI->getNumCases() < 3)
7345 MinCaseVal = CaseVal;
7347 MaxCaseVal = CaseVal;
7364 It->second.push_back(std::make_pair(CaseVal,
Value));
7372 bool HasDefaultResults =
7374 DefaultResultsList,
DL,
TTI);
7375 for (
const auto &
I : DefaultResultsList) {
7378 DefaultResults[
PHI] = Result;
7382 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7385 if (UseSwitchConditionAsTableIndex) {
7387 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7392 TableIndexOffset = MinCaseVal;
7399 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7401 bool TableHasHoles = (NumResults < TableSize);
7406 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7414 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7417 if (
SI->getNumCases() < 4)
7419 if (!
DL.fitsInLegalInteger(TableSize))
7428 if (UseSwitchConditionAsTableIndex) {
7429 TableIndex =
SI->getCondition();
7430 if (HasDefaultResults) {
7442 all_of(ResultTypes, [&](
const auto &ResultType) {
7443 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7448 TableSize = std::max(UpperBound, TableSize);
7451 DefaultIsReachable =
false;
7459 const auto &ResultList = ResultLists[
PHI];
7461 Type *ResultType = ResultList.begin()->second->getType();
7466 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7467 ResultList, DefaultVal,
DL,
TTI, FuncName);
7468 PhiToReplacementMap.
insert({
PHI, Replacement});
7471 bool AnyLookupTables =
any_of(
7472 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7473 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7474 [](
auto &KV) {
return KV.second.isBitMap(); });
7482 if (AnyLookupTables &&
7483 (!
TTI.shouldBuildLookupTables() ||
7489 if (!ConvertSwitchToLookupTable &&
7490 (AnyLookupTables || AnyBitMaps || NeedMask))
7493 Builder.SetInsertPoint(
SI);
7496 if (!UseSwitchConditionAsTableIndex) {
7499 bool MayWrap =
true;
7500 if (!DefaultIsReachable) {
7505 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7506 "switch.tableidx",
false,
7510 std::vector<DominatorTree::UpdateType> Updates;
7516 assert(MaxTableSize >= TableSize &&
7517 "It is impossible for a switch to have more entries than the max "
7518 "representable value of its input integer type's size.");
7523 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7528 Builder.SetInsertPoint(
SI);
7529 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7530 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7531 Builder.CreateBr(LookupBB);
7537 Value *Cmp = Builder.CreateICmpULT(
7538 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7540 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7541 CondBranch = RangeCheckBranch;
7547 Builder.SetInsertPoint(LookupBB);
7553 MaskBB->
setName(
"switch.hole_check");
7560 APInt MaskInt(TableSizePowOf2, 0);
7561 APInt One(TableSizePowOf2, 1);
7563 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7564 for (
const auto &Result : ResultList) {
7567 MaskInt |= One << Idx;
7569 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7576 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7577 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7578 Value *LoBit = Builder.CreateTrunc(
7580 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7585 Builder.SetInsertPoint(LookupBB);
7589 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7592 SI->getDefaultDest()->removePredecessor(BB,
7599 const ResultListTy &ResultList = ResultLists[
PHI];
7600 auto Replacement = PhiToReplacementMap.
at(
PHI);
7601 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7604 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7607 for (
auto *
User :
PHI->users()) {
7609 Replacement.getDefaultValue(), ResultList);
7613 PHI->addIncoming(Result, LookupBB);
7616 Builder.CreateBr(CommonDest);
7628 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7631 if (Succ ==
SI->getDefaultDest()) {
7632 if (HasBranchWeights)
7633 ToDefaultWeight += BranchWeights[
I];
7637 if (DTU && RemovedSuccessors.
insert(Succ).second)
7639 if (HasBranchWeights)
7640 ToLookupWeight += BranchWeights[
I];
7642 SI->eraseFromParent();
7643 if (HasBranchWeights)
7650 ++NumLookupTablesHoles;
7666 if (CondTy->getIntegerBitWidth() > 64 ||
7667 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7671 if (
SI->getNumCases() < 4)
7679 for (
const auto &
C :
SI->cases())
7680 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7688 int64_t
Base = Values[0];
7689 for (
auto &V : Values)
7702 unsigned Shift = 64;
7703 for (
auto &V : Values)
7707 for (
auto &V : Values)
7708 V = (int64_t)((
uint64_t)V >> Shift);
7725 Builder.SetInsertPoint(
SI);
7728 Value *Rot = Builder.CreateIntrinsic(
7729 Ty, Intrinsic::fshl,
7730 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7731 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7733 for (
auto Case :
SI->cases()) {
7734 auto *Orig = Case.getCaseValue();
7735 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7780 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
7781 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
7797 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
7800 return !Updates.
empty();
7830 Value *Condition =
SI->getCondition();
7834 if (CondTy->getIntegerBitWidth() > 64 ||
7835 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7847 if (
SI->getNumCases() < 4)
7852 for (
const auto &Case :
SI->cases()) {
7853 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7865 SI->getFunction()->hasOptSize()))
7869 Builder.SetInsertPoint(
SI);
7871 if (!
SI->defaultDestUnreachable()) {
7874 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
7875 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
7877 auto *OrigBB =
SI->getParent();
7878 auto *DefaultCaseBB =
SI->getDefaultDest();
7880 auto It = OrigBB->getTerminator()->getIterator();
7893 NewWeights[1] = Weights[0] / 2;
7894 NewWeights[0] = OrigDenominator - NewWeights[1];
7906 Weights[0] = NewWeights[1];
7907 uint64_t CasesDenominator = OrigDenominator - Weights[0];
7909 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
7914 BI->setDebugLoc(
SI->getDebugLoc());
7915 It->eraseFromParent();
7923 for (
auto &Case :
SI->cases()) {
7924 auto *OrigValue = Case.getCaseValue();
7925 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7926 OrigValue->getValue().countr_zero()));
7930 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7933 SI->setCondition(ConditionTrailingZeros);
7943 if (!Cmp || !Cmp->hasOneUse())
7954 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7957 if (
SI->getNumCases() == 2) {
7964 Succ =
SI->getDefaultDest();
7965 SuccWeight = Weights[0];
7967 for (
auto &Case :
SI->cases()) {
7968 std::optional<int64_t> Val =
7972 if (!Missing.erase(*Val))
7977 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7980 assert(Missing.size() == 1 &&
"Should have one case left");
7981 Res = *Missing.begin();
7982 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7984 Unreachable =
SI->getDefaultDest();
7986 for (
auto &Case :
SI->cases()) {
7987 BasicBlock *NewSucc = Case.getCaseSuccessor();
7988 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7991 OtherSuccWeight += Weight;
7994 SuccWeight = Weight;
7995 }
else if (Succ == NewSucc) {
8001 for (
auto &Case :
SI->cases()) {
8002 std::optional<int64_t> Val =
8004 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8006 if (Case.getCaseSuccessor() == Succ) {
8028 if (Cmp->isSigned())
8031 MDNode *NewWeights =
nullptr;
8037 Builder.SetInsertPoint(
SI->getIterator());
8038 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
8039 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8040 SI->getMetadata(LLVMContext::MD_unpredictable));
8044 SI->eraseFromParent();
8045 Cmp->eraseFromParent();
8046 if (DTU && Unreachable)
8071 assert(
BB &&
"Expected non-null BB");
8073 if (
BB->isEntryBlock())
8086 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8091 if (&
BB->front() != &
BB->back())
8106 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8117 return (*EBW->PhiPredIVs)[&Phi][BB];
8139 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8142 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8143 return PredIVs[
A] == PredIVs[
B];
8152 if (Candidates.
size() < 2)
8167 assert(Succ &&
"Expected unconditional BB");
8177 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8180 for (
auto &
IV : Phi->incoming_values())
8181 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8199 bool MadeChange =
false;
8213 if (!LivePreds.
contains(PredOfDead))
8220 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8221 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8226 T->replaceSuccessorWith(
Dead, Live);
8231 for (
const auto &EBW : BBs2Merge) {
8234 const auto &[It, Inserted] =
Keep.insert(&EBW);
8243 if (KeepBB == DeadBB)
8247 RedirectIncomingEdges(DeadBB, KeepBB);
8256 if (DTU && !Updates.
empty())
8262bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8263 DomTreeUpdater *DTU) {
8265 SmallSetVector<BasicBlock *, 16> FilteredArms(
8271bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8272 DomTreeUpdater *DTU) {
8283 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8289bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8292 if (isValueEqualityComparison(SI)) {
8296 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8297 return requestResimplify();
8301 if (simplifySwitchOnSelect(SI,
Select))
8302 return requestResimplify();
8306 if (SI == &*BB->
begin())
8307 if (foldValueComparisonIntoPredecessors(SI, Builder))
8308 return requestResimplify();
8314 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8315 return requestResimplify();
8319 return requestResimplify();
8322 return requestResimplify();
8325 return requestResimplify();
8328 return requestResimplify();
8333 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8335 Options.ConvertSwitchToLookupTable))
8336 return requestResimplify();
8339 return requestResimplify();
8342 return requestResimplify();
8345 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8346 return requestResimplify();
8350 if (simplifyDuplicateSwitchArms(SI, DTU))
8351 return requestResimplify();
8354 return requestResimplify();
8359bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8362 SmallVector<uint32_t> BranchWeights;
8366 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8367 if (HasBranchWeights)
8372 SmallPtrSet<Value *, 8> Succs;
8373 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8378 RemovedSuccs.
insert(Dest);
8388 std::vector<DominatorTree::UpdateType> Updates;
8389 Updates.reserve(RemovedSuccs.
size());
8390 for (
auto *RemovedSucc : RemovedSuccs)
8391 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8408 if (HasBranchWeights) {
8415 if (simplifyIndirectBrOnSelect(IBI, SI))
8416 return requestResimplify();
8452 if (BB == OtherPred)
8460 if (!BI2 || !BI2->isIdenticalTo(BI))
8463 std::vector<DominatorTree::UpdateType> Updates;
8470 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8471 "unexpected successor");
8472 II->setUnwindDest(OtherPred);
8487 Builder.CreateUnreachable();
8488 BI->eraseFromParent();
8496bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8508 bool NeedCanonicalLoop =
8522 if (
I->isTerminator() &&
8523 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8547 if (!PPred || (PredPred && PredPred != PPred))
8588 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8592 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8618 bool HasWeight =
false;
8623 BBTWeight = BBFWeight = 1;
8628 BB1TWeight = BB1FWeight = 1;
8633 BB2TWeight = BB2FWeight = 1;
8635 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8636 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8643bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
8647 "Tautological conditional branch should have been eliminated already.");
8650 if (!
Options.SimplifyCondBranch ||
8651 BI->getFunction()->hasFnAttribute(Attribute::OptForFuzzing))
8655 if (isValueEqualityComparison(BI)) {
8660 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8661 return requestResimplify();
8665 for (
auto &
I : *BB) {
8670 if (foldValueComparisonIntoPredecessors(BI, Builder))
8671 return requestResimplify();
8677 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8690 return requestResimplify();
8696 if (
Options.SpeculateBlocks &&
8699 return requestResimplify();
8708 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8709 return requestResimplify();
8711 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8713 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8714 auto CanSpeculateConditionalLoadsStores = [&]() {
8716 for (Instruction &
I : *Succ) {
8717 if (
I.isTerminator()) {
8718 if (
I.getNumSuccessors() > 1)
8722 SpeculatedConditionalLoadsStores.
size() ==
8726 SpeculatedConditionalLoadsStores.
push_back(&
I);
8729 return !SpeculatedConditionalLoadsStores.
empty();
8732 if (CanSpeculateConditionalLoadsStores()) {
8734 std::nullopt,
nullptr);
8735 return requestResimplify();
8745 return requestResimplify();
8754 return requestResimplify();
8760 if (foldCondBranchOnValueKnownInPredecessor(BI))
8761 return requestResimplify();
8768 return requestResimplify();
8776 return requestResimplify();
8780 return requestResimplify();
8787 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8799 auto *Use = cast<Instruction>(U.getUser());
8802 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
8805 switch (Use->getOpcode()) {
8808 case Instruction::GetElementPtr:
8809 case Instruction::Ret:
8810 case Instruction::BitCast:
8811 case Instruction::Load:
8812 case Instruction::Store:
8813 case Instruction::Call:
8814 case Instruction::CallBr:
8815 case Instruction::Invoke:
8816 case Instruction::UDiv:
8817 case Instruction::URem:
8821 case Instruction::SDiv:
8822 case Instruction::SRem:
8826 if (FindUse ==
I->use_end())
8828 auto &
Use = *FindUse;
8842 if (
GEP->getPointerOperand() ==
I) {
8845 if (
GEP->getType()->isVectorTy())
8853 if (!
GEP->hasAllZeroIndices() &&
8854 (!
GEP->isInBounds() ||
8856 GEP->getPointerAddressSpace())))
8857 PtrValueMayBeModified =
true;
8863 bool HasNoUndefAttr =
8864 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8869 if (
C->isNullValue() && HasNoUndefAttr &&
8870 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8871 return !PtrValueMayBeModified;
8877 if (!LI->isVolatile())
8879 LI->getPointerAddressSpace());
8883 if (!
SI->isVolatile())
8885 SI->getPointerAddressSpace())) &&
8886 SI->getPointerOperand() ==
I;
8891 if (
I == Assume->getArgOperand(0))
8899 if (CB->getCalledOperand() ==
I)
8902 if (CB->isArgOperand(&
Use)) {
8903 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8906 CB->paramHasNonNullAttr(ArgIdx,
false))
8907 return !PtrValueMayBeModified;
8926 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8934 Builder.CreateUnreachable();
8935 T->eraseFromParent();
8946 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8948 Assumption = Builder.CreateAssumption(
Cond);
8953 BI->eraseFromParent();
8962 Builder.SetInsertPoint(Unreachable);
8964 Builder.CreateUnreachable();
8965 for (
const auto &Case :
SI->cases())
8966 if (Case.getCaseSuccessor() == BB) {
8968 Case.setSuccessor(Unreachable);
8970 if (
SI->getDefaultDest() == BB) {
8972 SI->setDefaultDest(Unreachable);
8986bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9011 return requestResimplify();
9030 if (simplifyDuplicatePredecessors(BB, DTU))
9034 if (
Options.SpeculateBlocks &&
9041 Options.SpeculateUnpredictables))
9049 case Instruction::UncondBr:
9052 case Instruction::CondBr:
9055 case Instruction::Resume:
9058 case Instruction::CleanupRet:
9061 case Instruction::Switch:
9064 case Instruction::Unreachable:
9067 case Instruction::IndirectBr:
9075bool SimplifyCFGOpt::run(BasicBlock *BB) {
9085 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static bool IsIndirectCall(const MachineInstr *MI)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
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
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 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)
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 intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
Get the last element.
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...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI 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)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
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.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
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
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
FunctionAddr VTableAddr Value
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"))
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
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.
FunctionAddr VTableAddr Count
auto succ_size(const MachineBasicBlock *BB)
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
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.
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.
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...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
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...
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.