96#define DEBUG_TYPE "simplifycfg"
101 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
104 "Temporary development switch used to gradually uplift SimplifyCFG "
105 "into preserving DomTree,"));
114 "Control the amount of phi node folding to perform (default = 2)"));
118 cl::desc(
"Control the maximal total instruction cost that we are willing "
119 "to speculatively execute to fold a 2-entry PHI node into a "
120 "select (default = 4)"));
124 cl::desc(
"Hoist common instructions up to the parent block"));
128 cl::desc(
"Hoist loads if the target supports conditional faulting"));
132 cl::desc(
"Hoist stores if the target supports conditional faulting"));
136 cl::desc(
"Control the maximal conditional load/store that we are willing "
137 "to speculatively execute to eliminate conditional branch "
143 cl::desc(
"Allow reordering across at most this many "
144 "instructions when hoisting"));
148 cl::desc(
"Sink common instructions down to the end block"));
152 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
156 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
157 "precede - hoist multiple conditional stores into a single "
158 "predicated store"));
162 cl::desc(
"When merging conditional stores, do so even if the resultant "
163 "basic blocks are unlikely to be if-converted as a result"));
167 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
172 cl::desc(
"Limit maximum recursion depth when calculating costs of "
173 "speculatively executed instructions"));
178 cl::desc(
"Max size of a block which is still considered "
179 "small enough to thread through"));
185 cl::desc(
"Maximum cost of combining conditions when "
186 "folding branches"));
189 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
191 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
192 "to fold branch to common destination when vector operations are "
197 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
201 cl::desc(
"Limit cases to analyze when converting a switch to select"));
205 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
212STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
214 "Number of switch instructions turned into linear mapping");
216 "Number of switch instructions turned into lookup tables");
218 NumLookupTablesHoles,
219 "Number of switch instructions turned into lookup tables (holes checked)");
220STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
222 "Number of value comparisons folded into predecessor basic blocks");
224 "Number of branches folded into predecessor basic block");
227 "Number of common instruction 'blocks' hoisted up to the begin block");
229 "Number of common instructions hoisted up to the begin block");
231 "Number of common instruction 'blocks' sunk down to the end block");
233 "Number of common instructions sunk down to the end block");
234STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
236 "Number of invokes with empty resume blocks simplified into calls");
237STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
238STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
245using SwitchCaseResultVectorTy =
254struct ValueEqualityComparisonCase {
266 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
269class SimplifyCFGOpt {
270 const TargetTransformInfo &TTI;
272 const DataLayout &DL;
274 const SimplifyCFGOptions &Options;
277 Value *isValueEqualityComparison(Instruction *TI);
279 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
280 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
283 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
286 bool foldValueComparisonIntoPredecessors(Instruction *TI,
289 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
290 bool simplifySingleResume(ResumeInst *RI);
291 bool simplifyCommonResume(ResumeInst *RI);
292 bool simplifyCleanupReturn(CleanupReturnInst *RI);
293 bool simplifyUnreachable(UnreachableInst *UI);
294 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
295 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
296 bool simplifyIndirectBr(IndirectBrInst *IBI);
297 bool simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
298 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
299 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
301 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
303 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
306 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
307 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
308 Instruction *TI, Instruction *I1,
309 SmallVectorImpl<Instruction *> &OtherSuccTIs,
311 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
312 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
313 BasicBlock *TrueBB, BasicBlock *FalseBB,
314 uint32_t TrueWeight, uint32_t FalseWeight);
315 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
316 const DataLayout &DL);
317 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
318 bool simplifySwitchOnSelectRemap(SwitchInst *SI, SelectInst *
Select,
Value *
X,
319 ConstantInt *
C,
bool Negate);
320 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
321 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
322 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
325 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
327 const SimplifyCFGOptions &Opts)
328 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
329 assert((!DTU || !DTU->hasPostDomTree()) &&
330 "SimplifyCFG is not yet capable of maintaining validity of a "
331 "PostDomTree, so don't ask for it.");
334 bool simplifyOnce(BasicBlock *BB);
335 bool run(BasicBlock *BB);
338 bool requestResimplify() {
348isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
368 "Only for a pair of incoming blocks at the time!");
374 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
375 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
378 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
379 EquivalenceSet->contains(IV1))
402 if (!SI1Succs.
count(Succ))
408 FailBlocks->insert(Succ);
424 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
426 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
427 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
489 if (AggressiveInsts.
count(
I))
505 ZeroCostInstructions.
insert(OverflowInst);
507 }
else if (!ZeroCostInstructions.
contains(
I))
523 for (
Use &
Op :
I->operands())
525 TTI, AC, ZeroCostInstructions,
Depth + 1))
542 if (
DL.hasUnstableRepresentation(V->getType()))
551 return ConstantInt::get(
IntPtrTy, 0);
556 if (CE->getOpcode() == Instruction::IntToPtr)
580struct ConstantComparesGatherer {
581 const DataLayout &DL;
584 Value *CompValue =
nullptr;
587 Value *Extra =
nullptr;
593 unsigned UsedICmps = 0;
599 bool IgnoreFirstMatch =
false;
600 bool MultipleMatches =
false;
603 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
605 if (CompValue || !MultipleMatches)
610 IgnoreFirstMatch =
true;
614 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
615 ConstantComparesGatherer &
616 operator=(
const ConstantComparesGatherer &) =
delete;
621 bool setValueOnce(
Value *NewVal) {
622 if (IgnoreFirstMatch) {
623 IgnoreFirstMatch =
false;
626 if (CompValue && CompValue != NewVal) {
627 MultipleMatches =
true;
641 bool matchInstruction(Instruction *
I,
bool isEQ) {
648 if (!setValueOnce(Val))
668 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
712 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
714 if (!setValueOnce(RHSVal))
719 ConstantInt::get(
C->getContext(),
720 C->getValue() | Mask));
735 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
737 if (!setValueOnce(RHSVal))
741 Vals.push_back(ConstantInt::get(
C->getContext(),
742 C->getValue() & ~Mask));
763 Value *CandidateVal =
I->getOperand(0);
766 CandidateVal = RHSVal;
781 if (!setValueOnce(CandidateVal))
787 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
799 void gather(
Value *V) {
808 SmallVector<Value *, 8> DFT{Op0, Op1};
809 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
811 while (!DFT.
empty()) {
818 if (Visited.
insert(Op1).second)
820 if (Visited.
insert(Op0).second)
827 if (matchInstruction(
I, IsEq))
871 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
872 CV =
SI->getCondition();
874 if (BI->getCondition()->hasOneUse()) {
879 if (Trunc->hasNoUnsignedWrap())
880 CV = Trunc->getOperand(0);
887 Value *Ptr = PTII->getPointerOperand();
888 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
890 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
899BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
900 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
902 Cases.reserve(
SI->getNumCases());
903 for (
auto Case :
SI->cases())
904 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
905 Case.getCaseSuccessor()));
906 return SI->getDefaultDest();
911 ICmpInst::Predicate Pred;
917 Pred = ICmpInst::ICMP_NE;
922 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
930 std::vector<ValueEqualityComparisonCase> &Cases) {
936 std::vector<ValueEqualityComparisonCase> &C2) {
937 std::vector<ValueEqualityComparisonCase> *
V1 = &C1, *V2 = &C2;
940 if (
V1->size() > V2->size())
945 if (
V1->size() == 1) {
948 for (
const ValueEqualityComparisonCase &
VECC : *V2)
949 if (TheVal ==
VECC.Value)
956 unsigned i1 = 0, i2 = 0, e1 =
V1->size(), e2 = V2->size();
957 while (i1 != e1 && i2 != e2) {
973bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
974 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
979 Value *ThisVal = isValueEqualityComparison(TI);
980 assert(ThisVal &&
"This isn't a value comparison!!");
981 if (ThisVal != PredVal)
988 std::vector<ValueEqualityComparisonCase> PredCases;
990 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
994 std::vector<ValueEqualityComparisonCase> ThisCases;
995 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1010 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1016 ThisCases[0].Dest->removePredecessor(PredDef);
1019 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1026 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1033 SmallPtrSet<Constant *, 16> DeadCases;
1034 for (
const ValueEqualityComparisonCase &Case : PredCases)
1035 DeadCases.
insert(Case.Value);
1038 <<
"Through successor TI: " << *TI);
1040 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1043 auto *
Successor = i->getCaseSuccessor();
1046 if (DeadCases.
count(i->getCaseValue())) {
1055 std::vector<DominatorTree::UpdateType> Updates;
1056 for (
const auto &
I : NumPerSuccessorCases)
1058 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1068 ConstantInt *TIV =
nullptr;
1070 for (
const auto &[
Value, Dest] : PredCases)
1076 assert(TIV &&
"No edge from pred to succ?");
1081 for (
const auto &[
Value, Dest] : ThisCases)
1089 TheRealDest = ThisDef;
1091 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1096 if (Succ != CheckEdge) {
1097 if (Succ != TheRealDest)
1098 RemovedSuccs.
insert(Succ);
1101 CheckEdge =
nullptr;
1108 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1113 SmallVector<DominatorTree::UpdateType, 2> Updates;
1115 for (
auto *RemovedSucc : RemovedSuccs)
1116 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1127struct ConstantIntOrdering {
1128 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1129 return LHS->getValue().ult(
RHS->getValue());
1141 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1150 assert(MD &&
"Invalid branch-weight metadata");
1175 if (BonusInst.isTerminator())
1210 NewBonusInst->
takeName(&BonusInst);
1211 BonusInst.setName(NewBonusInst->
getName() +
".old");
1212 VMap[&BonusInst] = NewBonusInst;
1221 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1222 "If the user is not a PHI node, then it should be in the same "
1223 "block as, and come after, the original bonus instruction.");
1227 if (PN->getIncomingBlock(U) == BB)
1231 assert(PN->getIncomingBlock(U) == PredBlock &&
1232 "Not in block-closed SSA form?");
1233 U.set(NewBonusInst);
1243 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1244 PredDL.isSameSourceLocation(
DL)) {
1251bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1259 std::vector<ValueEqualityComparisonCase> BBCases;
1260 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1262 std::vector<ValueEqualityComparisonCase> PredCases;
1263 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1268 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1271 SmallVector<uint64_t, 8> Weights;
1275 if (PredHasWeights) {
1278 if (Weights.
size() != 1 + PredCases.size())
1279 PredHasWeights = SuccHasWeights =
false;
1280 }
else if (SuccHasWeights)
1284 Weights.
assign(1 + PredCases.size(), 1);
1286 SmallVector<uint64_t, 8> SuccWeights;
1287 if (SuccHasWeights) {
1290 if (SuccWeights.
size() != 1 + BBCases.size())
1291 PredHasWeights = SuccHasWeights =
false;
1292 }
else if (PredHasWeights)
1293 SuccWeights.
assign(1 + BBCases.size(), 1);
1295 if (PredDefault == BB) {
1298 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1299 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1300 if (PredCases[i].Dest != BB)
1301 PTIHandled.insert(PredCases[i].
Value);
1304 std::swap(PredCases[i], PredCases.back());
1306 if (PredHasWeights || SuccHasWeights) {
1308 Weights[0] += Weights[i + 1];
1313 PredCases.pop_back();
1319 if (PredDefault != BBDefault) {
1321 if (DTU && PredDefault != BB)
1322 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1323 PredDefault = BBDefault;
1324 ++NewSuccessors[BBDefault];
1327 unsigned CasesFromPred = Weights.
size();
1329 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1330 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1331 PredCases.push_back(BBCases[i]);
1332 ++NewSuccessors[BBCases[i].Dest];
1333 if (SuccHasWeights || PredHasWeights) {
1337 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1338 ValidTotalSuccWeight += SuccWeights[i + 1];
1342 if (SuccHasWeights || PredHasWeights) {
1343 ValidTotalSuccWeight += SuccWeights[0];
1345 for (
unsigned i = 1; i < CasesFromPred; ++i)
1346 Weights[i] *= ValidTotalSuccWeight;
1348 Weights[0] *= SuccWeights[0];
1354 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1355 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1356 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1357 if (PredCases[i].Dest == BB) {
1358 PTIHandled.insert(PredCases[i].
Value);
1360 if (PredHasWeights || SuccHasWeights) {
1361 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1366 std::swap(PredCases[i], PredCases.back());
1367 PredCases.pop_back();
1374 for (
const ValueEqualityComparisonCase &Case : BBCases)
1375 if (PTIHandled.count(Case.Value)) {
1377 if (PredHasWeights || SuccHasWeights)
1378 Weights.
push_back(WeightsForHandled[Case.Value]);
1379 PredCases.push_back(Case);
1380 ++NewSuccessors[Case.Dest];
1381 PTIHandled.erase(Case.Value);
1386 for (ConstantInt *
I : PTIHandled) {
1387 if (PredHasWeights || SuccHasWeights)
1389 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1390 ++NewSuccessors[BBDefault];
1397 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1402 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1404 for (
auto I :
seq(NewSuccessor.second)) {
1408 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1409 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1416 "Should not end up here with unstable pointers");
1422 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1424 for (ValueEqualityComparisonCase &V : PredCases)
1427 if (PredHasWeights || SuccHasWeights)
1433 if (MDNode *Unpredictable = PTI->
getMetadata(LLVMContext::MD_unpredictable))
1434 if (TI->
hasMetadata(LLVMContext::MD_unpredictable))
1435 NewSI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
1445 if (!InfLoopBlock) {
1453 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1460 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1462 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1467 ++NumFoldValueComparisonIntoPredecessors;
1475bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1478 Value *CV = isValueEqualityComparison(TI);
1479 assert(CV &&
"Not a comparison?");
1484 while (!Preds.empty()) {
1493 Value *PCV = isValueEqualityComparison(PTI);
1497 SmallSetVector<BasicBlock *, 4> FailBlocks;
1499 for (
auto *Succ : FailBlocks) {
1505 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1519 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1520 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1521 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1543 if (
I->mayReadFromMemory())
1575 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1583 if (J->getParent() == BB)
1605 if (C1->isMustTailCall() != C2->isMustTailCall())
1608 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1614 if (CB1->cannotMerge() || CB1->isConvergent())
1617 if (CB2->cannotMerge() || CB2->isConvergent())
1632 if (!I1->hasDbgRecords())
1634 using CurrentAndEndIt =
1635 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1641 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1642 return Pair.first == Pair.second;
1648 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1654 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1656 if (!
Other->hasDbgRecords())
1659 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1666 while (
none_of(Itrs, atEnd)) {
1667 bool HoistDVRs = allIdentical(Itrs);
1668 for (CurrentAndEndIt &Pair : Itrs) {
1682 if (I1->isIdenticalToWhenDefined(I2,
true))
1687 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1688 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1689 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1691 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1692 return I1->getOperand(0) == I2->
getOperand(1) &&
1758 auto &Context = BI->
getParent()->getContext();
1763 Value *Mask =
nullptr;
1764 Value *MaskFalse =
nullptr;
1765 Value *MaskTrue =
nullptr;
1766 if (Invert.has_value()) {
1767 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1768 Mask = Builder.CreateBitCast(
1773 MaskFalse = Builder.CreateBitCast(
1775 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1777 auto PeekThroughBitcasts = [](
Value *V) {
1779 V = BitCast->getOperand(0);
1782 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1784 if (!Invert.has_value())
1785 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1790 auto *Op0 =
I->getOperand(0);
1791 CallInst *MaskedLoadStore =
nullptr;
1794 auto *Ty =
I->getType();
1796 Value *PassThru =
nullptr;
1797 if (Invert.has_value())
1798 for (
User *U :
I->users()) {
1800 PassThru = Builder.CreateBitCast(
1809 Builder.SetInsertPoint(Ins);
1812 MaskedLoadStore = Builder.CreateMaskedLoad(
1814 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1817 I->replaceAllUsesWith(NewLoadStore);
1820 auto *StoredVal = Builder.CreateBitCast(
1822 MaskedLoadStore = Builder.CreateMaskedStore(
1833 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1835 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1839 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1840 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1843 I->eraseFromParent();
1850 bool IsStore =
false;
1873bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1874 bool AllInstsEqOnly) {
1890 for (
auto *Succ : UniqueSuccessors) {
1906 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1908 for (
auto *Succ : UniqueSuccessors) {
1912 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1915 if (AllInstsEqOnly) {
1921 unsigned Size0 = UniqueSuccessors[0]->size();
1922 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1926 Succ->
size() == Size0;
1930 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1931 while (LRI.isValid()) {
1933 if (
any_of(*LRI, [I0](Instruction *
I) {
1947 unsigned NumSkipped = 0;
1950 if (SuccIterPairs.
size() > 2) {
1953 if (SuccIterPairs.
size() < 2)
1960 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1961 auto &BB1ItrPair = *SuccIterPairBegin++;
1962 auto OtherSuccIterPairRange =
1968 bool AllInstsAreIdentical =
true;
1969 bool HasTerminator =
I1->isTerminator();
1970 for (
auto &SuccIter : OtherSuccIterRange) {
1974 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1975 AllInstsAreIdentical =
false;
1978 SmallVector<Instruction *, 8> OtherInsts;
1979 for (
auto &SuccIter : OtherSuccIterRange)
1984 if (HasTerminator) {
1988 if (NumSkipped || !AllInstsAreIdentical) {
1993 return hoistSuccIdenticalTerminatorToSwitchOrIf(
1994 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
1998 if (AllInstsAreIdentical) {
1999 unsigned SkipFlagsBB1 = BB1ItrPair.second;
2000 AllInstsAreIdentical =
2002 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
2004 unsigned SkipFlagsBB2 = Pair.second;
2019 AllInstsAreIdentical && CI && CI->isMustTailCall()) {
2020 AllInstsAreIdentical =
2021 NumSkipped == 0 &&
all_of(SuccIterPairs, [](
const SuccIterPair &
P) {
2026 if (AllInstsAreIdentical) {
2036 for (
auto &SuccIter : OtherSuccIterRange) {
2044 assert(
Success &&
"We should not be trying to hoist callbases "
2045 "with non-intersectable attributes");
2057 unsigned SkippedFlags = 0;
2058 for (
const SuccIterPair &
P : SuccIterPairs)
2059 SkippedFlags |=
P.second;
2062 I1->dropUBImplyingAttrsAndMetadata();
2065 NumHoistCommonCode += SuccIterPairs.size();
2067 NumHoistCommonInstrs += SuccIterPairs.size();
2076 for (
auto &SuccIterPair : SuccIterPairs) {
2085bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2086 Instruction *TI, Instruction *I1,
2087 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2097 auto *I2 = *OtherSuccTIs.
begin();
2117 for (PHINode &PN : Succ->
phis()) {
2118 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2119 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2120 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2140 if (!
NT->getType()->isVoidTy()) {
2141 I1->replaceAllUsesWith(NT);
2142 for (Instruction *OtherSuccTI : OtherSuccTIs)
2143 OtherSuccTI->replaceAllUsesWith(NT);
2147 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2153 for (
auto *OtherSuccTI : OtherSuccTIs)
2154 Locs.
push_back(OtherSuccTI->getDebugLoc());
2166 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2168 for (PHINode &PN : Succ->
phis()) {
2169 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2170 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2176 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2186 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2187 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2188 PN.setIncomingValue(i, SI);
2196 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
2200 if (DTU && VisitedSuccs.
insert(Succ).second)
2201 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2207 for (BasicBlock *Succ : UniqueSuccessors)
2208 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2222 if (
I->isIntDivRem())
2237 std::optional<unsigned> NumUses;
2238 for (
auto *
I : Insts) {
2241 I->getType()->isTokenTy())
2246 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2254 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2258 NumUses =
I->getNumUses();
2259 else if (NumUses !=
I->getNumUses())
2265 for (
auto *
I : Insts) {
2279 for (
const Use &U : I0->
uses()) {
2280 auto It = PHIOperands.find(&U);
2281 if (It == PHIOperands.end())
2284 if (!
equal(Insts, It->second))
2298 if (HaveIndirectCalls) {
2299 if (!AllCallsAreIndirect)
2303 Value *Callee =
nullptr;
2307 Callee = CurrCallee;
2308 else if (Callee != CurrCallee)
2314 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2320 if (!
all_of(Insts, SameAsI0)) {
2325 !
all_of(Insts, CanReplaceOperand))
2329 for (
auto *
I : Insts)
2330 Ops.push_back(
I->getOperand(OI));
2340 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2345 for (
auto *BB : Blocks) {
2347 I =
I->getPrevNode();
2372 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2375 PN->insertBefore(BBEnd->begin());
2376 for (
auto *
I : Insts)
2377 PN->addIncoming(
I->getOperand(O),
I->getParent());
2386 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2389 for (
auto *
I : Insts)
2403 assert(
Success &&
"We should not be trying to sink callbases "
2404 "with non-intersectable attributes");
2415 PN->replaceAllUsesWith(I0);
2416 PN->eraseFromParent();
2420 for (
auto *
I : Insts) {
2425 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2426 I->replaceAllUsesWith(I0);
2427 I->eraseFromParent();
2477 bool HaveNonUnconditionalPredecessors =
false;
2483 HaveNonUnconditionalPredecessors =
true;
2485 if (UnconditionalPreds.
size() < 2)
2498 for (
const Use &U : PN.incoming_values())
2499 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2500 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2502 Ops.push_back(*IncomingVals[Pred]);
2510 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2523 if (!followedByDeoptOrUnreachable) {
2525 auto IsMemOperand = [](
Use &U) {
2538 unsigned NumPHIInsts = 0;
2539 for (
Use &U : (*LRI)[0]->operands()) {
2540 auto It = PHIOperands.
find(&U);
2541 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2542 return InstructionsToSink.contains(V);
2549 if (IsMemOperand(U) &&
2550 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2557 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2558 return NumPHIInsts <= 1;
2575 while (Idx < ScanIdx) {
2576 if (!ProfitableToSinkInstruction(LRI)) {
2579 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2592 if (Idx < ScanIdx) {
2595 InstructionsToSink = InstructionsProfitableToSink;
2601 !ProfitableToSinkInstruction(LRI) &&
2602 "We already know that the last instruction is unprofitable to sink");
2610 for (
auto *
I : *LRI)
2611 InstructionsProfitableToSink.
erase(
I);
2612 if (!ProfitableToSinkInstruction(LRI)) {
2615 InstructionsToSink = InstructionsProfitableToSink;
2629 if (HaveNonUnconditionalPredecessors) {
2630 if (!followedByDeoptOrUnreachable) {
2638 bool Profitable =
false;
2639 while (Idx < ScanIdx) {
2673 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2675 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2683 NumSinkCommonInstrs++;
2687 ++NumSinkCommonCode;
2693struct CompatibleSets {
2694 using SetTy = SmallVector<InvokeInst *, 2>;
2700 SetTy &getCompatibleSet(InvokeInst *
II);
2702 void insert(InvokeInst *
II);
2705CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2710 for (CompatibleSets::SetTy &Set : Sets) {
2711 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2716 return Sets.emplace_back();
2719void CompatibleSets::insert(InvokeInst *
II) {
2720 getCompatibleSet(
II).emplace_back(
II);
2724 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2727 auto IsIllegalToMerge = [](InvokeInst *
II) {
2728 return II->cannotMerge() ||
II->isInlineAsm();
2730 if (
any_of(Invokes, IsIllegalToMerge))
2738 if (HaveIndirectCalls) {
2739 if (!AllCallsAreIndirect)
2744 for (InvokeInst *
II : Invokes) {
2745 Value *CurrCallee =
II->getCalledOperand();
2746 assert(CurrCallee &&
"There is always a called operand.");
2749 else if (Callee != CurrCallee)
2756 auto HasNormalDest = [](InvokeInst *
II) {
2759 if (
any_of(Invokes, HasNormalDest)) {
2762 if (!
all_of(Invokes, HasNormalDest))
2767 for (InvokeInst *
II : Invokes) {
2769 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2771 NormalBB = CurrNormalBB;
2772 else if (NormalBB != CurrNormalBB)
2780 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2789 for (InvokeInst *
II : Invokes) {
2791 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2793 UnwindBB = CurrUnwindBB;
2795 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2802 Invokes.front()->getUnwindDest(),
2803 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2808 const InvokeInst *II0 = Invokes.front();
2809 for (
auto *
II : Invokes.drop_front())
2814 auto IsIllegalToMergeArguments = [](
auto Ops) {
2815 Use &U0 = std::get<0>(
Ops);
2816 Use &U1 = std::get<1>(
Ops);
2822 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2823 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2824 IsIllegalToMergeArguments))
2836 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2842 bool HasNormalDest =
2847 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2851 II0->
getParent()->getIterator()->getNextNode();
2856 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2860 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2862 if (!HasNormalDest) {
2866 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2874 return MergedInvoke;
2888 SuccBBOfMergedInvoke});
2911 return II->getOperand(U.getOperandNo()) != U.get();
2930 Invokes.
front()->getParent());
2938 if (!MergedDebugLoc)
2939 MergedDebugLoc =
II->getDebugLoc();
2947 OrigSuccBB->removePredecessor(
II->getParent());
2953 assert(
Success &&
"Merged invokes with incompatible attributes");
2956 II->replaceAllUsesWith(MergedInvoke);
2957 II->eraseFromParent();
2961 ++NumInvokeSetsFormed;
2997 CompatibleSets Grouper;
3007 if (Invokes.
size() < 2)
3019class EphemeralValueTracker {
3020 SmallPtrSet<const Instruction *, 32> EphValues;
3022 bool isEphemeral(
const Instruction *
I) {
3025 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3026 all_of(
I->users(), [&](
const User *U) {
3027 return EphValues.count(cast<Instruction>(U));
3032 bool track(
const Instruction *
I) {
3033 if (isEphemeral(
I)) {
3084 unsigned MaxNumInstToLookAt = 9;
3088 if (!MaxNumInstToLookAt)
3090 --MaxNumInstToLookAt;
3103 if (
SI->getPointerOperand() == StorePtr &&
3104 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3107 return SI->getValueOperand();
3112 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3113 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3115 bool ExplicitlyDereferenceableOnly;
3123 (!ExplicitlyDereferenceableOnly ||
3141 unsigned &SpeculatedInstructions,
3149 bool HaveRewritablePHIs =
false;
3151 Value *OrigV = PN.getIncomingValueForBlock(BB);
3152 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3159 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3168 HaveRewritablePHIs =
true;
3171 if (!OrigCE && !ThenCE)
3178 if (OrigCost + ThenCost > MaxCost)
3185 ++SpeculatedInstructions;
3186 if (SpeculatedInstructions > 1)
3190 return HaveRewritablePHIs;
3194 std::optional<bool> Invert,
3198 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3205 if (!Invert.has_value())
3208 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3212 return BIEndProb < Likely;
3252bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3253 BasicBlock *ThenBB) {
3264 bool Invert =
false;
3279 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3281 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3283 unsigned SpeculatedInstructions = 0;
3284 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3285 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3286 Value *SpeculatedStoreValue =
nullptr;
3287 StoreInst *SpeculatedStore =
nullptr;
3288 EphemeralValueTracker EphTracker;
3303 if (EphTracker.track(&
I))
3308 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3310 SpeculatedConditionalLoadsStores.
size() <
3314 if (IsSafeCheapLoadStore)
3315 SpeculatedConditionalLoadsStores.
push_back(&
I);
3317 ++SpeculatedInstructions;
3319 if (SpeculatedInstructions > 1)
3323 if (!IsSafeCheapLoadStore &&
3326 (SpeculatedStoreValue =
3329 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3335 if (!SpeculatedStore && SpeculatedStoreValue)
3341 for (Use &
Op :
I.operands()) {
3346 ++SinkCandidateUseCounts[OpI];
3353 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3354 if (Inst->hasNUses(
Count)) {
3355 ++SpeculatedInstructions;
3356 if (SpeculatedInstructions > 1)
3363 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3366 SpeculatedInstructions,
Cost,
TTI);
3367 if (!Convert ||
Cost > Budget)
3371 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3376 if (SpeculatedStoreValue) {
3380 Value *FalseV = SpeculatedStoreValue;
3384 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3414 for (DbgVariableRecord *DbgAssign :
3417 DbgAssign->replaceVariableLocationOp(OrigV, S);
3427 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3430 I.dropUBImplyingAttrsAndMetadata();
3433 if (EphTracker.contains(&
I)) {
3435 I.eraseFromParent();
3441 for (
auto &It : *ThenBB)
3446 !DVR || !DVR->isDbgAssign())
3447 It.dropOneDbgRecord(&DR);
3449 std::prev(ThenBB->end()));
3451 if (!SpeculatedConditionalLoadsStores.
empty())
3457 for (PHINode &PN : EndBB->
phis()) {
3458 unsigned OrigI = PN.getBasicBlockIndex(BB);
3459 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3460 Value *OrigV = PN.getIncomingValue(OrigI);
3461 Value *ThenV = PN.getIncomingValue(ThenI);
3470 Value *TrueV = ThenV, *FalseV = OrigV;
3475 BrCond, TrueV, FalseV, PN.getFastMathFlagsOrNone(),
"spec.select", BI);
3476 PN.setIncomingValue(OrigI, V);
3477 PN.setIncomingValue(ThenI, V);
3481 for (Instruction *
I : SpeculatedPseudoProbes)
3482 I->eraseFromParent();
3495 if (!ReachesNonLocalUses.
insert(BB).second)
3510 EphemeralValueTracker EphTracker;
3517 if (CI->cannotDuplicate() || CI->isConvergent())
3530 for (
User *U :
I.users()) {
3533 if (UsedInBB == BB) {
3537 NonLocalUseBlocks.
insert(UsedInBB);
3551 if (
I &&
I->getParent() == To)
3571 static constexpr unsigned MaxInstructionsToScan = 512;
3585 unsigned NumScannedInstructions = 0;
3586 while (!Worklist.
empty()) {
3590 if (!CanReachStop.
insert(BB).second)
3594 if (++NumScannedInstructions > MaxInstructionsToScan)
3598 BlocksWithUncontrolledConvergentCalls.
insert(BB);
3612 while (!Worklist.
empty()) {
3614 if (BB == StopBB || !CanReachStop.
contains(BB))
3617 if (!Visited.
insert(BB).second)
3620 if (BlocksWithUncontrolledConvergentCalls.
contains(BB))
3652 KnownValues[CB].
insert(Pred);
3656 if (KnownValues.
empty())
3681 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3684 for (
const auto &Pair : KnownValues) {
3701 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3714 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3717 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3727 EdgeBB->setName(RealDest->
getName() +
".critedge");
3728 EdgeBB->moveBefore(RealDest);
3738 TranslateMap[
Cond] = CB;
3751 N->insertInto(EdgeBB, InsertPt);
3754 N->setName(BBI->getName() +
".c");
3765 if (!BBI->use_empty())
3766 TranslateMap[&*BBI] = V;
3767 if (!
N->mayHaveSideEffects()) {
3768 N->eraseFromParent();
3773 if (!BBI->use_empty())
3774 TranslateMap[&*BBI] =
N;
3780 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3781 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3782 SrcDbgCursor = std::next(BBI);
3784 N->cloneDebugInfoFrom(&*BBI);
3793 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3794 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3795 InsertPt->cloneDebugInfoFrom(BI);
3816 return std::nullopt;
3822bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3829 std::optional<bool>
Result;
3830 bool EverChanged =
false;
3836 }
while (Result == std::nullopt);
3845 bool SpeculateUnpredictables) {
3867 return isa<UncondBrInst>(IfBlock->getTerminator());
3870 "Will have either one or two blocks to speculate.");
3877 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3878 if (!IsUnpredictable) {
3881 (TWeight + FWeight) != 0) {
3886 if (IfBlocks.
size() == 1) {
3888 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3889 if (BIBBProb >= Likely)
3892 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3901 if (IfCondPhiInst->getParent() == BB)
3909 unsigned NumPhis = 0;
3922 if (SpeculateUnpredictables && IsUnpredictable)
3923 Budget +=
TTI.getBranchMispredictPenalty();
3936 AggressiveInsts, Cost, Budget,
TTI, AC,
3937 ZeroCostInstructions) ||
3939 AggressiveInsts, Cost, Budget,
TTI, AC,
3940 ZeroCostInstructions))
3953 auto IsBinOpOrAndEq = [](
Value *V) {
3976 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3989 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3991 <<
" F: " << IfFalse->
getName() <<
"\n");
4008 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
4013 PN->eraseFromParent();
4019 Builder.CreateBr(BB);
4040 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
4041 if (
Opc == Instruction::And)
4042 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
4043 if (
Opc == Instruction::Or)
4044 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
4056 bool PredHasWeights =
4058 bool SuccHasWeights =
4060 if (PredHasWeights || SuccHasWeights) {
4061 if (!PredHasWeights)
4062 PredTrueWeight = PredFalseWeight = 1;
4063 if (!SuccHasWeights)
4064 SuccTrueWeight = SuccFalseWeight = 1;
4074static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
4077 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
4079 "PredBB must be a predecessor of BB.");
4087 (PTWeight + PFWeight) != 0) {
4090 Likely =
TTI->getPredictableBranchThreshold();
4095 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4096 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4100 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4103 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4104 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4110 return std::nullopt;
4123 bool InvertPredCond;
4124 std::tie(CommonSucc,
Opc, InvertPredCond) =
4127 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4135 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4140 if (InvertPredCond) {
4153 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4156 SuccTrueWeight, SuccFalseWeight)) {
4162 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4167 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4168 PredTrueWeight * SuccFalseWeight);
4174 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4175 PredFalseWeight * SuccTrueWeight);
4177 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4218 if (!MDWeights.
empty()) {
4219 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4224 ++NumFoldBranchToCommonDest;
4231 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4232 return U->getType()->isVectorTy();
4243 unsigned BonusInstThreshold) {
4252 Cond->getParent() != BB || !
Cond->hasOneUse())
4273 bool InvertPredCond;
4275 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4307 unsigned NumBonusInsts = 0;
4308 bool SawVectorOp =
false;
4309 const unsigned PredCount = Preds.
size();
4313 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4333 NumBonusInsts += PredCount;
4341 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4344 return PN->getIncomingBlock(U) == BB;
4345 return UI->
getParent() == BB &&
I.comesBefore(UI);
4349 if (!
all_of(
I.uses(), IsBCSSAUse))
4353 BonusInstThreshold *
4369 for (
auto *BB : {BB1, BB2}) {
4385 Value *AlternativeV =
nullptr) {
4411 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4412 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4420 if (!AlternativeV &&
4426 PHI->addIncoming(V, BB);
4436 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4445 if (!PStore || !QStore)
4468 if (
I.mayReadOrWriteMemory())
4470 for (
auto &
I : *QFB)
4471 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4474 for (
auto &
I : *QTB)
4475 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4479 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4493 for (
auto &
I : *BB) {
4495 if (
I.isTerminator())
4513 "When we run out of budget we will eagerly return from within the "
4514 "per-instruction loop.");
4518 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4520 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4521 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4557 InvertPCond ^= (PStore->
getParent() != PTB);
4558 InvertQCond ^= (QStore->
getParent() != QTB);
4578 {CombinedWeights[0], CombinedWeights[1]},
4585 SI->copyMetadata(*QStore);
4591 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4594 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4657 bool InvertPCond =
false, InvertQCond =
false;
4663 if (QFB == PostBB) {
4682 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4685 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4693 for (
auto *BB : {PTB, PFB}) {
4698 PStoreAddresses.
insert(
SI->getPointerOperand());
4700 for (
auto *BB : {QTB, QFB}) {
4705 QStoreAddresses.
insert(
SI->getPointerOperand());
4711 auto &CommonAddresses = PStoreAddresses;
4714 for (
auto *Address : CommonAddresses)
4717 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4735 !BI->
getParent()->getSinglePredecessor())
4737 if (!IfFalseBB->
phis().empty())
4747 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4821 if (&*BB->
begin() != BI)
4849 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4851 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4855 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4858 if (CommonDestProb >= Likely)
4868 unsigned NumPhis = 0;
4890 if (OtherDest == BB) {
4898 OtherDest = InfLoopBlock;
4910 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4914 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4918 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4933 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4934 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4937 SuccTrueWeight, SuccFalseWeight);
4939 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4940 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4941 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4942 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4946 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4947 PredOther * SuccCommon,
4948 PredOther * SuccOther};
4955 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4957 assert(
SI->getCondition() == PBICond);
4974 Value *BIV = PN.getIncomingValueForBlock(BB);
4975 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4976 Value *PBIV = PN.getIncomingValue(PBBIdx);
4980 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4981 PN.setIncomingValue(PBBIdx, NV);
4985 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4986 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
5006bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
5008 BasicBlock *FalseBB,
5009 uint32_t TrueWeight,
5010 uint32_t FalseWeight) {
5017 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
5019 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
5022 for (BasicBlock *Succ :
successors(OldTerm)) {
5024 if (Succ == KeepEdge1)
5025 KeepEdge1 =
nullptr;
5026 else if (Succ == KeepEdge2)
5027 KeepEdge2 =
nullptr;
5032 if (Succ != TrueBB && Succ != FalseBB)
5033 RemovedSuccessors.
insert(Succ);
5041 if (!KeepEdge1 && !KeepEdge2) {
5042 if (TrueBB == FalseBB) {
5053 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
5073 SmallVector<DominatorTree::UpdateType, 2> Updates;
5075 for (
auto *RemovedSuccessor : RemovedSuccessors)
5076 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
5091bool SimplifyCFGOpt::simplifySwitchOnSelectRemap(SwitchInst *SI,
5093 ConstantInt *
C,
bool Negate) {
5104 BasicBlock *DestFork =
SI->findCaseValue(K)->getCaseSuccessor();
5105 auto CaseC =
SI->findCaseValue(
C);
5106 bool IsDefault = CaseC ==
SI->case_default();
5108 BasicBlock *OldDest = CaseC->getCaseSuccessor();
5113 SI->setCondition(
X);
5115 if (OldDest != DestFork) {
5119 SI->addCase(
C, DestFork);
5121 CaseC->setSuccessor(DestFork);
5128 bool OldDestStillTargeted =
any_of(
5129 successors(SI), [&](BasicBlock *Succ) {
return Succ == OldDest; });
5130 if (DTU && !OldDestStillTargeted)
5131 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
5136 SmallVector<uint32_t> SwitchWeights;
5144 bool SelectHasBranchWeights =
5149 if (SwitchHasBranchWeights && SelectHasBranchWeights &&
5157 SmallVector<uint64_t> NewSwitchWeights;
5158 NewSwitchWeights.reserve(SwitchWeights.
size());
5159 NewSwitchWeights.push_back(SwitchWeights[0] * SelectTotalWeight);
5160 for (
const auto &[SwitchCase, SwitchWeight] :
5162 if (SwitchCase.getCaseValue() ==
C) {
5164 }
else if (SwitchCase.getCaseValue() == K) {
5168 uint64_t ProbabilityKeyEqualsK = SwitchWeight * SelectTotalWeight;
5171 ProbabilityKeyEqualsK > ProbabilityXEqualsC
5172 ? ProbabilityKeyEqualsK - ProbabilityXEqualsC
5174 NewSwitchWeights.push_back(ProbabilityXEqualsK);
5176 NewSwitchWeights.push_back(SwitchWeight * SelectTotalWeight);
5180 }
else if (SwitchHasBranchWeights) {
5186 SI->setMetadata(LLVMContext::MD_prof,
nullptr);
5200bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
5205 if (
Select->hasOneUse() &&
5209 simplifySwitchOnSelectRemap(SI,
Select,
X,
C, Pred == ICmpInst::ICMP_NE))
5215 if (!TrueVal || !FalseVal)
5220 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
5221 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5224 uint32_t TrueWeight = 0, FalseWeight = 0;
5225 SmallVector<uint64_t, 8> Weights;
5229 if (Weights.
size() == 1 +
SI->getNumCases()) {
5231 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5233 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5238 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5247bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5261 SmallVector<uint32_t> SelectBranchWeights(2);
5264 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5265 SelectBranchWeights[0],
5266 SelectBranchWeights[1]);
5286bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5290 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5336bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5355 ConstantInt *NewCaseVal;
5363 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5369 SelectTrueVal = Builder.
getTrue();
5370 SelectFalseVal = Builder.
getFalse();
5373 SelectCond =
Select->getCondition();
5375 if (SelectCond != ICI)
5377 SelectTrueVal =
Select->getTrueValue();
5378 SelectFalseVal =
Select->getFalseValue();
5383 if (
SI->getCondition() != IcmpCond)
5389 if (
SI->getDefaultDest() != BB) {
5390 ConstantInt *VVal =
SI->findCaseDest(BB);
5391 assert(VVal &&
"Should have a unique destination value");
5399 return requestResimplify();
5405 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5407 if (Predicate == ICmpInst::ICMP_EQ)
5415 return requestResimplify();
5422 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5428 Value *DefaultCst = SelectFalseVal;
5429 Value *NewCst = SelectTrueVal;
5437 Select->replaceAllUsesWith(DefaultCst);
5438 Select->eraseFromParent();
5444 SmallVector<DominatorTree::UpdateType, 2> Updates;
5451 SwitchInstProfUpdateWrapper SIW(*SI);
5452 auto W0 = SIW.getSuccessorWeight(0);
5456 SIW.setSuccessorWeight(0, *NewW);
5458 SIW.addCase(NewCaseVal, NewBB, NewW);
5460 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5469 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5477bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5479 const DataLayout &
DL) {
5489 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5491 SmallVectorImpl<ConstantInt *> &
Values = ConstantCompare.Vals;
5492 Value *CompVal = ConstantCompare.CompValue;
5493 unsigned UsedICmps = ConstantCompare.UsedICmps;
5494 Value *ExtraCase = ConstantCompare.Extra;
5495 bool TrueWhenEqual = ConstantCompare.IsEq;
5512 if (ExtraCase &&
Values.size() < 2)
5515 SmallVector<uint32_t> BranchWeights;
5521 if (!TrueWhenEqual) {
5524 std::swap(BranchWeights[0], BranchWeights[1]);
5530 <<
" cases into SWITCH. BB is:\n"
5533 SmallVector<DominatorTree::UpdateType, 2> Updates;
5540 nullptr,
"switch.early.test");
5551 AssumptionCache *AC =
Options.AC;
5557 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5564 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5570 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5571 <<
"\nEXTRABB = " << *BB);
5579 "Should not end up here with unstable pointers");
5581 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5586 if (
Values.front()->getValue() -
Values.back()->getValue() ==
5589 Values.back()->getValue(),
Values.front()->getValue() + 1);
5591 ICmpInst::Predicate Pred;
5601 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5602 NewBI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5607 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5608 New->setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5613 SmallVector<uint32_t> NewWeights(
Values.size() + 1);
5614 NewWeights[0] = BranchWeights[1];
5617 V = BranchWeights[0] /
Values.size();
5622 for (ConstantInt *Val :
Values)
5623 New->addCase(Val, EdgeBB);
5631 for (
unsigned i = 0, e =
Values.size() - 1; i != e; ++i)
5641 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5645bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5647 return simplifyCommonResume(RI);
5651 return simplifySingleResume(RI);
5664 switch (IntrinsicID) {
5665 case Intrinsic::dbg_declare:
5666 case Intrinsic::dbg_value:
5667 case Intrinsic::dbg_label:
5668 case Intrinsic::lifetime_end:
5678bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5687 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5691 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5693 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5694 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5698 if (IncomingBB->getUniqueSuccessor() != BB)
5703 if (IncomingValue != LandingPad)
5707 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5708 TrivialUnwindBlocks.
insert(IncomingBB);
5712 if (TrivialUnwindBlocks.
empty())
5716 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5720 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5723 for (BasicBlock *Pred :
5734 TrivialBB->getTerminator()->eraseFromParent();
5735 new UnreachableInst(RI->
getContext(), TrivialBB);
5737 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5744 return !TrivialUnwindBlocks.empty();
5748bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5752 "Resume must unwind the exception that caused control to here");
5808 int Idx = DestPN.getBasicBlockIndex(BB);
5822 Value *SrcVal = DestPN.getIncomingValue(Idx);
5825 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5829 DestPN.addIncoming(Incoming, Pred);
5856 std::vector<DominatorTree::UpdateType> Updates;
5860 if (UnwindDest ==
nullptr) {
5901 if (!SuccessorCleanupPad)
5910 SuccessorCleanupPad->eraseFromParent();
5919bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5936bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5968 BBI->dropDbgRecords();
5972 BBI->eraseFromParent();
5978 if (&BB->
front() != UI)
5981 std::vector<DominatorTree::UpdateType> Updates;
5984 for (BasicBlock *Predecessor : Preds) {
5992 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6003 "The destinations are guaranteed to be different here.");
6004 CallInst *Assumption;
6020 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6022 SwitchInstProfUpdateWrapper SU(*SI);
6023 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
6024 if (i->getCaseSuccessor() != BB) {
6029 i = SU.removeCase(i);
6034 if (DTU &&
SI->getDefaultDest() != BB)
6035 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6037 if (
II->getUnwindDest() == BB) {
6043 if (!CI->doesNotThrow())
6044 CI->setDoesNotThrow();
6048 if (CSI->getUnwindDest() == BB) {
6059 E = CSI->handler_end();
6062 CSI->removeHandler(
I);
6069 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6070 if (CSI->getNumHandlers() == 0) {
6071 if (CSI->hasUnwindDest()) {
6075 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
6076 Updates.push_back({DominatorTree::Insert,
6077 PredecessorOfPredecessor,
6078 CSI->getUnwindDest()});
6079 Updates.push_back({DominatorTree::Delete,
6080 PredecessorOfPredecessor, Predecessor});
6083 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
6090 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
6091 for (BasicBlock *EHPred : EHPreds)
6095 new UnreachableInst(CSI->getContext(), CSI->getIterator());
6096 CSI->eraseFromParent();
6101 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
6102 "Expected to always have an unwind to BB.");
6104 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6132static std::optional<ContiguousCasesResult>
6139 const APInt &Min = Cases.
back()->getValue();
6140 const APInt &Max = Cases.
front()->getValue();
6142 size_t ContiguousOffset = Cases.
size() - 1;
6143 if (
Offset == ContiguousOffset) {
6162 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
6163 return L->getValue() != R->getValue() + 1;
6165 if (It == Cases.
end())
6166 return std::nullopt;
6167 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
6168 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
6172 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
6175 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
6183 return std::nullopt;
6188 bool RemoveOrigDefaultBlock =
true) {
6190 auto *BB = Switch->getParent();
6191 auto *OrigDefaultBlock = Switch->getDefaultDest();
6192 if (RemoveOrigDefaultBlock)
6193 OrigDefaultBlock->removePredecessor(BB);
6197 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
6199 Switch->setDefaultDest(&*NewDefaultBlock);
6203 if (RemoveOrigDefaultBlock &&
6213bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
6215 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6217 bool HasDefault = !
SI->defaultDestUnreachable();
6219 auto *BB =
SI->getParent();
6221 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6226 for (
auto Case :
SI->cases()) {
6230 if (Dest == DestA) {
6236 if (Dest == DestB) {
6246 "Single-destination switch should have been folded.");
6248 assert(DestB !=
SI->getDefaultDest());
6249 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6253 std::optional<ContiguousCasesResult> ContiguousCases;
6256 if (!HasDefault && CasesA.
size() == 1)
6257 ContiguousCases = ContiguousCasesResult{
6265 else if (CasesB.
size() == 1)
6266 ContiguousCases = ContiguousCasesResult{
6275 else if (!HasDefault)
6279 if (!ContiguousCases)
6283 if (!ContiguousCases)
6286 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6292 Max->getValue() - Min->getValue() + 1);
6295 assert(
Max->getValue() == Min->getValue());
6300 else if (NumCases->
isNullValue() && !Cases->empty()) {
6304 if (!
Offset->isNullValue())
6312 SmallVector<uint64_t, 8> Weights;
6314 if (Weights.
size() == 1 +
SI->getNumCases()) {
6317 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6318 if (
SI->getSuccessor(
I) == Dest)
6319 TrueWeight += Weights[
I];
6321 FalseWeight += Weights[
I];
6323 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6334 unsigned PreviousEdges = Cases->size();
6335 if (Dest ==
SI->getDefaultDest())
6337 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6338 PHI.removeIncomingValue(
SI->getParent());
6341 unsigned PreviousEdges = OtherCases->size();
6342 if (OtherDest ==
SI->getDefaultDest())
6344 unsigned E = PreviousEdges - 1;
6348 for (
unsigned I = 0;
I !=
E; ++
I)
6349 PHI.removeIncomingValue(
SI->getParent());
6353 SmallVector<DominatorTree::UpdateType, 2> Updates;
6357 Updates.
push_back({DominatorTree::Delete, BB, OrigDefaultBlock});
6361 SI->eraseFromParent();
6364 Updates.
push_back({DominatorTree::Delete, BB, OtherDest});
6384 unsigned MaxSignificantBitsInCond =
6391 for (
const auto &Case :
SI->cases()) {
6392 auto *
Successor = Case.getCaseSuccessor();
6401 if (
Known.Zero.intersects(CaseVal) || !
Known.One.isSubsetOf(CaseVal) ||
6403 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6409 }
else if (IsKnownValuesValid)
6410 KnownValues.
erase(CaseC);
6417 bool HasDefault = !
SI->defaultDestUnreachable();
6418 const unsigned NumUnknownBits =
6421 if (HasDefault && DeadCases.
empty()) {
6427 if (NumUnknownBits < 64 ) {
6428 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6429 if (
SI->getNumCases() == AllNumCases) {
6436 if (
SI->getNumCases() == AllNumCases - 1) {
6437 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6439 if (CondTy->getIntegerBitWidth() > 64 ||
6440 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6444 for (
const auto &Case :
SI->cases())
6445 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6447 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6449 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6459 if (DeadCases.
empty())
6465 assert(CaseI !=
SI->case_default() &&
6466 "Case was not found. Probably mistake in DeadCases forming.");
6468 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6473 std::vector<DominatorTree::UpdateType> Updates;
6474 for (
auto *
Successor : UniqueSuccessors)
6475 if (NumPerSuccessorCases[
Successor] == 0)
6502 int Idx =
PHI.getBasicBlockIndex(BB);
6503 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6505 Value *InValue =
PHI.getIncomingValue(Idx);
6506 if (InValue != CaseValue)
6522 ForwardingNodesMap ForwardingNodes;
6525 for (
const auto &Case :
SI->cases()) {
6527 BasicBlock *CaseDest = Case.getCaseSuccessor();
6546 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6547 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6548 count(Phi.blocks(), SwitchBlock) == 1) {
6549 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6557 ForwardingNodes[Phi].push_back(PhiIdx);
6560 for (
auto &ForwardingNode : ForwardingNodes) {
6561 PHINode *Phi = ForwardingNode.first;
6567 for (
int Index : Indexes)
6568 Phi->setIncomingValue(Index,
SI->getCondition());
6578 if (
C->isThreadDependent())
6580 if (
C->isDLLImportDependent())
6588 if (
C->getType()->isScalableTy())
6599 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6626 if (
A->isAllOnesValue())
6628 if (
A->isNullValue())
6634 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6659 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6661 if (
I.isTerminator()) {
6663 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6666 CaseDest =
I.getSuccessor(0);
6673 for (
auto &
Use :
I.uses()) {
6676 if (
I->getParent() == CaseDest)
6679 if (Phi->getIncomingBlock(
Use) == CaseDest)
6692 *CommonDest = CaseDest;
6694 if (CaseDest != *CommonDest)
6699 int Idx =
PHI.getBasicBlockIndex(Pred);
6708 Res.push_back(std::make_pair(&
PHI, ConstVal));
6711 return Res.
size() > 0;
6717 SwitchCaseResultVectorTy &UniqueResults,
6719 for (
auto &
I : UniqueResults) {
6720 if (
I.first == Result) {
6721 I.second.push_back(CaseVal);
6722 return I.second.size();
6725 UniqueResults.push_back(
6736 SwitchCaseResultVectorTy &UniqueResults,
6740 for (
const auto &
I :
SI->cases()) {
6754 const size_t NumCasesForResult =
6762 if (UniqueResults.size() > MaxUniqueResults)
6778 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6780 return DefaultResult ||
SI->defaultDestUnreachable();
6801 const bool HasBranchWeights = !BranchWeights.
empty();
6803 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6804 ResultVector[1].second.size() == 1) {
6805 ConstantInt *FirstCase = ResultVector[0].second[0];
6806 ConstantInt *SecondCase = ResultVector[1].second[0];
6807 Value *SelectValue = ResultVector[1].first;
6808 if (DefaultResult) {
6809 Value *ValueCompare =
6810 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6811 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6812 DefaultResult,
"switch.select");
6814 SI && HasBranchWeights) {
6821 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6825 Value *ValueCompare =
6826 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6827 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6828 SelectValue,
"switch.select");
6834 size_t FirstCasePos = (Condition !=
nullptr);
6835 size_t SecondCasePos = FirstCasePos + 1;
6836 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6838 {BranchWeights[FirstCasePos],
6839 DefaultCase + BranchWeights[SecondCasePos]},
6846 if (ResultVector.size() == 1 && DefaultResult) {
6848 unsigned CaseCount = CaseValues.
size();
6861 for (
auto *Case : CaseValues) {
6862 if (Case->getValue().slt(MinCaseVal->
getValue()))
6864 AndMask &= Case->getValue();
6868 if (!AndMask.
isZero() &&
Known.getMaxValue().uge(AndMask)) {
6870 unsigned FreeBits =
Known.countMaxActiveBits() - AndMask.
popcount();
6874 if (FreeBits ==
Log2_32(CaseCount)) {
6875 Value *
And = Builder.CreateAnd(Condition, AndMask);
6876 Value *Cmp = Builder.CreateICmpEQ(
6879 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6895 for (
auto *Case : CaseValues)
6896 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6902 Condition = Builder.CreateSub(Condition, MinCaseVal);
6903 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6904 Value *Cmp = Builder.CreateICmpEQ(
6907 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6920 if (CaseValues.
size() == 2) {
6921 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6922 "switch.selectcmp.case1");
6923 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6924 "switch.selectcmp.case2");
6925 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6927 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6947 std::vector<DominatorTree::UpdateType> Updates;
6954 Builder.CreateBr(DestBB);
6958 PHI->removeIncomingValueIf(
6959 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6960 PHI->addIncoming(SelectValue, SelectBB);
6963 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6969 if (DTU && RemovedSuccessors.
insert(Succ).second)
6972 SI->eraseFromParent();
6986 SwitchCaseResultVectorTy UniqueResults;
6992 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6993 Builder.SetInsertPoint(
SI);
6995 [[maybe_unused]]
auto HasWeights =
6999 (BranchWeights.
size() >=
7000 UniqueResults.size() + (DefaultResult !=
nullptr)));
7003 Builder,
DL, BranchWeights);
7015class SwitchReplacement {
7023 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7024 Constant *DefaultValue,
const DataLayout &
DL,
7025 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
7034 static bool wouldFitInRegister(
const DataLayout &
DL,
uint64_t TableSize,
7041 bool isLookupTable();
7047 bool isValid()
const {
return Kind != InvalidKind; }
7084 ConstantInt *BitMap =
nullptr;
7085 IntegerType *BitMapElementTy =
nullptr;
7088 ConstantInt *LinearOffset =
nullptr;
7089 ConstantInt *LinearMultiplier =
nullptr;
7090 bool LinearMapValWrapped =
false;
7098SwitchReplacement::SwitchReplacement(
7100 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7101 Constant *DefaultValue,
const DataLayout &
DL,
7102 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
7103 : DefaultValue(DefaultValue) {
7104 assert(
Values.size() &&
"Can't build lookup table without values!");
7105 assert(TableSize >=
Values.size() &&
"Can't fit values in table!");
7108 SingleValue =
Values.begin()->second;
7114 for (
const auto &[CaseVal, CaseRes] :
Values) {
7117 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
7118 TableContents[Idx] = CaseRes;
7125 if (
Values.size() < TableSize) {
7127 "Need a default value to fill the lookup table holes.");
7130 if (!TableContents[
I])
7131 TableContents[
I] = DefaultValue;
7137 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
7138 SingleValue =
nullptr;
7144 Kind = SingleValueKind;
7151 bool LinearMappingPossible =
true;
7156 bool NonMonotonic =
false;
7157 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
7173 LinearMappingPossible =
false;
7178 APInt Dist = Val - PrevVal;
7181 }
else if (Dist != DistToPrev) {
7182 LinearMappingPossible =
false;
7190 if (LinearMappingPossible) {
7192 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
7193 APInt M = LinearMultiplier->getValue();
7194 bool MayWrap =
true;
7195 if (
isIntN(M.getBitWidth(), TableSize - 1))
7196 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
7197 LinearMapValWrapped = NonMonotonic || MayWrap;
7198 Kind = LinearMapKind;
7205 if (wouldFitInRegister(
DL, TableSize,
ValueType) &&
7208 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
7210 TableInt <<=
IT->getBitWidth();
7214 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
7217 BitMap = ConstantInt::get(M.getContext(), TableInt);
7218 BitMapElementTy =
IT;
7224 if (!
all_of(TableContents,
7236 unsigned NeededBitWidth =
7237 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7250 Kind = LookupTableKind;
7258 case SingleValueKind:
7260 case LinearMapKind: {
7264 false,
"switch.idx.cast");
7265 if (!LinearMultiplier->
isOne())
7266 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7268 !LinearMapValWrapped);
7270 if (!LinearOffset->
isZero())
7273 !LinearMapValWrapped);
7290 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7291 "switch.shiftamt",
true,
true);
7294 Value *DownShifted =
7295 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7297 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7299 case LookupTableKind: {
7302 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7303 true, GlobalVariable::PrivateLinkage,
7304 Initializer,
"switch.table." +
Func->getName());
7305 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7309 Type *IndexTy =
DL.getIndexType(
Table->getType());
7312 if (
Index->getType() != IndexTy) {
7313 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7317 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7320 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7324 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7333bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7335 Type *ElementType) {
7343 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7345 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7351 if (
TTI.isTypeLegal(Ty))
7366 DL.fitsInLegalInteger(
IT->getBitWidth());
7369Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7371bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7373bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7380 const uint64_t MinDensity = OptSize ? 40 : 10;
7385 return NumCases * 100 >= CaseRange * MinDensity;
7397static std::optional<unsigned>
7400 assert(
Values.size() > 1 &&
"expected multiple switch cases");
7402 return std::nullopt;
7407 for (
auto &V : ReducedValues) {
7409 ReducedValuesOr |= Reduced;
7410 V = (int64_t)Reduced;
7423 for (
auto &V : ReducedValues)
7424 V = (int64_t)((
uint64_t)V >> Shift);
7427 return std::nullopt;
7441 if (
SI->getNumCases() > TableSize)
7444 bool AllTablesFitInRegister =
true;
7445 bool HasIllegalType =
false;
7446 for (
const auto &Ty : ResultTypes) {
7451 AllTablesFitInRegister =
7452 AllTablesFitInRegister &&
7453 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7458 if (HasIllegalType && !AllTablesFitInRegister)
7463 if (AllTablesFitInRegister)
7471 SI->getFunction()->hasOptSize());
7481 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7484 return all_of(ResultTypes, [&](
const auto &ResultType) {
7485 return SwitchReplacement::wouldFitInRegister(
7535 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7540 for (
auto ValuePair :
Values) {
7543 if (!CaseConst || CaseConst == DefaultConst ||
7544 (CaseConst != TrueConst && CaseConst != FalseConst))
7558 if (DefaultConst == FalseConst) {
7561 ++NumTableCmpReuses;
7564 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7565 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7568 ++NumTableCmpReuses;
7578 bool ConvertSwitchToLookupTable) {
7579 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7593 if (
SI->getNumCases() < 3)
7615 MinCaseVal = CaseVal;
7617 MaxCaseVal = CaseVal;
7634 It->second.push_back(std::make_pair(CaseVal,
Value));
7643 &CommonDest, DefaultResultsList,
DL);
7644 for (
const auto &
I : DefaultResultsList) {
7647 DefaultResults[
PHI] = Result;
7651 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7654 if (UseSwitchConditionAsTableIndex) {
7656 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7661 TableIndexOffset = MinCaseVal;
7668 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7670 bool TableHasHoles = (NumResults < TableSize);
7675 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7683 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7686 if (
SI->getNumCases() < 4)
7688 if (!
DL.fitsInLegalInteger(TableSize))
7697 if (UseSwitchConditionAsTableIndex) {
7698 TableIndex =
SI->getCondition();
7699 if (HasDefaultResults) {
7711 all_of(ResultTypes, [&](
const auto &ResultType) {
7712 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7717 TableSize = std::max(UpperBound, TableSize);
7720 DefaultIsReachable =
false;
7728 const auto &ResultList = ResultLists[
PHI];
7730 Type *ResultType = ResultList.begin()->second->getType();
7735 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7736 ResultList, DefaultVal,
DL,
TTI, FuncName);
7737 if (!Replacement.isValid())
7739 PhiToReplacementMap.
insert({
PHI, Replacement});
7742 bool AnyLookupTables =
any_of(
7743 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7744 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7745 [](
auto &KV) {
return KV.second.isBitMap(); });
7753 if (AnyLookupTables &&
7754 (!
TTI.shouldBuildLookupTables() ||
7760 if (!ConvertSwitchToLookupTable &&
7761 (AnyLookupTables || AnyBitMaps || NeedMask))
7764 Builder.SetInsertPoint(
SI);
7767 if (!UseSwitchConditionAsTableIndex) {
7770 bool MayWrap =
true;
7771 if (!DefaultIsReachable) {
7776 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7777 "switch.tableidx",
false,
7781 std::vector<DominatorTree::UpdateType> Updates;
7787 assert(MaxTableSize >= TableSize &&
7788 "It is impossible for a switch to have more entries than the max "
7789 "representable value of its input integer type's size.");
7794 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7799 Builder.SetInsertPoint(
SI);
7800 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7801 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7802 Builder.CreateBr(LookupBB);
7808 Value *Cmp = Builder.CreateICmpULT(
7809 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7811 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7812 CondBranch = RangeCheckBranch;
7818 Builder.SetInsertPoint(LookupBB);
7824 MaskBB->
setName(
"switch.hole_check");
7831 APInt MaskInt(TableSizePowOf2, 0);
7832 APInt One(TableSizePowOf2, 1);
7834 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7835 for (
const auto &Result : ResultList) {
7838 MaskInt |= One << Idx;
7840 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7847 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7848 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7849 Value *LoBit = Builder.CreateTrunc(
7851 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7856 Builder.SetInsertPoint(LookupBB);
7860 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7863 SI->getDefaultDest()->removePredecessor(BB,
7870 const ResultListTy &ResultList = ResultLists[
PHI];
7871 auto Replacement = PhiToReplacementMap.
at(
PHI);
7872 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7875 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7878 for (
auto *
User :
PHI->users()) {
7880 Replacement.getDefaultValue(), ResultList);
7884 PHI->addIncoming(Result, LookupBB);
7887 Builder.CreateBr(CommonDest);
7892 const bool HasBranchWeights =
7899 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7902 if (Succ ==
SI->getDefaultDest()) {
7903 if (HasBranchWeights)
7904 ToDefaultWeight += BranchWeights[
I];
7908 if (DTU && RemovedSuccessors.
insert(Succ).second)
7910 if (HasBranchWeights)
7911 ToLookupWeight += BranchWeights[
I];
7913 SI->eraseFromParent();
7914 if (HasBranchWeights)
7921 ++NumLookupTablesHoles;
7937 if (CondTy->getIntegerBitWidth() > 64 ||
7938 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7942 if (
SI->getNumCases() < 4)
7950 for (
const auto &
C :
SI->cases())
7951 Values.push_back(
C.getCaseValue()->getValue().getSExtValue());
7955 bool OptSize =
SI->getFunction()->hasOptSize();
7962 std::optional<unsigned> Shift;
7992 Builder.SetInsertPoint(
SI);
7996 Value *Rot = Builder.CreateIntrinsic(
7997 Ty, Intrinsic::fshl,
7998 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - *Shift)});
7999 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
8001 for (
auto Case :
SI->cases()) {
8002 auto *Orig = Case.getCaseValue();
8003 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
8048 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
8049 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
8066 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
8069 return !Updates.
empty();
8089 if (
SI->defaultDestUnreachable())
8100 if (!
Known.isConstant())
8107 ConstantInt::get(
SI->getContext(),
Known.getConstant());
8109 if (CaseIt ==
SI->case_default()) {
8118 SI->case_default());
8120 assert(
SI->getNumCases() > 0 &&
"Switch should have at least one case");
8121 assert(
SI->findCaseValue(CaseVal) !=
SI->case_default() &&
8122 "Proven value should have a dedicated case");
8123 assert(
SI->defaultDestUnreachable());
8141 Value *Condition =
SI->getCondition();
8145 if (CondTy->getIntegerBitWidth() > 64 ||
8146 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8158 if (
SI->getNumCases() < 4)
8163 for (
const auto &Case :
SI->cases()) {
8164 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
8166 Values.push_back(CaseValue);
8176 SI->getFunction()->hasOptSize()))
8180 Builder.SetInsertPoint(
SI);
8182 if (!
SI->defaultDestUnreachable()) {
8185 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
8186 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
8188 auto *OrigBB =
SI->getParent();
8189 auto *DefaultCaseBB =
SI->getDefaultDest();
8191 auto It = OrigBB->getTerminator()->getIterator();
8203 NewWeights[1] = Weights[0] / 2;
8204 NewWeights[0] = OrigDenominator - NewWeights[1];
8216 Weights[0] = NewWeights[1];
8217 uint64_t CasesDenominator = OrigDenominator - Weights[0];
8219 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
8225 It->eraseFromParent();
8233 for (
auto &Case :
SI->cases()) {
8234 auto *OrigValue = Case.getCaseValue();
8235 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
8236 OrigValue->getValue().countr_zero()));
8240 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
8243 SI->setCondition(ConditionTrailingZeros);
8253 if (!Cmp || !Cmp->hasOneUse())
8264 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
8267 if (
SI->getNumCases() == 2) {
8274 Succ =
SI->getDefaultDest();
8275 SuccWeight = Weights[0];
8277 for (
auto &Case :
SI->cases()) {
8278 std::optional<int64_t> Val =
8282 if (!Missing.erase(*Val))
8287 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
8290 assert(Missing.size() == 1 &&
"Should have one case left");
8291 Res = *Missing.begin();
8292 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
8294 Unreachable =
SI->getDefaultDest();
8296 for (
auto &Case :
SI->cases()) {
8297 BasicBlock *NewSucc = Case.getCaseSuccessor();
8298 uint32_t Weight = Weights[Case.getSuccessorIndex()];
8301 OtherSuccWeight += Weight;
8304 SuccWeight = Weight;
8305 }
else if (Succ == NewSucc) {
8311 for (
auto &Case :
SI->cases()) {
8312 std::optional<int64_t> Val =
8314 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8316 if (Case.getCaseSuccessor() == Succ) {
8338 if (Cmp->isSigned())
8341 MDNode *NewWeights =
nullptr;
8347 Builder.SetInsertPoint(
SI->getIterator());
8348 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
8349 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8350 SI->getMetadata(LLVMContext::MD_unpredictable));
8354 SI->eraseFromParent();
8355 Cmp->eraseFromParent();
8356 if (DTU && Unreachable)
8381 assert(
BB &&
"Expected non-null BB");
8383 if (
BB->isEntryBlock())
8396 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8401 if (&
BB->front() != &
BB->back())
8416 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8427 return (*EBW->PhiPredIVs)[&Phi][BB];
8449 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8452 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8453 return PredIVs[
A] == PredIVs[
B];
8462 if (Candidates.
size() < 2)
8477 assert(Succ &&
"Expected unconditional BB");
8487 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8490 for (
auto &
IV : Phi->incoming_values())
8491 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8509 bool MadeChange =
false;
8523 if (!LivePreds.
contains(PredOfDead))
8530 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8531 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8536 T->replaceSuccessorWith(
Dead, Live);
8541 for (
const auto &EBW : BBs2Merge) {
8544 const auto &[It, Inserted] =
Keep.insert(&EBW);
8553 if (KeepBB == DeadBB)
8557 RedirectIncomingEdges(DeadBB, KeepBB);
8566 if (DTU && !Updates.
empty())
8572bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8573 DomTreeUpdater *DTU) {
8575 SmallSetVector<BasicBlock *, 16> FilteredArms(
8581bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8582 DomTreeUpdater *DTU) {
8593 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8599bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8602 if (isValueEqualityComparison(SI)) {
8606 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8607 return requestResimplify();
8611 if (simplifySwitchOnSelect(SI,
Select))
8612 return requestResimplify();
8616 if (SI == &*BB->
begin())
8617 if (foldValueComparisonIntoPredecessors(SI, Builder))
8618 return requestResimplify();
8624 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8625 return requestResimplify();
8629 return requestResimplify();
8632 return requestResimplify();
8635 return requestResimplify();
8638 return requestResimplify();
8643 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8645 Options.ConvertSwitchToLookupTable))
8646 return requestResimplify();
8649 return requestResimplify();
8652 return requestResimplify();
8655 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8656 return requestResimplify();
8660 if (simplifyDuplicateSwitchArms(SI, DTU))
8661 return requestResimplify();
8664 return requestResimplify();
8667 return requestResimplify();
8672bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8675 SmallVector<uint32_t> BranchWeights;
8678 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8679 if (HasBranchWeights)
8684 SmallPtrSet<Value *, 8> Succs;
8685 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8690 RemovedSuccs.
insert(Dest);
8700 std::vector<DominatorTree::UpdateType> Updates;
8701 Updates.reserve(RemovedSuccs.
size());
8702 for (
auto *RemovedSucc : RemovedSuccs)
8703 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8720 if (HasBranchWeights) {
8727 if (simplifyIndirectBrOnSelect(IBI, SI))
8728 return requestResimplify();
8764 if (BB == OtherPred)
8775 std::vector<DominatorTree::UpdateType> Updates;
8782 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8783 "unexpected successor");
8784 II->setUnwindDest(OtherPred);
8799 Builder.CreateUnreachable();
8808bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8820 bool NeedCanonicalLoop =
8834 if (
I->isTerminator() &&
8835 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8859 if (!PPred || (PredPred && PredPred != PPred))
8900 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8904 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8934 bool HasWeight =
false;
8939 BBTWeight = BBFWeight = 1;
8944 BB1TWeight = BB1FWeight = 1;
8949 BB2TWeight = BB2FWeight = 1;
8951 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8952 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8959bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
8963 "Tautological conditional branch should have been eliminated already.");
8966 if (!
Options.SimplifyCondBranch ||
8971 if (isValueEqualityComparison(BI)) {
8976 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8977 return requestResimplify();
8981 for (
auto &
I : *BB) {
8986 if (foldValueComparisonIntoPredecessors(BI, Builder))
8987 return requestResimplify();
8993 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
9006 return requestResimplify();
9012 if (
Options.SpeculateBlocks &&
9015 return requestResimplify();
9024 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
9025 return requestResimplify();
9027 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
9029 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
9030 auto CanSpeculateConditionalLoadsStores = [&]() {
9032 for (Instruction &
I : *Succ) {
9033 if (
I.isTerminator()) {
9034 if (
I.getNumSuccessors() > 1)
9038 SpeculatedConditionalLoadsStores.
size() ==
9042 SpeculatedConditionalLoadsStores.
push_back(&
I);
9045 return !SpeculatedConditionalLoadsStores.
empty();
9048 if (CanSpeculateConditionalLoadsStores()) {
9050 std::nullopt,
nullptr);
9051 return requestResimplify();
9061 return requestResimplify();
9070 return requestResimplify();
9076 if (foldCondBranchOnValueKnownInPredecessor(BI))
9077 return requestResimplify();
9084 return requestResimplify();
9092 return requestResimplify();
9096 return requestResimplify();
9103 assert(V->getType() ==
I->getType() &&
"Mismatched types");
9115 auto *Use = cast<Instruction>(U.getUser());
9118 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
9121 switch (Use->getOpcode()) {
9124 case Instruction::GetElementPtr:
9125 case Instruction::Ret:
9126 case Instruction::BitCast:
9127 case Instruction::Load:
9128 case Instruction::Store:
9129 case Instruction::Call:
9130 case Instruction::CallBr:
9131 case Instruction::Invoke:
9132 case Instruction::UDiv:
9133 case Instruction::URem:
9137 case Instruction::SDiv:
9138 case Instruction::SRem:
9142 if (FindUse ==
I->use_end())
9144 auto &
Use = *FindUse;
9158 if (
GEP->getPointerOperand() ==
I) {
9161 if (
GEP->getType()->isVectorTy())
9169 if (!
GEP->hasAllZeroIndices() &&
9170 (!
GEP->isInBounds() ||
9172 GEP->getPointerAddressSpace())))
9173 PtrValueMayBeModified =
true;
9179 bool HasNoUndefAttr =
9180 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
9185 if (
C->isNullValue() && HasNoUndefAttr &&
9186 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
9187 return !PtrValueMayBeModified;
9193 if (!LI->isVolatile())
9195 LI->getPointerAddressSpace());
9199 if (!
SI->isVolatile())
9201 SI->getPointerAddressSpace())) &&
9202 SI->getPointerOperand() ==
I;
9207 if (
I == Assume->getArgOperand(0))
9215 if (CB->getCalledOperand() ==
I)
9218 if (CB->isArgOperand(&
Use)) {
9219 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
9222 CB->paramHasNonNullAttr(ArgIdx,
false))
9223 return !PtrValueMayBeModified;
9242 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
9250 Builder.CreateUnreachable();
9251 T->eraseFromParent();
9263 Builder.CreateUnreachable();
9270 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
9272 Assumption = Builder.CreateAssumption(
Cond);
9287 Builder.SetInsertPoint(Unreachable);
9289 Builder.CreateUnreachable();
9290 for (
const auto &Case :
SI->cases())
9291 if (Case.getCaseSuccessor() == BB) {
9293 Case.setSuccessor(Unreachable);
9295 if (
SI->getDefaultDest() == BB) {
9297 SI->setDefaultDest(Unreachable);
9311bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9336 return requestResimplify();
9355 if (simplifyDuplicatePredecessors(BB, DTU))
9359 if (
Options.SpeculateBlocks &&
9366 Options.SpeculateUnpredictables))
9374 case Instruction::UncondBr:
9377 case Instruction::CondBr:
9380 case Instruction::Resume:
9383 case Instruction::CleanupRet:
9386 case Instruction::Switch:
9389 case Instruction::Unreachable:
9392 case Instruction::IndirectBr:
9400bool SimplifyCFGOpt::run(BasicBlock *BB) {
9410 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static bool IsIndirectCall(const MachineInstr *MI)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
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.
static cl::opt< uint32_t > SelectFalseWeight("profcheck-default-select-false-weight", cl::init(3U), cl::desc("When annotating `select` instructions, this value will be used " "for the second ('false') case."))
static cl::opt< uint32_t > SelectTrueWeight("profcheck-default-select-true-weight", cl::init(2U), cl::desc("When annotating `select` instructions, this value will be used " "for the first ('true') case."))
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange, bool OptSize)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool isProfitableToSpeculate(const CondBrInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool 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 std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
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 getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
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 reachesUncontrolledConvergentCallBeforeBlock(BasicBlock *From, BasicBlock *StopBB)
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static void hoistConditionalLoadsStores(CondBrInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool simplifySwitchDefaultBranch(SwitchInst *SI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static 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 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 shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static bool performBranchToCommonDestFolding(CondBrInst *BI, CondBrInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static std::optional< unsigned > getDenseSwitchRangeReductionShift(ArrayRef< int64_t > Values, int64_t Base, bool OptSize)
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool mergeConditionalStores(CondBrInst *PBI, CondBrInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeNestedCondBranch(CondBrInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool tryWidenCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool mergeIdenticalBBs(ArrayRef< BasicBlock * > Candidates, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static bool tryToMergeLandingPad(LandingPadInst *LPad, UncondBrInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, uintptr_t MaxUniqueResults)
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 trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isUncontrolledConvergentCall(CallBase *CB)
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, CondBrInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & front() const
Get the first element.
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
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 isConvergent() const
Determine if the invoke is convergent.
Value * getConvergenceControlToken() const
Return the convergence control token for this call, if it exists.
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.
bool isEquality() const
Determine if this is an equals/not equals predicate.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Conditional Branch instruction.
static CondBrInst * Create(Value *Cond, BasicBlock *IfTrue, BasicBlock *IfFalse, InsertPosition InsertBefore=nullptr)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setCondition(Value *V)
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
ConstantFP - Floating Point Values [float, double].
ConstantFolder - Create constants with minimum, target independent, folding.
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
A constant pointer value that points to null.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
iterator find(const_arg_type_t< KeyT > Val)
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
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.
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
LLVM_ABI CallInst * CreateAssumption(Value *Cond)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
UncondBrInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
LLVM_ABI void dropLocation()
Drop the instruction's debug location.
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.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
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()
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
iterator_range< user_iterator > users()
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
void insert_range(Range &&R)
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this store instruction.
Value * getPointerOperand()
Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Unconditional Branch instruction.
void setSuccessor(BasicBlock *NewSucc)
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i=0) const
'undef' values are things that do not have specified contents.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
auto m_UMin(const Opnd0 &Op0, const Opnd1 &Op1)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
LLVM_ABI bool foldBranchToCommonDest(CondBrInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, AssumptionCache *AC=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
RelativeUniformCounterPtr Values
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
@ Known
Known to have no common set bits.
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
@ Load
The value being inserted comes from a load (InsertElement only).
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
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...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=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...
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.
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Function *CtxF=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
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 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.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible immediate values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
auto succ_size(const MachineBasicBlock *BB)
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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"))
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< T1, 2 > &B1, const SmallVector< T2, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Constant * ConstantFoldCastInstruction(unsigned opcode, Constant *V, Type *DestTy)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const SimplifyQuery &Q, bool IgnoreFree=false)
Equivalent to isDereferenceableAndAlignedPointer with an alignment of 1.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
@ Keep
No function return thunk.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, const SimplifyQuery &SQ, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two BBs are equal depends on the contents of the BasicBlock and the incoming values ...
SmallDenseMap< BasicBlock *, Value *, 8 > BB2ValueMap
DenseMap< PHINode *, BB2ValueMap > Phi2IVsMap
static bool canBeMerged(const BasicBlock *BB)
static bool isEqual(const EqualBBWrapper *LHS, const EqualBBWrapper *RHS)
static unsigned getHashValue(const EqualBBWrapper *EBW)
An information struct used to provide DenseMap with the various necessary components for a given valu...
A MapVector that performs no allocations if smaller than a certain size.