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)
1435 if (MDNode *Unpredictable = PTI->
getMetadata(LLVMContext::MD_unpredictable))
1436 if (TI->
hasMetadata(LLVMContext::MD_unpredictable))
1437 NewSI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
1447 if (!InfLoopBlock) {
1455 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1462 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1464 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1469 ++NumFoldValueComparisonIntoPredecessors;
1477bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1480 Value *CV = isValueEqualityComparison(TI);
1481 assert(CV &&
"Not a comparison?");
1486 while (!Preds.empty()) {
1495 Value *PCV = isValueEqualityComparison(PTI);
1499 SmallSetVector<BasicBlock *, 4> FailBlocks;
1501 for (
auto *Succ : FailBlocks) {
1507 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1521 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1522 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1523 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1545 if (
I->mayReadFromMemory())
1577 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1585 if (J->getParent() == BB)
1607 if (
C1->isMustTailCall() != C2->isMustTailCall())
1610 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1616 if (CB1->cannotMerge() || CB1->isConvergent())
1619 if (CB2->cannotMerge() || CB2->isConvergent())
1634 if (!I1->hasDbgRecords())
1636 using CurrentAndEndIt =
1637 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1643 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1644 return Pair.first == Pair.second;
1650 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1656 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1658 if (!
Other->hasDbgRecords())
1661 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1668 while (
none_of(Itrs, atEnd)) {
1669 bool HoistDVRs = allIdentical(Itrs);
1670 for (CurrentAndEndIt &Pair : Itrs) {
1684 if (I1->isIdenticalToWhenDefined(I2,
true))
1689 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1690 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1691 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1693 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1694 return I1->getOperand(0) == I2->
getOperand(1) &&
1760 auto &Context = BI->
getParent()->getContext();
1765 Value *Mask =
nullptr;
1766 Value *MaskFalse =
nullptr;
1767 Value *MaskTrue =
nullptr;
1768 if (Invert.has_value()) {
1769 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1770 Mask = Builder.CreateBitCast(
1775 MaskFalse = Builder.CreateBitCast(
1777 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1779 auto PeekThroughBitcasts = [](
Value *V) {
1781 V = BitCast->getOperand(0);
1784 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1786 if (!Invert.has_value())
1787 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1792 auto *Op0 =
I->getOperand(0);
1793 CallInst *MaskedLoadStore =
nullptr;
1796 auto *Ty =
I->getType();
1798 Value *PassThru =
nullptr;
1799 if (Invert.has_value())
1800 for (
User *U :
I->users()) {
1802 PassThru = Builder.CreateBitCast(
1811 Builder.SetInsertPoint(Ins);
1814 MaskedLoadStore = Builder.CreateMaskedLoad(
1816 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range)) {
1825 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1828 I->replaceAllUsesWith(NewLoadStore);
1831 auto *StoredVal = Builder.CreateBitCast(
1833 MaskedLoadStore = Builder.CreateMaskedStore(
1842 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1846 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1847 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1850 I->eraseFromParent();
1857 bool IsStore =
false;
1880bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1881 bool AllInstsEqOnly) {
1897 for (
auto *Succ : UniqueSuccessors) {
1913 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1915 for (
auto *Succ : UniqueSuccessors) {
1919 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1922 if (AllInstsEqOnly) {
1928 unsigned Size0 = UniqueSuccessors[0]->size();
1929 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1933 Succ->
size() == Size0;
1937 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1938 while (LRI.isValid()) {
1940 if (
any_of(*LRI, [I0](Instruction *
I) {
1954 unsigned NumSkipped = 0;
1957 if (SuccIterPairs.
size() > 2) {
1960 if (SuccIterPairs.
size() < 2)
1967 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1968 auto &BB1ItrPair = *SuccIterPairBegin++;
1969 auto OtherSuccIterPairRange =
1975 bool AllInstsAreIdentical =
true;
1976 bool HasTerminator =
I1->isTerminator();
1977 for (
auto &SuccIter : OtherSuccIterRange) {
1981 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1982 AllInstsAreIdentical =
false;
1985 SmallVector<Instruction *, 8> OtherInsts;
1986 for (
auto &SuccIter : OtherSuccIterRange)
1991 if (HasTerminator) {
1995 if (NumSkipped || !AllInstsAreIdentical) {
2000 return hoistSuccIdenticalTerminatorToSwitchOrIf(
2001 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
2005 if (AllInstsAreIdentical) {
2006 unsigned SkipFlagsBB1 = BB1ItrPair.second;
2007 AllInstsAreIdentical =
2009 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
2011 unsigned SkipFlagsBB2 = Pair.second;
2026 AllInstsAreIdentical && CI && CI->isMustTailCall()) {
2027 AllInstsAreIdentical =
2028 NumSkipped == 0 &&
all_of(SuccIterPairs, [](
const SuccIterPair &
P) {
2033 if (AllInstsAreIdentical) {
2043 for (
auto &SuccIter : OtherSuccIterRange) {
2051 assert(
Success &&
"We should not be trying to hoist callbases "
2052 "with non-intersectable attributes");
2070 unsigned SkippedFlags = 0;
2071 for (
const SuccIterPair &
P : SuccIterPairs)
2072 SkippedFlags |=
P.second;
2075 I1->dropUBImplyingAttrsAndMetadata();
2078 NumHoistCommonCode += SuccIterPairs.size();
2080 NumHoistCommonInstrs += SuccIterPairs.size();
2089 for (
auto &SuccIterPair : SuccIterPairs) {
2098bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2099 Instruction *TI, Instruction *I1,
2100 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2110 auto *I2 = *OtherSuccTIs.
begin();
2130 for (PHINode &PN : Succ->
phis()) {
2131 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2132 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2133 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2153 if (!
NT->getType()->isVoidTy()) {
2154 I1->replaceAllUsesWith(NT);
2155 for (Instruction *OtherSuccTI : OtherSuccTIs)
2156 OtherSuccTI->replaceAllUsesWith(NT);
2160 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2166 for (
auto *OtherSuccTI : OtherSuccTIs)
2167 Locs.
push_back(OtherSuccTI->getDebugLoc());
2179 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2181 for (PHINode &PN : Succ->
phis()) {
2182 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2183 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2189 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2199 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2200 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2201 PN.setIncomingValue(i, SI);
2209 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
2213 if (DTU && VisitedSuccs.
insert(Succ).second)
2214 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2220 for (BasicBlock *Succ : UniqueSuccessors)
2221 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2235 if (
I->isIntDivRem())
2250 std::optional<unsigned> NumUses;
2251 for (
auto *
I : Insts) {
2254 I->getType()->isTokenTy())
2259 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2267 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2271 NumUses =
I->getNumUses();
2272 else if (NumUses !=
I->getNumUses())
2278 for (
auto *
I : Insts) {
2292 for (
const Use &U : I0->
uses()) {
2293 auto It = PHIOperands.find(&U);
2294 if (It == PHIOperands.end())
2297 if (!
equal(Insts, It->second))
2311 if (HaveIndirectCalls) {
2312 if (!AllCallsAreIndirect)
2316 Value *Callee =
nullptr;
2320 Callee = CurrCallee;
2321 else if (Callee != CurrCallee)
2327 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2333 if (!
all_of(Insts, SameAsI0)) {
2338 !
all_of(Insts, CanReplaceOperand))
2342 for (
auto *
I : Insts)
2343 Ops.push_back(
I->getOperand(OI));
2353 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2358 for (
auto *BB : Blocks) {
2360 I =
I->getPrevNode();
2385 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2388 PN->insertBefore(BBEnd->begin());
2389 for (
auto *
I : Insts)
2390 PN->addIncoming(
I->getOperand(O),
I->getParent());
2399 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2402 for (
auto *
I : Insts)
2422 assert(
Success &&
"We should not be trying to sink callbases "
2423 "with non-intersectable attributes");
2434 PN->replaceAllUsesWith(I0);
2435 PN->eraseFromParent();
2439 for (
auto *
I : Insts) {
2444 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2445 I->replaceAllUsesWith(I0);
2446 I->eraseFromParent();
2496 bool HaveNonUnconditionalPredecessors =
false;
2502 HaveNonUnconditionalPredecessors =
true;
2504 if (UnconditionalPreds.
size() < 2)
2517 for (
const Use &U : PN.incoming_values())
2518 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2519 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2521 Ops.push_back(*IncomingVals[Pred]);
2529 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2542 if (!followedByDeoptOrUnreachable) {
2544 auto IsMemOperand = [](
Use &U) {
2557 unsigned NumPHIInsts = 0;
2558 for (
Use &U : (*LRI)[0]->operands()) {
2559 auto It = PHIOperands.
find(&U);
2560 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2561 return InstructionsToSink.contains(V);
2568 if (IsMemOperand(U) &&
2569 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2576 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2577 return NumPHIInsts <= 1;
2594 while (Idx < ScanIdx) {
2595 if (!ProfitableToSinkInstruction(LRI)) {
2598 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2611 if (Idx < ScanIdx) {
2614 InstructionsToSink = InstructionsProfitableToSink;
2620 !ProfitableToSinkInstruction(LRI) &&
2621 "We already know that the last instruction is unprofitable to sink");
2629 for (
auto *
I : *LRI)
2630 InstructionsProfitableToSink.
erase(
I);
2631 if (!ProfitableToSinkInstruction(LRI)) {
2634 InstructionsToSink = InstructionsProfitableToSink;
2648 if (HaveNonUnconditionalPredecessors) {
2649 if (!followedByDeoptOrUnreachable) {
2657 bool Profitable =
false;
2658 while (Idx < ScanIdx) {
2692 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2694 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2702 NumSinkCommonInstrs++;
2706 ++NumSinkCommonCode;
2712struct CompatibleSets {
2713 using SetTy = SmallVector<InvokeInst *, 2>;
2719 SetTy &getCompatibleSet(InvokeInst *
II);
2721 void insert(InvokeInst *
II);
2724CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2729 for (CompatibleSets::SetTy &Set : Sets) {
2730 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2735 return Sets.emplace_back();
2738void CompatibleSets::insert(InvokeInst *
II) {
2739 getCompatibleSet(
II).emplace_back(
II);
2743 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2746 auto IsIllegalToMerge = [](InvokeInst *
II) {
2747 return II->cannotMerge() ||
II->isInlineAsm();
2749 if (
any_of(Invokes, IsIllegalToMerge))
2757 if (HaveIndirectCalls) {
2758 if (!AllCallsAreIndirect)
2763 for (InvokeInst *
II : Invokes) {
2764 Value *CurrCallee =
II->getCalledOperand();
2765 assert(CurrCallee &&
"There is always a called operand.");
2768 else if (Callee != CurrCallee)
2775 auto HasNormalDest = [](InvokeInst *
II) {
2778 if (
any_of(Invokes, HasNormalDest)) {
2781 if (!
all_of(Invokes, HasNormalDest))
2786 for (InvokeInst *
II : Invokes) {
2788 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2790 NormalBB = CurrNormalBB;
2791 else if (NormalBB != CurrNormalBB)
2799 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2808 for (InvokeInst *
II : Invokes) {
2810 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2812 UnwindBB = CurrUnwindBB;
2814 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2821 Invokes.front()->getUnwindDest(),
2822 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2827 const InvokeInst *II0 = Invokes.front();
2828 for (
auto *
II : Invokes.drop_front())
2833 auto IsIllegalToMergeArguments = [](
auto Ops) {
2834 Use &U0 = std::get<0>(
Ops);
2835 Use &U1 = std::get<1>(
Ops);
2841 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2842 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2843 IsIllegalToMergeArguments))
2855 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2861 bool HasNormalDest =
2866 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2870 II0->
getParent()->getIterator()->getNextNode();
2875 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2879 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2881 if (!HasNormalDest) {
2885 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2893 return MergedInvoke;
2907 SuccBBOfMergedInvoke});
2930 return II->getOperand(U.getOperandNo()) != U.get();
2949 Invokes.
front()->getParent());
2957 if (!MergedDebugLoc)
2958 MergedDebugLoc =
II->getDebugLoc();
2966 OrigSuccBB->removePredecessor(
II->getParent());
2972 assert(
Success &&
"Merged invokes with incompatible attributes");
2975 II->replaceAllUsesWith(MergedInvoke);
2976 II->eraseFromParent();
2980 ++NumInvokeSetsFormed;
3016 CompatibleSets Grouper;
3026 if (Invokes.
size() < 2)
3038class EphemeralValueTracker {
3039 SmallPtrSet<const Instruction *, 32> EphValues;
3041 bool isEphemeral(
const Instruction *
I) {
3044 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3045 all_of(
I->users(), [&](
const User *U) {
3046 return EphValues.count(cast<Instruction>(U));
3051 bool track(
const Instruction *
I) {
3052 if (isEphemeral(
I)) {
3105 unsigned MaxNumInstToLookAt = 9;
3109 if (!MaxNumInstToLookAt)
3111 --MaxNumInstToLookAt;
3124 if (
SI->getPointerOperand() == StorePtr &&
3125 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3126 SI->getAlign() >= StoreToHoist->
getAlign()) {
3128 PreviousAccess =
SI;
3129 return SI->getValueOperand();
3135 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3136 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3138 bool ExplicitlyDereferenceableOnly;
3146 (!ExplicitlyDereferenceableOnly ||
3150 PreviousAccess = LI;
3165 unsigned &SpeculatedInstructions,
3173 bool HaveRewritablePHIs =
false;
3175 Value *OrigV = PN.getIncomingValueForBlock(BB);
3176 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3183 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3192 HaveRewritablePHIs =
true;
3195 if (!OrigCE && !ThenCE)
3202 if (OrigCost + ThenCost > MaxCost)
3209 ++SpeculatedInstructions;
3210 if (SpeculatedInstructions > 1)
3214 return HaveRewritablePHIs;
3218 std::optional<bool> Invert,
3222 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3229 if (!Invert.has_value())
3232 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3236 return BIEndProb < Likely;
3276bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3277 BasicBlock *ThenBB) {
3288 bool Invert =
false;
3303 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3305 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3307 unsigned SpeculatedInstructions = 0;
3308 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3309 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3310 Value *SpeculatedStoreValue =
nullptr;
3311 StoreInst *SpeculatedStore =
nullptr;
3313 EphemeralValueTracker EphTracker;
3328 if (EphTracker.track(&
I))
3333 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3335 SpeculatedConditionalLoadsStores.
size() <
3339 if (IsSafeCheapLoadStore)
3340 SpeculatedConditionalLoadsStores.
push_back(&
I);
3342 ++SpeculatedInstructions;
3344 if (SpeculatedInstructions > 1)
3348 if (!IsSafeCheapLoadStore &&
3352 PreviousStoreAccess))))
3354 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3360 if (!SpeculatedStore && SpeculatedStoreValue)
3366 for (Use &
Op :
I.operands()) {
3371 ++SinkCandidateUseCounts[OpI];
3378 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3379 if (Inst->hasNUses(
Count)) {
3380 ++SpeculatedInstructions;
3381 if (SpeculatedInstructions > 1)
3388 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3391 SpeculatedInstructions,
Cost,
TTI);
3392 if (!Convert ||
Cost > Budget)
3396 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3401 if (SpeculatedStoreValue) {
3405 Value *FalseV = SpeculatedStoreValue;
3409 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3439 for (DbgVariableRecord *DbgAssign :
3442 DbgAssign->replaceVariableLocationOp(OrigV, S);
3452 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3454 I.dropUBImplyingAttrsAndMetadata();
3456 assert(PreviousStoreAccess &&
"Missing previous store access");
3459 I.dropUBImplyingAttrsAndMetadata();
3460 I.setAAMetadata(MergedAA);
3464 if (EphTracker.contains(&
I)) {
3466 I.eraseFromParent();
3472 for (
auto &It : *ThenBB)
3477 !DVR || !DVR->isDbgAssign())
3478 It.dropOneDbgRecord(&DR);
3480 std::prev(ThenBB->end()));
3482 if (!SpeculatedConditionalLoadsStores.
empty())
3488 for (PHINode &PN : EndBB->
phis()) {
3489 unsigned OrigI = PN.getBasicBlockIndex(BB);
3490 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3491 Value *OrigV = PN.getIncomingValue(OrigI);
3492 Value *ThenV = PN.getIncomingValue(ThenI);
3501 Value *TrueV = ThenV, *FalseV = OrigV;
3506 BrCond, TrueV, FalseV, PN.getFastMathFlagsOrNone(),
"spec.select", BI);
3507 PN.setIncomingValue(OrigI, V);
3508 PN.setIncomingValue(ThenI, V);
3512 for (Instruction *
I : SpeculatedPseudoProbes)
3513 I->eraseFromParent();
3526 if (!ReachesNonLocalUses.
insert(BB).second)
3541 EphemeralValueTracker EphTracker;
3548 if (CI->cannotDuplicate() || CI->isConvergent())
3561 for (
User *U :
I.users()) {
3564 if (UsedInBB == BB) {
3568 NonLocalUseBlocks.
insert(UsedInBB);
3582 if (
I &&
I->getParent() == To)
3602 static constexpr unsigned MaxInstructionsToScan = 512;
3616 unsigned NumScannedInstructions = 0;
3617 while (!Worklist.
empty()) {
3621 if (!CanReachStop.
insert(BB).second)
3625 if (++NumScannedInstructions > MaxInstructionsToScan)
3629 BlocksWithUncontrolledConvergentCalls.
insert(BB);
3643 while (!Worklist.
empty()) {
3645 if (BB == StopBB || !CanReachStop.
contains(BB))
3648 if (!Visited.
insert(BB).second)
3651 if (BlocksWithUncontrolledConvergentCalls.
contains(BB))
3683 KnownValues[CB].
insert(Pred);
3687 if (KnownValues.
empty())
3712 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3715 for (
const auto &Pair : KnownValues) {
3732 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3745 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3748 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3758 EdgeBB->setName(RealDest->
getName() +
".critedge");
3759 EdgeBB->moveBefore(RealDest);
3769 TranslateMap[
Cond] = CB;
3782 N->insertInto(EdgeBB, InsertPt);
3785 N->setName(BBI->getName() +
".c");
3796 if (!BBI->use_empty())
3797 TranslateMap[&*BBI] = V;
3798 if (!
N->mayHaveSideEffects()) {
3799 N->eraseFromParent();
3804 if (!BBI->use_empty())
3805 TranslateMap[&*BBI] =
N;
3811 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3812 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3813 SrcDbgCursor = std::next(BBI);
3815 N->cloneDebugInfoFrom(&*BBI);
3824 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3825 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3826 InsertPt->cloneDebugInfoFrom(BI);
3847 return std::nullopt;
3853bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3860 std::optional<bool>
Result;
3861 bool EverChanged =
false;
3867 }
while (Result == std::nullopt);
3876 bool SpeculateUnpredictables) {
3898 return isa<UncondBrInst>(IfBlock->getTerminator());
3901 "Will have either one or two blocks to speculate.");
3908 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3909 if (!IsUnpredictable) {
3912 (TWeight + FWeight) != 0) {
3917 if (IfBlocks.
size() == 1) {
3919 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3920 if (BIBBProb >= Likely)
3923 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3932 if (IfCondPhiInst->getParent() == BB)
3940 unsigned NumPhis = 0;
3953 if (SpeculateUnpredictables && IsUnpredictable)
3954 Budget +=
TTI.getBranchMispredictPenalty();
3967 AggressiveInsts, Cost, Budget,
TTI, AC,
3968 ZeroCostInstructions) ||
3970 AggressiveInsts, Cost, Budget,
TTI, AC,
3971 ZeroCostInstructions))
3984 auto IsBinOpOrAndEq = [](
Value *V) {
4020 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
4022 <<
" F: " << IfFalse->
getName() <<
"\n");
4039 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
4044 PN->eraseFromParent();
4050 Builder.CreateBr(BB);
4071 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
4072 if (
Opc == Instruction::And)
4073 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
4074 if (
Opc == Instruction::Or)
4075 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
4087 bool PredHasWeights =
4089 bool SuccHasWeights =
4091 if (PredHasWeights || SuccHasWeights) {
4092 if (!PredHasWeights)
4093 PredTrueWeight = PredFalseWeight = 1;
4094 if (!SuccHasWeights)
4095 SuccTrueWeight = SuccFalseWeight = 1;
4105static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
4108 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
4110 "PredBB must be a predecessor of BB.");
4118 (PTWeight + PFWeight) != 0) {
4121 Likely =
TTI->getPredictableBranchThreshold();
4126 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4127 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4131 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4134 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4135 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4141 return std::nullopt;
4154 bool InvertPredCond;
4155 std::tie(CommonSucc,
Opc, InvertPredCond) =
4158 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4166 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4171 if (InvertPredCond) {
4184 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4187 SuccTrueWeight, SuccFalseWeight)) {
4193 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4198 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4199 PredTrueWeight * SuccFalseWeight);
4205 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4206 PredFalseWeight * SuccTrueWeight);
4208 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4251 if (!MDWeights.
empty()) {
4252 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4260 ++NumFoldBranchToCommonDest;
4267 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4268 return U->getType()->isVectorTy();
4279 unsigned BonusInstThreshold) {
4288 Cond->getParent() != BB || !
Cond->hasOneUse())
4309 bool InvertPredCond;
4311 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4322 Cost +=
TTI->getArithmeticInstrCost(Instruction::Xor, Ty, CostKind);
4343 unsigned NumBonusInsts = 0;
4344 bool SawVectorOp =
false;
4345 const unsigned PredCount = Preds.
size();
4349 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4367 if (!
TTI ||
TTI->getInstructionCost(&
I, CostKind) !=
4369 NumBonusInsts += PredCount;
4377 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4380 return PN->getIncomingBlock(U) == BB;
4381 return UI->
getParent() == BB &&
I.comesBefore(UI);
4385 if (!
all_of(
I.uses(), IsBCSSAUse))
4389 BonusInstThreshold *
4405 for (
auto *BB : {BB1, BB2}) {
4421 Value *AlternativeV =
nullptr) {
4447 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4448 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4456 if (!AlternativeV &&
4462 PHI->addIncoming(V, BB);
4472 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4481 if (!PStore || !QStore)
4504 if (
I.mayReadOrWriteMemory())
4506 for (
auto &
I : *QFB)
4507 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4510 for (
auto &
I : *QTB)
4511 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4515 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4529 for (
auto &
I : *BB) {
4531 if (
I.isTerminator())
4549 "When we run out of budget we will eagerly return from within the "
4550 "per-instruction loop.");
4554 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4556 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4557 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4591 InvertPCond ^= (PStore->
getParent() != PTB);
4592 InvertQCond ^= (QStore->
getParent() != QTB);
4612 {CombinedWeights[0], CombinedWeights[1]},
4619 SI->copyMetadata(*QStore);
4625 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4628 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4691 bool InvertPCond =
false, InvertQCond =
false;
4697 if (QFB == PostBB) {
4716 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4719 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4727 for (
auto *BB : {PTB, PFB}) {
4732 PStoreAddresses.
insert(
SI->getPointerOperand());
4734 for (
auto *BB : {QTB, QFB}) {
4739 QStoreAddresses.
insert(
SI->getPointerOperand());
4745 auto &CommonAddresses = PStoreAddresses;
4748 for (
auto *Address : CommonAddresses)
4751 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4769 !BI->
getParent()->getSinglePredecessor())
4771 if (!IfFalseBB->
phis().empty())
4781 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4855 if (&*BB->
begin() != BI)
4883 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4885 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4889 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4892 if (CommonDestProb >= Likely)
4902 unsigned NumPhis = 0;
4924 if (OtherDest == BB) {
4932 OtherDest = InfLoopBlock;
4944 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4948 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4952 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4967 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4968 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4971 SuccTrueWeight, SuccFalseWeight);
4973 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4974 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4975 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4976 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4980 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4981 PredOther * SuccCommon,
4982 PredOther * SuccOther};
4989 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4991 assert(
SI->getCondition() == PBICond);
5008 Value *BIV = PN.getIncomingValueForBlock(BB);
5009 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
5010 Value *PBIV = PN.getIncomingValue(PBBIdx);
5014 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
5015 PN.setIncomingValue(PBBIdx, NV);
5019 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
5020 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
5040bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
5042 BasicBlock *FalseBB,
5043 uint32_t TrueWeight,
5044 uint32_t FalseWeight) {
5051 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
5053 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
5056 for (BasicBlock *Succ :
successors(OldTerm)) {
5058 if (Succ == KeepEdge1)
5059 KeepEdge1 =
nullptr;
5060 else if (Succ == KeepEdge2)
5061 KeepEdge2 =
nullptr;
5066 if (Succ != TrueBB && Succ != FalseBB)
5067 RemovedSuccessors.
insert(Succ);
5075 if (!KeepEdge1 && !KeepEdge2) {
5076 if (TrueBB == FalseBB) {
5087 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
5107 SmallVector<DominatorTree::UpdateType, 2> Updates;
5109 for (
auto *RemovedSuccessor : RemovedSuccessors)
5110 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
5125bool SimplifyCFGOpt::simplifySwitchOnSelectRemap(SwitchInst *SI,
5127 ConstantInt *
C,
bool Negate) {
5138 BasicBlock *DestFork =
SI->findCaseValue(K)->getCaseSuccessor();
5139 auto CaseC =
SI->findCaseValue(
C);
5140 bool IsDefault = CaseC ==
SI->case_default();
5142 BasicBlock *OldDest = CaseC->getCaseSuccessor();
5147 SI->setCondition(
X);
5149 if (OldDest != DestFork) {
5153 SI->addCase(
C, DestFork);
5155 CaseC->setSuccessor(DestFork);
5162 bool OldDestStillTargeted =
any_of(
5163 successors(SI), [&](BasicBlock *Succ) {
return Succ == OldDest; });
5164 if (DTU && !OldDestStillTargeted)
5165 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
5170 SmallVector<uint32_t> SwitchWeights;
5178 bool SelectHasBranchWeights =
5183 if (SwitchHasBranchWeights && SelectHasBranchWeights &&
5191 SmallVector<uint64_t> NewSwitchWeights;
5192 NewSwitchWeights.reserve(SwitchWeights.
size());
5193 NewSwitchWeights.push_back(SwitchWeights[0] * SelectTotalWeight);
5194 for (
const auto &[SwitchCase, SwitchWeight] :
5196 if (SwitchCase.getCaseValue() ==
C) {
5198 }
else if (SwitchCase.getCaseValue() == K) {
5202 uint64_t ProbabilityKeyEqualsK = SwitchWeight * SelectTotalWeight;
5205 ProbabilityKeyEqualsK > ProbabilityXEqualsC
5206 ? ProbabilityKeyEqualsK - ProbabilityXEqualsC
5208 NewSwitchWeights.push_back(ProbabilityXEqualsK);
5210 NewSwitchWeights.push_back(SwitchWeight * SelectTotalWeight);
5214 }
else if (SwitchHasBranchWeights) {
5220 SI->setMetadata(LLVMContext::MD_prof,
nullptr);
5234bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
5239 if (
Select->hasOneUse() &&
5243 simplifySwitchOnSelectRemap(SI,
Select,
X,
C, Pred == ICmpInst::ICMP_NE))
5249 if (!TrueVal || !FalseVal)
5254 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
5255 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5258 uint32_t TrueWeight = 0, FalseWeight = 0;
5259 SmallVector<uint64_t, 8> Weights;
5263 if (Weights.
size() == 1 +
SI->getNumCases()) {
5265 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5267 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5272 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5281bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5295 SmallVector<uint32_t> SelectBranchWeights(2);
5298 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5299 SelectBranchWeights[0],
5300 SelectBranchWeights[1]);
5320bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5324 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5370bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5389 ConstantInt *NewCaseVal;
5397 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5403 SelectTrueVal = Builder.
getTrue();
5404 SelectFalseVal = Builder.
getFalse();
5407 SelectCond =
Select->getCondition();
5409 if (SelectCond != ICI)
5411 SelectTrueVal =
Select->getTrueValue();
5412 SelectFalseVal =
Select->getFalseValue();
5417 if (
SI->getCondition() != IcmpCond)
5423 if (
SI->getDefaultDest() != BB) {
5424 ConstantInt *VVal =
SI->findCaseDest(BB);
5425 assert(VVal &&
"Should have a unique destination value");
5433 return requestResimplify();
5439 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5441 if (Predicate == ICmpInst::ICMP_EQ)
5449 return requestResimplify();
5456 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5462 Value *DefaultCst = SelectFalseVal;
5463 Value *NewCst = SelectTrueVal;
5471 Select->replaceAllUsesWith(DefaultCst);
5472 Select->eraseFromParent();
5478 SmallVector<DominatorTree::UpdateType, 2> Updates;
5485 SwitchInstProfUpdateWrapper SIW(*SI);
5486 auto W0 = SIW.getSuccessorWeight(0);
5490 SIW.setSuccessorWeight(0, *NewW);
5492 SIW.addCase(NewCaseVal, NewBB, NewW);
5494 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5503 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5511bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5513 const DataLayout &
DL) {
5523 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5525 SmallVectorImpl<ConstantInt *> &
Values = ConstantCompare.Vals;
5526 Value *CompVal = ConstantCompare.CompValue;
5527 unsigned UsedICmps = ConstantCompare.UsedICmps;
5528 Value *ExtraCase = ConstantCompare.Extra;
5529 bool TrueWhenEqual = ConstantCompare.IsEq;
5546 if (ExtraCase &&
Values.size() < 2)
5549 SmallVector<uint32_t> BranchWeights;
5555 if (!TrueWhenEqual) {
5558 std::swap(BranchWeights[0], BranchWeights[1]);
5564 <<
" cases into SWITCH. BB is:\n"
5567 SmallVector<DominatorTree::UpdateType, 2> Updates;
5574 nullptr,
"switch.early.test");
5585 AssumptionCache *AC =
Options.AC;
5591 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5598 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5604 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5605 <<
"\nEXTRABB = " << *BB);
5613 "Should not end up here with unstable pointers");
5615 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5620 if (
Values.front()->getValue() -
Values.back()->getValue() ==
5623 Values.back()->getValue(),
Values.front()->getValue() + 1);
5625 ICmpInst::Predicate Pred;
5637 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5638 NewBI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5643 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5644 New->setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5649 SmallVector<uint32_t> NewWeights(
Values.size() + 1);
5650 NewWeights[0] = BranchWeights[1];
5653 V = BranchWeights[0] /
Values.size();
5660 for (ConstantInt *Val :
Values)
5661 New->addCase(Val, EdgeBB);
5669 for (
unsigned i = 0, e =
Values.size() - 1; i != e; ++i)
5679 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5683bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5685 return simplifyCommonResume(RI);
5689 return simplifySingleResume(RI);
5698 if (!
II ||
II->getIntrinsicID() != Intrinsic::lifetime_end)
5705bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5714 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5718 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues(); Idx !=
End;
5720 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5721 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5725 if (IncomingBB->getUniqueSuccessor() != BB)
5730 if (IncomingValue != LandingPad)
5734 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5735 TrivialUnwindBlocks.
insert(IncomingBB);
5739 if (TrivialUnwindBlocks.
empty())
5743 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5747 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5750 for (BasicBlock *Pred :
5761 TrivialBB->getTerminator()->eraseFromParent();
5762 new UnreachableInst(RI->
getContext(), TrivialBB);
5764 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5771 return !TrivialUnwindBlocks.empty();
5775bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5779 "Resume must unwind the exception that caused control to here");
5835 int Idx = DestPN.getBasicBlockIndex(BB);
5849 Value *SrcVal = DestPN.getIncomingValue(Idx);
5852 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5856 DestPN.addIncoming(Incoming, Pred);
5883 std::vector<DominatorTree::UpdateType> Updates;
5887 if (UnwindDest ==
nullptr) {
5928 if (!SuccessorCleanupPad)
5937 SuccessorCleanupPad->eraseFromParent();
5946bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5963bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5995 BBI->dropDbgRecords();
5999 BBI->eraseFromParent();
6005 if (&BB->
front() != UI)
6008 std::vector<DominatorTree::UpdateType> Updates;
6011 for (BasicBlock *Predecessor : Preds) {
6019 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6030 "The destinations are guaranteed to be different here.");
6047 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6049 SwitchInstProfUpdateWrapper SU(*SI);
6050 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
6051 if (i->getCaseSuccessor() != BB) {
6056 i = SU.removeCase(i);
6061 if (DTU &&
SI->getDefaultDest() != BB)
6062 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6064 if (
II->getUnwindDest() == BB) {
6070 if (!CI->doesNotThrow())
6071 CI->setDoesNotThrow();
6075 if (CSI->getUnwindDest() == BB) {
6086 E = CSI->handler_end();
6089 CSI->removeHandler(
I);
6096 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6097 if (CSI->getNumHandlers() == 0) {
6098 if (CSI->hasUnwindDest()) {
6102 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
6103 Updates.push_back({DominatorTree::Insert,
6104 PredecessorOfPredecessor,
6105 CSI->getUnwindDest()});
6106 Updates.push_back({DominatorTree::Delete,
6107 PredecessorOfPredecessor, Predecessor});
6110 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
6117 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
6118 for (BasicBlock *EHPred : EHPreds)
6122 new UnreachableInst(CSI->getContext(), CSI->getIterator());
6123 CSI->eraseFromParent();
6128 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
6129 "Expected to always have an unwind to BB.");
6131 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6159static std::optional<ContiguousCasesResult>
6166 const APInt &Min = Cases.
back()->getValue();
6167 const APInt &Max = Cases.
front()->getValue();
6169 size_t ContiguousOffset = Cases.
size() - 1;
6170 if (
Offset == ContiguousOffset) {
6189 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
6190 return L->getValue() != R->getValue() + 1;
6192 if (It == Cases.
end())
6193 return std::nullopt;
6194 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
6195 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
6199 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
6202 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
6210 return std::nullopt;
6215 bool RemoveOrigDefaultBlock =
true) {
6217 auto *BB = Switch->getParent();
6218 auto *OrigDefaultBlock = Switch->getDefaultDest();
6219 if (RemoveOrigDefaultBlock)
6220 OrigDefaultBlock->removePredecessor(BB);
6224 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
6226 Switch->setDefaultDest(&*NewDefaultBlock);
6230 if (RemoveOrigDefaultBlock &&
6240bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
6242 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6244 bool HasDefault = !
SI->defaultDestUnreachable();
6246 auto *BB =
SI->getParent();
6248 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6253 for (
auto Case :
SI->cases()) {
6257 if (Dest == DestA) {
6263 if (Dest == DestB) {
6273 "Single-destination switch should have been folded.");
6275 assert(DestB !=
SI->getDefaultDest());
6276 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6280 std::optional<ContiguousCasesResult> ContiguousCases;
6283 if (!HasDefault && CasesA.
size() == 1)
6284 ContiguousCases = ContiguousCasesResult{
6292 else if (CasesB.
size() == 1)
6293 ContiguousCases = ContiguousCasesResult{
6302 else if (!HasDefault)
6306 if (!ContiguousCases)
6310 if (!ContiguousCases)
6313 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6319 Max->getValue() - Min->getValue() + 1);
6322 assert(
Max->getValue() == Min->getValue());
6327 else if (NumCases->
isNullValue() && !Cases->empty()) {
6331 if (!
Offset->isNullValue())
6339 SmallVector<uint64_t, 8> Weights;
6341 if (Weights.
size() == 1 +
SI->getNumCases()) {
6344 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6345 if (
SI->getSuccessor(
I) == Dest)
6346 TrueWeight += Weights[
I];
6348 FalseWeight += Weights[
I];
6350 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6361 unsigned PreviousEdges = Cases->size();
6362 if (Dest ==
SI->getDefaultDest())
6364 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6365 PHI.removeIncomingValue(
SI->getParent());
6368 unsigned PreviousEdges = OtherCases->size();
6369 if (OtherDest ==
SI->getDefaultDest())
6371 unsigned E = PreviousEdges - 1;
6375 for (
unsigned I = 0;
I !=
E; ++
I)
6376 PHI.removeIncomingValue(
SI->getParent());
6380 SmallVector<DominatorTree::UpdateType, 2> Updates;
6384 Updates.
push_back({DominatorTree::Delete, BB, OrigDefaultBlock});
6388 SI->eraseFromParent();
6391 Updates.
push_back({DominatorTree::Delete, BB, OtherDest});
6411 unsigned MaxSignificantBitsInCond =
6418 for (
const auto &Case :
SI->cases()) {
6419 auto *
Successor = Case.getCaseSuccessor();
6428 if (
Known.Zero.intersects(CaseVal) || !
Known.One.isSubsetOf(CaseVal) ||
6430 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6436 }
else if (IsKnownValuesValid)
6437 KnownValues.
erase(CaseC);
6444 bool HasDefault = !
SI->defaultDestUnreachable();
6445 const unsigned NumUnknownBits =
6448 if (HasDefault && DeadCases.
empty()) {
6454 if (NumUnknownBits < 64 ) {
6455 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6456 if (
SI->getNumCases() == AllNumCases) {
6463 if (
SI->getNumCases() == AllNumCases - 1) {
6464 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6466 if (CondTy->getIntegerBitWidth() > 64 ||
6467 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6471 for (
const auto &Case :
SI->cases())
6472 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6474 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6476 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6486 if (DeadCases.
empty())
6492 assert(CaseI !=
SI->case_default() &&
6493 "Case was not found. Probably mistake in DeadCases forming.");
6495 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6500 std::vector<DominatorTree::UpdateType> Updates;
6501 for (
auto *
Successor : UniqueSuccessors)
6502 if (NumPerSuccessorCases[
Successor] == 0)
6529 int Idx =
PHI.getBasicBlockIndex(BB);
6530 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6532 Value *InValue =
PHI.getIncomingValue(Idx);
6533 if (InValue != CaseValue)
6549 ForwardingNodesMap ForwardingNodes;
6552 for (
const auto &Case :
SI->cases()) {
6554 BasicBlock *CaseDest = Case.getCaseSuccessor();
6573 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6574 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6575 count(Phi.blocks(), SwitchBlock) == 1) {
6576 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6584 ForwardingNodes[Phi].push_back(PhiIdx);
6587 for (
auto &ForwardingNode : ForwardingNodes) {
6588 PHINode *Phi = ForwardingNode.first;
6594 for (
int Index : Indexes)
6595 Phi->setIncomingValue(Index,
SI->getCondition());
6605 if (
C->isThreadDependent())
6607 if (
C->isDLLImportDependent())
6615 if (
C->getType()->isScalableTy())
6626 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6653 if (
A->isAllOnesValue())
6655 if (
A->isNullValue())
6661 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6686 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6688 if (
I.isTerminator()) {
6690 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6693 CaseDest =
I.getSuccessor(0);
6700 for (
auto &
Use :
I.uses()) {
6703 if (
I->getParent() == CaseDest)
6706 if (Phi->getIncomingBlock(
Use) == CaseDest)
6719 *CommonDest = CaseDest;
6721 if (CaseDest != *CommonDest)
6726 int Idx =
PHI.getBasicBlockIndex(Pred);
6735 Res.push_back(std::make_pair(&
PHI, ConstVal));
6738 return Res.
size() > 0;
6744 SwitchCaseResultVectorTy &UniqueResults,
6746 for (
auto &
I : UniqueResults) {
6747 if (
I.first == Result) {
6748 I.second.push_back(CaseVal);
6749 return I.second.size();
6752 UniqueResults.push_back(
6763 SwitchCaseResultVectorTy &UniqueResults,
6767 for (
const auto &
I :
SI->cases()) {
6781 const size_t NumCasesForResult =
6789 if (UniqueResults.size() > MaxUniqueResults)
6805 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6807 return DefaultResult ||
SI->defaultDestUnreachable();
6828 const bool HasBranchWeights = !BranchWeights.
empty();
6830 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6831 ResultVector[1].second.size() == 1) {
6832 ConstantInt *FirstCase = ResultVector[0].second[0];
6833 ConstantInt *SecondCase = ResultVector[1].second[0];
6834 Value *SelectValue = ResultVector[1].first;
6835 if (DefaultResult) {
6836 Value *ValueCompare =
6837 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6838 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6839 DefaultResult,
"switch.select");
6841 SI && HasBranchWeights) {
6848 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6852 Value *ValueCompare =
6853 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6854 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6855 SelectValue,
"switch.select");
6861 size_t FirstCasePos = (Condition !=
nullptr);
6862 size_t SecondCasePos = FirstCasePos + 1;
6863 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6865 {BranchWeights[FirstCasePos],
6866 DefaultCase + BranchWeights[SecondCasePos]},
6873 if (ResultVector.size() == 1 && DefaultResult) {
6875 unsigned CaseCount = CaseValues.
size();
6888 for (
auto *Case : CaseValues) {
6889 if (Case->getValue().slt(MinCaseVal->
getValue()))
6891 AndMask &= Case->getValue();
6895 if (!AndMask.
isZero() &&
Known.getMaxValue().uge(AndMask)) {
6897 unsigned FreeBits =
Known.countMaxActiveBits() - AndMask.
popcount();
6901 if (FreeBits ==
Log2_32(CaseCount)) {
6902 Value *
And = Builder.CreateAnd(Condition, AndMask);
6903 Value *Cmp = Builder.CreateICmpEQ(
6906 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6922 for (
auto *Case : CaseValues)
6923 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6929 Condition = Builder.CreateSub(Condition, MinCaseVal);
6930 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6931 Value *Cmp = Builder.CreateICmpEQ(
6934 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6947 if (CaseValues.
size() == 2) {
6948 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6949 "switch.selectcmp.case1");
6950 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6951 "switch.selectcmp.case2");
6952 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6954 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6974 std::vector<DominatorTree::UpdateType> Updates;
6981 Builder.CreateBr(DestBB);
6985 PHI->removeIncomingValueIf(
6986 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6987 PHI->addIncoming(SelectValue, SelectBB);
6990 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6996 if (DTU && RemovedSuccessors.
insert(Succ).second)
6999 SI->eraseFromParent();
7013 SwitchCaseResultVectorTy UniqueResults;
7019 assert(
PHI !=
nullptr &&
"PHI for value select not found");
7020 Builder.SetInsertPoint(
SI);
7022 [[maybe_unused]]
auto HasWeights =
7026 (BranchWeights.
size() >=
7027 UniqueResults.size() + (DefaultResult !=
nullptr)));
7030 Builder,
DL, BranchWeights);
7042class SwitchReplacement {
7050 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7051 Constant *DefaultValue,
const DataLayout &
DL,
7052 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
7061 static bool wouldFitInRegister(
const DataLayout &
DL,
uint64_t TableSize,
7068 bool isLookupTable();
7074 bool isValid()
const {
return Kind != InvalidKind; }
7111 ConstantInt *BitMap =
nullptr;
7112 IntegerType *BitMapElementTy =
nullptr;
7115 ConstantInt *LinearOffset =
nullptr;
7116 ConstantInt *LinearMultiplier =
nullptr;
7117 bool LinearMapValWrapped =
false;
7125SwitchReplacement::SwitchReplacement(
7127 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7128 Constant *DefaultValue,
const DataLayout &
DL,
7129 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
7130 : DefaultValue(DefaultValue) {
7131 assert(
Values.size() &&
"Can't build lookup table without values!");
7132 assert(TableSize >=
Values.size() &&
"Can't fit values in table!");
7135 SingleValue =
Values.begin()->second;
7141 for (
const auto &[CaseVal, CaseRes] :
Values) {
7145 TableContents[
Idx] = CaseRes;
7152 if (
Values.size() < TableSize) {
7154 "Need a default value to fill the lookup table holes.");
7157 if (!TableContents[
I])
7158 TableContents[
I] = DefaultValue;
7164 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
7165 SingleValue =
nullptr;
7171 Kind = SingleValueKind;
7178 bool LinearMappingPossible =
true;
7183 bool NonMonotonic =
false;
7184 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
7200 LinearMappingPossible =
false;
7205 APInt Dist = Val - PrevVal;
7208 }
else if (Dist != DistToPrev) {
7209 LinearMappingPossible =
false;
7217 if (LinearMappingPossible) {
7219 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
7220 APInt M = LinearMultiplier->getValue();
7221 bool MayWrap =
true;
7222 if (
isIntN(M.getBitWidth(), TableSize - 1))
7223 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
7224 LinearMapValWrapped = NonMonotonic || MayWrap;
7225 Kind = LinearMapKind;
7232 if (wouldFitInRegister(
DL, TableSize,
ValueType) &&
7235 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
7237 TableInt <<=
IT->getBitWidth();
7241 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
7244 BitMap = ConstantInt::get(M.getContext(), TableInt);
7245 BitMapElementTy =
IT;
7251 if (!
all_of(TableContents,
7263 unsigned NeededBitWidth =
7264 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7277 Kind = LookupTableKind;
7285 case SingleValueKind:
7287 case LinearMapKind: {
7291 false,
"switch.idx.cast");
7292 if (!LinearMultiplier->
isOne())
7293 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7295 !LinearMapValWrapped);
7297 if (!LinearOffset->
isZero())
7300 !LinearMapValWrapped);
7317 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7318 "switch.shiftamt",
true,
true);
7321 Value *DownShifted =
7322 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7324 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7326 case LookupTableKind: {
7329 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7330 true, GlobalVariable::PrivateLinkage,
7331 Initializer,
"switch.table." +
Func->getName());
7332 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7336 Type *IndexTy =
DL.getIndexType(
Table->getType());
7339 if (
Index->getType() != IndexTy) {
7340 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7344 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7347 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7351 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7360bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7362 Type *ElementType) {
7370 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7372 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7378 if (
TTI.isTypeLegal(Ty))
7393 DL.fitsInLegalInteger(
IT->getBitWidth());
7396Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7398bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7400bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7407 const uint64_t MinDensity = OptSize ? 40 : 10;
7412 return NumCases * 100 >= CaseRange * MinDensity;
7424static std::optional<unsigned>
7427 assert(
Values.size() > 1 &&
"expected multiple switch cases");
7429 return std::nullopt;
7434 for (
auto &V : ReducedValues) {
7436 ReducedValuesOr |= Reduced;
7437 V = (int64_t)Reduced;
7450 for (
auto &V : ReducedValues)
7451 V = (int64_t)((
uint64_t)V >> Shift);
7454 return std::nullopt;
7468 if (
SI->getNumCases() > TableSize)
7471 bool AllTablesFitInRegister =
true;
7472 bool HasIllegalType =
false;
7473 for (
const auto &Ty : ResultTypes) {
7478 AllTablesFitInRegister =
7479 AllTablesFitInRegister &&
7480 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7485 if (HasIllegalType && !AllTablesFitInRegister)
7490 if (AllTablesFitInRegister)
7498 SI->getFunction()->hasOptSize());
7508 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7511 return all_of(ResultTypes, [&](
const auto &ResultType) {
7512 return SwitchReplacement::wouldFitInRegister(
7562 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7567 for (
auto ValuePair :
Values) {
7570 if (!CaseConst || CaseConst == DefaultConst ||
7571 (CaseConst != TrueConst && CaseConst != FalseConst))
7585 if (DefaultConst == FalseConst) {
7588 ++NumTableCmpReuses;
7591 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7592 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7595 ++NumTableCmpReuses;
7605 bool ConvertSwitchToLookupTable) {
7606 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7620 if (
SI->getNumCases() < 3)
7642 MinCaseVal = CaseVal;
7644 MaxCaseVal = CaseVal;
7661 It->second.push_back(std::make_pair(CaseVal,
Value));
7670 &CommonDest, DefaultResultsList,
DL);
7671 for (
const auto &
I : DefaultResultsList) {
7674 DefaultResults[
PHI] = Result;
7678 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7681 if (UseSwitchConditionAsTableIndex) {
7683 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7688 TableIndexOffset = MinCaseVal;
7695 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7697 bool TableHasHoles = (NumResults < TableSize);
7702 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7710 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7713 if (
SI->getNumCases() < 4)
7715 if (!
DL.fitsInLegalInteger(TableSize))
7724 if (UseSwitchConditionAsTableIndex) {
7725 TableIndex =
SI->getCondition();
7726 if (HasDefaultResults) {
7738 all_of(ResultTypes, [&](
const auto &ResultType) {
7739 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7744 TableSize = std::max(UpperBound, TableSize);
7747 DefaultIsReachable =
false;
7755 const auto &ResultList = ResultLists[
PHI];
7757 Type *ResultType = ResultList.begin()->second->getType();
7762 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7763 ResultList, DefaultVal,
DL,
TTI, FuncName);
7764 if (!Replacement.isValid())
7766 PhiToReplacementMap.
insert({
PHI, Replacement});
7769 bool AnyLookupTables =
any_of(
7770 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7771 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7772 [](
auto &KV) {
return KV.second.isBitMap(); });
7780 if (AnyLookupTables &&
7781 (!
TTI.shouldBuildLookupTables() ||
7787 if (!ConvertSwitchToLookupTable &&
7788 (AnyLookupTables || AnyBitMaps || NeedMask))
7791 Builder.SetInsertPoint(
SI);
7794 if (!UseSwitchConditionAsTableIndex) {
7797 bool MayWrap =
true;
7798 if (!DefaultIsReachable) {
7803 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7804 "switch.tableidx",
false,
7808 std::vector<DominatorTree::UpdateType> Updates;
7814 assert(MaxTableSize >= TableSize &&
7815 "It is impossible for a switch to have more entries than the max "
7816 "representable value of its input integer type's size.");
7821 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7826 Builder.SetInsertPoint(
SI);
7827 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7828 const bool IsFullyCoveredLookupTable =
7829 !DefaultIsReachable || GeneratingCoveredLookupTable;
7830 if (IsFullyCoveredLookupTable) {
7831 Builder.CreateBr(LookupBB);
7837 Value *Cmp = Builder.CreateICmpULT(
7838 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7840 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7841 CondBranch = RangeCheckBranch;
7847 Builder.SetInsertPoint(LookupBB);
7853 MaskBB->
setName(
"switch.hole_check");
7860 APInt MaskInt(TableSizePowOf2, 0);
7861 APInt One(TableSizePowOf2, 1);
7863 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7864 for (
const auto &Result : ResultList) {
7867 MaskInt |= One << Idx;
7869 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7876 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7877 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7878 Value *LoBit = Builder.CreateTrunc(
7880 if (!IsFullyCoveredLookupTable)
7882 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7887 Builder.SetInsertPoint(LookupBB);
7891 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7894 SI->getDefaultDest()->removePredecessor(BB,
7901 const ResultListTy &ResultList = ResultLists[
PHI];
7902 auto Replacement = PhiToReplacementMap.
at(
PHI);
7903 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7906 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7909 for (
auto *
User :
PHI->users()) {
7911 Replacement.getDefaultValue(), ResultList);
7915 PHI->addIncoming(Result, LookupBB);
7918 Builder.CreateBr(CommonDest);
7923 const bool HasBranchWeights =
7930 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7933 if (Succ ==
SI->getDefaultDest()) {
7934 if (HasBranchWeights)
7935 ToDefaultWeight += BranchWeights[
I];
7939 if (DTU && RemovedSuccessors.
insert(Succ).second)
7941 if (HasBranchWeights)
7942 ToLookupWeight += BranchWeights[
I];
7944 SI->eraseFromParent();
7949 if ((NeedMask && !IsFullyCoveredLookupTable) &&
7952 else if (HasBranchWeights)
7959 ++NumLookupTablesHoles;
7975 if (CondTy->getIntegerBitWidth() > 64 ||
7976 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7980 if (
SI->getNumCases() < 4)
7988 for (
const auto &
C :
SI->cases())
7989 Values.push_back(
C.getCaseValue()->getValue().getSExtValue());
7993 bool OptSize =
SI->getFunction()->hasOptSize();
8000 std::optional<unsigned> Shift;
8030 Builder.SetInsertPoint(
SI);
8034 Value *Rot = Builder.CreateIntrinsic(
8035 Ty, Intrinsic::fshl,
8036 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - *Shift)});
8037 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
8039 for (
auto Case :
SI->cases()) {
8040 auto *Orig = Case.getCaseValue();
8041 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
8086 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
8087 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
8104 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
8107 return !Updates.
empty();
8127 if (
SI->defaultDestUnreachable())
8138 if (!
Known.isConstant())
8145 ConstantInt::get(
SI->getContext(),
Known.getConstant());
8147 if (CaseIt ==
SI->case_default()) {
8156 SI->case_default());
8158 assert(
SI->getNumCases() > 0 &&
"Switch should have at least one case");
8159 assert(
SI->findCaseValue(CaseVal) !=
SI->case_default() &&
8160 "Proven value should have a dedicated case");
8161 assert(
SI->defaultDestUnreachable());
8179 Value *Condition =
SI->getCondition();
8183 if (CondTy->getIntegerBitWidth() > 64 ||
8184 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8196 if (
SI->getNumCases() < 4)
8201 for (
const auto &Case :
SI->cases()) {
8202 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
8204 Values.push_back(CaseValue);
8214 SI->getFunction()->hasOptSize()))
8218 Builder.SetInsertPoint(
SI);
8220 if (!
SI->defaultDestUnreachable()) {
8223 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
8224 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
8226 auto *OrigBB =
SI->getParent();
8227 auto *DefaultCaseBB =
SI->getDefaultDest();
8229 auto It = OrigBB->getTerminator()->getIterator();
8241 NewWeights[1] = Weights[0] / 2;
8242 NewWeights[0] = OrigDenominator - NewWeights[1];
8254 Weights[0] = NewWeights[1];
8255 uint64_t CasesDenominator = OrigDenominator - Weights[0];
8257 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
8263 It->eraseFromParent();
8271 for (
auto &Case :
SI->cases()) {
8272 auto *OrigValue = Case.getCaseValue();
8273 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
8274 OrigValue->getValue().countr_zero()));
8278 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
8281 SI->setCondition(ConditionTrailingZeros);
8291 if (!Cmp || !Cmp->hasOneUse())
8302 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
8305 if (
SI->getNumCases() == 2) {
8312 Succ =
SI->getDefaultDest();
8313 SuccWeight = Weights[0];
8315 for (
auto &Case :
SI->cases()) {
8316 std::optional<int64_t> Val =
8320 if (!Missing.erase(*Val))
8325 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
8328 assert(Missing.size() == 1 &&
"Should have one case left");
8329 Res = *Missing.begin();
8330 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
8332 Unreachable =
SI->getDefaultDest();
8334 for (
auto &Case :
SI->cases()) {
8335 BasicBlock *NewSucc = Case.getCaseSuccessor();
8336 uint32_t Weight = Weights[Case.getSuccessorIndex()];
8339 OtherSuccWeight += Weight;
8342 SuccWeight = Weight;
8343 }
else if (Succ == NewSucc) {
8349 for (
auto &Case :
SI->cases()) {
8350 std::optional<int64_t> Val =
8352 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8354 if (Case.getCaseSuccessor() == Succ) {
8376 if (Cmp->isSigned())
8379 MDNode *NewWeights =
nullptr;
8385 Builder.SetInsertPoint(
SI->getIterator());
8386 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
8387 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8388 SI->getMetadata(LLVMContext::MD_unpredictable));
8392 SI->eraseFromParent();
8393 Cmp->eraseFromParent();
8394 if (DTU && Unreachable)
8419 assert(
BB &&
"Expected non-null BB");
8421 if (
BB->isEntryBlock())
8434 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8439 if (&
BB->front() != &
BB->back())
8454 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8465 return (*EBW->PhiPredIVs)[&Phi][BB];
8487 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8490 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8491 return PredIVs[
A] == PredIVs[
B];
8500 if (Candidates.
size() < 2)
8515 assert(Succ &&
"Expected unconditional BB");
8525 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8528 for (
auto &
IV : Phi->incoming_values())
8529 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8547 bool MadeChange =
false;
8561 if (!LivePreds.
contains(PredOfDead))
8568 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8569 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8574 T->replaceSuccessorWith(
Dead, Live);
8579 for (
const auto &EBW : BBs2Merge) {
8582 const auto &[It, Inserted] =
Keep.insert(&EBW);
8591 if (KeepBB == DeadBB)
8595 RedirectIncomingEdges(DeadBB, KeepBB);
8604 if (DTU && !Updates.
empty())
8610bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8611 DomTreeUpdater *DTU) {
8613 SmallSetVector<BasicBlock *, 16> FilteredArms(
8619bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8620 DomTreeUpdater *DTU) {
8631 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8637bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8640 if (isValueEqualityComparison(SI)) {
8644 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8645 return requestResimplify();
8649 if (simplifySwitchOnSelect(SI,
Select))
8650 return requestResimplify();
8654 if (SI == &*BB->
begin())
8655 if (foldValueComparisonIntoPredecessors(SI, Builder))
8656 return requestResimplify();
8662 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8663 return requestResimplify();
8667 return requestResimplify();
8670 return requestResimplify();
8673 return requestResimplify();
8676 return requestResimplify();
8681 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8683 Options.ConvertSwitchToLookupTable))
8684 return requestResimplify();
8687 return requestResimplify();
8690 return requestResimplify();
8693 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8694 return requestResimplify();
8698 if (simplifyDuplicateSwitchArms(SI, DTU))
8699 return requestResimplify();
8702 return requestResimplify();
8705 return requestResimplify();
8710bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8713 SmallVector<uint32_t> BranchWeights;
8716 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8717 if (HasBranchWeights)
8722 SmallPtrSet<Value *, 8> Succs;
8723 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8728 RemovedSuccs.
insert(Dest);
8738 std::vector<DominatorTree::UpdateType> Updates;
8739 Updates.reserve(RemovedSuccs.
size());
8740 for (
auto *RemovedSucc : RemovedSuccs)
8741 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8758 if (HasBranchWeights) {
8765 if (simplifyIndirectBrOnSelect(IBI, SI))
8766 return requestResimplify();
8798 if (BB == OtherPred)
8811 Value *V = PN.getIncomingValueForBlock(BB);
8812 Value *V2 = PN.getIncomingValueForBlock(OtherPred);
8813 return V == V2 || (V == LPad && V2 == LPad2);
8821 return PN.getIncomingValueForBlock(BB) == LPad;
8826 std::vector<DominatorTree::UpdateType> Updates;
8833 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8834 "unexpected successor");
8835 II->setUnwindDest(OtherPred);
8850 Builder.CreateUnreachable();
8859bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8871 bool NeedCanonicalLoop =
8885 if (
I->isTerminator() &&
8886 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8910 if (!PPred || (PredPred && PredPred != PPred))
8951 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8955 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8985 bool HasWeight =
false;
8990 BBTWeight = BBFWeight = 1;
8995 BB1TWeight = BB1FWeight = 1;
9000 BB2TWeight = BB2FWeight = 1;
9002 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
9003 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
9010bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
9014 "Tautological conditional branch should have been eliminated already.");
9017 if (!
Options.SimplifyCondBranch ||
9022 if (isValueEqualityComparison(BI)) {
9027 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
9028 return requestResimplify();
9032 for (
auto &
I : *BB) {
9037 if (foldValueComparisonIntoPredecessors(BI, Builder))
9038 return requestResimplify();
9044 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
9057 return requestResimplify();
9063 if (
Options.SpeculateBlocks &&
9066 return requestResimplify();
9075 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
9076 return requestResimplify();
9078 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
9080 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
9081 auto CanSpeculateConditionalLoadsStores = [&]() {
9083 for (Instruction &
I : *Succ) {
9084 if (
I.isTerminator()) {
9085 if (
I.getNumSuccessors() > 1)
9089 SpeculatedConditionalLoadsStores.
size() ==
9093 SpeculatedConditionalLoadsStores.
push_back(&
I);
9096 return !SpeculatedConditionalLoadsStores.
empty();
9099 if (CanSpeculateConditionalLoadsStores()) {
9101 std::nullopt,
nullptr);
9102 return requestResimplify();
9112 return requestResimplify();
9121 return requestResimplify();
9127 if (foldCondBranchOnValueKnownInPredecessor(BI))
9128 return requestResimplify();
9135 return requestResimplify();
9143 return requestResimplify();
9147 return requestResimplify();
9154 assert(V->getType() ==
I->getType() &&
"Mismatched types");
9166 auto *Use = cast<Instruction>(U.getUser());
9169 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
9172 switch (Use->getOpcode()) {
9175 case Instruction::GetElementPtr:
9176 case Instruction::Ret:
9177 case Instruction::BitCast:
9178 case Instruction::Load:
9179 case Instruction::Store:
9180 case Instruction::Call:
9181 case Instruction::CallBr:
9182 case Instruction::Invoke:
9183 case Instruction::UDiv:
9184 case Instruction::URem:
9188 case Instruction::SDiv:
9189 case Instruction::SRem:
9193 if (FindUse ==
I->use_end())
9195 auto &
Use = *FindUse;
9209 if (
GEP->getPointerOperand() ==
I) {
9212 if (
GEP->getType()->isVectorTy())
9220 if (!
GEP->hasAllZeroIndices() &&
9221 (!
GEP->isInBounds() ||
9223 GEP->getPointerAddressSpace())))
9224 PtrValueMayBeModified =
true;
9230 bool HasNoUndefAttr =
9231 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
9236 if (
C->isNullValue() && HasNoUndefAttr &&
9237 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
9238 return !PtrValueMayBeModified;
9244 if (!LI->isVolatile())
9246 LI->getPointerAddressSpace());
9250 if (!
SI->isVolatile())
9252 SI->getPointerAddressSpace())) &&
9253 SI->getPointerOperand() ==
I;
9258 if (
I == Assume->getArgOperand(0))
9266 if (CB->getCalledOperand() ==
I)
9269 if (CB->isArgOperand(&
Use)) {
9270 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
9273 CB->paramHasNonNullAttr(ArgIdx,
false))
9274 return !PtrValueMayBeModified;
9293 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
9301 Builder.CreateUnreachable();
9302 T->eraseFromParent();
9314 Builder.CreateUnreachable();
9321 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
9323 Assumption = Builder.CreateAssumption(
Cond);
9338 Builder.SetInsertPoint(Unreachable);
9340 Builder.CreateUnreachable();
9341 for (
const auto &Case :
SI->cases())
9342 if (Case.getCaseSuccessor() == BB) {
9344 Case.setSuccessor(Unreachable);
9346 if (
SI->getDefaultDest() == BB) {
9348 SI->setDefaultDest(Unreachable);
9362bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9387 return requestResimplify();
9406 if (simplifyDuplicatePredecessors(BB, DTU))
9410 if (
Options.SpeculateBlocks &&
9417 Options.SpeculateUnpredictables))
9425 case Instruction::UncondBr:
9428 case Instruction::CondBr:
9431 case Instruction::Resume:
9434 case Instruction::CleanupRet:
9437 case Instruction::Switch:
9440 case Instruction::Unreachable:
9443 case Instruction::IndirectBr:
9451bool SimplifyCFGOpt::run(BasicBlock *BB) {
9461 }
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...
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."))
SmallVector< MachineOperand, 4 > 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 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 Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB, Instruction *&PreviousAccess)
Determine if we can hoist sink a sole store instruction out of a conditional block.
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 hasTerminator() const LLVM_READONLY
Returns whether the block has a terminator.
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 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 InstListType::const_iterator getFirstNonPHIOrPseudoProbe() const
Returns an iterator to the first instruction in this block that is not a PHINode or a pseudo operatio...
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.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
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.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
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 AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
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.
LLVM_ABI bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
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.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
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.
@ End
Run the machine verifier once, at the end of the pipeline.
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)
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
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.