96#define DEBUG_TYPE "simplifycfg"
99 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
102 "Temporary development switch used to gradually uplift SimplifyCFG "
103 "into preserving DomTree,"));
112 "Control the amount of phi node folding to perform (default = 2)"));
116 cl::desc(
"Control the maximal total instruction cost that we are willing "
117 "to speculatively execute to fold a 2-entry PHI node into a "
118 "select (default = 4)"));
122 cl::desc(
"Hoist common instructions up to the parent block"));
126 cl::desc(
"Hoist loads if the target supports conditional faulting"));
130 cl::desc(
"Hoist stores if the target supports conditional faulting"));
134 cl::desc(
"Control the maximal conditional load/store that we are willing "
135 "to speculatively execute to eliminate conditional branch "
141 cl::desc(
"Allow reordering across at most this many "
142 "instructions when hoisting"));
146 cl::desc(
"Sink common instructions down to the end block"));
150 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
154 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
155 "precede - hoist multiple conditional stores into a single "
156 "predicated store"));
160 cl::desc(
"When merging conditional stores, do so even if the resultant "
161 "basic blocks are unlikely to be if-converted as a result"));
165 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
170 cl::desc(
"Limit maximum recursion depth when calculating costs of "
171 "speculatively executed instructions"));
176 cl::desc(
"Max size of a block which is still considered "
177 "small enough to thread through"));
183 cl::desc(
"Maximum cost of combining conditions when "
184 "folding branches"));
187 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
189 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
190 "to fold branch to common destination when vector operations are "
195 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
199 cl::desc(
"Limit cases to analyze when converting a switch to select"));
203 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
208STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
210 "Number of switch instructions turned into linear mapping");
212 "Number of switch instructions turned into lookup tables");
214 NumLookupTablesHoles,
215 "Number of switch instructions turned into lookup tables (holes checked)");
216STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
218 "Number of value comparisons folded into predecessor basic blocks");
220 "Number of branches folded into predecessor basic block");
223 "Number of common instruction 'blocks' hoisted up to the begin block");
225 "Number of common instructions hoisted up to the begin block");
227 "Number of common instruction 'blocks' sunk down to the end block");
229 "Number of common instructions sunk down to the end block");
230STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
232 "Number of invokes with empty resume blocks simplified into calls");
233STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
234STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
241using SwitchCaseResultVectorTy =
250struct ValueEqualityComparisonCase {
262 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
265class SimplifyCFGOpt {
266 const TargetTransformInfo &TTI;
268 const DataLayout &DL;
270 const SimplifyCFGOptions &Options;
273 Value *isValueEqualityComparison(Instruction *TI);
275 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
276 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
279 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
282 bool foldValueComparisonIntoPredecessors(Instruction *TI,
285 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
286 bool simplifySingleResume(ResumeInst *RI);
287 bool simplifyCommonResume(ResumeInst *RI);
288 bool simplifyCleanupReturn(CleanupReturnInst *RI);
289 bool simplifyUnreachable(UnreachableInst *UI);
290 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
291 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
292 bool simplifyIndirectBr(IndirectBrInst *IBI);
293 bool simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder);
294 bool simplifyUncondBranch(BranchInst *BI,
IRBuilder<> &Builder);
295 bool simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder);
296 bool foldCondBranchOnValueKnownInPredecessor(BranchInst *BI);
298 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
301 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
302 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
303 Instruction *TI, Instruction *I1,
304 SmallVectorImpl<Instruction *> &OtherSuccTIs);
305 bool speculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
306 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
307 BasicBlock *TrueBB, BasicBlock *FalseBB,
308 uint32_t TrueWeight, uint32_t FalseWeight);
309 bool simplifyBranchOnICmpChain(BranchInst *BI,
IRBuilder<> &Builder,
310 const DataLayout &DL);
311 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
312 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
313 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
316 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
318 const SimplifyCFGOptions &Opts)
319 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
320 assert((!DTU || !DTU->hasPostDomTree()) &&
321 "SimplifyCFG is not yet capable of maintaining validity of a "
322 "PostDomTree, so don't ask for it.");
325 bool simplifyOnce(BasicBlock *BB);
326 bool run(BasicBlock *BB);
329 bool requestResimplify() {
339isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
359 "Only for a pair of incoming blocks at the time!");
365 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
366 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
369 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
370 EquivalenceSet->contains(IV1))
393 if (!SI1Succs.
count(Succ))
399 FailBlocks->insert(Succ);
415 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
417 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
418 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
480 if (AggressiveInsts.
count(
I))
496 ZeroCostInstructions.
insert(OverflowInst);
498 }
else if (!ZeroCostInstructions.
contains(
I))
514 for (
Use &
Op :
I->operands())
516 TTI, AC, ZeroCostInstructions,
Depth + 1))
528 if (CI || !
isa<Constant>(V) || !V->getType()->isPointerTy() ||
529 DL.isNonIntegralPointerType(V->getType()))
538 return ConstantInt::get(PtrTy, 0);
542 if (CE->getOpcode() == Instruction::IntToPtr)
566struct ConstantComparesGatherer {
567 const DataLayout &DL;
570 Value *CompValue =
nullptr;
573 Value *Extra =
nullptr;
579 unsigned UsedICmps = 0;
585 bool IgnoreFirstMatch =
false;
586 bool MultipleMatches =
false;
589 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
591 if (CompValue || !MultipleMatches)
596 IgnoreFirstMatch =
true;
600 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
601 ConstantComparesGatherer &
602 operator=(
const ConstantComparesGatherer &) =
delete;
607 bool setValueOnce(
Value *NewVal) {
608 if (IgnoreFirstMatch) {
609 IgnoreFirstMatch =
false;
612 if (CompValue && CompValue != NewVal) {
613 MultipleMatches =
true;
627 bool matchInstruction(Instruction *
I,
bool isEQ) {
634 if (!setValueOnce(Val))
654 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
698 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
700 if (!setValueOnce(RHSVal))
705 ConstantInt::get(
C->getContext(),
706 C->getValue() | Mask));
721 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
723 if (!setValueOnce(RHSVal))
727 Vals.push_back(ConstantInt::get(
C->getContext(),
728 C->getValue() & ~Mask));
749 Value *CandidateVal =
I->getOperand(0);
752 CandidateVal = RHSVal;
767 if (!setValueOnce(CandidateVal))
772 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
783 void gather(
Value *V) {
792 SmallVector<Value *, 8> DFT{Op0, Op1};
793 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
795 while (!DFT.
empty()) {
802 if (Visited.
insert(Op1).second)
804 if (Visited.
insert(Op0).second)
811 if (matchInstruction(
I, IsEq))
838 if (BI->isConditional())
856 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
857 CV =
SI->getCondition();
859 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
864 if (Trunc->hasNoUnsignedWrap())
865 CV = Trunc->getOperand(0);
872 Value *
Ptr = PTII->getPointerOperand();
873 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
882BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
883 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
885 Cases.reserve(
SI->getNumCases());
886 for (
auto Case :
SI->cases())
887 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
888 Case.getCaseSuccessor()));
889 return SI->getDefaultDest();
894 ICmpInst::Predicate Pred;
900 Pred = ICmpInst::ICMP_NE;
905 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
913 std::vector<ValueEqualityComparisonCase> &Cases) {
919 std::vector<ValueEqualityComparisonCase> &C2) {
920 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
923 if (V1->size() > V2->size())
928 if (V1->size() == 1) {
931 for (
const ValueEqualityComparisonCase &
VECC : *V2)
932 if (TheVal ==
VECC.Value)
939 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
940 while (i1 != e1 && i2 != e2) {
961 SI->setMetadata(LLVMContext::MD_prof,
N);
967 uint32_t FalseWeight,
bool IsExpected) {
972 if (TrueWeight || FalseWeight)
975 I->setMetadata(LLVMContext::MD_prof,
N);
983bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
984 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
989 Value *ThisVal = isValueEqualityComparison(TI);
990 assert(ThisVal &&
"This isn't a value comparison!!");
991 if (ThisVal != PredVal)
998 std::vector<ValueEqualityComparisonCase> PredCases;
1000 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
1004 std::vector<ValueEqualityComparisonCase> ThisCases;
1005 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1020 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1026 ThisCases[0].Dest->removePredecessor(PredDef);
1029 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1036 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1043 SmallPtrSet<Constant *, 16> DeadCases;
1044 for (
const ValueEqualityComparisonCase &Case : PredCases)
1045 DeadCases.
insert(Case.Value);
1048 <<
"Through successor TI: " << *TI);
1050 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1053 auto *
Successor = i->getCaseSuccessor();
1056 if (DeadCases.
count(i->getCaseValue())) {
1065 std::vector<DominatorTree::UpdateType> Updates;
1066 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1068 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1078 ConstantInt *TIV =
nullptr;
1080 for (
const auto &[
Value, Dest] : PredCases)
1086 assert(TIV &&
"No edge from pred to succ?");
1091 for (
const auto &[
Value, Dest] : ThisCases)
1099 TheRealDest = ThisDef;
1101 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1106 if (Succ != CheckEdge) {
1107 if (Succ != TheRealDest)
1108 RemovedSuccs.
insert(Succ);
1111 CheckEdge =
nullptr;
1118 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1123 SmallVector<DominatorTree::UpdateType, 2> Updates;
1125 for (
auto *RemovedSucc : RemovedSuccs)
1126 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1137struct ConstantIntOrdering {
1138 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1139 return LHS->getValue().ult(
RHS->getValue());
1151 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1160 assert(MD &&
"Invalid branch-weight metadata");
1180 if (Max > UINT_MAX) {
1195 if (BonusInst.isTerminator())
1225 NewBonusInst->
takeName(&BonusInst);
1226 BonusInst.setName(NewBonusInst->
getName() +
".old");
1227 VMap[&BonusInst] = NewBonusInst;
1236 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1237 "If the user is not a PHI node, then it should be in the same "
1238 "block as, and come after, the original bonus instruction.");
1242 if (PN->getIncomingBlock(U) == BB)
1246 assert(PN->getIncomingBlock(U) == PredBlock &&
1247 "Not in block-closed SSA form?");
1248 U.set(NewBonusInst);
1258 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1259 PredDL.isSameSourceLocation(
DL)) {
1266bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1274 std::vector<ValueEqualityComparisonCase> BBCases;
1275 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1277 std::vector<ValueEqualityComparisonCase> PredCases;
1278 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1283 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1286 SmallVector<uint64_t, 8> Weights;
1290 if (PredHasWeights) {
1293 if (Weights.
size() != 1 + PredCases.size())
1294 PredHasWeights = SuccHasWeights =
false;
1295 }
else if (SuccHasWeights)
1299 Weights.
assign(1 + PredCases.size(), 1);
1301 SmallVector<uint64_t, 8> SuccWeights;
1302 if (SuccHasWeights) {
1305 if (SuccWeights.
size() != 1 + BBCases.size())
1306 PredHasWeights = SuccHasWeights =
false;
1307 }
else if (PredHasWeights)
1308 SuccWeights.
assign(1 + BBCases.size(), 1);
1310 if (PredDefault == BB) {
1313 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1314 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1315 if (PredCases[i].Dest != BB)
1316 PTIHandled.insert(PredCases[i].
Value);
1319 std::swap(PredCases[i], PredCases.back());
1321 if (PredHasWeights || SuccHasWeights) {
1323 Weights[0] += Weights[i + 1];
1328 PredCases.pop_back();
1334 if (PredDefault != BBDefault) {
1336 if (DTU && PredDefault != BB)
1337 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1338 PredDefault = BBDefault;
1339 ++NewSuccessors[BBDefault];
1342 unsigned CasesFromPred = Weights.
size();
1343 uint64_t ValidTotalSuccWeight = 0;
1344 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1345 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1346 PredCases.push_back(BBCases[i]);
1347 ++NewSuccessors[BBCases[i].Dest];
1348 if (SuccHasWeights || PredHasWeights) {
1352 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1353 ValidTotalSuccWeight += SuccWeights[i + 1];
1357 if (SuccHasWeights || PredHasWeights) {
1358 ValidTotalSuccWeight += SuccWeights[0];
1360 for (
unsigned i = 1; i < CasesFromPred; ++i)
1361 Weights[i] *= ValidTotalSuccWeight;
1363 Weights[0] *= SuccWeights[0];
1369 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1370 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1371 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1372 if (PredCases[i].Dest == BB) {
1373 PTIHandled.insert(PredCases[i].
Value);
1375 if (PredHasWeights || SuccHasWeights) {
1376 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1381 std::swap(PredCases[i], PredCases.back());
1382 PredCases.pop_back();
1389 for (
const ValueEqualityComparisonCase &Case : BBCases)
1390 if (PTIHandled.count(Case.Value)) {
1392 if (PredHasWeights || SuccHasWeights)
1393 Weights.
push_back(WeightsForHandled[Case.Value]);
1394 PredCases.push_back(Case);
1395 ++NewSuccessors[Case.Dest];
1396 PTIHandled.erase(Case.Value);
1401 for (ConstantInt *
I : PTIHandled) {
1402 if (PredHasWeights || SuccHasWeights)
1404 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1405 ++NewSuccessors[BBDefault];
1412 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1417 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1419 for (
auto I :
seq(NewSuccessor.second)) {
1423 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1424 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1435 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1437 for (ValueEqualityComparisonCase &V : PredCases)
1440 if (PredHasWeights || SuccHasWeights) {
1457 if (!InfLoopBlock) {
1465 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1472 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1474 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1479 ++NumFoldValueComparisonIntoPredecessors;
1487bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1490 Value *CV = isValueEqualityComparison(TI);
1491 assert(CV &&
"Not a comparison?");
1496 while (!Preds.empty()) {
1505 Value *PCV = isValueEqualityComparison(PTI);
1509 SmallSetVector<BasicBlock *, 4> FailBlocks;
1511 for (
auto *Succ : FailBlocks) {
1517 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1531 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1532 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1533 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1552 if (
I->mayReadFromMemory())
1584 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1592 if (J->getParent() == BB)
1614 if (C1->isMustTailCall() != C2->isMustTailCall())
1617 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1623 if (CB1->cannotMerge() || CB1->isConvergent())
1626 if (CB2->cannotMerge() || CB2->isConvergent())
1641 if (!I1->hasDbgRecords())
1643 using CurrentAndEndIt =
1644 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1650 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1651 return Pair.first == Pair.second;
1657 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1663 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1665 if (!
Other->hasDbgRecords())
1668 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1675 while (
none_of(Itrs, atEnd)) {
1676 bool HoistDVRs = allIdentical(Itrs);
1677 for (CurrentAndEndIt &Pair : Itrs) {
1691 if (I1->isIdenticalToWhenDefined(I2,
true))
1696 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1697 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1698 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1700 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1701 return I1->getOperand(0) == I2->
getOperand(1) &&
1767 auto &Context = BI->
getParent()->getContext();
1772 Value *Mask =
nullptr;
1773 Value *MaskFalse =
nullptr;
1774 Value *MaskTrue =
nullptr;
1775 if (Invert.has_value()) {
1776 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1777 Mask = Builder.CreateBitCast(
1782 MaskFalse = Builder.CreateBitCast(
1784 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1786 auto PeekThroughBitcasts = [](
Value *V) {
1788 V = BitCast->getOperand(0);
1791 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1793 if (!Invert.has_value())
1794 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1799 auto *Op0 =
I->getOperand(0);
1800 CallInst *MaskedLoadStore =
nullptr;
1803 auto *Ty =
I->getType();
1805 Value *PassThru =
nullptr;
1806 if (Invert.has_value())
1807 for (
User *U :
I->users()) {
1809 PassThru = Builder.CreateBitCast(
1813 Sel && Ins->getParent() == BB) {
1818 Builder.SetInsertPoint(Ins);
1821 MaskedLoadStore = Builder.CreateMaskedLoad(
1823 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1826 I->replaceAllUsesWith(NewLoadStore);
1829 auto *StoredVal = Builder.CreateBitCast(
1831 MaskedLoadStore = Builder.CreateMaskedStore(
1842 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1844 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1848 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1849 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1852 I->eraseFromParent();
1859 bool IsStore =
false;
1882bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1883 bool AllInstsEqOnly) {
1903 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1909 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1912 if (AllInstsEqOnly) {
1918 bool AllSame =
none_of(Succs, [&Succs](BasicBlock *Succ) {
1921 return !
Term->isSameOperationAs(Term0) ||
1928 LockstepReverseIterator<true> LRI(Succs);
1929 while (LRI.isValid()) {
1931 if (
any_of(*LRI, [I0](Instruction *
I) {
1946 unsigned NumSkipped = 0;
1949 if (SuccIterPairs.
size() > 2) {
1952 if (SuccIterPairs.
size() < 2)
1959 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1960 auto &BB1ItrPair = *SuccIterPairBegin++;
1961 auto OtherSuccIterPairRange =
1967 bool AllInstsAreIdentical =
true;
1968 bool HasTerminator =
I1->isTerminator();
1969 for (
auto &SuccIter : OtherSuccIterRange) {
1973 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1974 AllInstsAreIdentical =
false;
1977 SmallVector<Instruction *, 8> OtherInsts;
1978 for (
auto &SuccIter : OtherSuccIterRange)
1983 if (HasTerminator) {
1987 if (NumSkipped || !AllInstsAreIdentical) {
1992 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1996 if (AllInstsAreIdentical) {
1997 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1998 AllInstsAreIdentical =
2000 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
2002 unsigned SkipFlagsBB2 = Pair.second;
2012 if (AllInstsAreIdentical) {
2022 for (
auto &SuccIter : OtherSuccIterRange) {
2030 assert(
Success &&
"We should not be trying to hoist callbases "
2031 "with non-intersectable attributes");
2043 NumHoistCommonCode += SuccIterPairs.
size();
2045 NumHoistCommonInstrs += SuccIterPairs.
size();
2054 for (
auto &SuccIterPair : SuccIterPairs) {
2063bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2064 Instruction *TI, Instruction *I1,
2065 SmallVectorImpl<Instruction *> &OtherSuccTIs) {
2074 auto *I2 = *OtherSuccTIs.
begin();
2094 for (PHINode &PN : Succ->
phis()) {
2095 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2096 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2097 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2117 if (!
NT->getType()->isVoidTy()) {
2118 I1->replaceAllUsesWith(NT);
2119 for (Instruction *OtherSuccTI : OtherSuccTIs)
2120 OtherSuccTI->replaceAllUsesWith(NT);
2124 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2130 for (
auto *OtherSuccTI : OtherSuccTIs)
2131 Locs.
push_back(OtherSuccTI->getDebugLoc());
2143 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2145 for (PHINode &PN : Succ->
phis()) {
2146 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2147 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2153 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2163 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2164 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2165 PN.setIncomingValue(i, SI);
2176 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2181 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2194 if (
I->isIntDivRem())
2209 std::optional<unsigned> NumUses;
2210 for (
auto *
I : Insts) {
2213 I->getType()->isTokenTy())
2218 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2226 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2230 NumUses =
I->getNumUses();
2231 else if (NumUses !=
I->getNumUses())
2237 for (
auto *
I : Insts) {
2251 for (
const Use &U : I0->
uses()) {
2252 auto It = PHIOperands.find(&U);
2253 if (It == PHIOperands.end())
2256 if (!
equal(Insts, It->second))
2268 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2269 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2270 if (HaveIndirectCalls) {
2271 if (!AllCallsAreIndirect)
2275 Value *Callee =
nullptr;
2279 Callee = CurrCallee;
2280 else if (Callee != CurrCallee)
2286 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2292 if (!
all_of(Insts, SameAsI0)) {
2298 for (
auto *
I : Insts)
2299 Ops.push_back(
I->getOperand(OI));
2309 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2314 for (
auto *BB : Blocks) {
2316 I =
I->getPrevNode();
2341 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2344 PN->insertBefore(BBEnd->begin());
2345 for (
auto *
I : Insts)
2346 PN->addIncoming(
I->getOperand(O),
I->getParent());
2355 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2358 for (
auto *
I : Insts)
2372 assert(
Success &&
"We should not be trying to sink callbases "
2373 "with non-intersectable attributes");
2384 PN->replaceAllUsesWith(I0);
2385 PN->eraseFromParent();
2389 for (
auto *
I : Insts) {
2394 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2395 I->replaceAllUsesWith(I0);
2396 I->eraseFromParent();
2446 bool HaveNonUnconditionalPredecessors =
false;
2449 if (PredBr && PredBr->isUnconditional())
2452 HaveNonUnconditionalPredecessors =
true;
2454 if (UnconditionalPreds.
size() < 2)
2467 for (
const Use &U : PN.incoming_values())
2468 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2469 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2471 Ops.push_back(*IncomingVals[Pred]);
2479 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2492 if (!followedByDeoptOrUnreachable) {
2494 auto IsMemOperand = [](
Use &U) {
2507 unsigned NumPHIInsts = 0;
2508 for (
Use &U : (*LRI)[0]->operands()) {
2509 auto It = PHIOperands.
find(&U);
2510 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2511 return InstructionsToSink.contains(V);
2518 if (IsMemOperand(U) &&
2519 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2526 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2527 return NumPHIInsts <= 1;
2544 while (Idx < ScanIdx) {
2545 if (!ProfitableToSinkInstruction(LRI)) {
2548 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2561 if (Idx < ScanIdx) {
2564 InstructionsToSink = InstructionsProfitableToSink;
2570 !ProfitableToSinkInstruction(LRI) &&
2571 "We already know that the last instruction is unprofitable to sink");
2579 for (
auto *
I : *LRI)
2580 InstructionsProfitableToSink.
erase(
I);
2581 if (!ProfitableToSinkInstruction(LRI)) {
2584 InstructionsToSink = InstructionsProfitableToSink;
2598 if (HaveNonUnconditionalPredecessors) {
2599 if (!followedByDeoptOrUnreachable) {
2607 bool Profitable =
false;
2608 while (Idx < ScanIdx) {
2642 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2644 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2652 NumSinkCommonInstrs++;
2656 ++NumSinkCommonCode;
2662struct CompatibleSets {
2663 using SetTy = SmallVector<InvokeInst *, 2>;
2669 SetTy &getCompatibleSet(InvokeInst *
II);
2671 void insert(InvokeInst *
II);
2674CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2679 for (CompatibleSets::SetTy &Set : Sets) {
2680 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2685 return Sets.emplace_back();
2688void CompatibleSets::insert(InvokeInst *
II) {
2689 getCompatibleSet(
II).emplace_back(
II);
2693 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2696 auto IsIllegalToMerge = [](InvokeInst *
II) {
2697 return II->cannotMerge() ||
II->isInlineAsm();
2699 if (
any_of(Invokes, IsIllegalToMerge))
2704 auto IsIndirectCall = [](InvokeInst *
II) {
return II->isIndirectCall(); };
2705 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2706 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2707 if (HaveIndirectCalls) {
2708 if (!AllCallsAreIndirect)
2713 for (InvokeInst *
II : Invokes) {
2714 Value *CurrCallee =
II->getCalledOperand();
2715 assert(CurrCallee &&
"There is always a called operand.");
2718 else if (Callee != CurrCallee)
2725 auto HasNormalDest = [](InvokeInst *
II) {
2728 if (
any_of(Invokes, HasNormalDest)) {
2731 if (!
all_of(Invokes, HasNormalDest))
2736 for (InvokeInst *
II : Invokes) {
2738 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2740 NormalBB = CurrNormalBB;
2741 else if (NormalBB != CurrNormalBB)
2749 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2758 for (InvokeInst *
II : Invokes) {
2760 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2762 UnwindBB = CurrUnwindBB;
2764 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2771 Invokes.front()->getUnwindDest(),
2772 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2777 const InvokeInst *II0 = Invokes.front();
2778 for (
auto *
II : Invokes.drop_front())
2783 auto IsIllegalToMergeArguments = [](
auto Ops) {
2784 Use &U0 = std::get<0>(
Ops);
2785 Use &U1 = std::get<1>(
Ops);
2791 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2792 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2793 IsIllegalToMergeArguments))
2805 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2811 bool HasNormalDest =
2816 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2820 II0->
getParent()->getIterator()->getNextNode();
2825 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2829 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2831 if (!HasNormalDest) {
2835 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2843 return MergedInvoke;
2857 SuccBBOfMergedInvoke});
2867 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2873 if (!IsIndirectCall)
2880 return II->getOperand(U.getOperandNo()) != U.get();
2899 Invokes.
front()->getParent());
2907 if (!MergedDebugLoc)
2908 MergedDebugLoc =
II->getDebugLoc();
2916 OrigSuccBB->removePredecessor(
II->getParent());
2922 assert(
Success &&
"Merged invokes with incompatible attributes");
2925 II->replaceAllUsesWith(MergedInvoke);
2926 II->eraseFromParent();
2930 ++NumInvokeSetsFormed;
2966 CompatibleSets Grouper;
2976 if (Invokes.
size() < 2)
2988class EphemeralValueTracker {
2989 SmallPtrSet<const Instruction *, 32> EphValues;
2991 bool isEphemeral(
const Instruction *
I) {
2994 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2995 all_of(
I->users(), [&](
const User *U) {
2996 return EphValues.count(cast<Instruction>(U));
3001 bool track(
const Instruction *
I) {
3002 if (isEphemeral(
I)) {
3053 unsigned MaxNumInstToLookAt = 9;
3057 if (!MaxNumInstToLookAt)
3059 --MaxNumInstToLookAt;
3069 if (
SI->getPointerOperand() == StorePtr &&
3070 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3073 return SI->getValueOperand();
3078 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3079 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3081 bool ExplicitlyDereferenceableOnly;
3086 (!ExplicitlyDereferenceableOnly ||
3088 LI->getDataLayout()))) {
3104 unsigned &SpeculatedInstructions,
3112 bool HaveRewritablePHIs =
false;
3114 Value *OrigV = PN.getIncomingValueForBlock(BB);
3115 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3122 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3131 HaveRewritablePHIs =
true;
3134 if (!OrigCE && !ThenCE)
3141 if (OrigCost + ThenCost > MaxCost)
3148 ++SpeculatedInstructions;
3149 if (SpeculatedInstructions > 1)
3153 return HaveRewritablePHIs;
3157 std::optional<bool> Invert,
3161 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3168 if (!Invert.has_value())
3171 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3175 return BIEndProb < Likely;
3215bool SimplifyCFGOpt::speculativelyExecuteBB(BranchInst *BI,
3216 BasicBlock *ThenBB) {
3232 bool Invert =
false;
3247 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3249 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3251 unsigned SpeculatedInstructions = 0;
3252 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3253 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3254 Value *SpeculatedStoreValue =
nullptr;
3255 StoreInst *SpeculatedStore =
nullptr;
3256 EphemeralValueTracker EphTracker;
3271 if (EphTracker.track(&
I))
3276 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3278 SpeculatedConditionalLoadsStores.
size() <
3282 if (IsSafeCheapLoadStore)
3283 SpeculatedConditionalLoadsStores.
push_back(&
I);
3285 ++SpeculatedInstructions;
3287 if (SpeculatedInstructions > 1)
3291 if (!IsSafeCheapLoadStore &&
3294 (SpeculatedStoreValue =
3297 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3303 if (!SpeculatedStore && SpeculatedStoreValue)
3309 for (Use &
Op :
I.operands()) {
3314 ++SinkCandidateUseCounts[OpI];
3321 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3322 if (Inst->hasNUses(
Count)) {
3323 ++SpeculatedInstructions;
3324 if (SpeculatedInstructions > 1)
3331 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3334 SpeculatedInstructions,
Cost,
TTI);
3335 if (!Convert ||
Cost > Budget)
3339 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3343 if (SpeculatedStoreValue) {
3347 Value *FalseV = SpeculatedStoreValue;
3351 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3381 for (DbgVariableRecord *DbgAssign :
3384 DbgAssign->replaceVariableLocationOp(OrigV, S);
3394 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3397 I.dropUBImplyingAttrsAndMetadata();
3400 if (EphTracker.contains(&
I)) {
3402 I.eraseFromParent();
3408 for (
auto &It : *ThenBB)
3413 !DVR || !DVR->isDbgAssign())
3414 It.dropOneDbgRecord(&DR);
3416 std::prev(ThenBB->end()));
3418 if (!SpeculatedConditionalLoadsStores.
empty())
3424 for (PHINode &PN : EndBB->
phis()) {
3425 unsigned OrigI = PN.getBasicBlockIndex(BB);
3426 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3427 Value *OrigV = PN.getIncomingValue(OrigI);
3428 Value *ThenV = PN.getIncomingValue(ThenI);
3437 Value *TrueV = ThenV, *FalseV = OrigV;
3441 PN.setIncomingValue(OrigI, V);
3442 PN.setIncomingValue(ThenI, V);
3446 for (Instruction *
I : SpeculatedPseudoProbes)
3447 I->eraseFromParent();
3460 if (!ReachesNonLocalUses.
insert(BB).second)
3475 EphemeralValueTracker EphTracker;
3482 if (CI->cannotDuplicate() || CI->isConvergent())
3495 for (
User *U :
I.users()) {
3498 if (UsedInBB == BB) {
3502 NonLocalUseBlocks.
insert(UsedInBB);
3516 if (
I &&
I->getParent() == To)
3532static std::optional<bool>
3553 KnownValues[CB].
insert(Pred);
3557 if (KnownValues.
empty())
3582 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3585 for (
const auto &Pair : KnownValues) {
3602 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3607 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3610 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3618 EdgeBB->setName(RealDest->
getName() +
".critedge");
3619 EdgeBB->moveBefore(RealDest);
3629 TranslateMap[
Cond] = CB;
3642 N->insertInto(EdgeBB, InsertPt);
3645 N->setName(BBI->getName() +
".c");
3656 if (!BBI->use_empty())
3657 TranslateMap[&*BBI] = V;
3658 if (!
N->mayHaveSideEffects()) {
3659 N->eraseFromParent();
3664 if (!BBI->use_empty())
3665 TranslateMap[&*BBI] =
N;
3671 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3672 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3673 SrcDbgCursor = std::next(BBI);
3675 N->cloneDebugInfoFrom(&*BBI);
3684 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3685 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3686 InsertPt->cloneDebugInfoFrom(BI);
3707 return std::nullopt;
3713bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(BranchInst *BI) {
3720 std::optional<bool>
Result;
3721 bool EverChanged =
false;
3727 }
while (Result == std::nullopt);
3736 bool SpeculateUnpredictables) {
3758 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3761 "Will have either one or two blocks to speculate.");
3768 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3769 if (!IsUnpredictable) {
3772 (TWeight + FWeight) != 0) {
3777 if (IfBlocks.
size() == 1) {
3779 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3780 if (BIBBProb >= Likely)
3783 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3792 if (IfCondPhiInst->getParent() == BB)
3800 unsigned NumPhis = 0;
3813 if (SpeculateUnpredictables && IsUnpredictable)
3814 Budget +=
TTI.getBranchMispredictPenalty();
3827 AggressiveInsts, Cost, Budget,
TTI, AC,
3828 ZeroCostInstructions) ||
3830 AggressiveInsts, Cost, Budget,
TTI, AC,
3831 ZeroCostInstructions))
3843 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3854 auto IsBinOpOrAnd = [](
Value *V) {
3871 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3884 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3886 <<
" F: " << IfFalse->
getName() <<
"\n");
3903 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3908 PN->eraseFromParent();
3914 Builder.CreateBr(BB);
3935 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3936 if (
Opc == Instruction::And)
3937 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3938 if (
Opc == Instruction::Or)
3939 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3951 bool PredHasWeights =
3953 bool SuccHasWeights =
3955 if (PredHasWeights || SuccHasWeights) {
3956 if (!PredHasWeights)
3957 PredTrueWeight = PredFalseWeight = 1;
3958 if (!SuccHasWeights)
3959 SuccTrueWeight = SuccFalseWeight = 1;
3969static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3973 "Both blocks must end with a conditional branches.");
3975 "PredBB must be a predecessor of BB.");
3983 (PTWeight + PFWeight) != 0) {
3986 Likely =
TTI->getPredictableBranchThreshold();
3991 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3992 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3996 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3999 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4000 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4006 return std::nullopt;
4019 bool InvertPredCond;
4020 std::tie(CommonSucc,
Opc, InvertPredCond) =
4023 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4030 {LLVMContext::MD_annotation});
4033 if (InvertPredCond) {
4046 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4049 SuccTrueWeight, SuccFalseWeight)) {
4056 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4062 (SuccFalseWeight + SuccTrueWeight) +
4063 PredTrueWeight * SuccFalseWeight);
4069 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4070 PredFalseWeight * SuccTrueWeight);
4072 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4117 if (!MDWeights.
empty()) {
4118 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4123 ++NumFoldBranchToCommonDest;
4130 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4131 return U->getType()->isVectorTy();
4141 unsigned BonusInstThreshold) {
4155 Cond->getParent() != BB || !
Cond->hasOneUse())
4176 bool InvertPredCond;
4178 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4210 unsigned NumBonusInsts = 0;
4211 bool SawVectorOp =
false;
4212 const unsigned PredCount = Preds.
size();
4229 NumBonusInsts += PredCount;
4237 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4240 return PN->getIncomingBlock(U) == BB;
4241 return UI->
getParent() == BB &&
I.comesBefore(UI);
4245 if (!
all_of(
I.uses(), IsBCSSAUse))
4249 BonusInstThreshold *
4265 for (
auto *BB : {BB1, BB2}) {
4281 Value *AlternativeV =
nullptr) {
4307 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4308 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4316 if (!AlternativeV &&
4322 PHI->addIncoming(V, BB);
4332 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4341 if (!PStore || !QStore)
4362 if (
I.mayReadOrWriteMemory())
4364 for (
auto &
I : *QFB)
4365 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4368 for (
auto &
I : *QTB)
4369 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4373 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4389 if (
I.isTerminator())
4407 "When we run out of budget we will eagerly return from within the "
4408 "per-instruction loop.");
4412 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4414 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4415 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4451 InvertPCond ^= (PStore->
getParent() != PTB);
4452 InvertQCond ^= (QStore->
getParent() != QTB);
4537 bool InvertPCond =
false, InvertQCond =
false;
4543 if (QFB == PostBB) {
4562 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4565 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4573 for (
auto *BB : {PTB, PFB}) {
4578 PStoreAddresses.
insert(
SI->getPointerOperand());
4580 for (
auto *BB : {QTB, QFB}) {
4585 QStoreAddresses.
insert(
SI->getPointerOperand());
4591 auto &CommonAddresses = PStoreAddresses;
4594 for (
auto *Address : CommonAddresses)
4597 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4615 !BI->
getParent()->getSinglePredecessor())
4617 if (!IfFalseBB->
phis().empty())
4627 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4730 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4732 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4736 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4739 if (CommonDestProb >= Likely)
4749 unsigned NumPhis = 0;
4771 if (OtherDest == BB) {
4779 OtherDest = InfLoopBlock;
4791 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4795 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4799 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4814 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4815 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4818 SuccTrueWeight, SuccFalseWeight);
4820 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4821 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4822 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4823 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4827 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4828 PredOther * SuccCommon,
4829 PredOther * SuccOther};
4838 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4857 Value *BIV = PN.getIncomingValueForBlock(BB);
4858 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4859 Value *PBIV = PN.getIncomingValue(PBBIdx);
4863 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4864 PN.setIncomingValue(PBBIdx, NV);
4868 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4869 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4889bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4891 BasicBlock *FalseBB,
4892 uint32_t TrueWeight,
4893 uint32_t FalseWeight) {
4900 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4902 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4905 for (BasicBlock *Succ :
successors(OldTerm)) {
4907 if (Succ == KeepEdge1)
4908 KeepEdge1 =
nullptr;
4909 else if (Succ == KeepEdge2)
4910 KeepEdge2 =
nullptr;
4915 if (Succ != TrueBB && Succ != FalseBB)
4916 RemovedSuccessors.
insert(Succ);
4924 if (!KeepEdge1 && !KeepEdge2) {
4925 if (TrueBB == FalseBB) {
4933 if (TrueWeight != FalseWeight)
4936 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4956 SmallVector<DominatorTree::UpdateType, 2> Updates;
4958 for (
auto *RemovedSuccessor : RemovedSuccessors)
4959 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4970bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4975 if (!TrueVal || !FalseVal)
4980 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4981 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4984 uint32_t TrueWeight = 0, FalseWeight = 0;
4985 SmallVector<uint64_t, 8> Weights;
4989 if (Weights.
size() == 1 +
SI->getNumCases()) {
4991 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4993 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4998 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5007bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5020 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
5041bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5061 if (
SI->getCondition() != V)
5067 if (
SI->getDefaultDest() != BB) {
5068 ConstantInt *VVal =
SI->findCaseDest(BB);
5069 assert(VVal &&
"Should have a unique destination value");
5077 return requestResimplify();
5083 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5093 return requestResimplify();
5100 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5117 SmallVector<DominatorTree::UpdateType, 2> Updates;
5124 SwitchInstProfUpdateWrapper SIW(*SI);
5125 auto W0 = SIW.getSuccessorWeight(0);
5128 NewW = ((uint64_t(*W0) + 1) >> 1);
5129 SIW.setSuccessorWeight(0, *NewW);
5131 SIW.addCase(Cst, NewBB, NewW);
5133 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5142 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5151bool SimplifyCFGOpt::simplifyBranchOnICmpChain(BranchInst *BI,
5153 const DataLayout &
DL) {
5163 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5165 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5166 Value *CompVal = ConstantCompare.CompValue;
5167 unsigned UsedICmps = ConstantCompare.UsedICmps;
5168 Value *ExtraCase = ConstantCompare.Extra;
5169 bool TrueWhenEqual = ConstantCompare.IsEq;
5186 if (ExtraCase && Values.
size() < 2)
5201 <<
" cases into SWITCH. BB is:\n"
5204 SmallVector<DominatorTree::UpdateType, 2> Updates;
5211 nullptr,
"switch.early.test");
5222 AssumptionCache *AC =
Options.AC;
5235 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5241 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5242 <<
"\nEXTRABB = " << *BB);
5250 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5257 for (ConstantInt *Val : Values)
5258 New->addCase(Val, EdgeBB);
5266 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5275 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5279bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5281 return simplifyCommonResume(RI);
5285 return simplifySingleResume(RI);
5298 switch (IntrinsicID) {
5299 case Intrinsic::dbg_declare:
5300 case Intrinsic::dbg_value:
5301 case Intrinsic::dbg_label:
5302 case Intrinsic::lifetime_end:
5312bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5321 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5325 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5327 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5328 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5332 if (IncomingBB->getUniqueSuccessor() != BB)
5337 if (IncomingValue != LandingPad)
5341 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5342 TrivialUnwindBlocks.
insert(IncomingBB);
5346 if (TrivialUnwindBlocks.
empty())
5350 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5354 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5357 for (BasicBlock *Pred :
5368 TrivialBB->getTerminator()->eraseFromParent();
5369 new UnreachableInst(RI->
getContext(), TrivialBB);
5371 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5378 return !TrivialUnwindBlocks.empty();
5382bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5386 "Resume must unwind the exception that caused control to here");
5442 int Idx = DestPN.getBasicBlockIndex(BB);
5456 Value *SrcVal = DestPN.getIncomingValue(Idx);
5459 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5463 DestPN.addIncoming(
Incoming, Pred);
5490 std::vector<DominatorTree::UpdateType> Updates;
5494 if (UnwindDest ==
nullptr) {
5535 if (!SuccessorCleanupPad)
5544 SuccessorCleanupPad->eraseFromParent();
5553bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5570bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5602 BBI->dropDbgRecords();
5606 BBI->eraseFromParent();
5612 if (&BB->
front() != UI)
5615 std::vector<DominatorTree::UpdateType> Updates;
5618 for (BasicBlock *Predecessor : Preds) {
5625 [BB](
auto *
Successor) { return Successor == BB; })) {
5633 "The destinations are guaranteed to be different here.");
5634 CallInst *Assumption;
5650 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5652 SwitchInstProfUpdateWrapper SU(*SI);
5653 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5654 if (i->getCaseSuccessor() != BB) {
5659 i = SU.removeCase(i);
5664 if (DTU &&
SI->getDefaultDest() != BB)
5665 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5667 if (
II->getUnwindDest() == BB) {
5673 if (!CI->doesNotThrow())
5674 CI->setDoesNotThrow();
5678 if (CSI->getUnwindDest() == BB) {
5689 E = CSI->handler_end();
5692 CSI->removeHandler(
I);
5699 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5700 if (CSI->getNumHandlers() == 0) {
5701 if (CSI->hasUnwindDest()) {
5705 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5706 Updates.push_back({DominatorTree::Insert,
5707 PredecessorOfPredecessor,
5708 CSI->getUnwindDest()});
5709 Updates.push_back({DominatorTree::Delete,
5710 PredecessorOfPredecessor, Predecessor});
5713 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5720 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5721 for (BasicBlock *EHPred : EHPreds)
5725 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5726 CSI->eraseFromParent();
5731 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5732 "Expected to always have an unwind to BB.");
5734 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5757 for (
size_t I = 1,
E = Cases.
size();
I !=
E; ++
I) {
5758 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5766 bool RemoveOrigDefaultBlock =
true) {
5768 auto *BB = Switch->getParent();
5769 auto *OrigDefaultBlock = Switch->getDefaultDest();
5770 if (RemoveOrigDefaultBlock)
5771 OrigDefaultBlock->removePredecessor(BB);
5775 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5777 Switch->setDefaultDest(&*NewDefaultBlock);
5781 if (RemoveOrigDefaultBlock &&
5791bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5793 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5795 bool HasDefault = !
SI->defaultDestUnreachable();
5797 auto *BB =
SI->getParent();
5800 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5805 for (
auto Case :
SI->cases()) {
5809 if (Dest == DestA) {
5815 if (Dest == DestB) {
5825 "Single-destination switch should have been folded.");
5827 assert(DestB !=
SI->getDefaultDest());
5828 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5832 SmallVectorImpl<ConstantInt *> *ContiguousCases =
nullptr;
5836 ContiguousCases = &CasesA;
5837 ContiguousDest = DestA;
5840 ContiguousCases = &CasesB;
5841 ContiguousDest = DestB;
5850 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5853 if (!
Offset->isNullValue())
5862 BranchInst *NewBI = Builder.
CreateCondBr(Cmp, ContiguousDest, OtherDest);
5866 SmallVector<uint64_t, 8> Weights;
5868 if (Weights.
size() == 1 +
SI->getNumCases()) {
5869 uint64_t TrueWeight = 0;
5870 uint64_t FalseWeight = 0;
5871 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
5872 if (
SI->getSuccessor(
I) == ContiguousDest)
5873 TrueWeight += Weights[
I];
5875 FalseWeight += Weights[
I];
5877 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5887 unsigned PreviousEdges = ContiguousCases->
size();
5888 if (ContiguousDest ==
SI->getDefaultDest())
5890 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5894 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5895 if (OtherDest ==
SI->getDefaultDest())
5897 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5906 auto *UnreachableDefault =
SI->getDefaultDest();
5909 SI->eraseFromParent();
5911 if (!HasDefault && DTU)
5912 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5928 unsigned MaxSignificantBitsInCond =
5935 for (
const auto &Case :
SI->cases()) {
5936 auto *
Successor = Case.getCaseSuccessor();
5943 const APInt &CaseVal = Case.getCaseValue()->getValue();
5946 DeadCases.
push_back(Case.getCaseValue());
5958 bool HasDefault = !
SI->defaultDestUnreachable();
5959 const unsigned NumUnknownBits =
5962 if (HasDefault && DeadCases.
empty() &&
5963 NumUnknownBits < 64 ) {
5964 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5965 if (
SI->getNumCases() == AllNumCases) {
5972 if (
SI->getNumCases() == AllNumCases - 1) {
5973 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5980 for (
const auto &Case :
SI->cases())
5981 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5992 if (DeadCases.
empty())
5998 assert(CaseI !=
SI->case_default() &&
5999 "Case was not found. Probably mistake in DeadCases forming.");
6001 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6006 std::vector<DominatorTree::UpdateType> Updates;
6007 for (
auto *
Successor : UniqueSuccessors)
6008 if (NumPerSuccessorCases[
Successor] == 0)
6029 if (!Branch || !Branch->isUnconditional())
6035 int Idx =
PHI.getBasicBlockIndex(BB);
6036 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6038 Value *InValue =
PHI.getIncomingValue(Idx);
6039 if (InValue != CaseValue)
6055 ForwardingNodesMap ForwardingNodes;
6058 for (
const auto &Case :
SI->cases()) {
6060 BasicBlock *CaseDest = Case.getCaseSuccessor();
6079 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6080 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6081 count(Phi.blocks(), SwitchBlock) == 1) {
6082 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6090 ForwardingNodes[Phi].push_back(PhiIdx);
6093 for (
auto &ForwardingNode : ForwardingNodes) {
6094 PHINode *Phi = ForwardingNode.first;
6100 for (
int Index : Indexes)
6101 Phi->setIncomingValue(Index,
SI->getCondition());
6111 if (
C->isThreadDependent())
6113 if (
C->isDLLImportDependent())
6129 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6156 if (
A->isAllOnesValue())
6158 if (
A->isNullValue())
6164 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6189 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6191 if (
I.isTerminator()) {
6193 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6196 CaseDest =
I.getSuccessor(0);
6203 for (
auto &
Use :
I.uses()) {
6206 if (
I->getParent() == CaseDest)
6209 if (Phi->getIncomingBlock(
Use) == CaseDest)
6222 *CommonDest = CaseDest;
6224 if (CaseDest != *CommonDest)
6229 int Idx =
PHI.getBasicBlockIndex(Pred);
6242 Res.push_back(std::make_pair(&
PHI, ConstVal));
6245 return Res.
size() > 0;
6251 SwitchCaseResultVectorTy &UniqueResults,
6253 for (
auto &
I : UniqueResults) {
6254 if (
I.first == Result) {
6255 I.second.push_back(CaseVal);
6256 return I.second.size();
6259 UniqueResults.push_back(
6270 SwitchCaseResultVectorTy &UniqueResults,
6274 uintptr_t MaxUniqueResults) {
6275 for (
const auto &
I :
SI->cases()) {
6289 const size_t NumCasesForResult =
6297 if (UniqueResults.size() > MaxUniqueResults)
6313 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6315 return DefaultResult ||
SI->defaultDestUnreachable();
6332 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6333 ResultVector[1].second.size() == 1) {
6334 ConstantInt *FirstCase = ResultVector[0].second[0];
6335 ConstantInt *SecondCase = ResultVector[1].second[0];
6336 Value *SelectValue = ResultVector[1].first;
6337 if (DefaultResult) {
6338 Value *ValueCompare =
6339 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6340 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6341 DefaultResult,
"switch.select");
6343 Value *ValueCompare =
6344 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6345 return Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6346 SelectValue,
"switch.select");
6350 if (ResultVector.size() == 1 && DefaultResult) {
6352 unsigned CaseCount = CaseValues.
size();
6365 for (
auto *Case : CaseValues) {
6366 if (Case->getValue().slt(MinCaseVal->
getValue()))
6368 AndMask &= Case->getValue();
6378 if (FreeBits ==
Log2_32(CaseCount)) {
6379 Value *
And = Builder.CreateAnd(Condition, AndMask);
6380 Value *Cmp = Builder.CreateICmpEQ(
6382 return Builder.CreateSelect(Cmp, ResultVector[0].first,
6389 for (
auto *Case : CaseValues)
6390 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6396 Condition = Builder.CreateSub(Condition, MinCaseVal);
6397 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6398 Value *Cmp = Builder.CreateICmpEQ(
6400 return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6405 if (CaseValues.
size() == 2) {
6406 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6407 "switch.selectcmp.case1");
6408 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6409 "switch.selectcmp.case2");
6410 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6411 return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6424 std::vector<DominatorTree::UpdateType> Updates;
6431 Builder.CreateBr(DestBB);
6435 PHI->removeIncomingValueIf(
6436 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6437 PHI->addIncoming(SelectValue, SelectBB);
6440 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6446 if (DTU && RemovedSuccessors.
insert(Succ).second)
6449 SI->eraseFromParent();
6464 SwitchCaseResultVectorTy UniqueResults;
6470 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6471 Builder.SetInsertPoint(
SI);
6472 Value *SelectValue =
6485class SwitchReplacement {
6492 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6493 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName);
6502 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6509 bool isLookupTable();
6543 ConstantInt *BitMap =
nullptr;
6544 IntegerType *BitMapElementTy =
nullptr;
6547 ConstantInt *LinearOffset =
nullptr;
6548 ConstantInt *LinearMultiplier =
nullptr;
6549 bool LinearMapValWrapped =
false;
6557SwitchReplacement::SwitchReplacement(
6559 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6560 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName)
6561 : DefaultValue(DefaultValue) {
6562 assert(Values.size() &&
"Can't build lookup table without values!");
6563 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6566 SingleValue = Values.begin()->second;
6568 ValueType = Values.begin()->second->getType();
6572 for (
const auto &[CaseVal, CaseRes] : Values) {
6575 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6576 TableContents[Idx] = CaseRes;
6583 if (Values.size() < TableSize) {
6585 "Need a default value to fill the lookup table holes.");
6588 if (!TableContents[
I])
6589 TableContents[
I] = DefaultValue;
6595 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6596 SingleValue =
nullptr;
6602 Kind = SingleValueKind;
6609 bool LinearMappingPossible =
true;
6614 bool NonMonotonic =
false;
6615 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6632 LinearMappingPossible =
false;
6637 APInt Dist = Val - PrevVal;
6640 }
else if (Dist != DistToPrev) {
6641 LinearMappingPossible =
false;
6649 if (LinearMappingPossible) {
6651 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6652 APInt M = LinearMultiplier->getValue();
6653 bool MayWrap =
true;
6654 if (
isIntN(M.getBitWidth(), TableSize - 1))
6655 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6656 LinearMapValWrapped = NonMonotonic || MayWrap;
6657 Kind = LinearMapKind;
6663 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6665 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6667 TableInt <<=
IT->getBitWidth();
6671 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6674 BitMap = ConstantInt::get(M.getContext(), TableInt);
6675 BitMapElementTy =
IT;
6684 Kind = LookupTableKind;
6690 case SingleValueKind:
6692 case LinearMapKind: {
6696 false,
"switch.idx.cast");
6697 if (!LinearMultiplier->
isOne())
6698 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6700 !LinearMapValWrapped);
6702 if (!LinearOffset->
isZero())
6705 !LinearMapValWrapped);
6722 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
6723 "switch.shiftamt",
true,
true);
6726 Value *DownShifted =
6727 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6729 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6731 case LookupTableKind: {
6734 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
6735 true, GlobalVariable::PrivateLinkage,
6736 Initializer,
"switch.table." +
Func->getName());
6737 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6740 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
6741 Type *IndexTy =
DL.getIndexType(Table->getType());
6744 if (
Index->getType() != IndexTy) {
6745 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
6749 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
6752 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
6755 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
6761bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
6763 Type *ElementType) {
6771 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6773 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6779 if (
TTI.isTypeLegal(Ty))
6794 DL.fitsInLegalInteger(
IT->getBitWidth());
6797Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
6799bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
6810 return NumCases * 100 >= CaseRange * MinDensity;
6831 if (
SI->getNumCases() > TableSize)
6834 bool AllTablesFitInRegister =
true;
6835 bool HasIllegalType =
false;
6836 for (
const auto &Ty : ResultTypes) {
6841 AllTablesFitInRegister =
6842 AllTablesFitInRegister &&
6843 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
6848 if (HasIllegalType && !AllTablesFitInRegister)
6853 if (AllTablesFitInRegister)
6870 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6873 return all_of(ResultTypes, [&](
const auto &ResultType) {
6874 return SwitchReplacement::wouldFitInRegister(
6902 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6924 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6929 for (
auto ValuePair : Values) {
6932 if (!CaseConst || CaseConst == DefaultConst ||
6933 (CaseConst != TrueConst && CaseConst != FalseConst))
6947 if (DefaultConst == FalseConst) {
6950 ++NumTableCmpReuses;
6953 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6954 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6957 ++NumTableCmpReuses;
6967 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6981 if (
SI->getNumCases() < 3)
7003 MinCaseVal = CaseVal;
7005 MaxCaseVal = CaseVal;
7022 It->second.push_back(std::make_pair(CaseVal,
Value));
7030 bool HasDefaultResults =
7032 DefaultResultsList,
DL,
TTI);
7033 for (
const auto &
I : DefaultResultsList) {
7036 DefaultResults[
PHI] = Result;
7040 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7043 if (UseSwitchConditionAsTableIndex) {
7045 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7050 TableIndexOffset = MinCaseVal;
7057 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7059 bool TableHasHoles = (NumResults < TableSize);
7064 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7072 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7075 if (
SI->getNumCases() < 4)
7077 if (!
DL.fitsInLegalInteger(TableSize))
7086 if (UseSwitchConditionAsTableIndex) {
7087 TableIndex =
SI->getCondition();
7088 if (HasDefaultResults) {
7100 all_of(ResultTypes, [&](
const auto &ResultType) {
7101 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7106 TableSize = std::max(UpperBound, TableSize);
7109 DefaultIsReachable =
false;
7117 const auto &ResultList = ResultLists[
PHI];
7119 Type *ResultType = ResultList.begin()->second->getType();
7124 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7126 PhiToReplacementMap.
insert({
PHI, Replacement});
7129 bool AnyLookupTables =
any_of(
7130 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7138 if (AnyLookupTables &&
7139 (!
TTI.shouldBuildLookupTables() ||
7143 Builder.SetInsertPoint(
SI);
7146 if (!UseSwitchConditionAsTableIndex) {
7149 bool MayWrap =
true;
7150 if (!DefaultIsReachable) {
7155 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7156 "switch.tableidx",
false,
7160 std::vector<DominatorTree::UpdateType> Updates;
7166 assert(MaxTableSize >= TableSize &&
7167 "It is impossible for a switch to have more entries than the max "
7168 "representable value of its input integer type's size.");
7173 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7177 Builder.SetInsertPoint(
SI);
7178 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7179 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7180 Builder.CreateBr(LookupBB);
7186 Value *Cmp = Builder.CreateICmpULT(
7187 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7189 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7195 Builder.SetInsertPoint(LookupBB);
7201 MaskBB->
setName(
"switch.hole_check");
7208 APInt MaskInt(TableSizePowOf2, 0);
7209 APInt One(TableSizePowOf2, 1);
7211 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7212 for (
const auto &Result : ResultList) {
7215 MaskInt |= One << Idx;
7217 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7224 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7225 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7226 Value *LoBit = Builder.CreateTrunc(
7228 Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7233 Builder.SetInsertPoint(LookupBB);
7237 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7240 SI->getDefaultDest()->removePredecessor(BB,
7247 const ResultListTy &ResultList = ResultLists[
PHI];
7248 auto Replacement = PhiToReplacementMap.
at(
PHI);
7249 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7252 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7255 for (
auto *
User :
PHI->users()) {
7257 Replacement.getDefaultValue(), ResultList);
7261 PHI->addIncoming(Result, LookupBB);
7264 Builder.CreateBr(CommonDest);
7270 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
7273 if (Succ ==
SI->getDefaultDest())
7276 if (DTU && RemovedSuccessors.
insert(Succ).second)
7279 SI->eraseFromParent();
7285 ++NumLookupTablesHoles;
7301 if (CondTy->getIntegerBitWidth() > 64 ||
7302 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7306 if (
SI->getNumCases() < 4)
7314 for (
const auto &
C :
SI->cases())
7315 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7323 int64_t
Base = Values[0];
7324 for (
auto &V : Values)
7337 unsigned Shift = 64;
7338 for (
auto &V : Values)
7342 for (
auto &V : Values)
7343 V = (int64_t)((
uint64_t)V >> Shift);
7360 Builder.SetInsertPoint(
SI);
7362 Builder.CreateSub(
SI->getCondition(), ConstantInt::get(Ty,
Base));
7363 Value *Rot = Builder.CreateIntrinsic(
7364 Ty, Intrinsic::fshl,
7365 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7366 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7368 for (
auto Case :
SI->cases()) {
7369 auto *Orig = Case.getCaseValue();
7370 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7389 Value *Condition =
SI->getCondition();
7393 if (CondTy->getIntegerBitWidth() > 64 ||
7394 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7406 if (
SI->getNumCases() < 4)
7412 if (!
SI->defaultDestUnreachable())
7417 for (
const auto &Case :
SI->cases()) {
7418 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7432 Builder.SetInsertPoint(
SI);
7435 for (
auto &Case :
SI->cases()) {
7436 auto *OrigValue = Case.getCaseValue();
7437 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7438 OrigValue->getValue().countr_zero()));
7442 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7445 SI->setCondition(ConditionTrailingZeros);
7455 if (!Cmp || !Cmp->hasOneUse())
7466 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7469 if (
SI->getNumCases() == 2) {
7476 Succ =
SI->getDefaultDest();
7477 SuccWeight = Weights[0];
7479 for (
auto &Case :
SI->cases()) {
7480 std::optional<int64_t> Val =
7484 if (!Missing.erase(*Val))
7489 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7492 assert(Missing.size() == 1 &&
"Should have one case left");
7493 Res = *Missing.begin();
7494 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7496 Unreachable =
SI->getDefaultDest();
7498 for (
auto &Case :
SI->cases()) {
7499 BasicBlock *NewSucc = Case.getCaseSuccessor();
7500 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7503 OtherSuccWeight += Weight;
7506 SuccWeight = Weight;
7507 }
else if (Succ == NewSucc) {
7513 for (
auto &Case :
SI->cases()) {
7514 std::optional<int64_t> Val =
7516 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7518 if (Case.getCaseSuccessor() == Succ) {
7540 if (Cmp->isSigned())
7543 MDNode *NewWeights =
nullptr;
7549 Builder.SetInsertPoint(
SI->getIterator());
7550 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
7551 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
7552 SI->getMetadata(LLVMContext::MD_unpredictable));
7556 SI->eraseFromParent();
7557 Cmp->eraseFromParent();
7558 if (DTU && Unreachable)
7590 "Only supporting unconditional branches for now");
7592 "Expected unconditional branches to have one successor");
7593 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7614 if (LHS == EKey || RHS == EKey || LHS == TKey || RHS == TKey)
7630 "Only supporting unconditional branches for now");
7637 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
7638 if (PredIVs[
A] != PredIVs[
B])
7647bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
7648 DomTreeUpdater *DTU) {
7654 SmallPtrSet<PHINode *, 8> Phis;
7655 SmallPtrSet<BasicBlock *, 8> Seen;
7656 DenseMap<PHINode *, SmallDenseMap<BasicBlock *, Value *, 8>> PhiPredIVs;
7657 DenseMap<BasicBlock *, SmallVector<unsigned, 32>> BBToSuccessorIndexes;
7661 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7666 if (BB->
size() != 1)
7676 if (!Seen.
insert(BB).second) {
7677 auto It = BBToSuccessorIndexes.
find(BB);
7678 if (It != BBToSuccessorIndexes.
end())
7679 It->second.emplace_back(
I);
7693 Cases.
emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs});
7694 BBToSuccessorIndexes[BB].emplace_back(
I);
7700 for (PHINode *Phi : Phis) {
7702 PhiPredIVs.
try_emplace(Phi,
Phi->getNumIncomingValues()).first->second;
7703 for (
auto &
IV :
Phi->incoming_values())
7704 IVs.insert({
Phi->getIncomingBlock(
IV),
IV.get()});
7715 DenseSet<const SwitchSuccWrapper *> ReplaceWith;
7720 bool MadeChange =
false;
7721 for (
auto &SSW : Cases) {
7728 Updates.
push_back({DominatorTree::Delete,
SI->getParent(), SSW.Dest});
7729 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7730 for (
unsigned Idx : Successors)
7731 SI->setSuccessor(Idx, (*It)->Dest);
7742bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
7745 if (isValueEqualityComparison(SI)) {
7749 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7750 return requestResimplify();
7754 if (simplifySwitchOnSelect(SI,
Select))
7755 return requestResimplify();
7760 if (foldValueComparisonIntoPredecessors(SI, Builder))
7761 return requestResimplify();
7767 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7768 return requestResimplify();
7772 return requestResimplify();
7775 return requestResimplify();
7778 return requestResimplify();
7781 return requestResimplify();
7788 if (
Options.ConvertSwitchToLookupTable &&
7790 return requestResimplify();
7793 return requestResimplify();
7796 return requestResimplify();
7799 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
7800 return requestResimplify();
7802 if (simplifyDuplicateSwitchArms(SI, DTU))
7803 return requestResimplify();
7808bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
7813 SmallPtrSet<Value *, 8> Succs;
7814 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
7819 RemovedSuccs.
insert(Dest);
7829 std::vector<DominatorTree::UpdateType> Updates;
7830 Updates.reserve(RemovedSuccs.
size());
7831 for (
auto *RemovedSucc : RemovedSuccs)
7832 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7851 if (simplifyIndirectBrOnSelect(IBI, SI))
7852 return requestResimplify();
7888 if (BB == OtherPred)
7899 std::vector<DominatorTree::UpdateType> Updates;
7906 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7907 "unexpected successor");
7908 II->setUnwindDest(OtherPred);
7923 Builder.CreateUnreachable();
7932bool SimplifyCFGOpt::simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder) {
7933 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7934 : simplifyCondBranch(
Branch, Builder);
7937bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
7949 bool NeedCanonicalLoop =
7963 if (
I->isTerminator() &&
7964 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7980 if (
Options.SpeculateBlocks &&
7983 return requestResimplify();
7991 if (!PPred || (PredPred && PredPred != PPred))
8028 if (!SuccBI || !SuccBI->isConditional())
8032 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8036 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8062 bool HasWeight =
false;
8067 BBTWeight = BBFWeight = 1;
8072 BB1TWeight = BB1FWeight = 1;
8077 BB2TWeight = BB2FWeight = 1;
8079 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8080 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8087bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder) {
8091 "Tautological conditional branch should have been eliminated already.");
8094 if (!
Options.SimplifyCondBranch ||
8099 if (isValueEqualityComparison(BI)) {
8104 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8105 return requestResimplify();
8111 if (foldValueComparisonIntoPredecessors(BI, Builder))
8112 return requestResimplify();
8115 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8116 return requestResimplify();
8121 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8134 return requestResimplify();
8140 if (
Options.SpeculateBlocks &&
8143 return requestResimplify();
8152 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8153 return requestResimplify();
8155 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8157 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8158 auto CanSpeculateConditionalLoadsStores = [&]() {
8160 for (Instruction &
I : *Succ) {
8161 if (
I.isTerminator()) {
8162 if (
I.getNumSuccessors() > 1)
8166 SpeculatedConditionalLoadsStores.
size() ==
8170 SpeculatedConditionalLoadsStores.
push_back(&
I);
8173 return !SpeculatedConditionalLoadsStores.
empty();
8176 if (CanSpeculateConditionalLoadsStores()) {
8178 std::nullopt,
nullptr);
8179 return requestResimplify();
8189 return requestResimplify();
8198 return requestResimplify();
8204 if (foldCondBranchOnValueKnownInPredecessor(BI))
8205 return requestResimplify();
8210 if (PBI != BI && PBI->isConditional())
8212 return requestResimplify();
8218 if (PBI != BI && PBI->isConditional())
8220 return requestResimplify();
8224 return requestResimplify();
8231 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8243 auto *Use = cast<Instruction>(U.getUser());
8245 switch (Use->getOpcode()) {
8248 case Instruction::GetElementPtr:
8249 case Instruction::Ret:
8250 case Instruction::BitCast:
8251 case Instruction::Load:
8252 case Instruction::Store:
8253 case Instruction::Call:
8254 case Instruction::CallBr:
8255 case Instruction::Invoke:
8256 case Instruction::UDiv:
8257 case Instruction::URem:
8261 case Instruction::SDiv:
8262 case Instruction::SRem:
8266 if (FindUse ==
I->use_end())
8268 auto &
Use = *FindUse;
8273 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8274 User->comesBefore(
I))
8288 if (
GEP->getPointerOperand() ==
I) {
8291 if (
GEP->getType()->isVectorTy())
8299 if (!
GEP->hasAllZeroIndices() &&
8300 (!
GEP->isInBounds() ||
8302 GEP->getPointerAddressSpace())))
8303 PtrValueMayBeModified =
true;
8309 bool HasNoUndefAttr =
8310 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8315 if (
C->isNullValue() && HasNoUndefAttr &&
8316 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8317 return !PtrValueMayBeModified;
8323 if (!LI->isVolatile())
8325 LI->getPointerAddressSpace());
8329 if (!
SI->isVolatile())
8331 SI->getPointerAddressSpace())) &&
8332 SI->getPointerOperand() ==
I;
8337 if (
I == Assume->getArgOperand(0))
8345 if (CB->getCalledOperand() ==
I)
8348 if (CB->isArgOperand(&
Use)) {
8349 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8352 CB->paramHasNonNullAttr(ArgIdx,
false))
8353 return !PtrValueMayBeModified;
8372 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8382 Builder.CreateUnreachable();
8389 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8391 Assumption = Builder.CreateAssumption(
Cond);
8406 Builder.SetInsertPoint(Unreachable);
8408 Builder.CreateUnreachable();
8409 for (
const auto &Case :
SI->cases())
8410 if (Case.getCaseSuccessor() == BB) {
8412 Case.setSuccessor(Unreachable);
8414 if (
SI->getDefaultDest() == BB) {
8416 SI->setDefaultDest(Unreachable);
8430bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8455 return requestResimplify();
8476 if (
Options.SpeculateBlocks &&
8483 Options.SpeculateUnpredictables))
8490 case Instruction::Br:
8493 case Instruction::Resume:
8496 case Instruction::CleanupRet:
8499 case Instruction::Switch:
8502 case Instruction::Unreachable:
8505 case Instruction::IndirectBr:
8513bool SimplifyCFGOpt::run(BasicBlock *BB) {
8523 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
unsigned unsigned DefaultVal
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
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 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 simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static bool isProfitableToSpeculate(const BranchInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static 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"))
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static void hoistConditionalLoadsStores(BranchInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL)
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"))
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static 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"))
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
static 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)"))
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool tryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
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"))
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 isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static void fitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool casesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static 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"))
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
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 bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
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"))
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 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"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
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)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static 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"))
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
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 bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
LLVM_ABI 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 bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
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...
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
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...
LLVM_ABI BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
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.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
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.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
auto reverse(ContainerTy &&C)
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< uint32_t, 2 > &B1, const SmallVector< uint32_t, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
FunctionAddr VTableAddr Count
auto succ_size(const MachineBasicBlock *BB)
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
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.
LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
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
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
LLVM_ABI bool foldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Checking whether two cases of SI are equal depends on the contents of the BasicBlock and the incoming...
DenseMap< PHINode *, SmallDenseMap< BasicBlock *, Value *, 8 > > * PhiPredIVs
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const SwitchSuccWrapper * getEmptyKey()
static const SwitchSuccWrapper * getTombstoneKey()
static unsigned getHashValue(const SwitchSuccWrapper *SSW)
static bool isEqual(const SwitchSuccWrapper *LHS, const SwitchSuccWrapper *RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.