97#define DEBUG_TYPE "simplifycfg"
102 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
105 "Temporary development switch used to gradually uplift SimplifyCFG "
106 "into preserving DomTree,"));
115 "Control the amount of phi node folding to perform (default = 2)"));
119 cl::desc(
"Control the maximal total instruction cost that we are willing "
120 "to speculatively execute to fold a 2-entry PHI node into a "
121 "select (default = 4)"));
125 cl::desc(
"Hoist common instructions up to the parent block"));
129 cl::desc(
"Hoist loads if the target supports conditional faulting"));
133 cl::desc(
"Hoist stores if the target supports conditional faulting"));
137 cl::desc(
"Control the maximal conditional load/store that we are willing "
138 "to speculatively execute to eliminate conditional branch "
144 cl::desc(
"Allow reordering across at most this many "
145 "instructions when hoisting"));
149 cl::desc(
"Sink common instructions down to the end block"));
153 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
157 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
158 "precede - hoist multiple conditional stores into a single "
159 "predicated store"));
163 cl::desc(
"When merging conditional stores, do so even if the resultant "
164 "basic blocks are unlikely to be if-converted as a result"));
168 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
173 cl::desc(
"Limit maximum recursion depth when calculating costs of "
174 "speculatively executed instructions"));
179 cl::desc(
"Max size of a block which is still considered "
180 "small enough to thread through"));
186 cl::desc(
"Maximum cost of combining conditions when "
187 "folding branches"));
190 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
192 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
193 "to fold branch to common destination when vector operations are "
198 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
202 cl::desc(
"Limit cases to analyze when converting a switch to select"));
206 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
213STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
215 "Number of switch instructions turned into linear mapping");
217 "Number of switch instructions turned into lookup tables");
219 NumLookupTablesHoles,
220 "Number of switch instructions turned into lookup tables (holes checked)");
221STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
223 "Number of value comparisons folded into predecessor basic blocks");
225 "Number of branches folded into predecessor basic block");
228 "Number of common instruction 'blocks' hoisted up to the begin block");
230 "Number of common instructions hoisted up to the begin block");
232 "Number of common instruction 'blocks' sunk down to the end block");
234 "Number of common instructions sunk down to the end block");
235STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
237 "Number of invokes with empty resume blocks simplified into calls");
238STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
239STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
246using SwitchCaseResultVectorTy =
255struct ValueEqualityComparisonCase {
267 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
270class SimplifyCFGOpt {
271 const TargetTransformInfo &TTI;
273 const DataLayout &DL;
275 const SimplifyCFGOptions &Options;
278 Value *isValueEqualityComparison(Instruction *TI);
280 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
281 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
284 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
287 bool foldValueComparisonIntoPredecessors(Instruction *TI,
290 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
291 bool simplifySingleResume(ResumeInst *RI);
292 bool simplifyCommonResume(ResumeInst *RI);
293 bool simplifyCleanupReturn(CleanupReturnInst *RI);
294 bool simplifyUnreachable(UnreachableInst *UI);
295 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
296 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
297 bool simplifyIndirectBr(IndirectBrInst *IBI);
298 bool simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder);
299 bool simplifyUncondBranch(BranchInst *BI,
IRBuilder<> &Builder);
300 bool simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder);
301 bool foldCondBranchOnValueKnownInPredecessor(BranchInst *BI);
303 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
305 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
308 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
309 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
310 Instruction *TI, Instruction *I1,
311 SmallVectorImpl<Instruction *> &OtherSuccTIs);
312 bool speculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
313 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
314 BasicBlock *TrueBB, BasicBlock *FalseBB,
315 uint32_t TrueWeight, uint32_t FalseWeight);
316 bool simplifyBranchOnICmpChain(BranchInst *BI,
IRBuilder<> &Builder,
317 const DataLayout &DL);
318 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
319 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
320 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
323 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
325 const SimplifyCFGOptions &Opts)
326 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
327 assert((!DTU || !DTU->hasPostDomTree()) &&
328 "SimplifyCFG is not yet capable of maintaining validity of a "
329 "PostDomTree, so don't ask for it.");
332 bool simplifyOnce(BasicBlock *BB);
333 bool run(BasicBlock *BB);
336 bool requestResimplify() {
346isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
366 "Only for a pair of incoming blocks at the time!");
372 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
373 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
376 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
377 EquivalenceSet->contains(IV1))
400 if (!SI1Succs.
count(Succ))
406 FailBlocks->insert(Succ);
422 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
424 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
425 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
487 if (AggressiveInsts.
count(
I))
503 ZeroCostInstructions.
insert(OverflowInst);
505 }
else if (!ZeroCostInstructions.
contains(
I))
521 for (
Use &
Op :
I->operands())
523 TTI, AC, ZeroCostInstructions,
Depth + 1))
540 if (
DL.hasUnstableRepresentation(V->getType()))
549 return ConstantInt::get(IntPtrTy, 0);
554 if (CE->getOpcode() == Instruction::IntToPtr)
578struct ConstantComparesGatherer {
579 const DataLayout &DL;
582 Value *CompValue =
nullptr;
585 Value *Extra =
nullptr;
591 unsigned UsedICmps = 0;
597 bool IgnoreFirstMatch =
false;
598 bool MultipleMatches =
false;
601 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
603 if (CompValue || !MultipleMatches)
608 IgnoreFirstMatch =
true;
612 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
613 ConstantComparesGatherer &
614 operator=(
const ConstantComparesGatherer &) =
delete;
619 bool setValueOnce(
Value *NewVal) {
620 if (IgnoreFirstMatch) {
621 IgnoreFirstMatch =
false;
624 if (CompValue && CompValue != NewVal) {
625 MultipleMatches =
true;
639 bool matchInstruction(Instruction *
I,
bool isEQ) {
646 if (!setValueOnce(Val))
666 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
710 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
712 if (!setValueOnce(RHSVal))
717 ConstantInt::get(
C->getContext(),
718 C->getValue() | Mask));
733 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
735 if (!setValueOnce(RHSVal))
739 Vals.push_back(ConstantInt::get(
C->getContext(),
740 C->getValue() & ~Mask));
761 Value *CandidateVal =
I->getOperand(0);
764 CandidateVal = RHSVal;
779 if (!setValueOnce(CandidateVal))
785 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
797 void gather(
Value *V) {
806 SmallVector<Value *, 8> DFT{Op0, Op1};
807 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
809 while (!DFT.
empty()) {
816 if (Visited.
insert(Op1).second)
818 if (Visited.
insert(Op0).second)
825 if (matchInstruction(
I, IsEq))
852 if (BI->isConditional())
870 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
871 CV =
SI->getCondition();
873 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
878 if (Trunc->hasNoUnsignedWrap())
879 CV = Trunc->getOperand(0);
886 Value *
Ptr = PTII->getPointerOperand();
887 if (
DL.hasUnstableRepresentation(
Ptr->getType()))
889 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
898BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
899 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
901 Cases.reserve(
SI->getNumCases());
902 for (
auto Case :
SI->cases())
903 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
904 Case.getCaseSuccessor()));
905 return SI->getDefaultDest();
910 ICmpInst::Predicate Pred;
916 Pred = ICmpInst::ICMP_NE;
921 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
929 std::vector<ValueEqualityComparisonCase> &Cases) {
935 std::vector<ValueEqualityComparisonCase> &C2) {
936 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
939 if (V1->size() > V2->size())
944 if (V1->size() == 1) {
947 for (
const ValueEqualityComparisonCase &
VECC : *V2)
948 if (TheVal ==
VECC.Value)
955 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
956 while (i1 != e1 && i2 != e2) {
972bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
973 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
978 Value *ThisVal = isValueEqualityComparison(TI);
979 assert(ThisVal &&
"This isn't a value comparison!!");
980 if (ThisVal != PredVal)
987 std::vector<ValueEqualityComparisonCase> PredCases;
989 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
993 std::vector<ValueEqualityComparisonCase> ThisCases;
994 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1009 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1015 ThisCases[0].Dest->removePredecessor(PredDef);
1018 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1025 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1032 SmallPtrSet<Constant *, 16> DeadCases;
1033 for (
const ValueEqualityComparisonCase &Case : PredCases)
1034 DeadCases.
insert(Case.Value);
1037 <<
"Through successor TI: " << *TI);
1039 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1042 auto *
Successor = i->getCaseSuccessor();
1045 if (DeadCases.
count(i->getCaseValue())) {
1054 std::vector<DominatorTree::UpdateType> Updates;
1055 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1057 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1067 ConstantInt *TIV =
nullptr;
1069 for (
const auto &[
Value, Dest] : PredCases)
1075 assert(TIV &&
"No edge from pred to succ?");
1080 for (
const auto &[
Value, Dest] : ThisCases)
1088 TheRealDest = ThisDef;
1090 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1095 if (Succ != CheckEdge) {
1096 if (Succ != TheRealDest)
1097 RemovedSuccs.
insert(Succ);
1100 CheckEdge =
nullptr;
1107 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1112 SmallVector<DominatorTree::UpdateType, 2> Updates;
1114 for (
auto *RemovedSucc : RemovedSuccs)
1115 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1126struct ConstantIntOrdering {
1127 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1128 return LHS->getValue().ult(
RHS->getValue());
1140 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1149 assert(MD &&
"Invalid branch-weight metadata");
1174 if (BonusInst.isTerminator())
1204 NewBonusInst->
takeName(&BonusInst);
1205 BonusInst.setName(NewBonusInst->
getName() +
".old");
1206 VMap[&BonusInst] = NewBonusInst;
1215 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1216 "If the user is not a PHI node, then it should be in the same "
1217 "block as, and come after, the original bonus instruction.");
1221 if (PN->getIncomingBlock(U) == BB)
1225 assert(PN->getIncomingBlock(U) == PredBlock &&
1226 "Not in block-closed SSA form?");
1227 U.set(NewBonusInst);
1237 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1238 PredDL.isSameSourceLocation(
DL)) {
1245bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1253 std::vector<ValueEqualityComparisonCase> BBCases;
1254 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1256 std::vector<ValueEqualityComparisonCase> PredCases;
1257 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1262 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1265 SmallVector<uint64_t, 8> Weights;
1269 if (PredHasWeights) {
1272 if (Weights.
size() != 1 + PredCases.size())
1273 PredHasWeights = SuccHasWeights =
false;
1274 }
else if (SuccHasWeights)
1278 Weights.
assign(1 + PredCases.size(), 1);
1280 SmallVector<uint64_t, 8> SuccWeights;
1281 if (SuccHasWeights) {
1284 if (SuccWeights.
size() != 1 + BBCases.size())
1285 PredHasWeights = SuccHasWeights =
false;
1286 }
else if (PredHasWeights)
1287 SuccWeights.
assign(1 + BBCases.size(), 1);
1289 if (PredDefault == BB) {
1292 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1293 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1294 if (PredCases[i].Dest != BB)
1295 PTIHandled.insert(PredCases[i].
Value);
1298 std::swap(PredCases[i], PredCases.back());
1300 if (PredHasWeights || SuccHasWeights) {
1302 Weights[0] += Weights[i + 1];
1307 PredCases.pop_back();
1313 if (PredDefault != BBDefault) {
1315 if (DTU && PredDefault != BB)
1316 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1317 PredDefault = BBDefault;
1318 ++NewSuccessors[BBDefault];
1321 unsigned CasesFromPred = Weights.
size();
1322 uint64_t ValidTotalSuccWeight = 0;
1323 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1324 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1325 PredCases.push_back(BBCases[i]);
1326 ++NewSuccessors[BBCases[i].Dest];
1327 if (SuccHasWeights || PredHasWeights) {
1331 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1332 ValidTotalSuccWeight += SuccWeights[i + 1];
1336 if (SuccHasWeights || PredHasWeights) {
1337 ValidTotalSuccWeight += SuccWeights[0];
1339 for (
unsigned i = 1; i < CasesFromPred; ++i)
1340 Weights[i] *= ValidTotalSuccWeight;
1342 Weights[0] *= SuccWeights[0];
1348 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1349 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1350 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1351 if (PredCases[i].Dest == BB) {
1352 PTIHandled.insert(PredCases[i].
Value);
1354 if (PredHasWeights || SuccHasWeights) {
1355 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1360 std::swap(PredCases[i], PredCases.back());
1361 PredCases.pop_back();
1368 for (
const ValueEqualityComparisonCase &Case : BBCases)
1369 if (PTIHandled.count(Case.Value)) {
1371 if (PredHasWeights || SuccHasWeights)
1372 Weights.
push_back(WeightsForHandled[Case.Value]);
1373 PredCases.push_back(Case);
1374 ++NewSuccessors[Case.Dest];
1375 PTIHandled.erase(Case.Value);
1380 for (ConstantInt *
I : PTIHandled) {
1381 if (PredHasWeights || SuccHasWeights)
1383 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1384 ++NewSuccessors[BBDefault];
1391 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1396 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1398 for (
auto I :
seq(NewSuccessor.second)) {
1402 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1403 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1410 "Should not end up here with unstable pointers");
1416 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1418 for (ValueEqualityComparisonCase &V : PredCases)
1421 if (PredHasWeights || SuccHasWeights)
1433 if (!InfLoopBlock) {
1441 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1448 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1450 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1455 ++NumFoldValueComparisonIntoPredecessors;
1463bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1466 Value *CV = isValueEqualityComparison(TI);
1467 assert(CV &&
"Not a comparison?");
1472 while (!Preds.empty()) {
1481 Value *PCV = isValueEqualityComparison(PTI);
1485 SmallSetVector<BasicBlock *, 4> FailBlocks;
1487 for (
auto *Succ : FailBlocks) {
1493 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1507 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1508 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1509 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1528 if (
I->mayReadFromMemory())
1560 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1568 if (J->getParent() == BB)
1590 if (C1->isMustTailCall() != C2->isMustTailCall())
1593 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1599 if (CB1->cannotMerge() || CB1->isConvergent())
1602 if (CB2->cannotMerge() || CB2->isConvergent())
1617 if (!I1->hasDbgRecords())
1619 using CurrentAndEndIt =
1620 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1626 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1627 return Pair.first == Pair.second;
1633 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1639 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1641 if (!
Other->hasDbgRecords())
1644 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1651 while (
none_of(Itrs, atEnd)) {
1652 bool HoistDVRs = allIdentical(Itrs);
1653 for (CurrentAndEndIt &Pair : Itrs) {
1667 if (I1->isIdenticalToWhenDefined(I2,
true))
1672 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1673 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1674 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1676 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1677 return I1->getOperand(0) == I2->
getOperand(1) &&
1743 auto &Context = BI->
getParent()->getContext();
1748 Value *Mask =
nullptr;
1749 Value *MaskFalse =
nullptr;
1750 Value *MaskTrue =
nullptr;
1751 if (Invert.has_value()) {
1752 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1753 Mask = Builder.CreateBitCast(
1758 MaskFalse = Builder.CreateBitCast(
1760 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1762 auto PeekThroughBitcasts = [](
Value *V) {
1764 V = BitCast->getOperand(0);
1767 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1769 if (!Invert.has_value())
1770 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1775 auto *Op0 =
I->getOperand(0);
1776 CallInst *MaskedLoadStore =
nullptr;
1779 auto *Ty =
I->getType();
1781 Value *PassThru =
nullptr;
1782 if (Invert.has_value())
1783 for (
User *U :
I->users()) {
1785 PassThru = Builder.CreateBitCast(
1789 Sel && Ins->getParent() == BB) {
1794 Builder.SetInsertPoint(Ins);
1797 MaskedLoadStore = Builder.CreateMaskedLoad(
1799 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1802 I->replaceAllUsesWith(NewLoadStore);
1805 auto *StoredVal = Builder.CreateBitCast(
1807 MaskedLoadStore = Builder.CreateMaskedStore(
1818 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1820 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1824 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1825 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1828 I->eraseFromParent();
1835 bool IsStore =
false;
1858bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1859 bool AllInstsEqOnly) {
1888 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1894 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1897 if (AllInstsEqOnly) {
1903 bool AllSame =
none_of(Succs, [&Succs](BasicBlock *Succ) {
1906 return !
Term->isSameOperationAs(Term0) ||
1913 LockstepReverseIterator<true> LRI(Succs);
1914 while (LRI.isValid()) {
1916 if (
any_of(*LRI, [I0](Instruction *
I) {
1931 unsigned NumSkipped = 0;
1934 if (SuccIterPairs.
size() > 2) {
1937 if (SuccIterPairs.
size() < 2)
1944 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1945 auto &BB1ItrPair = *SuccIterPairBegin++;
1946 auto OtherSuccIterPairRange =
1952 bool AllInstsAreIdentical =
true;
1953 bool HasTerminator =
I1->isTerminator();
1954 for (
auto &SuccIter : OtherSuccIterRange) {
1958 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1959 AllInstsAreIdentical =
false;
1962 SmallVector<Instruction *, 8> OtherInsts;
1963 for (
auto &SuccIter : OtherSuccIterRange)
1968 if (HasTerminator) {
1972 if (NumSkipped || !AllInstsAreIdentical) {
1977 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1981 if (AllInstsAreIdentical) {
1982 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1983 AllInstsAreIdentical =
1985 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1987 unsigned SkipFlagsBB2 = Pair.second;
1997 if (AllInstsAreIdentical) {
2007 for (
auto &SuccIter : OtherSuccIterRange) {
2015 assert(
Success &&
"We should not be trying to hoist callbases "
2016 "with non-intersectable attributes");
2028 NumHoistCommonCode += SuccIterPairs.
size();
2030 NumHoistCommonInstrs += SuccIterPairs.
size();
2039 for (
auto &SuccIterPair : SuccIterPairs) {
2048bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2049 Instruction *TI, Instruction *I1,
2050 SmallVectorImpl<Instruction *> &OtherSuccTIs) {
2059 auto *I2 = *OtherSuccTIs.
begin();
2079 for (PHINode &PN : Succ->
phis()) {
2080 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2081 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2082 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2102 if (!
NT->getType()->isVoidTy()) {
2103 I1->replaceAllUsesWith(NT);
2104 for (Instruction *OtherSuccTI : OtherSuccTIs)
2105 OtherSuccTI->replaceAllUsesWith(NT);
2109 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2115 for (
auto *OtherSuccTI : OtherSuccTIs)
2116 Locs.
push_back(OtherSuccTI->getDebugLoc());
2128 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2130 for (PHINode &PN : Succ->
phis()) {
2131 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2132 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2138 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2148 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2149 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2150 PN.setIncomingValue(i, SI);
2161 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2166 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2179 if (
I->isIntDivRem())
2194 std::optional<unsigned> NumUses;
2195 for (
auto *
I : Insts) {
2198 I->getType()->isTokenTy())
2203 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2211 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2215 NumUses =
I->getNumUses();
2216 else if (NumUses !=
I->getNumUses())
2222 for (
auto *
I : Insts) {
2236 for (
const Use &U : I0->
uses()) {
2237 auto It = PHIOperands.find(&U);
2238 if (It == PHIOperands.end())
2241 if (!
equal(Insts, It->second))
2253 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2254 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2255 if (HaveIndirectCalls) {
2256 if (!AllCallsAreIndirect)
2260 Value *Callee =
nullptr;
2264 Callee = CurrCallee;
2265 else if (Callee != CurrCallee)
2271 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2277 if (!
all_of(Insts, SameAsI0)) {
2283 for (
auto *
I : Insts)
2284 Ops.push_back(
I->getOperand(OI));
2294 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2299 for (
auto *BB : Blocks) {
2301 I =
I->getPrevNode();
2326 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2329 PN->insertBefore(BBEnd->begin());
2330 for (
auto *
I : Insts)
2331 PN->addIncoming(
I->getOperand(O),
I->getParent());
2340 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2343 for (
auto *
I : Insts)
2357 assert(
Success &&
"We should not be trying to sink callbases "
2358 "with non-intersectable attributes");
2369 PN->replaceAllUsesWith(I0);
2370 PN->eraseFromParent();
2374 for (
auto *
I : Insts) {
2379 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2380 I->replaceAllUsesWith(I0);
2381 I->eraseFromParent();
2431 bool HaveNonUnconditionalPredecessors =
false;
2434 if (PredBr && PredBr->isUnconditional())
2437 HaveNonUnconditionalPredecessors =
true;
2439 if (UnconditionalPreds.
size() < 2)
2452 for (
const Use &U : PN.incoming_values())
2453 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2454 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2456 Ops.push_back(*IncomingVals[Pred]);
2464 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2477 if (!followedByDeoptOrUnreachable) {
2479 auto IsMemOperand = [](
Use &U) {
2492 unsigned NumPHIInsts = 0;
2493 for (
Use &U : (*LRI)[0]->operands()) {
2494 auto It = PHIOperands.
find(&U);
2495 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2496 return InstructionsToSink.contains(V);
2503 if (IsMemOperand(U) &&
2504 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2511 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2512 return NumPHIInsts <= 1;
2529 while (Idx < ScanIdx) {
2530 if (!ProfitableToSinkInstruction(LRI)) {
2533 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2546 if (Idx < ScanIdx) {
2549 InstructionsToSink = InstructionsProfitableToSink;
2555 !ProfitableToSinkInstruction(LRI) &&
2556 "We already know that the last instruction is unprofitable to sink");
2564 for (
auto *
I : *LRI)
2565 InstructionsProfitableToSink.
erase(
I);
2566 if (!ProfitableToSinkInstruction(LRI)) {
2569 InstructionsToSink = InstructionsProfitableToSink;
2583 if (HaveNonUnconditionalPredecessors) {
2584 if (!followedByDeoptOrUnreachable) {
2592 bool Profitable =
false;
2593 while (Idx < ScanIdx) {
2627 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2629 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2637 NumSinkCommonInstrs++;
2641 ++NumSinkCommonCode;
2647struct CompatibleSets {
2648 using SetTy = SmallVector<InvokeInst *, 2>;
2654 SetTy &getCompatibleSet(InvokeInst *
II);
2656 void insert(InvokeInst *
II);
2659CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2664 for (CompatibleSets::SetTy &Set : Sets) {
2665 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2670 return Sets.emplace_back();
2673void CompatibleSets::insert(InvokeInst *
II) {
2674 getCompatibleSet(
II).emplace_back(
II);
2678 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2681 auto IsIllegalToMerge = [](InvokeInst *
II) {
2682 return II->cannotMerge() ||
II->isInlineAsm();
2684 if (
any_of(Invokes, IsIllegalToMerge))
2689 auto IsIndirectCall = [](InvokeInst *
II) {
return II->isIndirectCall(); };
2690 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2691 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2692 if (HaveIndirectCalls) {
2693 if (!AllCallsAreIndirect)
2698 for (InvokeInst *
II : Invokes) {
2699 Value *CurrCallee =
II->getCalledOperand();
2700 assert(CurrCallee &&
"There is always a called operand.");
2703 else if (Callee != CurrCallee)
2710 auto HasNormalDest = [](InvokeInst *
II) {
2713 if (
any_of(Invokes, HasNormalDest)) {
2716 if (!
all_of(Invokes, HasNormalDest))
2721 for (InvokeInst *
II : Invokes) {
2723 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2725 NormalBB = CurrNormalBB;
2726 else if (NormalBB != CurrNormalBB)
2734 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2743 for (InvokeInst *
II : Invokes) {
2745 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2747 UnwindBB = CurrUnwindBB;
2749 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2756 Invokes.front()->getUnwindDest(),
2757 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2762 const InvokeInst *II0 = Invokes.front();
2763 for (
auto *
II : Invokes.drop_front())
2768 auto IsIllegalToMergeArguments = [](
auto Ops) {
2769 Use &U0 = std::get<0>(
Ops);
2770 Use &U1 = std::get<1>(
Ops);
2776 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2777 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2778 IsIllegalToMergeArguments))
2790 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2796 bool HasNormalDest =
2801 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2805 II0->
getParent()->getIterator()->getNextNode();
2810 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2814 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2816 if (!HasNormalDest) {
2820 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2828 return MergedInvoke;
2842 SuccBBOfMergedInvoke});
2852 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2858 if (!IsIndirectCall)
2865 return II->getOperand(U.getOperandNo()) != U.get();
2884 Invokes.
front()->getParent());
2892 if (!MergedDebugLoc)
2893 MergedDebugLoc =
II->getDebugLoc();
2901 OrigSuccBB->removePredecessor(
II->getParent());
2907 assert(
Success &&
"Merged invokes with incompatible attributes");
2910 II->replaceAllUsesWith(MergedInvoke);
2911 II->eraseFromParent();
2915 ++NumInvokeSetsFormed;
2951 CompatibleSets Grouper;
2961 if (Invokes.
size() < 2)
2973class EphemeralValueTracker {
2974 SmallPtrSet<const Instruction *, 32> EphValues;
2976 bool isEphemeral(
const Instruction *
I) {
2979 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2980 all_of(
I->users(), [&](
const User *U) {
2981 return EphValues.count(cast<Instruction>(U));
2986 bool track(
const Instruction *
I) {
2987 if (isEphemeral(
I)) {
3038 unsigned MaxNumInstToLookAt = 9;
3042 if (!MaxNumInstToLookAt)
3044 --MaxNumInstToLookAt;
3054 if (
SI->getPointerOperand() == StorePtr &&
3055 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3058 return SI->getValueOperand();
3063 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3064 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3066 bool ExplicitlyDereferenceableOnly;
3071 (!ExplicitlyDereferenceableOnly ||
3073 LI->getDataLayout()))) {
3089 unsigned &SpeculatedInstructions,
3097 bool HaveRewritablePHIs =
false;
3099 Value *OrigV = PN.getIncomingValueForBlock(BB);
3100 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3107 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3116 HaveRewritablePHIs =
true;
3119 if (!OrigCE && !ThenCE)
3126 if (OrigCost + ThenCost > MaxCost)
3133 ++SpeculatedInstructions;
3134 if (SpeculatedInstructions > 1)
3138 return HaveRewritablePHIs;
3142 std::optional<bool> Invert,
3146 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3153 if (!Invert.has_value())
3156 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3160 return BIEndProb < Likely;
3200bool SimplifyCFGOpt::speculativelyExecuteBB(BranchInst *BI,
3201 BasicBlock *ThenBB) {
3217 bool Invert =
false;
3232 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3234 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3236 unsigned SpeculatedInstructions = 0;
3237 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3238 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3239 Value *SpeculatedStoreValue =
nullptr;
3240 StoreInst *SpeculatedStore =
nullptr;
3241 EphemeralValueTracker EphTracker;
3256 if (EphTracker.track(&
I))
3261 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3263 SpeculatedConditionalLoadsStores.
size() <
3267 if (IsSafeCheapLoadStore)
3268 SpeculatedConditionalLoadsStores.
push_back(&
I);
3270 ++SpeculatedInstructions;
3272 if (SpeculatedInstructions > 1)
3276 if (!IsSafeCheapLoadStore &&
3279 (SpeculatedStoreValue =
3282 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3288 if (!SpeculatedStore && SpeculatedStoreValue)
3294 for (Use &
Op :
I.operands()) {
3299 ++SinkCandidateUseCounts[OpI];
3306 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3307 if (Inst->hasNUses(
Count)) {
3308 ++SpeculatedInstructions;
3309 if (SpeculatedInstructions > 1)
3316 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3319 SpeculatedInstructions,
Cost,
TTI);
3320 if (!Convert ||
Cost > Budget)
3324 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3328 if (SpeculatedStoreValue) {
3332 Value *FalseV = SpeculatedStoreValue;
3336 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3366 for (DbgVariableRecord *DbgAssign :
3369 DbgAssign->replaceVariableLocationOp(OrigV, S);
3379 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3382 I.dropUBImplyingAttrsAndMetadata();
3385 if (EphTracker.contains(&
I)) {
3387 I.eraseFromParent();
3393 for (
auto &It : *ThenBB)
3398 !DVR || !DVR->isDbgAssign())
3399 It.dropOneDbgRecord(&DR);
3401 std::prev(ThenBB->end()));
3403 if (!SpeculatedConditionalLoadsStores.
empty())
3409 for (PHINode &PN : EndBB->
phis()) {
3410 unsigned OrigI = PN.getBasicBlockIndex(BB);
3411 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3412 Value *OrigV = PN.getIncomingValue(OrigI);
3413 Value *ThenV = PN.getIncomingValue(ThenI);
3422 Value *TrueV = ThenV, *FalseV = OrigV;
3426 PN.setIncomingValue(OrigI, V);
3427 PN.setIncomingValue(ThenI, V);
3431 for (Instruction *
I : SpeculatedPseudoProbes)
3432 I->eraseFromParent();
3445 if (!ReachesNonLocalUses.
insert(BB).second)
3460 EphemeralValueTracker EphTracker;
3467 if (CI->cannotDuplicate() || CI->isConvergent())
3480 for (
User *U :
I.users()) {
3483 if (UsedInBB == BB) {
3487 NonLocalUseBlocks.
insert(UsedInBB);
3501 if (
I &&
I->getParent() == To)
3517static std::optional<bool>
3538 KnownValues[CB].
insert(Pred);
3542 if (KnownValues.
empty())
3567 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3570 for (
const auto &Pair : KnownValues) {
3587 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3592 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3595 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3603 EdgeBB->setName(RealDest->
getName() +
".critedge");
3604 EdgeBB->moveBefore(RealDest);
3614 TranslateMap[
Cond] = CB;
3627 N->insertInto(EdgeBB, InsertPt);
3630 N->setName(BBI->getName() +
".c");
3641 if (!BBI->use_empty())
3642 TranslateMap[&*BBI] = V;
3643 if (!
N->mayHaveSideEffects()) {
3644 N->eraseFromParent();
3649 if (!BBI->use_empty())
3650 TranslateMap[&*BBI] =
N;
3656 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3657 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3658 SrcDbgCursor = std::next(BBI);
3660 N->cloneDebugInfoFrom(&*BBI);
3669 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3670 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3671 InsertPt->cloneDebugInfoFrom(BI);
3692 return std::nullopt;
3698bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(BranchInst *BI) {
3705 std::optional<bool>
Result;
3706 bool EverChanged =
false;
3712 }
while (Result == std::nullopt);
3721 bool SpeculateUnpredictables) {
3743 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3746 "Will have either one or two blocks to speculate.");
3753 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3754 if (!IsUnpredictable) {
3757 (TWeight + FWeight) != 0) {
3762 if (IfBlocks.
size() == 1) {
3764 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3765 if (BIBBProb >= Likely)
3768 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3777 if (IfCondPhiInst->getParent() == BB)
3785 unsigned NumPhis = 0;
3798 if (SpeculateUnpredictables && IsUnpredictable)
3799 Budget +=
TTI.getBranchMispredictPenalty();
3812 AggressiveInsts, Cost, Budget,
TTI, AC,
3813 ZeroCostInstructions) ||
3815 AggressiveInsts, Cost, Budget,
TTI, AC,
3816 ZeroCostInstructions))
3828 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3839 auto IsBinOpOrAnd = [](
Value *V) {
3856 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3869 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3871 <<
" F: " << IfFalse->
getName() <<
"\n");
3888 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3893 PN->eraseFromParent();
3899 Builder.CreateBr(BB);
3920 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3921 if (
Opc == Instruction::And)
3922 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3923 if (
Opc == Instruction::Or)
3924 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3936 bool PredHasWeights =
3938 bool SuccHasWeights =
3940 if (PredHasWeights || SuccHasWeights) {
3941 if (!PredHasWeights)
3942 PredTrueWeight = PredFalseWeight = 1;
3943 if (!SuccHasWeights)
3944 SuccTrueWeight = SuccFalseWeight = 1;
3954static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3958 "Both blocks must end with a conditional branches.");
3960 "PredBB must be a predecessor of BB.");
3968 (PTWeight + PFWeight) != 0) {
3971 Likely =
TTI->getPredictableBranchThreshold();
3976 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3977 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3981 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3984 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3985 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3991 return std::nullopt;
4004 bool InvertPredCond;
4005 std::tie(CommonSucc,
Opc, InvertPredCond) =
4008 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4015 {LLVMContext::MD_annotation});
4018 if (InvertPredCond) {
4031 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4034 SuccTrueWeight, SuccFalseWeight)) {
4040 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4045 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4046 PredTrueWeight * SuccFalseWeight);
4052 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4053 PredFalseWeight * SuccTrueWeight);
4055 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4097 if (!MDWeights.
empty()) {
4098 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4103 ++NumFoldBranchToCommonDest;
4110 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4111 return U->getType()->isVectorTy();
4121 unsigned BonusInstThreshold) {
4135 Cond->getParent() != BB || !
Cond->hasOneUse())
4156 bool InvertPredCond;
4158 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4190 unsigned NumBonusInsts = 0;
4191 bool SawVectorOp =
false;
4192 const unsigned PredCount = Preds.
size();
4209 NumBonusInsts += PredCount;
4217 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4220 return PN->getIncomingBlock(U) == BB;
4221 return UI->
getParent() == BB &&
I.comesBefore(UI);
4225 if (!
all_of(
I.uses(), IsBCSSAUse))
4229 BonusInstThreshold *
4245 for (
auto *BB : {BB1, BB2}) {
4261 Value *AlternativeV =
nullptr) {
4287 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4288 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4296 if (!AlternativeV &&
4302 PHI->addIncoming(V, BB);
4312 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4321 if (!PStore || !QStore)
4342 if (
I.mayReadOrWriteMemory())
4344 for (
auto &
I : *QFB)
4345 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4348 for (
auto &
I : *QTB)
4349 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4353 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4369 if (
I.isTerminator())
4387 "When we run out of budget we will eagerly return from within the "
4388 "per-instruction loop.");
4392 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4394 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4395 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4431 InvertPCond ^= (PStore->
getParent() != PTB);
4432 InvertQCond ^= (QStore->
getParent() != QTB);
4453 {CombinedWeights[0], CombinedWeights[1]},
4517 bool InvertPCond =
false, InvertQCond =
false;
4523 if (QFB == PostBB) {
4542 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4545 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4553 for (
auto *BB : {PTB, PFB}) {
4558 PStoreAddresses.
insert(
SI->getPointerOperand());
4560 for (
auto *BB : {QTB, QFB}) {
4565 QStoreAddresses.
insert(
SI->getPointerOperand());
4571 auto &CommonAddresses = PStoreAddresses;
4574 for (
auto *Address : CommonAddresses)
4577 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4595 !BI->
getParent()->getSinglePredecessor())
4597 if (!IfFalseBB->
phis().empty())
4607 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4710 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4712 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4716 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4719 if (CommonDestProb >= Likely)
4729 unsigned NumPhis = 0;
4751 if (OtherDest == BB) {
4759 OtherDest = InfLoopBlock;
4771 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4775 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4779 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4794 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4795 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4798 SuccTrueWeight, SuccFalseWeight);
4800 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4801 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4802 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4803 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4807 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4808 PredOther * SuccCommon,
4809 PredOther * SuccOther};
4817 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4836 Value *BIV = PN.getIncomingValueForBlock(BB);
4837 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4838 Value *PBIV = PN.getIncomingValue(PBBIdx);
4842 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4843 PN.setIncomingValue(PBBIdx, NV);
4847 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4848 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4868bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4870 BasicBlock *FalseBB,
4871 uint32_t TrueWeight,
4872 uint32_t FalseWeight) {
4879 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4881 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4884 for (BasicBlock *Succ :
successors(OldTerm)) {
4886 if (Succ == KeepEdge1)
4887 KeepEdge1 =
nullptr;
4888 else if (Succ == KeepEdge2)
4889 KeepEdge2 =
nullptr;
4894 if (Succ != TrueBB && Succ != FalseBB)
4895 RemovedSuccessors.
insert(Succ);
4903 if (!KeepEdge1 && !KeepEdge2) {
4904 if (TrueBB == FalseBB) {
4915 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4935 SmallVector<DominatorTree::UpdateType, 2> Updates;
4937 for (
auto *RemovedSuccessor : RemovedSuccessors)
4938 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4949bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4954 if (!TrueVal || !FalseVal)
4959 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4960 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4963 uint32_t TrueWeight = 0, FalseWeight = 0;
4964 SmallVector<uint64_t, 8> Weights;
4968 if (Weights.
size() == 1 +
SI->getNumCases()) {
4970 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4972 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4977 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4986bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5000 SmallVector<uint32_t> SelectBranchWeights(2);
5004 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5005 SelectBranchWeights[0],
5006 SelectBranchWeights[1]);
5026bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5030 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5076bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5095 ConstantInt *NewCaseVal;
5103 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5109 SelectTrueVal = Builder.
getTrue();
5110 SelectFalseVal = Builder.
getFalse();
5113 SelectCond =
Select->getCondition();
5115 if (SelectCond != ICI)
5117 SelectTrueVal =
Select->getTrueValue();
5118 SelectFalseVal =
Select->getFalseValue();
5123 if (
SI->getCondition() != IcmpCond)
5129 if (
SI->getDefaultDest() != BB) {
5130 ConstantInt *VVal =
SI->findCaseDest(BB);
5131 assert(VVal &&
"Should have a unique destination value");
5139 return requestResimplify();
5145 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5147 if (Predicate == ICmpInst::ICMP_EQ)
5155 return requestResimplify();
5162 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5168 Value *DefaultCst = SelectFalseVal;
5169 Value *NewCst = SelectTrueVal;
5177 Select->replaceAllUsesWith(DefaultCst);
5178 Select->eraseFromParent();
5184 SmallVector<DominatorTree::UpdateType, 2> Updates;
5191 SwitchInstProfUpdateWrapper SIW(*SI);
5192 auto W0 = SIW.getSuccessorWeight(0);
5195 NewW = ((uint64_t(*W0) + 1) >> 1);
5196 SIW.setSuccessorWeight(0, *NewW);
5198 SIW.addCase(NewCaseVal, NewBB, NewW);
5200 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5209 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5218bool SimplifyCFGOpt::simplifyBranchOnICmpChain(BranchInst *BI,
5220 const DataLayout &
DL) {
5230 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5232 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5233 Value *CompVal = ConstantCompare.CompValue;
5234 unsigned UsedICmps = ConstantCompare.UsedICmps;
5235 Value *ExtraCase = ConstantCompare.Extra;
5236 bool TrueWhenEqual = ConstantCompare.IsEq;
5253 if (ExtraCase && Values.
size() < 2)
5256 SmallVector<uint32_t> BranchWeights;
5263 if (!TrueWhenEqual) {
5266 std::swap(BranchWeights[0], BranchWeights[1]);
5272 <<
" cases into SWITCH. BB is:\n"
5275 SmallVector<DominatorTree::UpdateType, 2> Updates;
5282 nullptr,
"switch.early.test");
5293 AssumptionCache *AC =
Options.AC;
5299 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5306 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5312 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5313 <<
"\nEXTRABB = " << *BB);
5321 "Should not end up here with unstable pointers");
5323 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5328 if (Values.
front()->getValue() - Values.
back()->getValue() ==
5329 Values.
size() - 1) {
5331 Values.
back()->getValue(), Values.
front()->getValue() + 1);
5333 ICmpInst::Predicate Pred;
5351 SmallVector<uint32_t> NewWeights(Values.
size() + 1);
5352 NewWeights[0] = BranchWeights[1];
5355 V = BranchWeights[0] / Values.
size();
5360 for (ConstantInt *Val : Values)
5361 New->addCase(Val, EdgeBB);
5369 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5379 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5383bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5385 return simplifyCommonResume(RI);
5389 return simplifySingleResume(RI);
5402 switch (IntrinsicID) {
5403 case Intrinsic::dbg_declare:
5404 case Intrinsic::dbg_value:
5405 case Intrinsic::dbg_label:
5406 case Intrinsic::lifetime_end:
5416bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5425 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5429 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5431 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5432 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5436 if (IncomingBB->getUniqueSuccessor() != BB)
5441 if (IncomingValue != LandingPad)
5445 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5446 TrivialUnwindBlocks.
insert(IncomingBB);
5450 if (TrivialUnwindBlocks.
empty())
5454 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5458 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5461 for (BasicBlock *Pred :
5472 TrivialBB->getTerminator()->eraseFromParent();
5473 new UnreachableInst(RI->
getContext(), TrivialBB);
5475 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5482 return !TrivialUnwindBlocks.empty();
5486bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5490 "Resume must unwind the exception that caused control to here");
5546 int Idx = DestPN.getBasicBlockIndex(BB);
5560 Value *SrcVal = DestPN.getIncomingValue(Idx);
5563 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5567 DestPN.addIncoming(
Incoming, Pred);
5594 std::vector<DominatorTree::UpdateType> Updates;
5598 if (UnwindDest ==
nullptr) {
5639 if (!SuccessorCleanupPad)
5648 SuccessorCleanupPad->eraseFromParent();
5657bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5674bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5706 BBI->dropDbgRecords();
5710 BBI->eraseFromParent();
5716 if (&BB->
front() != UI)
5719 std::vector<DominatorTree::UpdateType> Updates;
5722 for (BasicBlock *Predecessor : Preds) {
5729 [BB](
auto *
Successor) { return Successor == BB; })) {
5737 "The destinations are guaranteed to be different here.");
5738 CallInst *Assumption;
5754 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5756 SwitchInstProfUpdateWrapper SU(*SI);
5757 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5758 if (i->getCaseSuccessor() != BB) {
5763 i = SU.removeCase(i);
5768 if (DTU &&
SI->getDefaultDest() != BB)
5769 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5771 if (
II->getUnwindDest() == BB) {
5777 if (!CI->doesNotThrow())
5778 CI->setDoesNotThrow();
5782 if (CSI->getUnwindDest() == BB) {
5793 E = CSI->handler_end();
5796 CSI->removeHandler(
I);
5803 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5804 if (CSI->getNumHandlers() == 0) {
5805 if (CSI->hasUnwindDest()) {
5809 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5810 Updates.push_back({DominatorTree::Insert,
5811 PredecessorOfPredecessor,
5812 CSI->getUnwindDest()});
5813 Updates.push_back({DominatorTree::Delete,
5814 PredecessorOfPredecessor, Predecessor});
5817 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5824 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5825 for (BasicBlock *EHPred : EHPreds)
5829 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5830 CSI->eraseFromParent();
5835 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5836 "Expected to always have an unwind to BB.");
5838 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5866static std::optional<ContiguousCasesResult>
5873 const APInt &Min = Cases.
back()->getValue();
5874 const APInt &Max = Cases.
front()->getValue();
5876 size_t ContiguousOffset = Cases.
size() - 1;
5877 if (
Offset == ContiguousOffset) {
5895 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
5896 return L->getValue() != R->getValue() + 1;
5898 if (It == Cases.
end())
5899 return std::nullopt;
5900 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5901 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5905 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5908 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5916 return std::nullopt;
5921 bool RemoveOrigDefaultBlock =
true) {
5923 auto *BB = Switch->getParent();
5924 auto *OrigDefaultBlock = Switch->getDefaultDest();
5925 if (RemoveOrigDefaultBlock)
5926 OrigDefaultBlock->removePredecessor(BB);
5930 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5932 Switch->setDefaultDest(&*NewDefaultBlock);
5936 if (RemoveOrigDefaultBlock &&
5946bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5948 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5950 bool HasDefault = !
SI->defaultDestUnreachable();
5952 auto *BB =
SI->getParent();
5954 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5959 for (
auto Case :
SI->cases()) {
5963 if (Dest == DestA) {
5969 if (Dest == DestB) {
5979 "Single-destination switch should have been folded.");
5981 assert(DestB !=
SI->getDefaultDest());
5982 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5986 std::optional<ContiguousCasesResult> ContiguousCases;
5989 if (!HasDefault && CasesA.
size() == 1)
5990 ContiguousCases = ContiguousCasesResult{
5998 else if (CasesB.
size() == 1)
5999 ContiguousCases = ContiguousCasesResult{
6008 else if (!HasDefault)
6012 if (!ContiguousCases)
6016 if (!ContiguousCases)
6019 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6025 Max->getValue() - Min->getValue() + 1);
6028 assert(
Max->getValue() == Min->getValue());
6033 else if (NumCases->
isNullValue() && !Cases->empty()) {
6037 if (!
Offset->isNullValue())
6045 SmallVector<uint64_t, 8> Weights;
6047 if (Weights.
size() == 1 +
SI->getNumCases()) {
6048 uint64_t TrueWeight = 0;
6049 uint64_t FalseWeight = 0;
6050 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6051 if (
SI->getSuccessor(
I) == Dest)
6052 TrueWeight += Weights[
I];
6054 FalseWeight += Weights[
I];
6056 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6067 unsigned PreviousEdges = Cases->size();
6068 if (Dest ==
SI->getDefaultDest())
6070 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6071 PHI.removeIncomingValue(
SI->getParent());
6074 unsigned PreviousEdges = OtherCases->size();
6075 if (OtherDest ==
SI->getDefaultDest())
6077 unsigned E = PreviousEdges - 1;
6081 for (
unsigned I = 0;
I !=
E; ++
I)
6082 PHI.removeIncomingValue(
SI->getParent());
6090 auto *UnreachableDefault =
SI->getDefaultDest();
6093 SI->eraseFromParent();
6095 if (!HasDefault && DTU)
6096 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
6114 unsigned MaxSignificantBitsInCond =
6121 for (
const auto &Case :
SI->cases()) {
6122 auto *
Successor = Case.getCaseSuccessor();
6133 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6139 }
else if (IsKnownValuesValid)
6140 KnownValues.
erase(CaseC);
6147 bool HasDefault = !
SI->defaultDestUnreachable();
6148 const unsigned NumUnknownBits =
6151 if (HasDefault && DeadCases.
empty()) {
6157 if (NumUnknownBits < 64 ) {
6158 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6159 if (
SI->getNumCases() == AllNumCases) {
6166 if (
SI->getNumCases() == AllNumCases - 1) {
6167 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6174 for (
const auto &Case :
SI->cases())
6175 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6177 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6179 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6189 if (DeadCases.
empty())
6195 assert(CaseI !=
SI->case_default() &&
6196 "Case was not found. Probably mistake in DeadCases forming.");
6198 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6203 std::vector<DominatorTree::UpdateType> Updates;
6204 for (
auto *
Successor : UniqueSuccessors)
6205 if (NumPerSuccessorCases[
Successor] == 0)
6226 if (!Branch || !Branch->isUnconditional())
6232 int Idx =
PHI.getBasicBlockIndex(BB);
6233 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6235 Value *InValue =
PHI.getIncomingValue(Idx);
6236 if (InValue != CaseValue)
6252 ForwardingNodesMap ForwardingNodes;
6255 for (
const auto &Case :
SI->cases()) {
6257 BasicBlock *CaseDest = Case.getCaseSuccessor();
6276 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6277 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6278 count(Phi.blocks(), SwitchBlock) == 1) {
6279 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6287 ForwardingNodes[Phi].push_back(PhiIdx);
6290 for (
auto &ForwardingNode : ForwardingNodes) {
6291 PHINode *Phi = ForwardingNode.first;
6297 for (
int Index : Indexes)
6298 Phi->setIncomingValue(Index,
SI->getCondition());
6308 if (
C->isThreadDependent())
6310 if (
C->isDLLImportDependent())
6326 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6353 if (
A->isAllOnesValue())
6355 if (
A->isNullValue())
6361 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6386 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6388 if (
I.isTerminator()) {
6390 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6393 CaseDest =
I.getSuccessor(0);
6400 for (
auto &
Use :
I.uses()) {
6403 if (
I->getParent() == CaseDest)
6406 if (Phi->getIncomingBlock(
Use) == CaseDest)
6419 *CommonDest = CaseDest;
6421 if (CaseDest != *CommonDest)
6426 int Idx =
PHI.getBasicBlockIndex(Pred);
6439 Res.push_back(std::make_pair(&
PHI, ConstVal));
6442 return Res.
size() > 0;
6448 SwitchCaseResultVectorTy &UniqueResults,
6450 for (
auto &
I : UniqueResults) {
6451 if (
I.first == Result) {
6452 I.second.push_back(CaseVal);
6453 return I.second.size();
6456 UniqueResults.push_back(
6467 SwitchCaseResultVectorTy &UniqueResults,
6471 uintptr_t MaxUniqueResults) {
6472 for (
const auto &
I :
SI->cases()) {
6486 const size_t NumCasesForResult =
6494 if (UniqueResults.size() > MaxUniqueResults)
6510 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6512 return DefaultResult ||
SI->defaultDestUnreachable();
6533 const bool HasBranchWeights =
6536 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6537 ResultVector[1].second.size() == 1) {
6538 ConstantInt *FirstCase = ResultVector[0].second[0];
6539 ConstantInt *SecondCase = ResultVector[1].second[0];
6540 Value *SelectValue = ResultVector[1].first;
6541 if (DefaultResult) {
6542 Value *ValueCompare =
6543 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6544 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6545 DefaultResult,
"switch.select");
6547 SI && HasBranchWeights) {
6554 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6558 Value *ValueCompare =
6559 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6560 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6561 SelectValue,
"switch.select");
6567 size_t FirstCasePos = (Condition !=
nullptr);
6568 size_t SecondCasePos = FirstCasePos + 1;
6569 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6571 {BranchWeights[FirstCasePos],
6572 DefaultCase + BranchWeights[SecondCasePos]},
6579 if (ResultVector.size() == 1 && DefaultResult) {
6581 unsigned CaseCount = CaseValues.
size();
6594 for (
auto *Case : CaseValues) {
6595 if (Case->getValue().slt(MinCaseVal->
getValue()))
6597 AndMask &= Case->getValue();
6607 if (FreeBits ==
Log2_32(CaseCount)) {
6608 Value *
And = Builder.CreateAnd(Condition, AndMask);
6609 Value *Cmp = Builder.CreateICmpEQ(
6612 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6628 for (
auto *Case : CaseValues)
6629 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6635 Condition = Builder.CreateSub(Condition, MinCaseVal);
6636 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6637 Value *Cmp = Builder.CreateICmpEQ(
6640 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6653 if (CaseValues.
size() == 2) {
6654 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6655 "switch.selectcmp.case1");
6656 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6657 "switch.selectcmp.case2");
6658 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6660 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6680 std::vector<DominatorTree::UpdateType> Updates;
6687 Builder.CreateBr(DestBB);
6691 PHI->removeIncomingValueIf(
6692 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6693 PHI->addIncoming(SelectValue, SelectBB);
6696 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6702 if (DTU && RemovedSuccessors.
insert(Succ).second)
6705 SI->eraseFromParent();
6720 SwitchCaseResultVectorTy UniqueResults;
6726 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6727 Builder.SetInsertPoint(
SI);
6730 [[maybe_unused]]
auto HasWeights =
6735 (BranchWeights.
size() >=
6736 UniqueResults.size() + (DefaultResult !=
nullptr)));
6739 Builder,
DL, BranchWeights);
6751class SwitchReplacement {
6758 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6759 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName);
6768 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6775 bool isLookupTable();
6812 ConstantInt *BitMap =
nullptr;
6813 IntegerType *BitMapElementTy =
nullptr;
6816 ConstantInt *LinearOffset =
nullptr;
6817 ConstantInt *LinearMultiplier =
nullptr;
6818 bool LinearMapValWrapped =
false;
6826SwitchReplacement::SwitchReplacement(
6828 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6829 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName)
6830 : DefaultValue(DefaultValue) {
6831 assert(Values.size() &&
"Can't build lookup table without values!");
6832 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6835 SingleValue = Values.begin()->second;
6837 ValueType = Values.begin()->second->getType();
6841 for (
const auto &[CaseVal, CaseRes] : Values) {
6844 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6845 TableContents[Idx] = CaseRes;
6852 if (Values.size() < TableSize) {
6854 "Need a default value to fill the lookup table holes.");
6857 if (!TableContents[
I])
6858 TableContents[
I] = DefaultValue;
6864 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6865 SingleValue =
nullptr;
6871 Kind = SingleValueKind;
6878 bool LinearMappingPossible =
true;
6883 bool NonMonotonic =
false;
6884 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6901 LinearMappingPossible =
false;
6906 APInt Dist = Val - PrevVal;
6909 }
else if (Dist != DistToPrev) {
6910 LinearMappingPossible =
false;
6918 if (LinearMappingPossible) {
6920 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6921 APInt M = LinearMultiplier->getValue();
6922 bool MayWrap =
true;
6923 if (
isIntN(M.getBitWidth(), TableSize - 1))
6924 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6925 LinearMapValWrapped = NonMonotonic || MayWrap;
6926 Kind = LinearMapKind;
6932 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6934 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6936 TableInt <<=
IT->getBitWidth();
6940 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6943 BitMap = ConstantInt::get(M.getContext(), TableInt);
6944 BitMapElementTy =
IT;
6953 Kind = LookupTableKind;
6959 case SingleValueKind:
6961 case LinearMapKind: {
6965 false,
"switch.idx.cast");
6966 if (!LinearMultiplier->
isOne())
6967 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6969 !LinearMapValWrapped);
6971 if (!LinearOffset->
isZero())
6974 !LinearMapValWrapped);
6991 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
6992 "switch.shiftamt",
true,
true);
6995 Value *DownShifted =
6996 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6998 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7000 case LookupTableKind: {
7003 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7004 true, GlobalVariable::PrivateLinkage,
7005 Initializer,
"switch.table." +
Func->getName());
7006 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7009 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
7010 Type *IndexTy =
DL.getIndexType(Table->getType());
7013 if (
Index->getType() != IndexTy) {
7014 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7018 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7021 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7024 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7030bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7032 Type *ElementType) {
7040 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7042 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7048 if (
TTI.isTypeLegal(Ty))
7063 DL.fitsInLegalInteger(
IT->getBitWidth());
7066Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7068bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7070bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7081 return NumCases * 100 >= CaseRange * MinDensity;
7102 if (
SI->getNumCases() > TableSize)
7105 bool AllTablesFitInRegister =
true;
7106 bool HasIllegalType =
false;
7107 for (
const auto &Ty : ResultTypes) {
7112 AllTablesFitInRegister =
7113 AllTablesFitInRegister &&
7114 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7119 if (HasIllegalType && !AllTablesFitInRegister)
7124 if (AllTablesFitInRegister)
7141 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7144 return all_of(ResultTypes, [&](
const auto &ResultType) {
7145 return SwitchReplacement::wouldFitInRegister(
7173 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
7195 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7200 for (
auto ValuePair : Values) {
7203 if (!CaseConst || CaseConst == DefaultConst ||
7204 (CaseConst != TrueConst && CaseConst != FalseConst))
7218 if (DefaultConst == FalseConst) {
7221 ++NumTableCmpReuses;
7224 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7225 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7228 ++NumTableCmpReuses;
7238 bool ConvertSwitchToLookupTable) {
7239 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7253 if (
SI->getNumCases() < 3)
7275 MinCaseVal = CaseVal;
7277 MaxCaseVal = CaseVal;
7294 It->second.push_back(std::make_pair(CaseVal,
Value));
7302 bool HasDefaultResults =
7304 DefaultResultsList,
DL,
TTI);
7305 for (
const auto &
I : DefaultResultsList) {
7308 DefaultResults[
PHI] = Result;
7312 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7315 if (UseSwitchConditionAsTableIndex) {
7317 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7322 TableIndexOffset = MinCaseVal;
7329 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7331 bool TableHasHoles = (NumResults < TableSize);
7336 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7344 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7347 if (
SI->getNumCases() < 4)
7349 if (!
DL.fitsInLegalInteger(TableSize))
7358 if (UseSwitchConditionAsTableIndex) {
7359 TableIndex =
SI->getCondition();
7360 if (HasDefaultResults) {
7372 all_of(ResultTypes, [&](
const auto &ResultType) {
7373 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7378 TableSize = std::max(UpperBound, TableSize);
7381 DefaultIsReachable =
false;
7389 const auto &ResultList = ResultLists[
PHI];
7391 Type *ResultType = ResultList.begin()->second->getType();
7396 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7398 PhiToReplacementMap.
insert({
PHI, Replacement});
7401 bool AnyLookupTables =
any_of(
7402 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7403 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7404 [](
auto &KV) {
return KV.second.isBitMap(); });
7412 if (AnyLookupTables &&
7413 (!
TTI.shouldBuildLookupTables() ||
7419 if (!ConvertSwitchToLookupTable &&
7420 (AnyLookupTables || AnyBitMaps || NeedMask))
7423 Builder.SetInsertPoint(
SI);
7426 if (!UseSwitchConditionAsTableIndex) {
7429 bool MayWrap =
true;
7430 if (!DefaultIsReachable) {
7435 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7436 "switch.tableidx",
false,
7440 std::vector<DominatorTree::UpdateType> Updates;
7446 assert(MaxTableSize >= TableSize &&
7447 "It is impossible for a switch to have more entries than the max "
7448 "representable value of its input integer type's size.");
7453 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7458 Builder.SetInsertPoint(
SI);
7459 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7460 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7461 Builder.CreateBr(LookupBB);
7467 Value *Cmp = Builder.CreateICmpULT(
7468 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7470 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7471 CondBranch = RangeCheckBranch;
7477 Builder.SetInsertPoint(LookupBB);
7483 MaskBB->
setName(
"switch.hole_check");
7490 APInt MaskInt(TableSizePowOf2, 0);
7491 APInt One(TableSizePowOf2, 1);
7493 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7494 for (
const auto &Result : ResultList) {
7497 MaskInt |= One << Idx;
7499 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7506 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7507 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7508 Value *LoBit = Builder.CreateTrunc(
7510 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7515 Builder.SetInsertPoint(LookupBB);
7519 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7522 SI->getDefaultDest()->removePredecessor(BB,
7529 const ResultListTy &ResultList = ResultLists[
PHI];
7530 auto Replacement = PhiToReplacementMap.
at(
PHI);
7531 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7534 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7537 for (
auto *
User :
PHI->users()) {
7539 Replacement.getDefaultValue(), ResultList);
7543 PHI->addIncoming(Result, LookupBB);
7546 Builder.CreateBr(CommonDest);
7558 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7561 if (Succ ==
SI->getDefaultDest()) {
7562 if (HasBranchWeights)
7563 ToDefaultWeight += BranchWeights[
I];
7567 if (DTU && RemovedSuccessors.
insert(Succ).second)
7569 if (HasBranchWeights)
7570 ToLookupWeight += BranchWeights[
I];
7572 SI->eraseFromParent();
7573 if (HasBranchWeights)
7580 ++NumLookupTablesHoles;
7596 if (CondTy->getIntegerBitWidth() > 64 ||
7597 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7601 if (
SI->getNumCases() < 4)
7609 for (
const auto &
C :
SI->cases())
7610 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7618 int64_t
Base = Values[0];
7619 for (
auto &V : Values)
7632 unsigned Shift = 64;
7633 for (
auto &V : Values)
7637 for (
auto &V : Values)
7638 V = (int64_t)((
uint64_t)V >> Shift);
7655 Builder.SetInsertPoint(
SI);
7657 Builder.CreateSub(
SI->getCondition(), ConstantInt::get(Ty,
Base));
7658 Value *Rot = Builder.CreateIntrinsic(
7659 Ty, Intrinsic::fshl,
7660 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7661 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7663 for (
auto Case :
SI->cases()) {
7664 auto *Orig = Case.getCaseValue();
7665 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7710 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
7711 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
7727 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
7730 return !Updates.
empty();
7760 Value *Condition =
SI->getCondition();
7764 if (CondTy->getIntegerBitWidth() > 64 ||
7765 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7777 if (
SI->getNumCases() < 4)
7782 for (
const auto &Case :
SI->cases()) {
7783 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7797 Builder.SetInsertPoint(
SI);
7799 if (!
SI->defaultDestUnreachable()) {
7802 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
7803 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
7805 auto *OrigBB =
SI->getParent();
7806 auto *DefaultCaseBB =
SI->getDefaultDest();
7808 auto It = OrigBB->getTerminator()->getIterator();
7813 if (HasWeights &&
any_of(Weights, [](
const auto &V) {
return V != 0; })) {
7821 NewWeights[1] = Weights[0] / 2;
7822 NewWeights[0] = OrigDenominator - NewWeights[1];
7834 Weights[0] = NewWeights[1];
7835 uint64_t CasesDenominator = OrigDenominator - Weights[0];
7837 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
7843 It->eraseFromParent();
7851 for (
auto &Case :
SI->cases()) {
7852 auto *OrigValue = Case.getCaseValue();
7853 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7854 OrigValue->getValue().countr_zero()));
7858 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7861 SI->setCondition(ConditionTrailingZeros);
7871 if (!Cmp || !Cmp->hasOneUse())
7882 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7885 if (
SI->getNumCases() == 2) {
7892 Succ =
SI->getDefaultDest();
7893 SuccWeight = Weights[0];
7895 for (
auto &Case :
SI->cases()) {
7896 std::optional<int64_t> Val =
7900 if (!Missing.erase(*Val))
7905 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7908 assert(Missing.size() == 1 &&
"Should have one case left");
7909 Res = *Missing.begin();
7910 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7912 Unreachable =
SI->getDefaultDest();
7914 for (
auto &Case :
SI->cases()) {
7915 BasicBlock *NewSucc = Case.getCaseSuccessor();
7916 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7919 OtherSuccWeight += Weight;
7922 SuccWeight = Weight;
7923 }
else if (Succ == NewSucc) {
7929 for (
auto &Case :
SI->cases()) {
7930 std::optional<int64_t> Val =
7932 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7934 if (Case.getCaseSuccessor() == Succ) {
7956 if (Cmp->isSigned())
7959 MDNode *NewWeights =
nullptr;
7965 Builder.SetInsertPoint(
SI->getIterator());
7966 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
7967 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
7968 SI->getMetadata(LLVMContext::MD_unpredictable));
7972 SI->eraseFromParent();
7973 Cmp->eraseFromParent();
7974 if (DTU && Unreachable)
8005 "Only supporting unconditional branches for now");
8007 "Expected unconditional branches to have one successor");
8008 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
8029 if (LHS == EKey || RHS == EKey || LHS == TKey || RHS == TKey)
8045 "Only supporting unconditional branches for now");
8052 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8053 if (PredIVs[
A] != PredIVs[
B])
8061bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *
SI,
8075 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
8080 if (BB->
size() != 1)
8090 if (!Seen.
insert(BB).second) {
8091 auto It = BBToSuccessorIndexes.
find(BB);
8092 if (It != BBToSuccessorIndexes.
end())
8093 It->second.emplace_back(
I);
8107 Cases.
emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs});
8108 BBToSuccessorIndexes[BB].emplace_back(
I);
8114 for (PHINode *Phi : Phis) {
8116 PhiPredIVs.
try_emplace(Phi,
Phi->getNumIncomingValues()).first->second;
8117 for (
auto &
IV :
Phi->incoming_values())
8118 IVs.insert({
Phi->getIncomingBlock(
IV),
IV.get()});
8129 DenseSet<const SwitchSuccWrapper *> ReplaceWith;
8134 bool MadeChange =
false;
8135 for (
auto &SSW : Cases) {
8142 Updates.
push_back({DominatorTree::Delete,
SI->getParent(), SSW.Dest});
8143 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
8144 for (
unsigned Idx : Successors)
8145 SI->setSuccessor(Idx, (*It)->Dest);
8156bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8159 if (isValueEqualityComparison(SI)) {
8163 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8164 return requestResimplify();
8168 if (simplifySwitchOnSelect(SI,
Select))
8169 return requestResimplify();
8174 if (foldValueComparisonIntoPredecessors(SI, Builder))
8175 return requestResimplify();
8181 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8182 return requestResimplify();
8186 return requestResimplify();
8189 return requestResimplify();
8192 return requestResimplify();
8195 return requestResimplify();
8200 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8202 Options.ConvertSwitchToLookupTable))
8203 return requestResimplify();
8206 return requestResimplify();
8209 return requestResimplify();
8212 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8213 return requestResimplify();
8215 if (simplifyDuplicateSwitchArms(SI, DTU))
8216 return requestResimplify();
8219 return requestResimplify();
8224bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8227 SmallVector<uint32_t> BranchWeights;
8231 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8232 if (HasBranchWeights)
8237 SmallPtrSet<Value *, 8> Succs;
8238 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8243 RemovedSuccs.
insert(Dest);
8253 std::vector<DominatorTree::UpdateType> Updates;
8254 Updates.reserve(RemovedSuccs.
size());
8255 for (
auto *RemovedSucc : RemovedSuccs)
8256 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8273 if (HasBranchWeights) {
8280 if (simplifyIndirectBrOnSelect(IBI, SI))
8281 return requestResimplify();
8317 if (BB == OtherPred)
8328 std::vector<DominatorTree::UpdateType> Updates;
8335 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8336 "unexpected successor");
8337 II->setUnwindDest(OtherPred);
8352 Builder.CreateUnreachable();
8361bool SimplifyCFGOpt::simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder) {
8362 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
8363 : simplifyCondBranch(
Branch, Builder);
8366bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
8378 bool NeedCanonicalLoop =
8392 if (
I->isTerminator() &&
8393 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8414 if (
Options.SpeculateBlocks &&
8417 return requestResimplify();
8425 if (!PPred || (PredPred && PredPred != PPred))
8462 if (!SuccBI || !SuccBI->isConditional())
8466 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8470 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8496 bool HasWeight =
false;
8501 BBTWeight = BBFWeight = 1;
8506 BB1TWeight = BB1FWeight = 1;
8511 BB2TWeight = BB2FWeight = 1;
8513 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8514 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8521bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder) {
8525 "Tautological conditional branch should have been eliminated already.");
8528 if (!
Options.SimplifyCondBranch ||
8533 if (isValueEqualityComparison(BI)) {
8538 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8539 return requestResimplify();
8545 if (foldValueComparisonIntoPredecessors(BI, Builder))
8546 return requestResimplify();
8549 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8550 return requestResimplify();
8555 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8568 return requestResimplify();
8574 if (
Options.SpeculateBlocks &&
8577 return requestResimplify();
8586 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8587 return requestResimplify();
8589 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8591 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8592 auto CanSpeculateConditionalLoadsStores = [&]() {
8594 for (Instruction &
I : *Succ) {
8595 if (
I.isTerminator()) {
8596 if (
I.getNumSuccessors() > 1)
8600 SpeculatedConditionalLoadsStores.
size() ==
8604 SpeculatedConditionalLoadsStores.
push_back(&
I);
8607 return !SpeculatedConditionalLoadsStores.
empty();
8610 if (CanSpeculateConditionalLoadsStores()) {
8612 std::nullopt,
nullptr);
8613 return requestResimplify();
8623 return requestResimplify();
8632 return requestResimplify();
8638 if (foldCondBranchOnValueKnownInPredecessor(BI))
8639 return requestResimplify();
8644 if (PBI != BI && PBI->isConditional())
8646 return requestResimplify();
8652 if (PBI != BI && PBI->isConditional())
8654 return requestResimplify();
8658 return requestResimplify();
8665 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8677 auto *Use = cast<Instruction>(U.getUser());
8679 switch (Use->getOpcode()) {
8682 case Instruction::GetElementPtr:
8683 case Instruction::Ret:
8684 case Instruction::BitCast:
8685 case Instruction::Load:
8686 case Instruction::Store:
8687 case Instruction::Call:
8688 case Instruction::CallBr:
8689 case Instruction::Invoke:
8690 case Instruction::UDiv:
8691 case Instruction::URem:
8695 case Instruction::SDiv:
8696 case Instruction::SRem:
8700 if (FindUse ==
I->use_end())
8702 auto &
Use = *FindUse;
8707 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8708 User->comesBefore(
I))
8722 if (
GEP->getPointerOperand() ==
I) {
8725 if (
GEP->getType()->isVectorTy())
8733 if (!
GEP->hasAllZeroIndices() &&
8734 (!
GEP->isInBounds() ||
8736 GEP->getPointerAddressSpace())))
8737 PtrValueMayBeModified =
true;
8743 bool HasNoUndefAttr =
8744 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8749 if (
C->isNullValue() && HasNoUndefAttr &&
8750 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8751 return !PtrValueMayBeModified;
8757 if (!LI->isVolatile())
8759 LI->getPointerAddressSpace());
8763 if (!
SI->isVolatile())
8765 SI->getPointerAddressSpace())) &&
8766 SI->getPointerOperand() ==
I;
8771 if (
I == Assume->getArgOperand(0))
8779 if (CB->getCalledOperand() ==
I)
8782 if (CB->isArgOperand(&
Use)) {
8783 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8786 CB->paramHasNonNullAttr(ArgIdx,
false))
8787 return !PtrValueMayBeModified;
8806 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8816 Builder.CreateUnreachable();
8823 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8825 Assumption = Builder.CreateAssumption(
Cond);
8840 Builder.SetInsertPoint(Unreachable);
8842 Builder.CreateUnreachable();
8843 for (
const auto &Case :
SI->cases())
8844 if (Case.getCaseSuccessor() == BB) {
8846 Case.setSuccessor(Unreachable);
8848 if (
SI->getDefaultDest() == BB) {
8850 SI->setDefaultDest(Unreachable);
8864bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8889 return requestResimplify();
8910 if (
Options.SpeculateBlocks &&
8917 Options.SpeculateUnpredictables))
8924 case Instruction::Br:
8927 case Instruction::Resume:
8930 case Instruction::CleanupRet:
8933 case Instruction::Switch:
8936 case Instruction::Unreachable:
8939 case Instruction::IndirectBr:
8947bool SimplifyCFGOpt::run(BasicBlock *BB) {
8957 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static Value * getCondition(Instruction *I)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
unsigned unsigned DefaultVal
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool isProfitableToSpeculate(const BranchInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static void hoistConditionalLoadsStores(BranchInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool tryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
LLVM_ABI CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
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 unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
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)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
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.
@ User
could "use" a pointer
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
LLVM_ABI BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
auto map_range(ContainerTy &&C, FuncTy F)
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr detail::StaticCastFunc< To > StaticCastTo
Function objects corresponding to the Cast types defined above.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< uint32_t, 2 > &B1, const SmallVector< uint32_t, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
void sort(IteratorTy Start, IteratorTy End)
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
FunctionAddr VTableAddr Count
auto succ_size(const MachineBasicBlock *BB)
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
static cl::opt< unsigned > MaxJumpThreadingLiveBlocks("max-jump-threading-live-blocks", cl::Hidden, cl::init(24), cl::desc("Limit number of blocks a define in a threaded block is allowed " "to be live in"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
LLVM_ABI bool foldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two cases of SI are equal depends on the contents of the BasicBlock and the incoming...
DenseMap< PHINode *, SmallDenseMap< BasicBlock *, Value *, 8 > > * PhiPredIVs
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const SwitchSuccWrapper * getEmptyKey()
static const SwitchSuccWrapper * getTombstoneKey()
static unsigned getHashValue(const SwitchSuccWrapper *SSW)
static bool isEqual(const SwitchSuccWrapper *LHS, const SwitchSuccWrapper *RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.