97#define DEBUG_TYPE "simplifycfg"
102 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
105 "Temporary development switch used to gradually uplift SimplifyCFG "
106 "into preserving DomTree,"));
115 "Control the amount of phi node folding to perform (default = 2)"));
119 cl::desc(
"Control the maximal total instruction cost that we are willing "
120 "to speculatively execute to fold a 2-entry PHI node into a "
121 "select (default = 4)"));
125 cl::desc(
"Hoist common instructions up to the parent block"));
129 cl::desc(
"Hoist loads if the target supports conditional faulting"));
133 cl::desc(
"Hoist stores if the target supports conditional faulting"));
137 cl::desc(
"Control the maximal conditional load/store that we are willing "
138 "to speculatively execute to eliminate conditional branch "
144 cl::desc(
"Allow reordering across at most this many "
145 "instructions when hoisting"));
149 cl::desc(
"Sink common instructions down to the end block"));
153 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
157 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
158 "precede - hoist multiple conditional stores into a single "
159 "predicated store"));
163 cl::desc(
"When merging conditional stores, do so even if the resultant "
164 "basic blocks are unlikely to be if-converted as a result"));
168 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
173 cl::desc(
"Limit maximum recursion depth when calculating costs of "
174 "speculatively executed instructions"));
179 cl::desc(
"Max size of a block which is still considered "
180 "small enough to thread through"));
186 cl::desc(
"Maximum cost of combining conditions when "
187 "folding branches"));
190 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
192 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
193 "to fold branch to common destination when vector operations are "
198 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
202 cl::desc(
"Limit cases to analyze when converting a switch to select"));
206 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
213STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
215 "Number of switch instructions turned into linear mapping");
217 "Number of switch instructions turned into lookup tables");
219 NumLookupTablesHoles,
220 "Number of switch instructions turned into lookup tables (holes checked)");
221STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
223 "Number of value comparisons folded into predecessor basic blocks");
225 "Number of branches folded into predecessor basic block");
228 "Number of common instruction 'blocks' hoisted up to the begin block");
230 "Number of common instructions hoisted up to the begin block");
232 "Number of common instruction 'blocks' sunk down to the end block");
234 "Number of common instructions sunk down to the end block");
235STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
237 "Number of invokes with empty resume blocks simplified into calls");
238STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
239STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
246using SwitchCaseResultVectorTy =
255struct ValueEqualityComparisonCase {
267 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
270class SimplifyCFGOpt {
271 const TargetTransformInfo &TTI;
273 const DataLayout &DL;
275 const SimplifyCFGOptions &Options;
278 Value *isValueEqualityComparison(Instruction *TI);
280 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
281 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
284 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
287 bool foldValueComparisonIntoPredecessors(Instruction *TI,
290 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
291 bool simplifySingleResume(ResumeInst *RI);
292 bool simplifyCommonResume(ResumeInst *RI);
293 bool simplifyCleanupReturn(CleanupReturnInst *RI);
294 bool simplifyUnreachable(UnreachableInst *UI);
295 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
296 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
297 bool simplifyIndirectBr(IndirectBrInst *IBI);
298 bool simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
299 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
300 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
302 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
304 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
307 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
308 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
309 Instruction *TI, Instruction *I1,
310 SmallVectorImpl<Instruction *> &OtherSuccTIs,
312 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
313 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
314 BasicBlock *TrueBB, BasicBlock *FalseBB,
315 uint32_t TrueWeight, uint32_t FalseWeight);
316 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
317 const DataLayout &DL);
318 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
319 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
320 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
321 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
324 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
326 const SimplifyCFGOptions &Opts)
327 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
328 assert((!DTU || !DTU->hasPostDomTree()) &&
329 "SimplifyCFG is not yet capable of maintaining validity of a "
330 "PostDomTree, so don't ask for it.");
333 bool simplifyOnce(BasicBlock *BB);
334 bool run(BasicBlock *BB);
337 bool requestResimplify() {
347isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
367 "Only for a pair of incoming blocks at the time!");
373 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
374 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
377 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
378 EquivalenceSet->contains(IV1))
401 if (!SI1Succs.
count(Succ))
407 FailBlocks->insert(Succ);
423 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
425 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
426 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
488 if (AggressiveInsts.
count(
I))
504 ZeroCostInstructions.
insert(OverflowInst);
506 }
else if (!ZeroCostInstructions.
contains(
I))
522 for (
Use &
Op :
I->operands())
524 TTI, AC, ZeroCostInstructions,
Depth + 1))
541 if (
DL.hasUnstableRepresentation(V->getType()))
550 return ConstantInt::get(IntPtrTy, 0);
555 if (CE->getOpcode() == Instruction::IntToPtr)
579struct ConstantComparesGatherer {
580 const DataLayout &DL;
583 Value *CompValue =
nullptr;
586 Value *Extra =
nullptr;
592 unsigned UsedICmps = 0;
598 bool IgnoreFirstMatch =
false;
599 bool MultipleMatches =
false;
602 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
604 if (CompValue || !MultipleMatches)
609 IgnoreFirstMatch =
true;
613 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
614 ConstantComparesGatherer &
615 operator=(
const ConstantComparesGatherer &) =
delete;
620 bool setValueOnce(
Value *NewVal) {
621 if (IgnoreFirstMatch) {
622 IgnoreFirstMatch =
false;
625 if (CompValue && CompValue != NewVal) {
626 MultipleMatches =
true;
640 bool matchInstruction(Instruction *
I,
bool isEQ) {
647 if (!setValueOnce(Val))
667 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
711 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
713 if (!setValueOnce(RHSVal))
718 ConstantInt::get(
C->getContext(),
719 C->getValue() | Mask));
734 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
736 if (!setValueOnce(RHSVal))
740 Vals.push_back(ConstantInt::get(
C->getContext(),
741 C->getValue() & ~Mask));
762 Value *CandidateVal =
I->getOperand(0);
765 CandidateVal = RHSVal;
780 if (!setValueOnce(CandidateVal))
786 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
798 void gather(
Value *V) {
807 SmallVector<Value *, 8> DFT{Op0, Op1};
808 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
810 while (!DFT.
empty()) {
817 if (Visited.
insert(Op1).second)
819 if (Visited.
insert(Op0).second)
826 if (matchInstruction(
I, IsEq))
870 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
871 CV =
SI->getCondition();
873 if (BI->getCondition()->hasOneUse()) {
878 if (Trunc->hasNoUnsignedWrap())
879 CV = Trunc->getOperand(0);
886 Value *Ptr = PTII->getPointerOperand();
887 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
889 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
898BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
899 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
901 Cases.reserve(
SI->getNumCases());
902 for (
auto Case :
SI->cases())
903 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
904 Case.getCaseSuccessor()));
905 return SI->getDefaultDest();
910 ICmpInst::Predicate Pred;
916 Pred = ICmpInst::ICMP_NE;
921 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
929 std::vector<ValueEqualityComparisonCase> &Cases) {
935 std::vector<ValueEqualityComparisonCase> &C2) {
936 std::vector<ValueEqualityComparisonCase> *
V1 = &C1, *V2 = &C2;
939 if (
V1->size() > V2->size())
944 if (
V1->size() == 1) {
947 for (
const ValueEqualityComparisonCase &
VECC : *V2)
948 if (TheVal ==
VECC.Value)
955 unsigned i1 = 0, i2 = 0, e1 =
V1->size(), e2 = V2->size();
956 while (i1 != e1 && i2 != e2) {
972bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
973 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
978 Value *ThisVal = isValueEqualityComparison(TI);
979 assert(ThisVal &&
"This isn't a value comparison!!");
980 if (ThisVal != PredVal)
987 std::vector<ValueEqualityComparisonCase> PredCases;
989 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
993 std::vector<ValueEqualityComparisonCase> ThisCases;
994 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1009 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1015 ThisCases[0].Dest->removePredecessor(PredDef);
1018 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1025 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1032 SmallPtrSet<Constant *, 16> DeadCases;
1033 for (
const ValueEqualityComparisonCase &Case : PredCases)
1034 DeadCases.
insert(Case.Value);
1037 <<
"Through successor TI: " << *TI);
1039 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1042 auto *
Successor = i->getCaseSuccessor();
1045 if (DeadCases.
count(i->getCaseValue())) {
1054 std::vector<DominatorTree::UpdateType> Updates;
1055 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1057 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1067 ConstantInt *TIV =
nullptr;
1069 for (
const auto &[
Value, Dest] : PredCases)
1075 assert(TIV &&
"No edge from pred to succ?");
1080 for (
const auto &[
Value, Dest] : ThisCases)
1088 TheRealDest = ThisDef;
1090 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1095 if (Succ != CheckEdge) {
1096 if (Succ != TheRealDest)
1097 RemovedSuccs.
insert(Succ);
1100 CheckEdge =
nullptr;
1107 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1112 SmallVector<DominatorTree::UpdateType, 2> Updates;
1114 for (
auto *RemovedSucc : RemovedSuccs)
1115 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1126struct ConstantIntOrdering {
1127 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1128 return LHS->getValue().ult(
RHS->getValue());
1140 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1149 assert(MD &&
"Invalid branch-weight metadata");
1174 if (BonusInst.isTerminator())
1204 NewBonusInst->
takeName(&BonusInst);
1205 BonusInst.setName(NewBonusInst->
getName() +
".old");
1206 VMap[&BonusInst] = NewBonusInst;
1215 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1216 "If the user is not a PHI node, then it should be in the same "
1217 "block as, and come after, the original bonus instruction.");
1221 if (PN->getIncomingBlock(U) == BB)
1225 assert(PN->getIncomingBlock(U) == PredBlock &&
1226 "Not in block-closed SSA form?");
1227 U.set(NewBonusInst);
1237 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1238 PredDL.isSameSourceLocation(
DL)) {
1245bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1253 std::vector<ValueEqualityComparisonCase> BBCases;
1254 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1256 std::vector<ValueEqualityComparisonCase> PredCases;
1257 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1262 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1265 SmallVector<uint64_t, 8> Weights;
1269 if (PredHasWeights) {
1272 if (Weights.
size() != 1 + PredCases.size())
1273 PredHasWeights = SuccHasWeights =
false;
1274 }
else if (SuccHasWeights)
1278 Weights.
assign(1 + PredCases.size(), 1);
1280 SmallVector<uint64_t, 8> SuccWeights;
1281 if (SuccHasWeights) {
1284 if (SuccWeights.
size() != 1 + BBCases.size())
1285 PredHasWeights = SuccHasWeights =
false;
1286 }
else if (PredHasWeights)
1287 SuccWeights.
assign(1 + BBCases.size(), 1);
1289 if (PredDefault == BB) {
1292 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1293 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1294 if (PredCases[i].Dest != BB)
1295 PTIHandled.insert(PredCases[i].
Value);
1298 std::swap(PredCases[i], PredCases.back());
1300 if (PredHasWeights || SuccHasWeights) {
1302 Weights[0] += Weights[i + 1];
1307 PredCases.pop_back();
1313 if (PredDefault != BBDefault) {
1315 if (DTU && PredDefault != BB)
1316 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1317 PredDefault = BBDefault;
1318 ++NewSuccessors[BBDefault];
1321 unsigned CasesFromPred = Weights.
size();
1322 uint64_t ValidTotalSuccWeight = 0;
1323 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1324 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1325 PredCases.push_back(BBCases[i]);
1326 ++NewSuccessors[BBCases[i].Dest];
1327 if (SuccHasWeights || PredHasWeights) {
1331 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1332 ValidTotalSuccWeight += SuccWeights[i + 1];
1336 if (SuccHasWeights || PredHasWeights) {
1337 ValidTotalSuccWeight += SuccWeights[0];
1339 for (
unsigned i = 1; i < CasesFromPred; ++i)
1340 Weights[i] *= ValidTotalSuccWeight;
1342 Weights[0] *= SuccWeights[0];
1348 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1349 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1350 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1351 if (PredCases[i].Dest == BB) {
1352 PTIHandled.insert(PredCases[i].
Value);
1354 if (PredHasWeights || SuccHasWeights) {
1355 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1360 std::swap(PredCases[i], PredCases.back());
1361 PredCases.pop_back();
1368 for (
const ValueEqualityComparisonCase &Case : BBCases)
1369 if (PTIHandled.count(Case.Value)) {
1371 if (PredHasWeights || SuccHasWeights)
1372 Weights.
push_back(WeightsForHandled[Case.Value]);
1373 PredCases.push_back(Case);
1374 ++NewSuccessors[Case.Dest];
1375 PTIHandled.erase(Case.Value);
1380 for (ConstantInt *
I : PTIHandled) {
1381 if (PredHasWeights || SuccHasWeights)
1383 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1384 ++NewSuccessors[BBDefault];
1391 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1396 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1398 for (
auto I :
seq(NewSuccessor.second)) {
1402 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1403 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1410 "Should not end up here with unstable pointers");
1416 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1418 for (ValueEqualityComparisonCase &V : PredCases)
1421 if (PredHasWeights || SuccHasWeights)
1433 if (!InfLoopBlock) {
1441 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1448 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1450 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1455 ++NumFoldValueComparisonIntoPredecessors;
1463bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1466 Value *CV = isValueEqualityComparison(TI);
1467 assert(CV &&
"Not a comparison?");
1472 while (!Preds.empty()) {
1481 Value *PCV = isValueEqualityComparison(PTI);
1485 SmallSetVector<BasicBlock *, 4> FailBlocks;
1487 for (
auto *Succ : FailBlocks) {
1493 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1507 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1508 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1509 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1528 if (
I->mayReadFromMemory())
1560 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1568 if (J->getParent() == BB)
1590 if (C1->isMustTailCall() != C2->isMustTailCall())
1593 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1599 if (CB1->cannotMerge() || CB1->isConvergent())
1602 if (CB2->cannotMerge() || CB2->isConvergent())
1617 if (!I1->hasDbgRecords())
1619 using CurrentAndEndIt =
1620 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1626 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1627 return Pair.first == Pair.second;
1633 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1639 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1641 if (!
Other->hasDbgRecords())
1644 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1651 while (
none_of(Itrs, atEnd)) {
1652 bool HoistDVRs = allIdentical(Itrs);
1653 for (CurrentAndEndIt &Pair : Itrs) {
1667 if (I1->isIdenticalToWhenDefined(I2,
true))
1672 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1673 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1674 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1676 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1677 return I1->getOperand(0) == I2->
getOperand(1) &&
1743 auto &Context = BI->getParent()->getContext();
1748 Value *Mask =
nullptr;
1749 Value *MaskFalse =
nullptr;
1750 Value *MaskTrue =
nullptr;
1751 if (Invert.has_value()) {
1752 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1753 Mask = Builder.CreateBitCast(
1758 MaskFalse = Builder.CreateBitCast(
1760 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1762 auto PeekThroughBitcasts = [](
Value *V) {
1764 V = BitCast->getOperand(0);
1767 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1769 if (!Invert.has_value())
1770 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1775 auto *Op0 =
I->getOperand(0);
1776 CallInst *MaskedLoadStore =
nullptr;
1779 auto *Ty =
I->getType();
1781 Value *PassThru =
nullptr;
1782 if (Invert.has_value())
1783 for (
User *U :
I->users()) {
1785 PassThru = Builder.CreateBitCast(
1794 Builder.SetInsertPoint(Ins);
1797 MaskedLoadStore = Builder.CreateMaskedLoad(
1799 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1802 I->replaceAllUsesWith(NewLoadStore);
1805 auto *StoredVal = Builder.CreateBitCast(
1807 MaskedLoadStore = Builder.CreateMaskedStore(
1818 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1820 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1824 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1825 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1828 I->eraseFromParent();
1835 bool IsStore =
false;
1858bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1859 bool AllInstsEqOnly) {
1875 for (
auto *Succ : UniqueSuccessors) {
1891 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1893 for (
auto *Succ : UniqueSuccessors) {
1897 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1900 if (AllInstsEqOnly) {
1906 unsigned Size0 = UniqueSuccessors[0]->size();
1907 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1911 Succ->
size() == Size0;
1915 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1916 while (LRI.isValid()) {
1918 if (
any_of(*LRI, [I0](Instruction *
I) {
1932 unsigned NumSkipped = 0;
1935 if (SuccIterPairs.
size() > 2) {
1938 if (SuccIterPairs.
size() < 2)
1945 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1946 auto &BB1ItrPair = *SuccIterPairBegin++;
1947 auto OtherSuccIterPairRange =
1953 bool AllInstsAreIdentical =
true;
1954 bool HasTerminator =
I1->isTerminator();
1955 for (
auto &SuccIter : OtherSuccIterRange) {
1959 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1960 AllInstsAreIdentical =
false;
1963 SmallVector<Instruction *, 8> OtherInsts;
1964 for (
auto &SuccIter : OtherSuccIterRange)
1969 if (HasTerminator) {
1973 if (NumSkipped || !AllInstsAreIdentical) {
1978 return hoistSuccIdenticalTerminatorToSwitchOrIf(
1979 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
1983 if (AllInstsAreIdentical) {
1984 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1985 AllInstsAreIdentical =
1987 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1989 unsigned SkipFlagsBB2 = Pair.second;
1999 if (AllInstsAreIdentical) {
2009 for (
auto &SuccIter : OtherSuccIterRange) {
2017 assert(
Success &&
"We should not be trying to hoist callbases "
2018 "with non-intersectable attributes");
2030 NumHoistCommonCode += SuccIterPairs.
size();
2032 NumHoistCommonInstrs += SuccIterPairs.
size();
2041 for (
auto &SuccIterPair : SuccIterPairs) {
2050bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2051 Instruction *TI, Instruction *I1,
2052 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2062 auto *I2 = *OtherSuccTIs.
begin();
2082 for (PHINode &PN : Succ->
phis()) {
2083 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2084 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2085 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2105 if (!
NT->getType()->isVoidTy()) {
2106 I1->replaceAllUsesWith(NT);
2107 for (Instruction *OtherSuccTI : OtherSuccTIs)
2108 OtherSuccTI->replaceAllUsesWith(NT);
2112 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2118 for (
auto *OtherSuccTI : OtherSuccTIs)
2119 Locs.
push_back(OtherSuccTI->getDebugLoc());
2131 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2133 for (PHINode &PN : Succ->
phis()) {
2134 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2135 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2141 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2151 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2152 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2153 PN.setIncomingValue(i, SI);
2164 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2170 for (BasicBlock *Succ : UniqueSuccessors)
2171 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2185 if (
I->isIntDivRem())
2200 std::optional<unsigned> NumUses;
2201 for (
auto *
I : Insts) {
2204 I->getType()->isTokenTy())
2209 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2217 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2221 NumUses =
I->getNumUses();
2222 else if (NumUses !=
I->getNumUses())
2228 for (
auto *
I : Insts) {
2242 for (
const Use &U : I0->
uses()) {
2243 auto It = PHIOperands.find(&U);
2244 if (It == PHIOperands.end())
2247 if (!
equal(Insts, It->second))
2261 if (HaveIndirectCalls) {
2262 if (!AllCallsAreIndirect)
2266 Value *Callee =
nullptr;
2270 Callee = CurrCallee;
2271 else if (Callee != CurrCallee)
2277 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2283 if (!
all_of(Insts, SameAsI0)) {
2289 for (
auto *
I : Insts)
2290 Ops.push_back(
I->getOperand(OI));
2300 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2305 for (
auto *BB : Blocks) {
2307 I =
I->getPrevNode();
2332 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2335 PN->insertBefore(BBEnd->begin());
2336 for (
auto *
I : Insts)
2337 PN->addIncoming(
I->getOperand(O),
I->getParent());
2346 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2349 for (
auto *
I : Insts)
2363 assert(
Success &&
"We should not be trying to sink callbases "
2364 "with non-intersectable attributes");
2375 PN->replaceAllUsesWith(I0);
2376 PN->eraseFromParent();
2380 for (
auto *
I : Insts) {
2385 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2386 I->replaceAllUsesWith(I0);
2387 I->eraseFromParent();
2437 bool HaveNonUnconditionalPredecessors =
false;
2443 HaveNonUnconditionalPredecessors =
true;
2445 if (UnconditionalPreds.
size() < 2)
2458 for (
const Use &U : PN.incoming_values())
2459 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2460 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2462 Ops.push_back(*IncomingVals[Pred]);
2470 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2483 if (!followedByDeoptOrUnreachable) {
2485 auto IsMemOperand = [](
Use &U) {
2498 unsigned NumPHIInsts = 0;
2499 for (
Use &U : (*LRI)[0]->operands()) {
2500 auto It = PHIOperands.
find(&U);
2501 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2502 return InstructionsToSink.contains(V);
2509 if (IsMemOperand(U) &&
2510 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2517 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2518 return NumPHIInsts <= 1;
2535 while (Idx < ScanIdx) {
2536 if (!ProfitableToSinkInstruction(LRI)) {
2539 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2552 if (Idx < ScanIdx) {
2555 InstructionsToSink = InstructionsProfitableToSink;
2561 !ProfitableToSinkInstruction(LRI) &&
2562 "We already know that the last instruction is unprofitable to sink");
2570 for (
auto *
I : *LRI)
2571 InstructionsProfitableToSink.
erase(
I);
2572 if (!ProfitableToSinkInstruction(LRI)) {
2575 InstructionsToSink = InstructionsProfitableToSink;
2589 if (HaveNonUnconditionalPredecessors) {
2590 if (!followedByDeoptOrUnreachable) {
2598 bool Profitable =
false;
2599 while (Idx < ScanIdx) {
2633 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2635 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2643 NumSinkCommonInstrs++;
2647 ++NumSinkCommonCode;
2653struct CompatibleSets {
2654 using SetTy = SmallVector<InvokeInst *, 2>;
2660 SetTy &getCompatibleSet(InvokeInst *
II);
2662 void insert(InvokeInst *
II);
2665CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2670 for (CompatibleSets::SetTy &Set : Sets) {
2671 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2676 return Sets.emplace_back();
2679void CompatibleSets::insert(InvokeInst *
II) {
2680 getCompatibleSet(
II).emplace_back(
II);
2684 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2687 auto IsIllegalToMerge = [](InvokeInst *
II) {
2688 return II->cannotMerge() ||
II->isInlineAsm();
2690 if (
any_of(Invokes, IsIllegalToMerge))
2698 if (HaveIndirectCalls) {
2699 if (!AllCallsAreIndirect)
2704 for (InvokeInst *
II : Invokes) {
2705 Value *CurrCallee =
II->getCalledOperand();
2706 assert(CurrCallee &&
"There is always a called operand.");
2709 else if (Callee != CurrCallee)
2716 auto HasNormalDest = [](InvokeInst *
II) {
2719 if (
any_of(Invokes, HasNormalDest)) {
2722 if (!
all_of(Invokes, HasNormalDest))
2727 for (InvokeInst *
II : Invokes) {
2729 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2731 NormalBB = CurrNormalBB;
2732 else if (NormalBB != CurrNormalBB)
2740 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2749 for (InvokeInst *
II : Invokes) {
2751 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2753 UnwindBB = CurrUnwindBB;
2755 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2762 Invokes.front()->getUnwindDest(),
2763 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2768 const InvokeInst *II0 = Invokes.front();
2769 for (
auto *
II : Invokes.drop_front())
2774 auto IsIllegalToMergeArguments = [](
auto Ops) {
2775 Use &U0 = std::get<0>(
Ops);
2776 Use &U1 = std::get<1>(
Ops);
2782 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2783 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2784 IsIllegalToMergeArguments))
2796 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2802 bool HasNormalDest =
2807 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2811 II0->
getParent()->getIterator()->getNextNode();
2816 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2820 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2822 if (!HasNormalDest) {
2826 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2834 return MergedInvoke;
2848 SuccBBOfMergedInvoke});
2871 return II->getOperand(U.getOperandNo()) != U.get();
2890 Invokes.
front()->getParent());
2898 if (!MergedDebugLoc)
2899 MergedDebugLoc =
II->getDebugLoc();
2907 OrigSuccBB->removePredecessor(
II->getParent());
2911 BI->setDebugLoc(
II->getDebugLoc());
2913 assert(
Success &&
"Merged invokes with incompatible attributes");
2916 II->replaceAllUsesWith(MergedInvoke);
2917 II->eraseFromParent();
2921 ++NumInvokeSetsFormed;
2957 CompatibleSets Grouper;
2967 if (Invokes.
size() < 2)
2979class EphemeralValueTracker {
2980 SmallPtrSet<const Instruction *, 32> EphValues;
2982 bool isEphemeral(
const Instruction *
I) {
2985 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2986 all_of(
I->users(), [&](
const User *U) {
2987 return EphValues.count(cast<Instruction>(U));
2992 bool track(
const Instruction *
I) {
2993 if (isEphemeral(
I)) {
3044 unsigned MaxNumInstToLookAt = 9;
3048 if (!MaxNumInstToLookAt)
3050 --MaxNumInstToLookAt;
3063 if (
SI->getPointerOperand() == StorePtr &&
3064 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3067 return SI->getValueOperand();
3072 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3073 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3075 bool ExplicitlyDereferenceableOnly;
3083 (!ExplicitlyDereferenceableOnly ||
3101 unsigned &SpeculatedInstructions,
3109 bool HaveRewritablePHIs =
false;
3111 Value *OrigV = PN.getIncomingValueForBlock(BB);
3112 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3119 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3128 HaveRewritablePHIs =
true;
3131 if (!OrigCE && !ThenCE)
3138 if (OrigCost + ThenCost > MaxCost)
3145 ++SpeculatedInstructions;
3146 if (SpeculatedInstructions > 1)
3150 return HaveRewritablePHIs;
3154 std::optional<bool> Invert,
3158 if (BI->getMetadata(LLVMContext::MD_unpredictable))
3165 if (!Invert.has_value())
3168 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3172 return BIEndProb < Likely;
3212bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3213 BasicBlock *ThenBB) {
3229 bool Invert =
false;
3244 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3246 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3248 unsigned SpeculatedInstructions = 0;
3249 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3250 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3251 Value *SpeculatedStoreValue =
nullptr;
3252 StoreInst *SpeculatedStore =
nullptr;
3253 EphemeralValueTracker EphTracker;
3268 if (EphTracker.track(&
I))
3273 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3275 SpeculatedConditionalLoadsStores.
size() <
3279 if (IsSafeCheapLoadStore)
3280 SpeculatedConditionalLoadsStores.
push_back(&
I);
3282 ++SpeculatedInstructions;
3284 if (SpeculatedInstructions > 1)
3288 if (!IsSafeCheapLoadStore &&
3291 (SpeculatedStoreValue =
3294 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3300 if (!SpeculatedStore && SpeculatedStoreValue)
3306 for (Use &
Op :
I.operands()) {
3311 ++SinkCandidateUseCounts[OpI];
3318 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3319 if (Inst->hasNUses(
Count)) {
3320 ++SpeculatedInstructions;
3321 if (SpeculatedInstructions > 1)
3328 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3331 SpeculatedInstructions,
Cost,
TTI);
3332 if (!Convert ||
Cost > Budget)
3336 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3340 if (SpeculatedStoreValue) {
3344 Value *FalseV = SpeculatedStoreValue;
3348 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3378 for (DbgVariableRecord *DbgAssign :
3381 DbgAssign->replaceVariableLocationOp(OrigV, S);
3391 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3394 I.dropUBImplyingAttrsAndMetadata();
3397 if (EphTracker.contains(&
I)) {
3399 I.eraseFromParent();
3405 for (
auto &It : *ThenBB)
3410 !DVR || !DVR->isDbgAssign())
3411 It.dropOneDbgRecord(&DR);
3412 BB->
splice(BI->getIterator(), ThenBB, ThenBB->begin(),
3413 std::prev(ThenBB->end()));
3415 if (!SpeculatedConditionalLoadsStores.
empty())
3421 for (PHINode &PN : EndBB->
phis()) {
3422 unsigned OrigI = PN.getBasicBlockIndex(BB);
3423 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3424 Value *OrigV = PN.getIncomingValue(OrigI);
3425 Value *ThenV = PN.getIncomingValue(ThenI);
3434 Value *TrueV = ThenV, *FalseV = OrigV;
3438 PN.setIncomingValue(OrigI, V);
3439 PN.setIncomingValue(ThenI, V);
3443 for (Instruction *
I : SpeculatedPseudoProbes)
3444 I->eraseFromParent();
3457 if (!ReachesNonLocalUses.
insert(BB).second)
3472 EphemeralValueTracker EphTracker;
3479 if (CI->cannotDuplicate() || CI->isConvergent())
3492 for (
User *U :
I.users()) {
3495 if (UsedInBB == BB) {
3499 NonLocalUseBlocks.
insert(UsedInBB);
3513 if (
I &&
I->getParent() == To)
3529static std::optional<bool>
3550 KnownValues[CB].
insert(Pred);
3554 if (KnownValues.
empty())
3579 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3582 for (
const auto &Pair : KnownValues) {
3599 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3604 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3607 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3617 EdgeBB->setName(RealDest->
getName() +
".critedge");
3618 EdgeBB->moveBefore(RealDest);
3628 TranslateMap[
Cond] = CB;
3641 N->insertInto(EdgeBB, InsertPt);
3644 N->setName(BBI->getName() +
".c");
3655 if (!BBI->use_empty())
3656 TranslateMap[&*BBI] = V;
3657 if (!
N->mayHaveSideEffects()) {
3658 N->eraseFromParent();
3663 if (!BBI->use_empty())
3664 TranslateMap[&*BBI] =
N;
3670 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3671 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3672 SrcDbgCursor = std::next(BBI);
3674 N->cloneDebugInfoFrom(&*BBI);
3683 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3684 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3685 InsertPt->cloneDebugInfoFrom(BI);
3690 EdgeBI->setDebugLoc(BI->getDebugLoc());
3706 return std::nullopt;
3712bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3719 std::optional<bool>
Result;
3720 bool EverChanged =
false;
3726 }
while (Result == std::nullopt);
3735 bool SpeculateUnpredictables) {
3757 return isa<UncondBrInst>(IfBlock->getTerminator());
3760 "Will have either one or two blocks to speculate.");
3767 bool IsUnpredictable = DomBI->getMetadata(LLVMContext::MD_unpredictable);
3768 if (!IsUnpredictable) {
3771 (TWeight + FWeight) != 0) {
3776 if (IfBlocks.
size() == 1) {
3778 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3779 if (BIBBProb >= Likely)
3782 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3791 if (IfCondPhiInst->getParent() == BB)
3799 unsigned NumPhis = 0;
3812 if (SpeculateUnpredictables && IsUnpredictable)
3813 Budget +=
TTI.getBranchMispredictPenalty();
3826 AggressiveInsts, Cost, Budget,
TTI, AC,
3827 ZeroCostInstructions) ||
3829 AggressiveInsts, Cost, Budget,
TTI, AC,
3830 ZeroCostInstructions))
3843 auto IsBinOpOrAndEq = [](
Value *V) {
3866 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3879 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3881 <<
" F: " << IfFalse->
getName() <<
"\n");
3898 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3903 PN->eraseFromParent();
3909 Builder.CreateBr(BB);
3918 DomBI->eraseFromParent();
3930 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3931 if (
Opc == Instruction::And)
3932 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3933 if (
Opc == Instruction::Or)
3934 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3946 bool PredHasWeights =
3948 bool SuccHasWeights =
3950 if (PredHasWeights || SuccHasWeights) {
3951 if (!PredHasWeights)
3952 PredTrueWeight = PredFalseWeight = 1;
3953 if (!SuccHasWeights)
3954 SuccTrueWeight = SuccFalseWeight = 1;
3964static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3967 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
3969 "PredBB must be a predecessor of BB.");
3975 if (
TTI && !PBI->getMetadata(LLVMContext::MD_unpredictable) &&
3977 (PTWeight + PFWeight) != 0) {
3980 Likely =
TTI->getPredictableBranchThreshold();
3985 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3986 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3990 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3993 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3994 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4000 return std::nullopt;
4013 bool InvertPredCond;
4014 std::tie(CommonSucc,
Opc, InvertPredCond) =
4017 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4024 {LLVMContext::MD_annotation});
4027 if (InvertPredCond) {
4040 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4043 SuccTrueWeight, SuccFalseWeight)) {
4049 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4054 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4055 PredTrueWeight * SuccFalseWeight);
4061 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4062 PredFalseWeight * SuccTrueWeight);
4064 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4073 PBI->setMetadata(LLVMContext::MD_prof,
nullptr);
4084 if (
MDNode *LoopMD = BI->getMetadata(LLVMContext::MD_loop))
4085 PBI->setMetadata(LLVMContext::MD_loop, LoopMD);
4106 if (!MDWeights.
empty()) {
4107 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4112 ++NumFoldBranchToCommonDest;
4119 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4120 return U->getType()->isVectorTy();
4131 unsigned BonusInstThreshold) {
4140 Cond->getParent() != BB || !
Cond->hasOneUse())
4161 bool InvertPredCond;
4163 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4195 unsigned NumBonusInsts = 0;
4196 bool SawVectorOp =
false;
4197 const unsigned PredCount = Preds.
size();
4201 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4218 NumBonusInsts += PredCount;
4226 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4229 return PN->getIncomingBlock(U) == BB;
4230 return UI->
getParent() == BB &&
I.comesBefore(UI);
4234 if (!
all_of(
I.uses(), IsBCSSAUse))
4238 BonusInstThreshold *
4254 for (
auto *BB : {BB1, BB2}) {
4270 Value *AlternativeV =
nullptr) {
4296 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4297 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4305 if (!AlternativeV &&
4311 PHI->addIncoming(V, BB);
4321 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4330 if (!PStore || !QStore)
4353 if (
I.mayReadOrWriteMemory())
4355 for (
auto &
I : *QFB)
4356 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4359 for (
auto &
I : *QTB)
4360 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4364 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4378 for (
auto &
I : *BB) {
4380 if (
I.isTerminator())
4398 "When we run out of budget we will eagerly return from within the "
4399 "per-instruction loop.");
4403 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4405 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4406 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4442 InvertPCond ^= (PStore->
getParent() != PTB);
4443 InvertQCond ^= (QStore->
getParent() != QTB);
4464 {CombinedWeights[0], CombinedWeights[1]},
4471 SI->copyMetadata(*QStore);
4477 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4480 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4543 bool InvertPCond =
false, InvertQCond =
false;
4545 if (PFB == QBI->getParent()) {
4549 if (QFB == PostBB) {
4556 if (PTB == QBI->getParent())
4567 if (!HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) ||
4568 !HasOnePredAndOneSucc(QFB, QBI->getParent(), PostBB))
4570 if ((PTB && !HasOnePredAndOneSucc(PTB, PBI->getParent(), QBI->getParent())) ||
4571 (QTB && !HasOnePredAndOneSucc(QTB, QBI->getParent(), PostBB)))
4573 if (!QBI->getParent()->hasNUses(2))
4579 for (
auto *BB : {PTB, PFB}) {
4584 PStoreAddresses.
insert(
SI->getPointerOperand());
4586 for (
auto *BB : {QTB, QFB}) {
4591 QStoreAddresses.
insert(
SI->getPointerOperand());
4597 auto &CommonAddresses = PStoreAddresses;
4600 for (
auto *Address : CommonAddresses)
4603 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4621 !BI->getParent()->getSinglePredecessor())
4623 if (!IfFalseBB->
phis().empty())
4633 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4638 NoSideEffects(*BI->getParent())) {
4650 NoSideEffects(*BI->getParent())) {
4707 if (&*BB->
begin() != BI)
4735 if (!PBI->getMetadata(LLVMContext::MD_unpredictable) &&
4737 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4741 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4744 if (CommonDestProb >= Likely)
4754 unsigned NumPhis = 0;
4765 <<
"AND: " << *BI->getParent());
4776 if (OtherDest == BB) {
4784 OtherDest = InfLoopBlock;
4796 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4800 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4804 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4819 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4820 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4823 SuccTrueWeight, SuccFalseWeight);
4825 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4826 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4827 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4828 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4832 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4833 PredOther * SuccCommon,
4834 PredOther * SuccOther};
4842 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4844 assert(
SI->getCondition() == PBICond);
4861 Value *BIV = PN.getIncomingValueForBlock(BB);
4862 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->getParent());
4863 Value *PBIV = PN.getIncomingValue(PBBIdx);
4867 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4868 PN.setIncomingValue(PBBIdx, NV);
4872 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4873 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4893bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4895 BasicBlock *FalseBB,
4896 uint32_t TrueWeight,
4897 uint32_t FalseWeight) {
4904 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4906 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4909 for (BasicBlock *Succ :
successors(OldTerm)) {
4911 if (Succ == KeepEdge1)
4912 KeepEdge1 =
nullptr;
4913 else if (Succ == KeepEdge2)
4914 KeepEdge2 =
nullptr;
4919 if (Succ != TrueBB && Succ != FalseBB)
4920 RemovedSuccessors.
insert(Succ);
4928 if (!KeepEdge1 && !KeepEdge2) {
4929 if (TrueBB == FalseBB) {
4940 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4960 SmallVector<DominatorTree::UpdateType, 2> Updates;
4962 for (
auto *RemovedSuccessor : RemovedSuccessors)
4963 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4974bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4979 if (!TrueVal || !FalseVal)
4984 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4985 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4988 uint32_t TrueWeight = 0, FalseWeight = 0;
4989 SmallVector<uint64_t, 8> Weights;
4993 if (Weights.
size() == 1 +
SI->getNumCases()) {
4995 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4997 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5002 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5011bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5025 SmallVector<uint32_t> SelectBranchWeights(2);
5029 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5030 SelectBranchWeights[0],
5031 SelectBranchWeights[1]);
5051bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5055 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5101bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5120 ConstantInt *NewCaseVal;
5128 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5134 SelectTrueVal = Builder.
getTrue();
5135 SelectFalseVal = Builder.
getFalse();
5138 SelectCond =
Select->getCondition();
5140 if (SelectCond != ICI)
5142 SelectTrueVal =
Select->getTrueValue();
5143 SelectFalseVal =
Select->getFalseValue();
5148 if (
SI->getCondition() != IcmpCond)
5154 if (
SI->getDefaultDest() != BB) {
5155 ConstantInt *VVal =
SI->findCaseDest(BB);
5156 assert(VVal &&
"Should have a unique destination value");
5164 return requestResimplify();
5170 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5172 if (Predicate == ICmpInst::ICMP_EQ)
5180 return requestResimplify();
5187 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5193 Value *DefaultCst = SelectFalseVal;
5194 Value *NewCst = SelectTrueVal;
5202 Select->replaceAllUsesWith(DefaultCst);
5203 Select->eraseFromParent();
5209 SmallVector<DominatorTree::UpdateType, 2> Updates;
5216 SwitchInstProfUpdateWrapper SIW(*SI);
5217 auto W0 = SIW.getSuccessorWeight(0);
5220 NewW = ((uint64_t(*W0) + 1) >> 1);
5221 SIW.setSuccessorWeight(0, *NewW);
5223 SIW.addCase(NewCaseVal, NewBB, NewW);
5225 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5234 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5242bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5244 const DataLayout &
DL) {
5254 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5256 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5257 Value *CompVal = ConstantCompare.CompValue;
5258 unsigned UsedICmps = ConstantCompare.UsedICmps;
5259 Value *ExtraCase = ConstantCompare.Extra;
5260 bool TrueWhenEqual = ConstantCompare.IsEq;
5277 if (ExtraCase && Values.
size() < 2)
5280 SmallVector<uint32_t> BranchWeights;
5287 if (!TrueWhenEqual) {
5290 std::swap(BranchWeights[0], BranchWeights[1]);
5296 <<
" cases into SWITCH. BB is:\n"
5299 SmallVector<DominatorTree::UpdateType, 2> Updates;
5306 nullptr,
"switch.early.test");
5317 AssumptionCache *AC =
Options.AC;
5323 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5330 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5336 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5337 <<
"\nEXTRABB = " << *BB);
5345 "Should not end up here with unstable pointers");
5347 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5352 if (Values.
front()->getValue() - Values.
back()->getValue() ==
5353 Values.
size() - 1) {
5355 Values.
back()->getValue(), Values.
front()->getValue() + 1);
5357 ICmpInst::Predicate Pred;
5375 SmallVector<uint32_t> NewWeights(Values.
size() + 1);
5376 NewWeights[0] = BranchWeights[1];
5379 V = BranchWeights[0] / Values.
size();
5384 for (ConstantInt *Val : Values)
5385 New->addCase(Val, EdgeBB);
5393 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5403 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5407bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5409 return simplifyCommonResume(RI);
5413 return simplifySingleResume(RI);
5426 switch (IntrinsicID) {
5427 case Intrinsic::dbg_declare:
5428 case Intrinsic::dbg_value:
5429 case Intrinsic::dbg_label:
5430 case Intrinsic::lifetime_end:
5440bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5449 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5453 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5455 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5456 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5460 if (IncomingBB->getUniqueSuccessor() != BB)
5465 if (IncomingValue != LandingPad)
5469 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5470 TrivialUnwindBlocks.
insert(IncomingBB);
5474 if (TrivialUnwindBlocks.
empty())
5478 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5482 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5485 for (BasicBlock *Pred :
5496 TrivialBB->getTerminator()->eraseFromParent();
5497 new UnreachableInst(RI->
getContext(), TrivialBB);
5499 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5506 return !TrivialUnwindBlocks.empty();
5510bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5514 "Resume must unwind the exception that caused control to here");
5570 int Idx = DestPN.getBasicBlockIndex(BB);
5584 Value *SrcVal = DestPN.getIncomingValue(Idx);
5587 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5591 DestPN.addIncoming(Incoming, Pred);
5618 std::vector<DominatorTree::UpdateType> Updates;
5622 if (UnwindDest ==
nullptr) {
5663 if (!SuccessorCleanupPad)
5672 SuccessorCleanupPad->eraseFromParent();
5681bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5698bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5730 BBI->dropDbgRecords();
5734 BBI->eraseFromParent();
5740 if (&BB->
front() != UI)
5743 std::vector<DominatorTree::UpdateType> Updates;
5746 for (BasicBlock *Predecessor : Preds) {
5754 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5765 "The destinations are guaranteed to be different here.");
5766 CallInst *Assumption;
5782 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5784 SwitchInstProfUpdateWrapper SU(*SI);
5785 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5786 if (i->getCaseSuccessor() != BB) {
5791 i = SU.removeCase(i);
5796 if (DTU &&
SI->getDefaultDest() != BB)
5797 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5799 if (
II->getUnwindDest() == BB) {
5805 if (!CI->doesNotThrow())
5806 CI->setDoesNotThrow();
5810 if (CSI->getUnwindDest() == BB) {
5821 E = CSI->handler_end();
5824 CSI->removeHandler(
I);
5831 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5832 if (CSI->getNumHandlers() == 0) {
5833 if (CSI->hasUnwindDest()) {
5837 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5838 Updates.push_back({DominatorTree::Insert,
5839 PredecessorOfPredecessor,
5840 CSI->getUnwindDest()});
5841 Updates.push_back({DominatorTree::Delete,
5842 PredecessorOfPredecessor, Predecessor});
5845 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5852 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5853 for (BasicBlock *EHPred : EHPreds)
5857 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5858 CSI->eraseFromParent();
5863 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5864 "Expected to always have an unwind to BB.");
5866 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5894static std::optional<ContiguousCasesResult>
5901 const APInt &Min = Cases.
back()->getValue();
5902 const APInt &Max = Cases.
front()->getValue();
5904 size_t ContiguousOffset = Cases.
size() - 1;
5905 if (
Offset == ContiguousOffset) {
5924 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
5925 return L->getValue() != R->getValue() + 1;
5927 if (It == Cases.
end())
5928 return std::nullopt;
5929 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5930 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5934 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5937 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5945 return std::nullopt;
5950 bool RemoveOrigDefaultBlock =
true) {
5952 auto *BB = Switch->getParent();
5953 auto *OrigDefaultBlock = Switch->getDefaultDest();
5954 if (RemoveOrigDefaultBlock)
5955 OrigDefaultBlock->removePredecessor(BB);
5959 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5961 Switch->setDefaultDest(&*NewDefaultBlock);
5965 if (RemoveOrigDefaultBlock &&
5975bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5977 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5979 bool HasDefault = !
SI->defaultDestUnreachable();
5981 auto *BB =
SI->getParent();
5983 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5988 for (
auto Case :
SI->cases()) {
5992 if (Dest == DestA) {
5998 if (Dest == DestB) {
6008 "Single-destination switch should have been folded.");
6010 assert(DestB !=
SI->getDefaultDest());
6011 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6015 std::optional<ContiguousCasesResult> ContiguousCases;
6018 if (!HasDefault && CasesA.
size() == 1)
6019 ContiguousCases = ContiguousCasesResult{
6027 else if (CasesB.
size() == 1)
6028 ContiguousCases = ContiguousCasesResult{
6037 else if (!HasDefault)
6041 if (!ContiguousCases)
6045 if (!ContiguousCases)
6048 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6054 Max->getValue() - Min->getValue() + 1);
6057 assert(
Max->getValue() == Min->getValue());
6062 else if (NumCases->
isNullValue() && !Cases->empty()) {
6066 if (!
Offset->isNullValue())
6074 SmallVector<uint64_t, 8> Weights;
6076 if (Weights.
size() == 1 +
SI->getNumCases()) {
6077 uint64_t TrueWeight = 0;
6078 uint64_t FalseWeight = 0;
6079 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6080 if (
SI->getSuccessor(
I) == Dest)
6081 TrueWeight += Weights[
I];
6083 FalseWeight += Weights[
I];
6085 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6096 unsigned PreviousEdges = Cases->size();
6097 if (Dest ==
SI->getDefaultDest())
6099 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6100 PHI.removeIncomingValue(
SI->getParent());
6103 unsigned PreviousEdges = OtherCases->size();
6104 if (OtherDest ==
SI->getDefaultDest())
6106 unsigned E = PreviousEdges - 1;
6110 for (
unsigned I = 0;
I !=
E; ++
I)
6111 PHI.removeIncomingValue(
SI->getParent());
6119 auto *UnreachableDefault =
SI->getDefaultDest();
6122 SI->eraseFromParent();
6124 if (!HasDefault && DTU)
6125 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
6143 unsigned MaxSignificantBitsInCond =
6150 for (
const auto &Case :
SI->cases()) {
6151 auto *
Successor = Case.getCaseSuccessor();
6162 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6168 }
else if (IsKnownValuesValid)
6169 KnownValues.
erase(CaseC);
6176 bool HasDefault = !
SI->defaultDestUnreachable();
6177 const unsigned NumUnknownBits =
6180 if (HasDefault && DeadCases.
empty()) {
6186 if (NumUnknownBits < 64 ) {
6187 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6188 if (
SI->getNumCases() == AllNumCases) {
6195 if (
SI->getNumCases() == AllNumCases - 1) {
6196 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6198 if (CondTy->getIntegerBitWidth() > 64 ||
6199 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6203 for (
const auto &Case :
SI->cases())
6204 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6206 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6208 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6218 if (DeadCases.
empty())
6224 assert(CaseI !=
SI->case_default() &&
6225 "Case was not found. Probably mistake in DeadCases forming.");
6227 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6232 std::vector<DominatorTree::UpdateType> Updates;
6233 for (
auto *
Successor : UniqueSuccessors)
6234 if (NumPerSuccessorCases[
Successor] == 0)
6261 int Idx =
PHI.getBasicBlockIndex(BB);
6262 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6264 Value *InValue =
PHI.getIncomingValue(Idx);
6265 if (InValue != CaseValue)
6281 ForwardingNodesMap ForwardingNodes;
6284 for (
const auto &Case :
SI->cases()) {
6286 BasicBlock *CaseDest = Case.getCaseSuccessor();
6305 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6306 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6307 count(Phi.blocks(), SwitchBlock) == 1) {
6308 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6316 ForwardingNodes[Phi].push_back(PhiIdx);
6319 for (
auto &ForwardingNode : ForwardingNodes) {
6320 PHINode *Phi = ForwardingNode.first;
6326 for (
int Index : Indexes)
6327 Phi->setIncomingValue(Index,
SI->getCondition());
6337 if (
C->isThreadDependent())
6339 if (
C->isDLLImportDependent())
6347 if (
C->getType()->isScalableTy())
6358 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6385 if (
A->isAllOnesValue())
6387 if (
A->isNullValue())
6393 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6418 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6420 if (
I.isTerminator()) {
6422 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6425 CaseDest =
I.getSuccessor(0);
6432 for (
auto &
Use :
I.uses()) {
6435 if (
I->getParent() == CaseDest)
6438 if (Phi->getIncomingBlock(
Use) == CaseDest)
6451 *CommonDest = CaseDest;
6453 if (CaseDest != *CommonDest)
6458 int Idx =
PHI.getBasicBlockIndex(Pred);
6471 Res.push_back(std::make_pair(&
PHI, ConstVal));
6474 return Res.
size() > 0;
6480 SwitchCaseResultVectorTy &UniqueResults,
6482 for (
auto &
I : UniqueResults) {
6483 if (
I.first == Result) {
6484 I.second.push_back(CaseVal);
6485 return I.second.size();
6488 UniqueResults.push_back(
6499 SwitchCaseResultVectorTy &UniqueResults,
6503 uintptr_t MaxUniqueResults) {
6504 for (
const auto &
I :
SI->cases()) {
6518 const size_t NumCasesForResult =
6526 if (UniqueResults.size() > MaxUniqueResults)
6542 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6544 return DefaultResult ||
SI->defaultDestUnreachable();
6565 const bool HasBranchWeights =
6568 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6569 ResultVector[1].second.size() == 1) {
6570 ConstantInt *FirstCase = ResultVector[0].second[0];
6571 ConstantInt *SecondCase = ResultVector[1].second[0];
6572 Value *SelectValue = ResultVector[1].first;
6573 if (DefaultResult) {
6574 Value *ValueCompare =
6575 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6576 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6577 DefaultResult,
"switch.select");
6579 SI && HasBranchWeights) {
6586 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6590 Value *ValueCompare =
6591 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6592 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6593 SelectValue,
"switch.select");
6599 size_t FirstCasePos = (Condition !=
nullptr);
6600 size_t SecondCasePos = FirstCasePos + 1;
6601 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6603 {BranchWeights[FirstCasePos],
6604 DefaultCase + BranchWeights[SecondCasePos]},
6611 if (ResultVector.size() == 1 && DefaultResult) {
6613 unsigned CaseCount = CaseValues.
size();
6626 for (
auto *Case : CaseValues) {
6627 if (Case->getValue().slt(MinCaseVal->
getValue()))
6629 AndMask &= Case->getValue();
6639 if (FreeBits ==
Log2_32(CaseCount)) {
6640 Value *
And = Builder.CreateAnd(Condition, AndMask);
6641 Value *Cmp = Builder.CreateICmpEQ(
6644 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6660 for (
auto *Case : CaseValues)
6661 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6667 Condition = Builder.CreateSub(Condition, MinCaseVal);
6668 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6669 Value *Cmp = Builder.CreateICmpEQ(
6672 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6685 if (CaseValues.
size() == 2) {
6686 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6687 "switch.selectcmp.case1");
6688 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6689 "switch.selectcmp.case2");
6690 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6692 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6712 std::vector<DominatorTree::UpdateType> Updates;
6719 Builder.CreateBr(DestBB);
6723 PHI->removeIncomingValueIf(
6724 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6725 PHI->addIncoming(SelectValue, SelectBB);
6728 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6734 if (DTU && RemovedSuccessors.
insert(Succ).second)
6737 SI->eraseFromParent();
6752 SwitchCaseResultVectorTy UniqueResults;
6758 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6759 Builder.SetInsertPoint(
SI);
6762 [[maybe_unused]]
auto HasWeights =
6767 (BranchWeights.
size() >=
6768 UniqueResults.size() + (DefaultResult !=
nullptr)));
6771 Builder,
DL, BranchWeights);
6783class SwitchReplacement {
6790 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6791 Constant *DefaultValue,
const DataLayout &
DL,
6792 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
6801 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6808 bool isLookupTable();
6845 ConstantInt *BitMap =
nullptr;
6846 IntegerType *BitMapElementTy =
nullptr;
6849 ConstantInt *LinearOffset =
nullptr;
6850 ConstantInt *LinearMultiplier =
nullptr;
6851 bool LinearMapValWrapped =
false;
6859SwitchReplacement::SwitchReplacement(
6861 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6862 Constant *DefaultValue,
const DataLayout &
DL,
6863 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
6864 : DefaultValue(DefaultValue) {
6865 assert(Values.size() &&
"Can't build lookup table without values!");
6866 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6869 SingleValue = Values.begin()->second;
6871 ValueType = Values.begin()->second->getType();
6875 for (
const auto &[CaseVal, CaseRes] : Values) {
6878 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6879 TableContents[Idx] = CaseRes;
6886 if (Values.size() < TableSize) {
6888 "Need a default value to fill the lookup table holes.");
6891 if (!TableContents[
I])
6892 TableContents[
I] = DefaultValue;
6898 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6899 SingleValue =
nullptr;
6905 Kind = SingleValueKind;
6912 bool LinearMappingPossible =
true;
6917 bool NonMonotonic =
false;
6918 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6935 LinearMappingPossible =
false;
6940 APInt Dist = Val - PrevVal;
6943 }
else if (Dist != DistToPrev) {
6944 LinearMappingPossible =
false;
6952 if (LinearMappingPossible) {
6954 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6955 APInt M = LinearMultiplier->getValue();
6956 bool MayWrap =
true;
6957 if (
isIntN(M.getBitWidth(), TableSize - 1))
6958 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6959 LinearMapValWrapped = NonMonotonic || MayWrap;
6960 Kind = LinearMapKind;
6966 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6968 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6970 TableInt <<=
IT->getBitWidth();
6974 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6977 BitMap = ConstantInt::get(M.getContext(), TableInt);
6978 BitMapElementTy =
IT;
6989 unsigned NeededBitWidth =
6990 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7003 Kind = LookupTableKind;
7009 case SingleValueKind:
7011 case LinearMapKind: {
7015 false,
"switch.idx.cast");
7016 if (!LinearMultiplier->
isOne())
7017 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7019 !LinearMapValWrapped);
7021 if (!LinearOffset->
isZero())
7024 !LinearMapValWrapped);
7041 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7042 "switch.shiftamt",
true,
true);
7045 Value *DownShifted =
7046 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7048 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7050 case LookupTableKind: {
7053 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7054 true, GlobalVariable::PrivateLinkage,
7055 Initializer,
"switch.table." +
Func->getName());
7056 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7059 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
7060 Type *IndexTy =
DL.getIndexType(Table->getType());
7063 if (
Index->getType() != IndexTy) {
7064 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7068 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7071 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7075 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7084bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7086 Type *ElementType) {
7094 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7096 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7102 if (
TTI.isTypeLegal(Ty))
7117 DL.fitsInLegalInteger(
IT->getBitWidth());
7120Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7122bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7124bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7131 const uint64_t MinDensity = OptSize ? 40 : 10;
7136 return NumCases * 100 >= CaseRange * MinDensity;
7157 if (
SI->getNumCases() > TableSize)
7160 bool AllTablesFitInRegister =
true;
7161 bool HasIllegalType =
false;
7162 for (
const auto &Ty : ResultTypes) {
7167 AllTablesFitInRegister =
7168 AllTablesFitInRegister &&
7169 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7174 if (HasIllegalType && !AllTablesFitInRegister)
7179 if (AllTablesFitInRegister)
7187 SI->getFunction()->hasOptSize());
7197 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7200 return all_of(ResultTypes, [&](
const auto &ResultType) {
7201 return SwitchReplacement::wouldFitInRegister(
7229 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
7251 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7256 for (
auto ValuePair : Values) {
7259 if (!CaseConst || CaseConst == DefaultConst ||
7260 (CaseConst != TrueConst && CaseConst != FalseConst))
7268 BasicBlock *BranchBlock = RangeCheckBranch->getParent();
7274 if (DefaultConst == FalseConst) {
7277 ++NumTableCmpReuses;
7280 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7281 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7282 RangeCheckBranch->getIterator());
7284 ++NumTableCmpReuses;
7294 bool ConvertSwitchToLookupTable) {
7295 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7309 if (
SI->getNumCases() < 3)
7331 MinCaseVal = CaseVal;
7333 MaxCaseVal = CaseVal;
7350 It->second.push_back(std::make_pair(CaseVal,
Value));
7358 bool HasDefaultResults =
7360 DefaultResultsList,
DL,
TTI);
7361 for (
const auto &
I : DefaultResultsList) {
7364 DefaultResults[
PHI] = Result;
7368 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7371 if (UseSwitchConditionAsTableIndex) {
7373 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7378 TableIndexOffset = MinCaseVal;
7385 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7387 bool TableHasHoles = (NumResults < TableSize);
7392 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7400 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7403 if (
SI->getNumCases() < 4)
7405 if (!
DL.fitsInLegalInteger(TableSize))
7414 if (UseSwitchConditionAsTableIndex) {
7415 TableIndex =
SI->getCondition();
7416 if (HasDefaultResults) {
7428 all_of(ResultTypes, [&](
const auto &ResultType) {
7429 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7434 TableSize = std::max(UpperBound, TableSize);
7437 DefaultIsReachable =
false;
7445 const auto &ResultList = ResultLists[
PHI];
7447 Type *ResultType = ResultList.begin()->second->getType();
7452 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7453 ResultList, DefaultVal,
DL,
TTI, FuncName);
7454 PhiToReplacementMap.
insert({
PHI, Replacement});
7457 bool AnyLookupTables =
any_of(
7458 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7459 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7460 [](
auto &KV) {
return KV.second.isBitMap(); });
7468 if (AnyLookupTables &&
7469 (!
TTI.shouldBuildLookupTables() ||
7475 if (!ConvertSwitchToLookupTable &&
7476 (AnyLookupTables || AnyBitMaps || NeedMask))
7479 Builder.SetInsertPoint(
SI);
7482 if (!UseSwitchConditionAsTableIndex) {
7485 bool MayWrap =
true;
7486 if (!DefaultIsReachable) {
7491 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7492 "switch.tableidx",
false,
7496 std::vector<DominatorTree::UpdateType> Updates;
7502 assert(MaxTableSize >= TableSize &&
7503 "It is impossible for a switch to have more entries than the max "
7504 "representable value of its input integer type's size.");
7509 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7514 Builder.SetInsertPoint(
SI);
7515 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7516 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7517 Builder.CreateBr(LookupBB);
7523 Value *Cmp = Builder.CreateICmpULT(
7524 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7526 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7527 CondBranch = RangeCheckBranch;
7533 Builder.SetInsertPoint(LookupBB);
7539 MaskBB->
setName(
"switch.hole_check");
7546 APInt MaskInt(TableSizePowOf2, 0);
7547 APInt One(TableSizePowOf2, 1);
7549 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7550 for (
const auto &Result : ResultList) {
7553 MaskInt |= One << Idx;
7555 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7562 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7563 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7564 Value *LoBit = Builder.CreateTrunc(
7566 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7571 Builder.SetInsertPoint(LookupBB);
7575 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7578 SI->getDefaultDest()->removePredecessor(BB,
7585 const ResultListTy &ResultList = ResultLists[
PHI];
7586 auto Replacement = PhiToReplacementMap.
at(
PHI);
7587 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7590 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7593 for (
auto *
User :
PHI->users()) {
7595 Replacement.getDefaultValue(), ResultList);
7599 PHI->addIncoming(Result, LookupBB);
7602 Builder.CreateBr(CommonDest);
7614 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7617 if (Succ ==
SI->getDefaultDest()) {
7618 if (HasBranchWeights)
7619 ToDefaultWeight += BranchWeights[
I];
7623 if (DTU && RemovedSuccessors.
insert(Succ).second)
7625 if (HasBranchWeights)
7626 ToLookupWeight += BranchWeights[
I];
7628 SI->eraseFromParent();
7629 if (HasBranchWeights)
7636 ++NumLookupTablesHoles;
7652 if (CondTy->getIntegerBitWidth() > 64 ||
7653 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7657 if (
SI->getNumCases() < 4)
7665 for (
const auto &
C :
SI->cases())
7666 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7674 int64_t
Base = Values[0];
7675 for (
auto &V : Values)
7688 unsigned Shift = 64;
7689 for (
auto &V : Values)
7693 for (
auto &V : Values)
7694 V = (int64_t)((
uint64_t)V >> Shift);
7711 Builder.SetInsertPoint(
SI);
7714 Value *Rot = Builder.CreateIntrinsic(
7715 Ty, Intrinsic::fshl,
7716 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7717 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7719 for (
auto Case :
SI->cases()) {
7720 auto *Orig = Case.getCaseValue();
7721 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7766 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
7767 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
7783 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
7786 return !Updates.
empty();
7816 Value *Condition =
SI->getCondition();
7820 if (CondTy->getIntegerBitWidth() > 64 ||
7821 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7833 if (
SI->getNumCases() < 4)
7838 for (
const auto &Case :
SI->cases()) {
7839 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7851 SI->getFunction()->hasOptSize()))
7855 Builder.SetInsertPoint(
SI);
7857 if (!
SI->defaultDestUnreachable()) {
7860 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
7861 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
7863 auto *OrigBB =
SI->getParent();
7864 auto *DefaultCaseBB =
SI->getDefaultDest();
7866 auto It = OrigBB->getTerminator()->getIterator();
7879 NewWeights[1] = Weights[0] / 2;
7880 NewWeights[0] = OrigDenominator - NewWeights[1];
7892 Weights[0] = NewWeights[1];
7893 uint64_t CasesDenominator = OrigDenominator - Weights[0];
7895 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
7900 BI->setDebugLoc(
SI->getDebugLoc());
7901 It->eraseFromParent();
7909 for (
auto &Case :
SI->cases()) {
7910 auto *OrigValue = Case.getCaseValue();
7911 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7912 OrigValue->getValue().countr_zero()));
7916 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7919 SI->setCondition(ConditionTrailingZeros);
7929 if (!Cmp || !Cmp->hasOneUse())
7940 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7943 if (
SI->getNumCases() == 2) {
7950 Succ =
SI->getDefaultDest();
7951 SuccWeight = Weights[0];
7953 for (
auto &Case :
SI->cases()) {
7954 std::optional<int64_t> Val =
7958 if (!Missing.erase(*Val))
7963 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7966 assert(Missing.size() == 1 &&
"Should have one case left");
7967 Res = *Missing.begin();
7968 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7970 Unreachable =
SI->getDefaultDest();
7972 for (
auto &Case :
SI->cases()) {
7973 BasicBlock *NewSucc = Case.getCaseSuccessor();
7974 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7977 OtherSuccWeight += Weight;
7980 SuccWeight = Weight;
7981 }
else if (Succ == NewSucc) {
7987 for (
auto &Case :
SI->cases()) {
7988 std::optional<int64_t> Val =
7990 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7992 if (Case.getCaseSuccessor() == Succ) {
8014 if (Cmp->isSigned())
8017 MDNode *NewWeights =
nullptr;
8023 Builder.SetInsertPoint(
SI->getIterator());
8024 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
8025 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8026 SI->getMetadata(LLVMContext::MD_unpredictable));
8030 SI->eraseFromParent();
8031 Cmp->eraseFromParent();
8032 if (DTU && Unreachable)
8057 assert(
BB &&
"Expected non-null BB");
8059 if (
BB->isEntryBlock())
8072 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8077 if (&
BB->front() != &
BB->back())
8092 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8103 return (*EBW->PhiPredIVs)[&Phi][BB];
8125 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8128 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8129 return PredIVs[
A] == PredIVs[
B];
8138 if (Candidates.
size() < 2)
8153 assert(Succ &&
"Expected unconditional BB");
8163 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8166 for (
auto &
IV : Phi->incoming_values())
8167 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8185 bool MadeChange =
false;
8199 if (!LivePreds.
contains(PredOfDead))
8206 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8207 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8212 T->replaceSuccessorWith(
Dead, Live);
8217 for (
const auto &EBW : BBs2Merge) {
8220 const auto &[It, Inserted] =
Keep.insert(&EBW);
8229 if (KeepBB == DeadBB)
8233 RedirectIncomingEdges(DeadBB, KeepBB);
8242 if (DTU && !Updates.
empty())
8248bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8249 DomTreeUpdater *DTU) {
8251 SmallSetVector<BasicBlock *, 16> FilteredArms(
8257bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8258 DomTreeUpdater *DTU) {
8269 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8275bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8278 if (isValueEqualityComparison(SI)) {
8282 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8283 return requestResimplify();
8287 if (simplifySwitchOnSelect(SI,
Select))
8288 return requestResimplify();
8292 if (SI == &*BB->
begin())
8293 if (foldValueComparisonIntoPredecessors(SI, Builder))
8294 return requestResimplify();
8300 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8301 return requestResimplify();
8305 return requestResimplify();
8308 return requestResimplify();
8311 return requestResimplify();
8314 return requestResimplify();
8319 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8321 Options.ConvertSwitchToLookupTable))
8322 return requestResimplify();
8325 return requestResimplify();
8328 return requestResimplify();
8331 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8332 return requestResimplify();
8336 if (simplifyDuplicateSwitchArms(SI, DTU))
8337 return requestResimplify();
8340 return requestResimplify();
8345bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8348 SmallVector<uint32_t> BranchWeights;
8352 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8353 if (HasBranchWeights)
8358 SmallPtrSet<Value *, 8> Succs;
8359 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8364 RemovedSuccs.
insert(Dest);
8374 std::vector<DominatorTree::UpdateType> Updates;
8375 Updates.reserve(RemovedSuccs.
size());
8376 for (
auto *RemovedSucc : RemovedSuccs)
8377 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8394 if (HasBranchWeights) {
8401 if (simplifyIndirectBrOnSelect(IBI, SI))
8402 return requestResimplify();
8438 if (BB == OtherPred)
8446 if (!BI2 || !BI2->isIdenticalTo(BI))
8449 std::vector<DominatorTree::UpdateType> Updates;
8456 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8457 "unexpected successor");
8458 II->setUnwindDest(OtherPred);
8473 Builder.CreateUnreachable();
8474 BI->eraseFromParent();
8482bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8494 bool NeedCanonicalLoop =
8508 if (
I->isTerminator() &&
8509 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8533 if (!PPred || (PredPred && PredPred != PPred))
8574 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8578 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8604 bool HasWeight =
false;
8609 BBTWeight = BBFWeight = 1;
8614 BB1TWeight = BB1FWeight = 1;
8619 BB2TWeight = BB2FWeight = 1;
8621 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8622 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8629bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
8633 "Tautological conditional branch should have been eliminated already.");
8636 if (!
Options.SimplifyCondBranch ||
8637 BI->getFunction()->hasFnAttribute(Attribute::OptForFuzzing))
8641 if (isValueEqualityComparison(BI)) {
8646 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8647 return requestResimplify();
8651 for (
auto &
I : *BB) {
8656 if (foldValueComparisonIntoPredecessors(BI, Builder))
8657 return requestResimplify();
8663 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8676 return requestResimplify();
8682 if (
Options.SpeculateBlocks &&
8685 return requestResimplify();
8694 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8695 return requestResimplify();
8697 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8699 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8700 auto CanSpeculateConditionalLoadsStores = [&]() {
8702 for (Instruction &
I : *Succ) {
8703 if (
I.isTerminator()) {
8704 if (
I.getNumSuccessors() > 1)
8708 SpeculatedConditionalLoadsStores.
size() ==
8712 SpeculatedConditionalLoadsStores.
push_back(&
I);
8715 return !SpeculatedConditionalLoadsStores.
empty();
8718 if (CanSpeculateConditionalLoadsStores()) {
8720 std::nullopt,
nullptr);
8721 return requestResimplify();
8731 return requestResimplify();
8740 return requestResimplify();
8746 if (foldCondBranchOnValueKnownInPredecessor(BI))
8747 return requestResimplify();
8754 return requestResimplify();
8762 return requestResimplify();
8766 return requestResimplify();
8773 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8785 auto *Use = cast<Instruction>(U.getUser());
8788 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
8791 switch (Use->getOpcode()) {
8794 case Instruction::GetElementPtr:
8795 case Instruction::Ret:
8796 case Instruction::BitCast:
8797 case Instruction::Load:
8798 case Instruction::Store:
8799 case Instruction::Call:
8800 case Instruction::CallBr:
8801 case Instruction::Invoke:
8802 case Instruction::UDiv:
8803 case Instruction::URem:
8807 case Instruction::SDiv:
8808 case Instruction::SRem:
8812 if (FindUse ==
I->use_end())
8814 auto &
Use = *FindUse;
8828 if (
GEP->getPointerOperand() ==
I) {
8831 if (
GEP->getType()->isVectorTy())
8839 if (!
GEP->hasAllZeroIndices() &&
8840 (!
GEP->isInBounds() ||
8842 GEP->getPointerAddressSpace())))
8843 PtrValueMayBeModified =
true;
8849 bool HasNoUndefAttr =
8850 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8855 if (
C->isNullValue() && HasNoUndefAttr &&
8856 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8857 return !PtrValueMayBeModified;
8863 if (!LI->isVolatile())
8865 LI->getPointerAddressSpace());
8869 if (!
SI->isVolatile())
8871 SI->getPointerAddressSpace())) &&
8872 SI->getPointerOperand() ==
I;
8877 if (
I == Assume->getArgOperand(0))
8885 if (CB->getCalledOperand() ==
I)
8888 if (CB->isArgOperand(&
Use)) {
8889 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8892 CB->paramHasNonNullAttr(ArgIdx,
false))
8893 return !PtrValueMayBeModified;
8912 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8920 Builder.CreateUnreachable();
8921 T->eraseFromParent();
8932 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8934 Assumption = Builder.CreateAssumption(
Cond);
8939 BI->eraseFromParent();
8948 Builder.SetInsertPoint(Unreachable);
8950 Builder.CreateUnreachable();
8951 for (
const auto &Case :
SI->cases())
8952 if (Case.getCaseSuccessor() == BB) {
8954 Case.setSuccessor(Unreachable);
8956 if (
SI->getDefaultDest() == BB) {
8958 SI->setDefaultDest(Unreachable);
8972bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8997 return requestResimplify();
9016 if (simplifyDuplicatePredecessors(BB, DTU))
9020 if (
Options.SpeculateBlocks &&
9027 Options.SpeculateUnpredictables))
9035 case Instruction::UncondBr:
9038 case Instruction::CondBr:
9041 case Instruction::Resume:
9044 case Instruction::CleanupRet:
9047 case Instruction::Switch:
9050 case Instruction::Unreachable:
9053 case Instruction::IndirectBr:
9061bool SimplifyCFGOpt::run(BasicBlock *BB) {
9071 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static bool IsIndirectCall(const MachineInstr *MI)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange, bool OptSize)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool isProfitableToSpeculate(const CondBrInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(CondBrInst *BI, CondBrInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static void hoistConditionalLoadsStores(CondBrInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool extractPredSuccWeights(CondBrInst *PBI, CondBrInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static bool performBranchToCommonDestFolding(CondBrInst *BI, CondBrInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool mergeConditionalStores(CondBrInst *PBI, CondBrInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeNestedCondBranch(CondBrInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool tryWidenCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool mergeIdenticalBBs(ArrayRef< BasicBlock * > Candidates, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static bool tryToMergeLandingPad(LandingPadInst *LPad, UncondBrInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool SimplifyCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, CondBrInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
Get the last element.
const T & front() const
Get the first element.
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
bool isEquality() const
Determine if this is an equals/not equals predicate.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Conditional Branch instruction.
static CondBrInst * Create(Value *Cond, BasicBlock *IfTrue, BasicBlock *IfFalse, InsertPosition InsertBefore=nullptr)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setCondition(Value *V)
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
ConstantFP - Floating Point Values [float, double].
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
A constant pointer value that points to null.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Implements a dense probed hash-table based set.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
LLVM_ABI CallInst * CreateAssumption(Value *Cond)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
UncondBrInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
void insert_range(Range &&R)
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this store instruction.
Value * getPointerOperand()
Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Unconditional Branch instruction.
void setSuccessor(BasicBlock *NewSucc)
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i=0) const
'undef' values are things that do not have specified contents.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
DXILDebugInfoMap run(Module &M)
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
FunctionAddr VTableAddr Value
LLVM_ABI bool foldBranchToCommonDest(CondBrInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, AssumptionCache *AC=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr detail::StaticCastFunc< To > StaticCastTo
Function objects corresponding to the Cast types defined above.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI CondBrInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
LLVM_ABI void InvertBranch(CondBrInst *PBI, IRBuilderBase &Builder)
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible immediate values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
FunctionAddr VTableAddr Count
auto succ_size(const MachineBasicBlock *BB)
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
static cl::opt< unsigned > MaxJumpThreadingLiveBlocks("max-jump-threading-live-blocks", cl::Hidden, cl::init(24), cl::desc("Limit number of blocks a define in a threaded block is allowed " "to be live in"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
LLVM_ABI bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< T1, 2 > &B1, const SmallVector< T2, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Constant * ConstantFoldCastInstruction(unsigned opcode, Constant *V, Type *DestTy)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const SimplifyQuery &Q, bool IgnoreFree=false)
Equivalent to isDereferenceableAndAlignedPointer with an alignment of 1.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
@ Keep
No function return thunk.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, const SimplifyQuery &SQ, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two BBs are equal depends on the contents of the BasicBlock and the incoming values ...
SmallDenseMap< BasicBlock *, Value *, 8 > BB2ValueMap
DenseMap< PHINode *, BB2ValueMap > Phi2IVsMap
static bool canBeMerged(const BasicBlock *BB)
static bool isEqual(const EqualBBWrapper *LHS, const EqualBBWrapper *RHS)
static unsigned getHashValue(const EqualBBWrapper *EBW)
An information struct used to provide DenseMap with the various necessary components for a given valu...
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.