97#define DEBUG_TYPE "simplifycfg"
102 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
105 "Temporary development switch used to gradually uplift SimplifyCFG "
106 "into preserving DomTree,"));
115 "Control the amount of phi node folding to perform (default = 2)"));
119 cl::desc(
"Control the maximal total instruction cost that we are willing "
120 "to speculatively execute to fold a 2-entry PHI node into a "
121 "select (default = 4)"));
125 cl::desc(
"Hoist common instructions up to the parent block"));
129 cl::desc(
"Hoist loads if the target supports conditional faulting"));
133 cl::desc(
"Hoist stores if the target supports conditional faulting"));
137 cl::desc(
"Control the maximal conditional load/store that we are willing "
138 "to speculatively execute to eliminate conditional branch "
144 cl::desc(
"Allow reordering across at most this many "
145 "instructions when hoisting"));
149 cl::desc(
"Sink common instructions down to the end block"));
153 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
157 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
158 "precede - hoist multiple conditional stores into a single "
159 "predicated store"));
163 cl::desc(
"When merging conditional stores, do so even if the resultant "
164 "basic blocks are unlikely to be if-converted as a result"));
168 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
173 cl::desc(
"Limit maximum recursion depth when calculating costs of "
174 "speculatively executed instructions"));
179 cl::desc(
"Max size of a block which is still considered "
180 "small enough to thread through"));
186 cl::desc(
"Maximum cost of combining conditions when "
187 "folding branches"));
190 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
192 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
193 "to fold branch to common destination when vector operations are "
198 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
202 cl::desc(
"Limit cases to analyze when converting a switch to select"));
206 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
213STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
215 "Number of switch instructions turned into linear mapping");
217 "Number of switch instructions turned into lookup tables");
219 NumLookupTablesHoles,
220 "Number of switch instructions turned into lookup tables (holes checked)");
221STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
223 "Number of value comparisons folded into predecessor basic blocks");
225 "Number of branches folded into predecessor basic block");
228 "Number of common instruction 'blocks' hoisted up to the begin block");
230 "Number of common instructions hoisted up to the begin block");
232 "Number of common instruction 'blocks' sunk down to the end block");
234 "Number of common instructions sunk down to the end block");
235STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
237 "Number of invokes with empty resume blocks simplified into calls");
238STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
239STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
246using SwitchCaseResultVectorTy =
255struct ValueEqualityComparisonCase {
267 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
270class SimplifyCFGOpt {
271 const TargetTransformInfo &TTI;
273 const DataLayout &DL;
275 const SimplifyCFGOptions &Options;
278 Value *isValueEqualityComparison(Instruction *TI);
280 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
281 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
284 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
287 bool foldValueComparisonIntoPredecessors(Instruction *TI,
290 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
291 bool simplifySingleResume(ResumeInst *RI);
292 bool simplifyCommonResume(ResumeInst *RI);
293 bool simplifyCleanupReturn(CleanupReturnInst *RI);
294 bool simplifyUnreachable(UnreachableInst *UI);
295 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
296 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
297 bool simplifyIndirectBr(IndirectBrInst *IBI);
298 bool simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder);
299 bool simplifyUncondBranch(BranchInst *BI,
IRBuilder<> &Builder);
300 bool simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder);
301 bool foldCondBranchOnValueKnownInPredecessor(BranchInst *BI);
303 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
306 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
307 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
308 Instruction *TI, Instruction *I1,
309 SmallVectorImpl<Instruction *> &OtherSuccTIs);
310 bool speculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
311 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
312 BasicBlock *TrueBB, BasicBlock *FalseBB,
313 uint32_t TrueWeight, uint32_t FalseWeight);
314 bool simplifyBranchOnICmpChain(BranchInst *BI,
IRBuilder<> &Builder,
315 const DataLayout &DL);
316 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
317 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
318 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
321 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
323 const SimplifyCFGOptions &Opts)
324 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
325 assert((!DTU || !DTU->hasPostDomTree()) &&
326 "SimplifyCFG is not yet capable of maintaining validity of a "
327 "PostDomTree, so don't ask for it.");
330 bool simplifyOnce(BasicBlock *BB);
331 bool run(BasicBlock *BB);
334 bool requestResimplify() {
344isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
364 "Only for a pair of incoming blocks at the time!");
370 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
371 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
374 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
375 EquivalenceSet->contains(IV1))
398 if (!SI1Succs.
count(Succ))
404 FailBlocks->insert(Succ);
420 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
422 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
423 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
485 if (AggressiveInsts.
count(
I))
501 ZeroCostInstructions.
insert(OverflowInst);
503 }
else if (!ZeroCostInstructions.
contains(
I))
519 for (
Use &
Op :
I->operands())
521 TTI, AC, ZeroCostInstructions,
Depth + 1))
538 if (
DL.hasUnstableRepresentation(V->getType()))
547 return ConstantInt::get(IntPtrTy, 0);
552 if (CE->getOpcode() == Instruction::IntToPtr)
576struct ConstantComparesGatherer {
577 const DataLayout &DL;
580 Value *CompValue =
nullptr;
583 Value *Extra =
nullptr;
589 unsigned UsedICmps = 0;
595 bool IgnoreFirstMatch =
false;
596 bool MultipleMatches =
false;
599 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
601 if (CompValue || !MultipleMatches)
606 IgnoreFirstMatch =
true;
610 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
611 ConstantComparesGatherer &
612 operator=(
const ConstantComparesGatherer &) =
delete;
617 bool setValueOnce(
Value *NewVal) {
618 if (IgnoreFirstMatch) {
619 IgnoreFirstMatch =
false;
622 if (CompValue && CompValue != NewVal) {
623 MultipleMatches =
true;
637 bool matchInstruction(Instruction *
I,
bool isEQ) {
644 if (!setValueOnce(Val))
664 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
708 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
710 if (!setValueOnce(RHSVal))
715 ConstantInt::get(
C->getContext(),
716 C->getValue() | Mask));
731 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
733 if (!setValueOnce(RHSVal))
737 Vals.push_back(ConstantInt::get(
C->getContext(),
738 C->getValue() & ~Mask));
759 Value *CandidateVal =
I->getOperand(0);
762 CandidateVal = RHSVal;
777 if (!setValueOnce(CandidateVal))
782 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
793 void gather(
Value *V) {
802 SmallVector<Value *, 8> DFT{Op0, Op1};
803 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
805 while (!DFT.
empty()) {
812 if (Visited.
insert(Op1).second)
814 if (Visited.
insert(Op0).second)
821 if (matchInstruction(
I, IsEq))
848 if (BI->isConditional())
866 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
867 CV =
SI->getCondition();
869 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
874 if (Trunc->hasNoUnsignedWrap())
875 CV = Trunc->getOperand(0);
882 Value *
Ptr = PTII->getPointerOperand();
883 if (
DL.hasUnstableRepresentation(
Ptr->getType()))
885 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
894BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
895 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
897 Cases.reserve(
SI->getNumCases());
898 for (
auto Case :
SI->cases())
899 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
900 Case.getCaseSuccessor()));
901 return SI->getDefaultDest();
906 ICmpInst::Predicate Pred;
912 Pred = ICmpInst::ICMP_NE;
917 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
925 std::vector<ValueEqualityComparisonCase> &Cases) {
931 std::vector<ValueEqualityComparisonCase> &C2) {
932 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
935 if (V1->size() > V2->size())
940 if (V1->size() == 1) {
943 for (
const ValueEqualityComparisonCase &
VECC : *V2)
944 if (TheVal ==
VECC.Value)
951 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
952 while (i1 != e1 && i2 != e2) {
968bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
969 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
974 Value *ThisVal = isValueEqualityComparison(TI);
975 assert(ThisVal &&
"This isn't a value comparison!!");
976 if (ThisVal != PredVal)
983 std::vector<ValueEqualityComparisonCase> PredCases;
985 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
989 std::vector<ValueEqualityComparisonCase> ThisCases;
990 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1005 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1011 ThisCases[0].Dest->removePredecessor(PredDef);
1014 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1021 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1028 SmallPtrSet<Constant *, 16> DeadCases;
1029 for (
const ValueEqualityComparisonCase &Case : PredCases)
1030 DeadCases.
insert(Case.Value);
1033 <<
"Through successor TI: " << *TI);
1035 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1038 auto *
Successor = i->getCaseSuccessor();
1041 if (DeadCases.
count(i->getCaseValue())) {
1050 std::vector<DominatorTree::UpdateType> Updates;
1051 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1053 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1063 ConstantInt *TIV =
nullptr;
1065 for (
const auto &[
Value, Dest] : PredCases)
1071 assert(TIV &&
"No edge from pred to succ?");
1076 for (
const auto &[
Value, Dest] : ThisCases)
1084 TheRealDest = ThisDef;
1086 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1091 if (Succ != CheckEdge) {
1092 if (Succ != TheRealDest)
1093 RemovedSuccs.
insert(Succ);
1096 CheckEdge =
nullptr;
1103 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1108 SmallVector<DominatorTree::UpdateType, 2> Updates;
1110 for (
auto *RemovedSucc : RemovedSuccs)
1111 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1122struct ConstantIntOrdering {
1123 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1124 return LHS->getValue().ult(
RHS->getValue());
1136 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1145 assert(MD &&
"Invalid branch-weight metadata");
1170 if (BonusInst.isTerminator())
1200 NewBonusInst->
takeName(&BonusInst);
1201 BonusInst.setName(NewBonusInst->
getName() +
".old");
1202 VMap[&BonusInst] = NewBonusInst;
1211 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1212 "If the user is not a PHI node, then it should be in the same "
1213 "block as, and come after, the original bonus instruction.");
1217 if (PN->getIncomingBlock(U) == BB)
1221 assert(PN->getIncomingBlock(U) == PredBlock &&
1222 "Not in block-closed SSA form?");
1223 U.set(NewBonusInst);
1233 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1234 PredDL.isSameSourceLocation(
DL)) {
1241bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1249 std::vector<ValueEqualityComparisonCase> BBCases;
1250 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1252 std::vector<ValueEqualityComparisonCase> PredCases;
1253 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1258 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1261 SmallVector<uint64_t, 8> Weights;
1265 if (PredHasWeights) {
1268 if (Weights.
size() != 1 + PredCases.size())
1269 PredHasWeights = SuccHasWeights =
false;
1270 }
else if (SuccHasWeights)
1274 Weights.
assign(1 + PredCases.size(), 1);
1276 SmallVector<uint64_t, 8> SuccWeights;
1277 if (SuccHasWeights) {
1280 if (SuccWeights.
size() != 1 + BBCases.size())
1281 PredHasWeights = SuccHasWeights =
false;
1282 }
else if (PredHasWeights)
1283 SuccWeights.
assign(1 + BBCases.size(), 1);
1285 if (PredDefault == BB) {
1288 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1289 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1290 if (PredCases[i].Dest != BB)
1291 PTIHandled.insert(PredCases[i].
Value);
1294 std::swap(PredCases[i], PredCases.back());
1296 if (PredHasWeights || SuccHasWeights) {
1298 Weights[0] += Weights[i + 1];
1303 PredCases.pop_back();
1309 if (PredDefault != BBDefault) {
1311 if (DTU && PredDefault != BB)
1312 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1313 PredDefault = BBDefault;
1314 ++NewSuccessors[BBDefault];
1317 unsigned CasesFromPred = Weights.
size();
1318 uint64_t ValidTotalSuccWeight = 0;
1319 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1320 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1321 PredCases.push_back(BBCases[i]);
1322 ++NewSuccessors[BBCases[i].Dest];
1323 if (SuccHasWeights || PredHasWeights) {
1327 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1328 ValidTotalSuccWeight += SuccWeights[i + 1];
1332 if (SuccHasWeights || PredHasWeights) {
1333 ValidTotalSuccWeight += SuccWeights[0];
1335 for (
unsigned i = 1; i < CasesFromPred; ++i)
1336 Weights[i] *= ValidTotalSuccWeight;
1338 Weights[0] *= SuccWeights[0];
1344 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1345 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1346 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1347 if (PredCases[i].Dest == BB) {
1348 PTIHandled.insert(PredCases[i].
Value);
1350 if (PredHasWeights || SuccHasWeights) {
1351 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1356 std::swap(PredCases[i], PredCases.back());
1357 PredCases.pop_back();
1364 for (
const ValueEqualityComparisonCase &Case : BBCases)
1365 if (PTIHandled.count(Case.Value)) {
1367 if (PredHasWeights || SuccHasWeights)
1368 Weights.
push_back(WeightsForHandled[Case.Value]);
1369 PredCases.push_back(Case);
1370 ++NewSuccessors[Case.Dest];
1371 PTIHandled.erase(Case.Value);
1376 for (ConstantInt *
I : PTIHandled) {
1377 if (PredHasWeights || SuccHasWeights)
1379 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1380 ++NewSuccessors[BBDefault];
1387 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1392 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1394 for (
auto I :
seq(NewSuccessor.second)) {
1398 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1399 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1406 "Should not end up here with unstable pointers");
1412 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1414 for (ValueEqualityComparisonCase &V : PredCases)
1417 if (PredHasWeights || SuccHasWeights)
1429 if (!InfLoopBlock) {
1437 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1444 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1446 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1451 ++NumFoldValueComparisonIntoPredecessors;
1459bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1462 Value *CV = isValueEqualityComparison(TI);
1463 assert(CV &&
"Not a comparison?");
1468 while (!Preds.empty()) {
1477 Value *PCV = isValueEqualityComparison(PTI);
1481 SmallSetVector<BasicBlock *, 4> FailBlocks;
1483 for (
auto *Succ : FailBlocks) {
1489 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1503 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1504 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1505 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1524 if (
I->mayReadFromMemory())
1556 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1564 if (J->getParent() == BB)
1586 if (C1->isMustTailCall() != C2->isMustTailCall())
1589 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1595 if (CB1->cannotMerge() || CB1->isConvergent())
1598 if (CB2->cannotMerge() || CB2->isConvergent())
1613 if (!I1->hasDbgRecords())
1615 using CurrentAndEndIt =
1616 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1622 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1623 return Pair.first == Pair.second;
1629 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1635 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1637 if (!
Other->hasDbgRecords())
1640 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1647 while (
none_of(Itrs, atEnd)) {
1648 bool HoistDVRs = allIdentical(Itrs);
1649 for (CurrentAndEndIt &Pair : Itrs) {
1663 if (I1->isIdenticalToWhenDefined(I2,
true))
1668 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1669 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1670 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1672 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1673 return I1->getOperand(0) == I2->
getOperand(1) &&
1739 auto &Context = BI->
getParent()->getContext();
1744 Value *Mask =
nullptr;
1745 Value *MaskFalse =
nullptr;
1746 Value *MaskTrue =
nullptr;
1747 if (Invert.has_value()) {
1748 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1749 Mask = Builder.CreateBitCast(
1754 MaskFalse = Builder.CreateBitCast(
1756 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1758 auto PeekThroughBitcasts = [](
Value *V) {
1760 V = BitCast->getOperand(0);
1763 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1765 if (!Invert.has_value())
1766 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1771 auto *Op0 =
I->getOperand(0);
1772 CallInst *MaskedLoadStore =
nullptr;
1775 auto *Ty =
I->getType();
1777 Value *PassThru =
nullptr;
1778 if (Invert.has_value())
1779 for (
User *U :
I->users()) {
1781 PassThru = Builder.CreateBitCast(
1785 Sel && Ins->getParent() == BB) {
1790 Builder.SetInsertPoint(Ins);
1793 MaskedLoadStore = Builder.CreateMaskedLoad(
1795 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1798 I->replaceAllUsesWith(NewLoadStore);
1801 auto *StoredVal = Builder.CreateBitCast(
1803 MaskedLoadStore = Builder.CreateMaskedStore(
1814 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1816 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1820 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1821 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1824 I->eraseFromParent();
1831 bool IsStore =
false;
1854bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1855 bool AllInstsEqOnly) {
1884 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1890 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1893 if (AllInstsEqOnly) {
1899 bool AllSame =
none_of(Succs, [&Succs](BasicBlock *Succ) {
1902 return !
Term->isSameOperationAs(Term0) ||
1909 LockstepReverseIterator<true> LRI(Succs);
1910 while (LRI.isValid()) {
1912 if (
any_of(*LRI, [I0](Instruction *
I) {
1927 unsigned NumSkipped = 0;
1930 if (SuccIterPairs.
size() > 2) {
1933 if (SuccIterPairs.
size() < 2)
1940 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1941 auto &BB1ItrPair = *SuccIterPairBegin++;
1942 auto OtherSuccIterPairRange =
1948 bool AllInstsAreIdentical =
true;
1949 bool HasTerminator =
I1->isTerminator();
1950 for (
auto &SuccIter : OtherSuccIterRange) {
1954 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1955 AllInstsAreIdentical =
false;
1958 SmallVector<Instruction *, 8> OtherInsts;
1959 for (
auto &SuccIter : OtherSuccIterRange)
1964 if (HasTerminator) {
1968 if (NumSkipped || !AllInstsAreIdentical) {
1973 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1977 if (AllInstsAreIdentical) {
1978 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1979 AllInstsAreIdentical =
1981 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1983 unsigned SkipFlagsBB2 = Pair.second;
1993 if (AllInstsAreIdentical) {
2003 for (
auto &SuccIter : OtherSuccIterRange) {
2011 assert(
Success &&
"We should not be trying to hoist callbases "
2012 "with non-intersectable attributes");
2024 NumHoistCommonCode += SuccIterPairs.
size();
2026 NumHoistCommonInstrs += SuccIterPairs.
size();
2035 for (
auto &SuccIterPair : SuccIterPairs) {
2044bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2045 Instruction *TI, Instruction *I1,
2046 SmallVectorImpl<Instruction *> &OtherSuccTIs) {
2055 auto *I2 = *OtherSuccTIs.
begin();
2075 for (PHINode &PN : Succ->
phis()) {
2076 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2077 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2078 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2098 if (!
NT->getType()->isVoidTy()) {
2099 I1->replaceAllUsesWith(NT);
2100 for (Instruction *OtherSuccTI : OtherSuccTIs)
2101 OtherSuccTI->replaceAllUsesWith(NT);
2105 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2111 for (
auto *OtherSuccTI : OtherSuccTIs)
2112 Locs.
push_back(OtherSuccTI->getDebugLoc());
2124 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2126 for (PHINode &PN : Succ->
phis()) {
2127 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2128 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2134 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2144 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2145 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2146 PN.setIncomingValue(i, SI);
2157 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2162 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2175 if (
I->isIntDivRem())
2190 std::optional<unsigned> NumUses;
2191 for (
auto *
I : Insts) {
2194 I->getType()->isTokenTy())
2199 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2207 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2211 NumUses =
I->getNumUses();
2212 else if (NumUses !=
I->getNumUses())
2218 for (
auto *
I : Insts) {
2232 for (
const Use &U : I0->
uses()) {
2233 auto It = PHIOperands.find(&U);
2234 if (It == PHIOperands.end())
2237 if (!
equal(Insts, It->second))
2249 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2250 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2251 if (HaveIndirectCalls) {
2252 if (!AllCallsAreIndirect)
2256 Value *Callee =
nullptr;
2260 Callee = CurrCallee;
2261 else if (Callee != CurrCallee)
2267 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2273 if (!
all_of(Insts, SameAsI0)) {
2279 for (
auto *
I : Insts)
2280 Ops.push_back(
I->getOperand(OI));
2290 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2295 for (
auto *BB : Blocks) {
2297 I =
I->getPrevNode();
2322 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2325 PN->insertBefore(BBEnd->begin());
2326 for (
auto *
I : Insts)
2327 PN->addIncoming(
I->getOperand(O),
I->getParent());
2336 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2339 for (
auto *
I : Insts)
2353 assert(
Success &&
"We should not be trying to sink callbases "
2354 "with non-intersectable attributes");
2365 PN->replaceAllUsesWith(I0);
2366 PN->eraseFromParent();
2370 for (
auto *
I : Insts) {
2375 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2376 I->replaceAllUsesWith(I0);
2377 I->eraseFromParent();
2427 bool HaveNonUnconditionalPredecessors =
false;
2430 if (PredBr && PredBr->isUnconditional())
2433 HaveNonUnconditionalPredecessors =
true;
2435 if (UnconditionalPreds.
size() < 2)
2448 for (
const Use &U : PN.incoming_values())
2449 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2450 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2452 Ops.push_back(*IncomingVals[Pred]);
2460 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2473 if (!followedByDeoptOrUnreachable) {
2475 auto IsMemOperand = [](
Use &U) {
2488 unsigned NumPHIInsts = 0;
2489 for (
Use &U : (*LRI)[0]->operands()) {
2490 auto It = PHIOperands.
find(&U);
2491 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2492 return InstructionsToSink.contains(V);
2499 if (IsMemOperand(U) &&
2500 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2507 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2508 return NumPHIInsts <= 1;
2525 while (Idx < ScanIdx) {
2526 if (!ProfitableToSinkInstruction(LRI)) {
2529 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2542 if (Idx < ScanIdx) {
2545 InstructionsToSink = InstructionsProfitableToSink;
2551 !ProfitableToSinkInstruction(LRI) &&
2552 "We already know that the last instruction is unprofitable to sink");
2560 for (
auto *
I : *LRI)
2561 InstructionsProfitableToSink.
erase(
I);
2562 if (!ProfitableToSinkInstruction(LRI)) {
2565 InstructionsToSink = InstructionsProfitableToSink;
2579 if (HaveNonUnconditionalPredecessors) {
2580 if (!followedByDeoptOrUnreachable) {
2588 bool Profitable =
false;
2589 while (Idx < ScanIdx) {
2623 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2625 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2633 NumSinkCommonInstrs++;
2637 ++NumSinkCommonCode;
2643struct CompatibleSets {
2644 using SetTy = SmallVector<InvokeInst *, 2>;
2650 SetTy &getCompatibleSet(InvokeInst *
II);
2652 void insert(InvokeInst *
II);
2655CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2660 for (CompatibleSets::SetTy &Set : Sets) {
2661 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2666 return Sets.emplace_back();
2669void CompatibleSets::insert(InvokeInst *
II) {
2670 getCompatibleSet(
II).emplace_back(
II);
2674 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2677 auto IsIllegalToMerge = [](InvokeInst *
II) {
2678 return II->cannotMerge() ||
II->isInlineAsm();
2680 if (
any_of(Invokes, IsIllegalToMerge))
2685 auto IsIndirectCall = [](InvokeInst *
II) {
return II->isIndirectCall(); };
2686 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2687 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2688 if (HaveIndirectCalls) {
2689 if (!AllCallsAreIndirect)
2694 for (InvokeInst *
II : Invokes) {
2695 Value *CurrCallee =
II->getCalledOperand();
2696 assert(CurrCallee &&
"There is always a called operand.");
2699 else if (Callee != CurrCallee)
2706 auto HasNormalDest = [](InvokeInst *
II) {
2709 if (
any_of(Invokes, HasNormalDest)) {
2712 if (!
all_of(Invokes, HasNormalDest))
2717 for (InvokeInst *
II : Invokes) {
2719 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2721 NormalBB = CurrNormalBB;
2722 else if (NormalBB != CurrNormalBB)
2730 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2739 for (InvokeInst *
II : Invokes) {
2741 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2743 UnwindBB = CurrUnwindBB;
2745 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2752 Invokes.front()->getUnwindDest(),
2753 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2758 const InvokeInst *II0 = Invokes.front();
2759 for (
auto *
II : Invokes.drop_front())
2764 auto IsIllegalToMergeArguments = [](
auto Ops) {
2765 Use &U0 = std::get<0>(
Ops);
2766 Use &U1 = std::get<1>(
Ops);
2772 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2773 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2774 IsIllegalToMergeArguments))
2786 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2792 bool HasNormalDest =
2797 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2801 II0->
getParent()->getIterator()->getNextNode();
2806 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2810 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2812 if (!HasNormalDest) {
2816 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2824 return MergedInvoke;
2838 SuccBBOfMergedInvoke});
2848 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2854 if (!IsIndirectCall)
2861 return II->getOperand(U.getOperandNo()) != U.get();
2880 Invokes.
front()->getParent());
2888 if (!MergedDebugLoc)
2889 MergedDebugLoc =
II->getDebugLoc();
2897 OrigSuccBB->removePredecessor(
II->getParent());
2903 assert(
Success &&
"Merged invokes with incompatible attributes");
2906 II->replaceAllUsesWith(MergedInvoke);
2907 II->eraseFromParent();
2911 ++NumInvokeSetsFormed;
2947 CompatibleSets Grouper;
2957 if (Invokes.
size() < 2)
2969class EphemeralValueTracker {
2970 SmallPtrSet<const Instruction *, 32> EphValues;
2972 bool isEphemeral(
const Instruction *
I) {
2975 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2976 all_of(
I->users(), [&](
const User *U) {
2977 return EphValues.count(cast<Instruction>(U));
2982 bool track(
const Instruction *
I) {
2983 if (isEphemeral(
I)) {
3034 unsigned MaxNumInstToLookAt = 9;
3038 if (!MaxNumInstToLookAt)
3040 --MaxNumInstToLookAt;
3050 if (
SI->getPointerOperand() == StorePtr &&
3051 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3054 return SI->getValueOperand();
3059 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3060 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3062 bool ExplicitlyDereferenceableOnly;
3067 (!ExplicitlyDereferenceableOnly ||
3069 LI->getDataLayout()))) {
3085 unsigned &SpeculatedInstructions,
3093 bool HaveRewritablePHIs =
false;
3095 Value *OrigV = PN.getIncomingValueForBlock(BB);
3096 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3103 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3112 HaveRewritablePHIs =
true;
3115 if (!OrigCE && !ThenCE)
3122 if (OrigCost + ThenCost > MaxCost)
3129 ++SpeculatedInstructions;
3130 if (SpeculatedInstructions > 1)
3134 return HaveRewritablePHIs;
3138 std::optional<bool> Invert,
3142 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3149 if (!Invert.has_value())
3152 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3156 return BIEndProb < Likely;
3196bool SimplifyCFGOpt::speculativelyExecuteBB(BranchInst *BI,
3197 BasicBlock *ThenBB) {
3213 bool Invert =
false;
3228 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3230 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3232 unsigned SpeculatedInstructions = 0;
3233 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3234 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3235 Value *SpeculatedStoreValue =
nullptr;
3236 StoreInst *SpeculatedStore =
nullptr;
3237 EphemeralValueTracker EphTracker;
3252 if (EphTracker.track(&
I))
3257 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3259 SpeculatedConditionalLoadsStores.
size() <
3263 if (IsSafeCheapLoadStore)
3264 SpeculatedConditionalLoadsStores.
push_back(&
I);
3266 ++SpeculatedInstructions;
3268 if (SpeculatedInstructions > 1)
3272 if (!IsSafeCheapLoadStore &&
3275 (SpeculatedStoreValue =
3278 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3284 if (!SpeculatedStore && SpeculatedStoreValue)
3290 for (Use &
Op :
I.operands()) {
3295 ++SinkCandidateUseCounts[OpI];
3302 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3303 if (Inst->hasNUses(
Count)) {
3304 ++SpeculatedInstructions;
3305 if (SpeculatedInstructions > 1)
3312 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3315 SpeculatedInstructions,
Cost,
TTI);
3316 if (!Convert ||
Cost > Budget)
3320 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3324 if (SpeculatedStoreValue) {
3328 Value *FalseV = SpeculatedStoreValue;
3332 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3362 for (DbgVariableRecord *DbgAssign :
3365 DbgAssign->replaceVariableLocationOp(OrigV, S);
3375 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3378 I.dropUBImplyingAttrsAndMetadata();
3381 if (EphTracker.contains(&
I)) {
3383 I.eraseFromParent();
3389 for (
auto &It : *ThenBB)
3394 !DVR || !DVR->isDbgAssign())
3395 It.dropOneDbgRecord(&DR);
3397 std::prev(ThenBB->end()));
3399 if (!SpeculatedConditionalLoadsStores.
empty())
3405 for (PHINode &PN : EndBB->
phis()) {
3406 unsigned OrigI = PN.getBasicBlockIndex(BB);
3407 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3408 Value *OrigV = PN.getIncomingValue(OrigI);
3409 Value *ThenV = PN.getIncomingValue(ThenI);
3418 Value *TrueV = ThenV, *FalseV = OrigV;
3422 PN.setIncomingValue(OrigI, V);
3423 PN.setIncomingValue(ThenI, V);
3427 for (Instruction *
I : SpeculatedPseudoProbes)
3428 I->eraseFromParent();
3441 if (!ReachesNonLocalUses.
insert(BB).second)
3456 EphemeralValueTracker EphTracker;
3463 if (CI->cannotDuplicate() || CI->isConvergent())
3476 for (
User *U :
I.users()) {
3479 if (UsedInBB == BB) {
3483 NonLocalUseBlocks.
insert(UsedInBB);
3497 if (
I &&
I->getParent() == To)
3513static std::optional<bool>
3534 KnownValues[CB].
insert(Pred);
3538 if (KnownValues.
empty())
3563 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3566 for (
const auto &Pair : KnownValues) {
3583 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3588 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3591 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3599 EdgeBB->setName(RealDest->
getName() +
".critedge");
3600 EdgeBB->moveBefore(RealDest);
3610 TranslateMap[
Cond] = CB;
3623 N->insertInto(EdgeBB, InsertPt);
3626 N->setName(BBI->getName() +
".c");
3637 if (!BBI->use_empty())
3638 TranslateMap[&*BBI] = V;
3639 if (!
N->mayHaveSideEffects()) {
3640 N->eraseFromParent();
3645 if (!BBI->use_empty())
3646 TranslateMap[&*BBI] =
N;
3652 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3653 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3654 SrcDbgCursor = std::next(BBI);
3656 N->cloneDebugInfoFrom(&*BBI);
3665 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3666 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3667 InsertPt->cloneDebugInfoFrom(BI);
3688 return std::nullopt;
3694bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(BranchInst *BI) {
3701 std::optional<bool>
Result;
3702 bool EverChanged =
false;
3708 }
while (Result == std::nullopt);
3717 bool SpeculateUnpredictables) {
3739 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3742 "Will have either one or two blocks to speculate.");
3749 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3750 if (!IsUnpredictable) {
3753 (TWeight + FWeight) != 0) {
3758 if (IfBlocks.
size() == 1) {
3760 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3761 if (BIBBProb >= Likely)
3764 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3773 if (IfCondPhiInst->getParent() == BB)
3781 unsigned NumPhis = 0;
3794 if (SpeculateUnpredictables && IsUnpredictable)
3795 Budget +=
TTI.getBranchMispredictPenalty();
3808 AggressiveInsts, Cost, Budget,
TTI, AC,
3809 ZeroCostInstructions) ||
3811 AggressiveInsts, Cost, Budget,
TTI, AC,
3812 ZeroCostInstructions))
3824 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3835 auto IsBinOpOrAnd = [](
Value *V) {
3852 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3865 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3867 <<
" F: " << IfFalse->
getName() <<
"\n");
3884 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3889 PN->eraseFromParent();
3895 Builder.CreateBr(BB);
3916 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3917 if (
Opc == Instruction::And)
3918 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3919 if (
Opc == Instruction::Or)
3920 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3932 bool PredHasWeights =
3934 bool SuccHasWeights =
3936 if (PredHasWeights || SuccHasWeights) {
3937 if (!PredHasWeights)
3938 PredTrueWeight = PredFalseWeight = 1;
3939 if (!SuccHasWeights)
3940 SuccTrueWeight = SuccFalseWeight = 1;
3950static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3954 "Both blocks must end with a conditional branches.");
3956 "PredBB must be a predecessor of BB.");
3964 (PTWeight + PFWeight) != 0) {
3967 Likely =
TTI->getPredictableBranchThreshold();
3972 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3973 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3977 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3980 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3981 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3987 return std::nullopt;
4000 bool InvertPredCond;
4001 std::tie(CommonSucc,
Opc, InvertPredCond) =
4004 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4011 {LLVMContext::MD_annotation});
4014 if (InvertPredCond) {
4027 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4030 SuccTrueWeight, SuccFalseWeight)) {
4036 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4041 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4042 PredTrueWeight * SuccFalseWeight);
4048 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4049 PredFalseWeight * SuccTrueWeight);
4051 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4093 if (!MDWeights.
empty()) {
4094 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4099 ++NumFoldBranchToCommonDest;
4106 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4107 return U->getType()->isVectorTy();
4117 unsigned BonusInstThreshold) {
4131 Cond->getParent() != BB || !
Cond->hasOneUse())
4152 bool InvertPredCond;
4154 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4186 unsigned NumBonusInsts = 0;
4187 bool SawVectorOp =
false;
4188 const unsigned PredCount = Preds.
size();
4205 NumBonusInsts += PredCount;
4213 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4216 return PN->getIncomingBlock(U) == BB;
4217 return UI->
getParent() == BB &&
I.comesBefore(UI);
4221 if (!
all_of(
I.uses(), IsBCSSAUse))
4225 BonusInstThreshold *
4241 for (
auto *BB : {BB1, BB2}) {
4257 Value *AlternativeV =
nullptr) {
4283 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4284 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4292 if (!AlternativeV &&
4298 PHI->addIncoming(V, BB);
4308 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4317 if (!PStore || !QStore)
4338 if (
I.mayReadOrWriteMemory())
4340 for (
auto &
I : *QFB)
4341 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4344 for (
auto &
I : *QTB)
4345 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4349 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4365 if (
I.isTerminator())
4383 "When we run out of budget we will eagerly return from within the "
4384 "per-instruction loop.");
4388 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4390 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4391 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4427 InvertPCond ^= (PStore->
getParent() != PTB);
4428 InvertQCond ^= (QStore->
getParent() != QTB);
4449 {CombinedWeights[0], CombinedWeights[1]},
4513 bool InvertPCond =
false, InvertQCond =
false;
4519 if (QFB == PostBB) {
4538 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4541 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4549 for (
auto *BB : {PTB, PFB}) {
4554 PStoreAddresses.
insert(
SI->getPointerOperand());
4556 for (
auto *BB : {QTB, QFB}) {
4561 QStoreAddresses.
insert(
SI->getPointerOperand());
4567 auto &CommonAddresses = PStoreAddresses;
4570 for (
auto *Address : CommonAddresses)
4573 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4591 !BI->
getParent()->getSinglePredecessor())
4593 if (!IfFalseBB->
phis().empty())
4603 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4706 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4708 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4712 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4715 if (CommonDestProb >= Likely)
4725 unsigned NumPhis = 0;
4747 if (OtherDest == BB) {
4755 OtherDest = InfLoopBlock;
4767 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4771 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4775 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4790 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4791 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4794 SuccTrueWeight, SuccFalseWeight);
4796 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4797 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4798 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4799 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4803 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4804 PredOther * SuccCommon,
4805 PredOther * SuccOther};
4813 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4832 Value *BIV = PN.getIncomingValueForBlock(BB);
4833 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4834 Value *PBIV = PN.getIncomingValue(PBBIdx);
4838 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4839 PN.setIncomingValue(PBBIdx, NV);
4843 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4844 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4864bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4866 BasicBlock *FalseBB,
4867 uint32_t TrueWeight,
4868 uint32_t FalseWeight) {
4875 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4877 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4880 for (BasicBlock *Succ :
successors(OldTerm)) {
4882 if (Succ == KeepEdge1)
4883 KeepEdge1 =
nullptr;
4884 else if (Succ == KeepEdge2)
4885 KeepEdge2 =
nullptr;
4890 if (Succ != TrueBB && Succ != FalseBB)
4891 RemovedSuccessors.
insert(Succ);
4899 if (!KeepEdge1 && !KeepEdge2) {
4900 if (TrueBB == FalseBB) {
4911 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4931 SmallVector<DominatorTree::UpdateType, 2> Updates;
4933 for (
auto *RemovedSuccessor : RemovedSuccessors)
4934 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4945bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4950 if (!TrueVal || !FalseVal)
4955 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4956 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4959 uint32_t TrueWeight = 0, FalseWeight = 0;
4960 SmallVector<uint64_t, 8> Weights;
4964 if (Weights.
size() == 1 +
SI->getNumCases()) {
4966 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4968 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4973 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4982bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
4996 SmallVector<uint32_t> SelectBranchWeights(2);
5000 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5001 SelectBranchWeights[0],
5002 SelectBranchWeights[1]);
5022bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5042 if (
SI->getCondition() != V)
5048 if (
SI->getDefaultDest() != BB) {
5049 ConstantInt *VVal =
SI->findCaseDest(BB);
5050 assert(VVal &&
"Should have a unique destination value");
5058 return requestResimplify();
5064 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5074 return requestResimplify();
5081 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5098 SmallVector<DominatorTree::UpdateType, 2> Updates;
5105 SwitchInstProfUpdateWrapper SIW(*SI);
5106 auto W0 = SIW.getSuccessorWeight(0);
5109 NewW = ((uint64_t(*W0) + 1) >> 1);
5110 SIW.setSuccessorWeight(0, *NewW);
5112 SIW.addCase(Cst, NewBB, NewW);
5114 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5123 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5132bool SimplifyCFGOpt::simplifyBranchOnICmpChain(BranchInst *BI,
5134 const DataLayout &
DL) {
5144 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5146 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5147 Value *CompVal = ConstantCompare.CompValue;
5148 unsigned UsedICmps = ConstantCompare.UsedICmps;
5149 Value *ExtraCase = ConstantCompare.Extra;
5150 bool TrueWhenEqual = ConstantCompare.IsEq;
5167 if (ExtraCase && Values.
size() < 2)
5170 SmallVector<uint32_t> BranchWeights;
5177 if (!TrueWhenEqual) {
5180 std::swap(BranchWeights[0], BranchWeights[1]);
5186 <<
" cases into SWITCH. BB is:\n"
5189 SmallVector<DominatorTree::UpdateType, 2> Updates;
5196 nullptr,
"switch.early.test");
5207 AssumptionCache *AC =
Options.AC;
5213 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5221 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5227 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5228 <<
"\nEXTRABB = " << *BB);
5236 "Should not end up here with unstable pointers");
5238 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5243 if (Values.
front()->getValue() - Values.
back()->getValue() ==
5244 Values.
size() - 1) {
5246 Values.
back()->getValue(), Values.
front()->getValue() + 1);
5248 ICmpInst::Predicate Pred;
5266 SmallVector<uint32_t> NewWeights(Values.
size() + 1);
5267 NewWeights[0] = BranchWeights[1];
5270 V = BranchWeights[0] / Values.
size();
5275 for (ConstantInt *Val : Values)
5276 New->addCase(Val, EdgeBB);
5284 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5294 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5298bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5300 return simplifyCommonResume(RI);
5304 return simplifySingleResume(RI);
5317 switch (IntrinsicID) {
5318 case Intrinsic::dbg_declare:
5319 case Intrinsic::dbg_value:
5320 case Intrinsic::dbg_label:
5321 case Intrinsic::lifetime_end:
5331bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5340 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5344 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5346 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5347 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5351 if (IncomingBB->getUniqueSuccessor() != BB)
5356 if (IncomingValue != LandingPad)
5360 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5361 TrivialUnwindBlocks.
insert(IncomingBB);
5365 if (TrivialUnwindBlocks.
empty())
5369 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5373 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5376 for (BasicBlock *Pred :
5387 TrivialBB->getTerminator()->eraseFromParent();
5388 new UnreachableInst(RI->
getContext(), TrivialBB);
5390 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5397 return !TrivialUnwindBlocks.empty();
5401bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5405 "Resume must unwind the exception that caused control to here");
5461 int Idx = DestPN.getBasicBlockIndex(BB);
5475 Value *SrcVal = DestPN.getIncomingValue(Idx);
5478 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5482 DestPN.addIncoming(
Incoming, Pred);
5509 std::vector<DominatorTree::UpdateType> Updates;
5513 if (UnwindDest ==
nullptr) {
5554 if (!SuccessorCleanupPad)
5563 SuccessorCleanupPad->eraseFromParent();
5572bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5589bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5621 BBI->dropDbgRecords();
5625 BBI->eraseFromParent();
5631 if (&BB->
front() != UI)
5634 std::vector<DominatorTree::UpdateType> Updates;
5637 for (BasicBlock *Predecessor : Preds) {
5644 [BB](
auto *
Successor) { return Successor == BB; })) {
5652 "The destinations are guaranteed to be different here.");
5653 CallInst *Assumption;
5669 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5671 SwitchInstProfUpdateWrapper SU(*SI);
5672 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5673 if (i->getCaseSuccessor() != BB) {
5678 i = SU.removeCase(i);
5683 if (DTU &&
SI->getDefaultDest() != BB)
5684 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5686 if (
II->getUnwindDest() == BB) {
5692 if (!CI->doesNotThrow())
5693 CI->setDoesNotThrow();
5697 if (CSI->getUnwindDest() == BB) {
5708 E = CSI->handler_end();
5711 CSI->removeHandler(
I);
5718 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5719 if (CSI->getNumHandlers() == 0) {
5720 if (CSI->hasUnwindDest()) {
5724 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5725 Updates.push_back({DominatorTree::Insert,
5726 PredecessorOfPredecessor,
5727 CSI->getUnwindDest()});
5728 Updates.push_back({DominatorTree::Delete,
5729 PredecessorOfPredecessor, Predecessor});
5732 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5739 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5740 for (BasicBlock *EHPred : EHPreds)
5744 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5745 CSI->eraseFromParent();
5750 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5751 "Expected to always have an unwind to BB.");
5753 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5781static std::optional<ContiguousCasesResult>
5788 const APInt &Min = Cases.
back()->getValue();
5789 const APInt &Max = Cases.
front()->getValue();
5791 size_t ContiguousOffset = Cases.
size() - 1;
5792 if (
Offset == ContiguousOffset) {
5810 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
5811 return L->getValue() != R->getValue() + 1;
5813 if (It == Cases.
end())
5814 return std::nullopt;
5815 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5816 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5820 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5823 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5831 return std::nullopt;
5836 bool RemoveOrigDefaultBlock =
true) {
5838 auto *BB = Switch->getParent();
5839 auto *OrigDefaultBlock = Switch->getDefaultDest();
5840 if (RemoveOrigDefaultBlock)
5841 OrigDefaultBlock->removePredecessor(BB);
5845 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5847 Switch->setDefaultDest(&*NewDefaultBlock);
5851 if (RemoveOrigDefaultBlock &&
5861bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5863 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5865 bool HasDefault = !
SI->defaultDestUnreachable();
5867 auto *BB =
SI->getParent();
5869 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5874 for (
auto Case :
SI->cases()) {
5878 if (Dest == DestA) {
5884 if (Dest == DestB) {
5894 "Single-destination switch should have been folded.");
5896 assert(DestB !=
SI->getDefaultDest());
5897 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5901 std::optional<ContiguousCasesResult> ContiguousCases;
5904 if (!HasDefault && CasesA.
size() == 1)
5905 ContiguousCases = ContiguousCasesResult{
5913 else if (CasesB.
size() == 1)
5914 ContiguousCases = ContiguousCasesResult{
5923 else if (!HasDefault)
5927 if (!ContiguousCases)
5931 if (!ContiguousCases)
5934 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
5940 Max->getValue() - Min->getValue() + 1);
5943 assert(
Max->getValue() == Min->getValue());
5948 else if (NumCases->
isNullValue() && !Cases->empty()) {
5952 if (!
Offset->isNullValue())
5960 SmallVector<uint64_t, 8> Weights;
5962 if (Weights.
size() == 1 +
SI->getNumCases()) {
5963 uint64_t TrueWeight = 0;
5964 uint64_t FalseWeight = 0;
5965 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
5966 if (
SI->getSuccessor(
I) == Dest)
5967 TrueWeight += Weights[
I];
5969 FalseWeight += Weights[
I];
5971 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5982 unsigned PreviousEdges = Cases->size();
5983 if (Dest ==
SI->getDefaultDest())
5985 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5986 PHI.removeIncomingValue(
SI->getParent());
5989 unsigned PreviousEdges = OtherCases->size();
5990 if (OtherDest ==
SI->getDefaultDest())
5992 unsigned E = PreviousEdges - 1;
5996 for (
unsigned I = 0;
I !=
E; ++
I)
5997 PHI.removeIncomingValue(
SI->getParent());
6005 auto *UnreachableDefault =
SI->getDefaultDest();
6008 SI->eraseFromParent();
6010 if (!HasDefault && DTU)
6011 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
6027 unsigned MaxSignificantBitsInCond =
6034 for (
const auto &Case :
SI->cases()) {
6035 auto *
Successor = Case.getCaseSuccessor();
6042 const APInt &CaseVal = Case.getCaseValue()->getValue();
6045 DeadCases.
push_back(Case.getCaseValue());
6057 bool HasDefault = !
SI->defaultDestUnreachable();
6058 const unsigned NumUnknownBits =
6061 if (HasDefault && DeadCases.
empty() &&
6062 NumUnknownBits < 64 ) {
6063 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6064 if (
SI->getNumCases() == AllNumCases) {
6071 if (
SI->getNumCases() == AllNumCases - 1) {
6072 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6079 for (
const auto &Case :
SI->cases())
6080 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6091 if (DeadCases.
empty())
6097 assert(CaseI !=
SI->case_default() &&
6098 "Case was not found. Probably mistake in DeadCases forming.");
6100 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6105 std::vector<DominatorTree::UpdateType> Updates;
6106 for (
auto *
Successor : UniqueSuccessors)
6107 if (NumPerSuccessorCases[
Successor] == 0)
6128 if (!Branch || !Branch->isUnconditional())
6134 int Idx =
PHI.getBasicBlockIndex(BB);
6135 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6137 Value *InValue =
PHI.getIncomingValue(Idx);
6138 if (InValue != CaseValue)
6154 ForwardingNodesMap ForwardingNodes;
6157 for (
const auto &Case :
SI->cases()) {
6159 BasicBlock *CaseDest = Case.getCaseSuccessor();
6178 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6179 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6180 count(Phi.blocks(), SwitchBlock) == 1) {
6181 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6189 ForwardingNodes[Phi].push_back(PhiIdx);
6192 for (
auto &ForwardingNode : ForwardingNodes) {
6193 PHINode *Phi = ForwardingNode.first;
6199 for (
int Index : Indexes)
6200 Phi->setIncomingValue(Index,
SI->getCondition());
6210 if (
C->isThreadDependent())
6212 if (
C->isDLLImportDependent())
6228 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6255 if (
A->isAllOnesValue())
6257 if (
A->isNullValue())
6263 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6288 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6290 if (
I.isTerminator()) {
6292 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6295 CaseDest =
I.getSuccessor(0);
6302 for (
auto &
Use :
I.uses()) {
6305 if (
I->getParent() == CaseDest)
6308 if (Phi->getIncomingBlock(
Use) == CaseDest)
6321 *CommonDest = CaseDest;
6323 if (CaseDest != *CommonDest)
6328 int Idx =
PHI.getBasicBlockIndex(Pred);
6341 Res.push_back(std::make_pair(&
PHI, ConstVal));
6344 return Res.
size() > 0;
6350 SwitchCaseResultVectorTy &UniqueResults,
6352 for (
auto &
I : UniqueResults) {
6353 if (
I.first == Result) {
6354 I.second.push_back(CaseVal);
6355 return I.second.size();
6358 UniqueResults.push_back(
6369 SwitchCaseResultVectorTy &UniqueResults,
6373 uintptr_t MaxUniqueResults) {
6374 for (
const auto &
I :
SI->cases()) {
6388 const size_t NumCasesForResult =
6396 if (UniqueResults.size() > MaxUniqueResults)
6412 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6414 return DefaultResult ||
SI->defaultDestUnreachable();
6435 const bool HasBranchWeights =
6438 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6439 ResultVector[1].second.size() == 1) {
6440 ConstantInt *FirstCase = ResultVector[0].second[0];
6441 ConstantInt *SecondCase = ResultVector[1].second[0];
6442 Value *SelectValue = ResultVector[1].first;
6443 if (DefaultResult) {
6444 Value *ValueCompare =
6445 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6446 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6447 DefaultResult,
"switch.select");
6449 SI && HasBranchWeights) {
6456 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6460 Value *ValueCompare =
6461 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6462 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6463 SelectValue,
"switch.select");
6469 size_t FirstCasePos = (Condition !=
nullptr);
6470 size_t SecondCasePos = FirstCasePos + 1;
6471 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6473 {BranchWeights[FirstCasePos],
6474 DefaultCase + BranchWeights[SecondCasePos]},
6481 if (ResultVector.size() == 1 && DefaultResult) {
6483 unsigned CaseCount = CaseValues.
size();
6496 for (
auto *Case : CaseValues) {
6497 if (Case->getValue().slt(MinCaseVal->
getValue()))
6499 AndMask &= Case->getValue();
6509 if (FreeBits ==
Log2_32(CaseCount)) {
6510 Value *
And = Builder.CreateAnd(Condition, AndMask);
6511 Value *Cmp = Builder.CreateICmpEQ(
6514 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6530 for (
auto *Case : CaseValues)
6531 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6537 Condition = Builder.CreateSub(Condition, MinCaseVal);
6538 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6539 Value *Cmp = Builder.CreateICmpEQ(
6542 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6555 if (CaseValues.
size() == 2) {
6556 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6557 "switch.selectcmp.case1");
6558 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6559 "switch.selectcmp.case2");
6560 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6562 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6582 std::vector<DominatorTree::UpdateType> Updates;
6589 Builder.CreateBr(DestBB);
6593 PHI->removeIncomingValueIf(
6594 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6595 PHI->addIncoming(SelectValue, SelectBB);
6598 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6604 if (DTU && RemovedSuccessors.
insert(Succ).second)
6607 SI->eraseFromParent();
6622 SwitchCaseResultVectorTy UniqueResults;
6628 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6629 Builder.SetInsertPoint(
SI);
6632 [[maybe_unused]]
auto HasWeights =
6637 (BranchWeights.
size() >=
6638 UniqueResults.size() + (DefaultResult !=
nullptr)));
6641 Builder,
DL, BranchWeights);
6653class SwitchReplacement {
6660 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6661 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName);
6670 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6677 bool isLookupTable();
6714 ConstantInt *BitMap =
nullptr;
6715 IntegerType *BitMapElementTy =
nullptr;
6718 ConstantInt *LinearOffset =
nullptr;
6719 ConstantInt *LinearMultiplier =
nullptr;
6720 bool LinearMapValWrapped =
false;
6728SwitchReplacement::SwitchReplacement(
6730 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6731 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName)
6732 : DefaultValue(DefaultValue) {
6733 assert(Values.size() &&
"Can't build lookup table without values!");
6734 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6737 SingleValue = Values.begin()->second;
6739 ValueType = Values.begin()->second->getType();
6743 for (
const auto &[CaseVal, CaseRes] : Values) {
6746 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6747 TableContents[Idx] = CaseRes;
6754 if (Values.size() < TableSize) {
6756 "Need a default value to fill the lookup table holes.");
6759 if (!TableContents[
I])
6760 TableContents[
I] = DefaultValue;
6766 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6767 SingleValue =
nullptr;
6773 Kind = SingleValueKind;
6780 bool LinearMappingPossible =
true;
6785 bool NonMonotonic =
false;
6786 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6803 LinearMappingPossible =
false;
6808 APInt Dist = Val - PrevVal;
6811 }
else if (Dist != DistToPrev) {
6812 LinearMappingPossible =
false;
6820 if (LinearMappingPossible) {
6822 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6823 APInt M = LinearMultiplier->getValue();
6824 bool MayWrap =
true;
6825 if (
isIntN(M.getBitWidth(), TableSize - 1))
6826 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6827 LinearMapValWrapped = NonMonotonic || MayWrap;
6828 Kind = LinearMapKind;
6834 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6836 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6838 TableInt <<=
IT->getBitWidth();
6842 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6845 BitMap = ConstantInt::get(M.getContext(), TableInt);
6846 BitMapElementTy =
IT;
6855 Kind = LookupTableKind;
6861 case SingleValueKind:
6863 case LinearMapKind: {
6867 false,
"switch.idx.cast");
6868 if (!LinearMultiplier->
isOne())
6869 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6871 !LinearMapValWrapped);
6873 if (!LinearOffset->
isZero())
6876 !LinearMapValWrapped);
6893 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
6894 "switch.shiftamt",
true,
true);
6897 Value *DownShifted =
6898 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6900 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6902 case LookupTableKind: {
6905 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
6906 true, GlobalVariable::PrivateLinkage,
6907 Initializer,
"switch.table." +
Func->getName());
6908 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6911 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
6912 Type *IndexTy =
DL.getIndexType(Table->getType());
6915 if (
Index->getType() != IndexTy) {
6916 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
6920 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
6923 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
6926 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
6932bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
6934 Type *ElementType) {
6942 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6944 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6950 if (
TTI.isTypeLegal(Ty))
6965 DL.fitsInLegalInteger(
IT->getBitWidth());
6968Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
6970bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
6972bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
6983 return NumCases * 100 >= CaseRange * MinDensity;
7004 if (
SI->getNumCases() > TableSize)
7007 bool AllTablesFitInRegister =
true;
7008 bool HasIllegalType =
false;
7009 for (
const auto &Ty : ResultTypes) {
7014 AllTablesFitInRegister =
7015 AllTablesFitInRegister &&
7016 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7021 if (HasIllegalType && !AllTablesFitInRegister)
7026 if (AllTablesFitInRegister)
7043 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7046 return all_of(ResultTypes, [&](
const auto &ResultType) {
7047 return SwitchReplacement::wouldFitInRegister(
7075 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
7097 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7102 for (
auto ValuePair : Values) {
7105 if (!CaseConst || CaseConst == DefaultConst ||
7106 (CaseConst != TrueConst && CaseConst != FalseConst))
7120 if (DefaultConst == FalseConst) {
7123 ++NumTableCmpReuses;
7126 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7127 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7130 ++NumTableCmpReuses;
7140 bool ConvertSwitchToLookupTable) {
7141 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7155 if (
SI->getNumCases() < 3)
7177 MinCaseVal = CaseVal;
7179 MaxCaseVal = CaseVal;
7196 It->second.push_back(std::make_pair(CaseVal,
Value));
7204 bool HasDefaultResults =
7206 DefaultResultsList,
DL,
TTI);
7207 for (
const auto &
I : DefaultResultsList) {
7210 DefaultResults[
PHI] = Result;
7214 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7217 if (UseSwitchConditionAsTableIndex) {
7219 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7224 TableIndexOffset = MinCaseVal;
7231 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7233 bool TableHasHoles = (NumResults < TableSize);
7238 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7246 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7249 if (
SI->getNumCases() < 4)
7251 if (!
DL.fitsInLegalInteger(TableSize))
7260 if (UseSwitchConditionAsTableIndex) {
7261 TableIndex =
SI->getCondition();
7262 if (HasDefaultResults) {
7274 all_of(ResultTypes, [&](
const auto &ResultType) {
7275 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7280 TableSize = std::max(UpperBound, TableSize);
7283 DefaultIsReachable =
false;
7291 const auto &ResultList = ResultLists[
PHI];
7293 Type *ResultType = ResultList.begin()->second->getType();
7298 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7300 PhiToReplacementMap.
insert({
PHI, Replacement});
7303 bool AnyLookupTables =
any_of(
7304 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7305 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7306 [](
auto &KV) {
return KV.second.isBitMap(); });
7314 if (AnyLookupTables &&
7315 (!
TTI.shouldBuildLookupTables() ||
7321 if (!ConvertSwitchToLookupTable &&
7322 (AnyLookupTables || AnyBitMaps || NeedMask))
7325 Builder.SetInsertPoint(
SI);
7328 if (!UseSwitchConditionAsTableIndex) {
7331 bool MayWrap =
true;
7332 if (!DefaultIsReachable) {
7337 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7338 "switch.tableidx",
false,
7342 std::vector<DominatorTree::UpdateType> Updates;
7348 assert(MaxTableSize >= TableSize &&
7349 "It is impossible for a switch to have more entries than the max "
7350 "representable value of its input integer type's size.");
7355 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7360 Builder.SetInsertPoint(
SI);
7361 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7362 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7363 Builder.CreateBr(LookupBB);
7369 Value *Cmp = Builder.CreateICmpULT(
7370 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7372 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7373 CondBranch = RangeCheckBranch;
7379 Builder.SetInsertPoint(LookupBB);
7385 MaskBB->
setName(
"switch.hole_check");
7392 APInt MaskInt(TableSizePowOf2, 0);
7393 APInt One(TableSizePowOf2, 1);
7395 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7396 for (
const auto &Result : ResultList) {
7399 MaskInt |= One << Idx;
7401 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7408 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7409 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7410 Value *LoBit = Builder.CreateTrunc(
7412 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7417 Builder.SetInsertPoint(LookupBB);
7421 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7424 SI->getDefaultDest()->removePredecessor(BB,
7431 const ResultListTy &ResultList = ResultLists[
PHI];
7432 auto Replacement = PhiToReplacementMap.
at(
PHI);
7433 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7436 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7439 for (
auto *
User :
PHI->users()) {
7441 Replacement.getDefaultValue(), ResultList);
7445 PHI->addIncoming(Result, LookupBB);
7448 Builder.CreateBr(CommonDest);
7460 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7463 if (Succ ==
SI->getDefaultDest()) {
7464 if (HasBranchWeights)
7465 ToDefaultWeight += BranchWeights[
I];
7469 if (DTU && RemovedSuccessors.
insert(Succ).second)
7471 if (HasBranchWeights)
7472 ToLookupWeight += BranchWeights[
I];
7474 SI->eraseFromParent();
7475 if (HasBranchWeights)
7482 ++NumLookupTablesHoles;
7498 if (CondTy->getIntegerBitWidth() > 64 ||
7499 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7503 if (
SI->getNumCases() < 4)
7511 for (
const auto &
C :
SI->cases())
7512 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7520 int64_t
Base = Values[0];
7521 for (
auto &V : Values)
7534 unsigned Shift = 64;
7535 for (
auto &V : Values)
7539 for (
auto &V : Values)
7540 V = (int64_t)((
uint64_t)V >> Shift);
7557 Builder.SetInsertPoint(
SI);
7559 Builder.CreateSub(
SI->getCondition(), ConstantInt::get(Ty,
Base));
7560 Value *Rot = Builder.CreateIntrinsic(
7561 Ty, Intrinsic::fshl,
7562 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7563 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7565 for (
auto Case :
SI->cases()) {
7566 auto *Orig = Case.getCaseValue();
7567 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7587 Value *Condition =
SI->getCondition();
7591 if (CondTy->getIntegerBitWidth() > 64 ||
7592 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7604 if (
SI->getNumCases() < 4)
7609 for (
const auto &Case :
SI->cases()) {
7610 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7624 Builder.SetInsertPoint(
SI);
7626 if (!
SI->defaultDestUnreachable()) {
7629 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
7630 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
7632 auto *OrigBB =
SI->getParent();
7633 auto *DefaultCaseBB =
SI->getDefaultDest();
7635 auto It = OrigBB->getTerminator()->getIterator();
7640 if (HasWeights &&
any_of(Weights, [](
const auto &V) {
return V != 0; })) {
7646 Weights, [](
const auto &V) {
return static_cast<uint64_t>(V); }));
7648 NewWeights[1] = Weights[0] / 2;
7649 NewWeights[0] = OrigDenominator - NewWeights[1];
7656 uint64_t CasesDenominator = OrigDenominator - Weights[0];
7659 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
7665 It->eraseFromParent();
7673 for (
auto &Case :
SI->cases()) {
7674 auto *OrigValue = Case.getCaseValue();
7675 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7676 OrigValue->getValue().countr_zero()));
7680 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7683 SI->setCondition(ConditionTrailingZeros);
7693 if (!Cmp || !Cmp->hasOneUse())
7704 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7707 if (
SI->getNumCases() == 2) {
7714 Succ =
SI->getDefaultDest();
7715 SuccWeight = Weights[0];
7717 for (
auto &Case :
SI->cases()) {
7718 std::optional<int64_t> Val =
7722 if (!Missing.erase(*Val))
7727 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7730 assert(Missing.size() == 1 &&
"Should have one case left");
7731 Res = *Missing.begin();
7732 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7734 Unreachable =
SI->getDefaultDest();
7736 for (
auto &Case :
SI->cases()) {
7737 BasicBlock *NewSucc = Case.getCaseSuccessor();
7738 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7741 OtherSuccWeight += Weight;
7744 SuccWeight = Weight;
7745 }
else if (Succ == NewSucc) {
7751 for (
auto &Case :
SI->cases()) {
7752 std::optional<int64_t> Val =
7754 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7756 if (Case.getCaseSuccessor() == Succ) {
7778 if (Cmp->isSigned())
7781 MDNode *NewWeights =
nullptr;
7787 Builder.SetInsertPoint(
SI->getIterator());
7788 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
7789 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
7790 SI->getMetadata(LLVMContext::MD_unpredictable));
7794 SI->eraseFromParent();
7795 Cmp->eraseFromParent();
7796 if (DTU && Unreachable)
7827 "Only supporting unconditional branches for now");
7829 "Expected unconditional branches to have one successor");
7830 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7851 if (LHS == EKey || RHS == EKey || LHS == TKey || RHS == TKey)
7867 "Only supporting unconditional branches for now");
7874 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
7875 if (PredIVs[
A] != PredIVs[
B])
7883bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *
SI,
7897 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7902 if (BB->
size() != 1)
7912 if (!Seen.
insert(BB).second) {
7913 auto It = BBToSuccessorIndexes.
find(BB);
7914 if (It != BBToSuccessorIndexes.
end())
7915 It->second.emplace_back(
I);
7929 Cases.
emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs});
7930 BBToSuccessorIndexes[BB].emplace_back(
I);
7936 for (PHINode *Phi : Phis) {
7938 PhiPredIVs.
try_emplace(Phi,
Phi->getNumIncomingValues()).first->second;
7939 for (
auto &
IV :
Phi->incoming_values())
7940 IVs.insert({
Phi->getIncomingBlock(
IV),
IV.get()});
7951 DenseSet<const SwitchSuccWrapper *> ReplaceWith;
7956 bool MadeChange =
false;
7957 for (
auto &SSW : Cases) {
7964 Updates.
push_back({DominatorTree::Delete,
SI->getParent(), SSW.Dest});
7965 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7966 for (
unsigned Idx : Successors)
7967 SI->setSuccessor(Idx, (*It)->Dest);
7978bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
7981 if (isValueEqualityComparison(SI)) {
7985 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7986 return requestResimplify();
7990 if (simplifySwitchOnSelect(SI,
Select))
7991 return requestResimplify();
7996 if (foldValueComparisonIntoPredecessors(SI, Builder))
7997 return requestResimplify();
8003 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8004 return requestResimplify();
8008 return requestResimplify();
8011 return requestResimplify();
8014 return requestResimplify();
8017 return requestResimplify();
8022 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8024 Options.ConvertSwitchToLookupTable))
8025 return requestResimplify();
8028 return requestResimplify();
8031 return requestResimplify();
8034 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8035 return requestResimplify();
8037 if (simplifyDuplicateSwitchArms(SI, DTU))
8038 return requestResimplify();
8043bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8046 SmallVector<uint32_t> BranchWeights;
8050 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8051 if (HasBranchWeights)
8056 SmallPtrSet<Value *, 8> Succs;
8057 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8062 RemovedSuccs.
insert(Dest);
8072 std::vector<DominatorTree::UpdateType> Updates;
8073 Updates.reserve(RemovedSuccs.
size());
8074 for (
auto *RemovedSucc : RemovedSuccs)
8075 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8092 if (HasBranchWeights) {
8099 if (simplifyIndirectBrOnSelect(IBI, SI))
8100 return requestResimplify();
8136 if (BB == OtherPred)
8147 std::vector<DominatorTree::UpdateType> Updates;
8154 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8155 "unexpected successor");
8156 II->setUnwindDest(OtherPred);
8171 Builder.CreateUnreachable();
8180bool SimplifyCFGOpt::simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder) {
8181 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
8182 : simplifyCondBranch(
Branch, Builder);
8185bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
8197 bool NeedCanonicalLoop =
8211 if (
I->isTerminator() &&
8212 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8228 if (
Options.SpeculateBlocks &&
8231 return requestResimplify();
8239 if (!PPred || (PredPred && PredPred != PPred))
8276 if (!SuccBI || !SuccBI->isConditional())
8280 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8284 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8310 bool HasWeight =
false;
8315 BBTWeight = BBFWeight = 1;
8320 BB1TWeight = BB1FWeight = 1;
8325 BB2TWeight = BB2FWeight = 1;
8327 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8328 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8335bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder) {
8339 "Tautological conditional branch should have been eliminated already.");
8342 if (!
Options.SimplifyCondBranch ||
8347 if (isValueEqualityComparison(BI)) {
8352 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8353 return requestResimplify();
8359 if (foldValueComparisonIntoPredecessors(BI, Builder))
8360 return requestResimplify();
8363 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8364 return requestResimplify();
8369 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8382 return requestResimplify();
8388 if (
Options.SpeculateBlocks &&
8391 return requestResimplify();
8400 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8401 return requestResimplify();
8403 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8405 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8406 auto CanSpeculateConditionalLoadsStores = [&]() {
8408 for (Instruction &
I : *Succ) {
8409 if (
I.isTerminator()) {
8410 if (
I.getNumSuccessors() > 1)
8414 SpeculatedConditionalLoadsStores.
size() ==
8418 SpeculatedConditionalLoadsStores.
push_back(&
I);
8421 return !SpeculatedConditionalLoadsStores.
empty();
8424 if (CanSpeculateConditionalLoadsStores()) {
8426 std::nullopt,
nullptr);
8427 return requestResimplify();
8437 return requestResimplify();
8446 return requestResimplify();
8452 if (foldCondBranchOnValueKnownInPredecessor(BI))
8453 return requestResimplify();
8458 if (PBI != BI && PBI->isConditional())
8460 return requestResimplify();
8466 if (PBI != BI && PBI->isConditional())
8468 return requestResimplify();
8472 return requestResimplify();
8479 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8491 auto *Use = cast<Instruction>(U.getUser());
8493 switch (Use->getOpcode()) {
8496 case Instruction::GetElementPtr:
8497 case Instruction::Ret:
8498 case Instruction::BitCast:
8499 case Instruction::Load:
8500 case Instruction::Store:
8501 case Instruction::Call:
8502 case Instruction::CallBr:
8503 case Instruction::Invoke:
8504 case Instruction::UDiv:
8505 case Instruction::URem:
8509 case Instruction::SDiv:
8510 case Instruction::SRem:
8514 if (FindUse ==
I->use_end())
8516 auto &
Use = *FindUse;
8521 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8522 User->comesBefore(
I))
8536 if (
GEP->getPointerOperand() ==
I) {
8539 if (
GEP->getType()->isVectorTy())
8547 if (!
GEP->hasAllZeroIndices() &&
8548 (!
GEP->isInBounds() ||
8550 GEP->getPointerAddressSpace())))
8551 PtrValueMayBeModified =
true;
8557 bool HasNoUndefAttr =
8558 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8563 if (
C->isNullValue() && HasNoUndefAttr &&
8564 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8565 return !PtrValueMayBeModified;
8571 if (!LI->isVolatile())
8573 LI->getPointerAddressSpace());
8577 if (!
SI->isVolatile())
8579 SI->getPointerAddressSpace())) &&
8580 SI->getPointerOperand() ==
I;
8585 if (
I == Assume->getArgOperand(0))
8593 if (CB->getCalledOperand() ==
I)
8596 if (CB->isArgOperand(&
Use)) {
8597 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8600 CB->paramHasNonNullAttr(ArgIdx,
false))
8601 return !PtrValueMayBeModified;
8620 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8630 Builder.CreateUnreachable();
8637 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8639 Assumption = Builder.CreateAssumption(
Cond);
8654 Builder.SetInsertPoint(Unreachable);
8656 Builder.CreateUnreachable();
8657 for (
const auto &Case :
SI->cases())
8658 if (Case.getCaseSuccessor() == BB) {
8660 Case.setSuccessor(Unreachable);
8662 if (
SI->getDefaultDest() == BB) {
8664 SI->setDefaultDest(Unreachable);
8678bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8703 return requestResimplify();
8724 if (
Options.SpeculateBlocks &&
8731 Options.SpeculateUnpredictables))
8738 case Instruction::Br:
8741 case Instruction::Resume:
8744 case Instruction::CleanupRet:
8747 case Instruction::Switch:
8750 case Instruction::Unreachable:
8753 case Instruction::IndirectBr:
8761bool SimplifyCFGOpt::run(BasicBlock *BB) {
8771 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static Value * getCondition(Instruction *I)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
unsigned unsigned DefaultVal
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool isProfitableToSpeculate(const BranchInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static void hoistConditionalLoadsStores(BranchInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool tryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
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.
BasicBlock * getSuccessor(unsigned idx) const
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.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
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)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
LLVM_ABI BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, Function &F, StringRef PassName)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< uint32_t, 2 > &B1, const SmallVector< uint32_t, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
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 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)
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
static cl::opt< unsigned > MaxJumpThreadingLiveBlocks("max-jump-threading-live-blocks", cl::Hidden, cl::init(24), cl::desc("Limit number of blocks a define in a threaded block is allowed " "to be live in"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
LLVM_ABI bool foldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two cases of SI are equal depends on the contents of the BasicBlock and the incoming...
DenseMap< PHINode *, SmallDenseMap< BasicBlock *, Value *, 8 > > * PhiPredIVs
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const SwitchSuccWrapper * getEmptyKey()
static const SwitchSuccWrapper * getTombstoneKey()
static unsigned getHashValue(const SwitchSuccWrapper *SSW)
static bool isEqual(const SwitchSuccWrapper *LHS, const SwitchSuccWrapper *RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.