96#define DEBUG_TYPE "simplifycfg"
101 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
104 "Temporary development switch used to gradually uplift SimplifyCFG "
105 "into preserving DomTree,"));
114 "Control the amount of phi node folding to perform (default = 2)"));
118 cl::desc(
"Control the maximal total instruction cost that we are willing "
119 "to speculatively execute to fold a 2-entry PHI node into a "
120 "select (default = 4)"));
124 cl::desc(
"Hoist common instructions up to the parent block"));
128 cl::desc(
"Hoist loads if the target supports conditional faulting"));
132 cl::desc(
"Hoist stores if the target supports conditional faulting"));
136 cl::desc(
"Control the maximal conditional load/store that we are willing "
137 "to speculatively execute to eliminate conditional branch "
143 cl::desc(
"Allow reordering across at most this many "
144 "instructions when hoisting"));
148 cl::desc(
"Sink common instructions down to the end block"));
152 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
156 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
157 "precede - hoist multiple conditional stores into a single "
158 "predicated store"));
162 cl::desc(
"When merging conditional stores, do so even if the resultant "
163 "basic blocks are unlikely to be if-converted as a result"));
167 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
172 cl::desc(
"Limit maximum recursion depth when calculating costs of "
173 "speculatively executed instructions"));
178 cl::desc(
"Max size of a block which is still considered "
179 "small enough to thread through"));
185 cl::desc(
"Maximum cost of combining conditions when "
186 "folding branches"));
189 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
191 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
192 "to fold branch to common destination when vector operations are "
197 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
201 cl::desc(
"Limit cases to analyze when converting a switch to select"));
205 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
212STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
214 "Number of switch instructions turned into linear mapping");
216 "Number of switch instructions turned into lookup tables");
218 NumLookupTablesHoles,
219 "Number of switch instructions turned into lookup tables (holes checked)");
220STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
222 "Number of value comparisons folded into predecessor basic blocks");
224 "Number of branches folded into predecessor basic block");
227 "Number of common instruction 'blocks' hoisted up to the begin block");
229 "Number of common instructions hoisted up to the begin block");
231 "Number of common instruction 'blocks' sunk down to the end block");
233 "Number of common instructions sunk down to the end block");
234STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
236 "Number of invokes with empty resume blocks simplified into calls");
237STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
238STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
245using SwitchCaseResultVectorTy =
254struct ValueEqualityComparisonCase {
266 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
269class SimplifyCFGOpt {
270 const TargetTransformInfo &TTI;
272 const DataLayout &DL;
274 const SimplifyCFGOptions &Options;
277 Value *isValueEqualityComparison(Instruction *TI);
279 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
280 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
283 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
286 bool foldValueComparisonIntoPredecessors(Instruction *TI,
289 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
290 bool simplifySingleResume(ResumeInst *RI);
291 bool simplifyCommonResume(ResumeInst *RI);
292 bool simplifyCleanupReturn(CleanupReturnInst *RI);
293 bool simplifyUnreachable(UnreachableInst *UI);
294 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
295 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
296 bool simplifyIndirectBr(IndirectBrInst *IBI);
297 bool simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder);
298 bool simplifyUncondBranch(BranchInst *BI,
IRBuilder<> &Builder);
299 bool simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder);
300 bool foldCondBranchOnValueKnownInPredecessor(BranchInst *BI);
302 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
305 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
306 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
307 Instruction *TI, Instruction *I1,
308 SmallVectorImpl<Instruction *> &OtherSuccTIs);
309 bool speculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB);
310 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
311 BasicBlock *TrueBB, BasicBlock *FalseBB,
312 uint32_t TrueWeight, uint32_t FalseWeight);
313 bool simplifyBranchOnICmpChain(BranchInst *BI,
IRBuilder<> &Builder,
314 const DataLayout &DL);
315 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
316 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
317 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
320 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
322 const SimplifyCFGOptions &Opts)
323 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
324 assert((!DTU || !DTU->hasPostDomTree()) &&
325 "SimplifyCFG is not yet capable of maintaining validity of a "
326 "PostDomTree, so don't ask for it.");
329 bool simplifyOnce(BasicBlock *BB);
330 bool run(BasicBlock *BB);
333 bool requestResimplify() {
343isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
363 "Only for a pair of incoming blocks at the time!");
369 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
370 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
373 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
374 EquivalenceSet->contains(IV1))
397 if (!SI1Succs.
count(Succ))
403 FailBlocks->insert(Succ);
419 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
421 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
422 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
484 if (AggressiveInsts.
count(
I))
500 ZeroCostInstructions.
insert(OverflowInst);
502 }
else if (!ZeroCostInstructions.
contains(
I))
518 for (
Use &
Op :
I->operands())
520 TTI, AC, ZeroCostInstructions,
Depth + 1))
537 if (
DL.hasUnstableRepresentation(V->getType()))
546 return ConstantInt::get(IntPtrTy, 0);
551 if (CE->getOpcode() == Instruction::IntToPtr)
575struct ConstantComparesGatherer {
576 const DataLayout &DL;
579 Value *CompValue =
nullptr;
582 Value *Extra =
nullptr;
588 unsigned UsedICmps = 0;
594 bool IgnoreFirstMatch =
false;
595 bool MultipleMatches =
false;
598 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
600 if (CompValue || !MultipleMatches)
605 IgnoreFirstMatch =
true;
609 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
610 ConstantComparesGatherer &
611 operator=(
const ConstantComparesGatherer &) =
delete;
616 bool setValueOnce(
Value *NewVal) {
617 if (IgnoreFirstMatch) {
618 IgnoreFirstMatch =
false;
621 if (CompValue && CompValue != NewVal) {
622 MultipleMatches =
true;
636 bool matchInstruction(Instruction *
I,
bool isEQ) {
643 if (!setValueOnce(Val))
663 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
707 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
709 if (!setValueOnce(RHSVal))
714 ConstantInt::get(
C->getContext(),
715 C->getValue() | Mask));
730 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
732 if (!setValueOnce(RHSVal))
736 Vals.push_back(ConstantInt::get(
C->getContext(),
737 C->getValue() & ~Mask));
758 Value *CandidateVal =
I->getOperand(0);
761 CandidateVal = RHSVal;
776 if (!setValueOnce(CandidateVal))
781 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
792 void gather(
Value *V) {
801 SmallVector<Value *, 8> DFT{Op0, Op1};
802 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
804 while (!DFT.
empty()) {
811 if (Visited.
insert(Op1).second)
813 if (Visited.
insert(Op0).second)
820 if (matchInstruction(
I, IsEq))
847 if (BI->isConditional())
865 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
866 CV =
SI->getCondition();
868 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
873 if (Trunc->hasNoUnsignedWrap())
874 CV = Trunc->getOperand(0);
881 Value *
Ptr = PTII->getPointerOperand();
882 if (
DL.hasUnstableRepresentation(
Ptr->getType()))
884 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
893BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
894 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
896 Cases.reserve(
SI->getNumCases());
897 for (
auto Case :
SI->cases())
898 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
899 Case.getCaseSuccessor()));
900 return SI->getDefaultDest();
905 ICmpInst::Predicate Pred;
911 Pred = ICmpInst::ICMP_NE;
916 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
924 std::vector<ValueEqualityComparisonCase> &Cases) {
930 std::vector<ValueEqualityComparisonCase> &C2) {
931 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
934 if (V1->size() > V2->size())
939 if (V1->size() == 1) {
942 for (
const ValueEqualityComparisonCase &
VECC : *V2)
943 if (TheVal ==
VECC.Value)
950 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
951 while (i1 != e1 && i2 != e2) {
967bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
968 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
973 Value *ThisVal = isValueEqualityComparison(TI);
974 assert(ThisVal &&
"This isn't a value comparison!!");
975 if (ThisVal != PredVal)
982 std::vector<ValueEqualityComparisonCase> PredCases;
984 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
988 std::vector<ValueEqualityComparisonCase> ThisCases;
989 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1004 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1010 ThisCases[0].Dest->removePredecessor(PredDef);
1013 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1020 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1027 SmallPtrSet<Constant *, 16> DeadCases;
1028 for (
const ValueEqualityComparisonCase &Case : PredCases)
1029 DeadCases.
insert(Case.Value);
1032 <<
"Through successor TI: " << *TI);
1034 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1037 auto *
Successor = i->getCaseSuccessor();
1040 if (DeadCases.
count(i->getCaseValue())) {
1049 std::vector<DominatorTree::UpdateType> Updates;
1050 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1052 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1062 ConstantInt *TIV =
nullptr;
1064 for (
const auto &[
Value, Dest] : PredCases)
1070 assert(TIV &&
"No edge from pred to succ?");
1075 for (
const auto &[
Value, Dest] : ThisCases)
1083 TheRealDest = ThisDef;
1085 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1090 if (Succ != CheckEdge) {
1091 if (Succ != TheRealDest)
1092 RemovedSuccs.
insert(Succ);
1095 CheckEdge =
nullptr;
1102 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1107 SmallVector<DominatorTree::UpdateType, 2> Updates;
1109 for (
auto *RemovedSucc : RemovedSuccs)
1110 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1121struct ConstantIntOrdering {
1122 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1123 return LHS->getValue().ult(
RHS->getValue());
1135 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1144 assert(MD &&
"Invalid branch-weight metadata");
1169 if (BonusInst.isTerminator())
1199 NewBonusInst->
takeName(&BonusInst);
1200 BonusInst.setName(NewBonusInst->
getName() +
".old");
1201 VMap[&BonusInst] = NewBonusInst;
1210 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1211 "If the user is not a PHI node, then it should be in the same "
1212 "block as, and come after, the original bonus instruction.");
1216 if (PN->getIncomingBlock(U) == BB)
1220 assert(PN->getIncomingBlock(U) == PredBlock &&
1221 "Not in block-closed SSA form?");
1222 U.set(NewBonusInst);
1232 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1233 PredDL.isSameSourceLocation(
DL)) {
1240bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1248 std::vector<ValueEqualityComparisonCase> BBCases;
1249 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1251 std::vector<ValueEqualityComparisonCase> PredCases;
1252 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1257 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1260 SmallVector<uint64_t, 8> Weights;
1264 if (PredHasWeights) {
1267 if (Weights.
size() != 1 + PredCases.size())
1268 PredHasWeights = SuccHasWeights =
false;
1269 }
else if (SuccHasWeights)
1273 Weights.
assign(1 + PredCases.size(), 1);
1275 SmallVector<uint64_t, 8> SuccWeights;
1276 if (SuccHasWeights) {
1279 if (SuccWeights.
size() != 1 + BBCases.size())
1280 PredHasWeights = SuccHasWeights =
false;
1281 }
else if (PredHasWeights)
1282 SuccWeights.
assign(1 + BBCases.size(), 1);
1284 if (PredDefault == BB) {
1287 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1288 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1289 if (PredCases[i].Dest != BB)
1290 PTIHandled.insert(PredCases[i].
Value);
1293 std::swap(PredCases[i], PredCases.back());
1295 if (PredHasWeights || SuccHasWeights) {
1297 Weights[0] += Weights[i + 1];
1302 PredCases.pop_back();
1308 if (PredDefault != BBDefault) {
1310 if (DTU && PredDefault != BB)
1311 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1312 PredDefault = BBDefault;
1313 ++NewSuccessors[BBDefault];
1316 unsigned CasesFromPred = Weights.
size();
1317 uint64_t ValidTotalSuccWeight = 0;
1318 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1319 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1320 PredCases.push_back(BBCases[i]);
1321 ++NewSuccessors[BBCases[i].Dest];
1322 if (SuccHasWeights || PredHasWeights) {
1326 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1327 ValidTotalSuccWeight += SuccWeights[i + 1];
1331 if (SuccHasWeights || PredHasWeights) {
1332 ValidTotalSuccWeight += SuccWeights[0];
1334 for (
unsigned i = 1; i < CasesFromPred; ++i)
1335 Weights[i] *= ValidTotalSuccWeight;
1337 Weights[0] *= SuccWeights[0];
1343 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1344 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1345 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1346 if (PredCases[i].Dest == BB) {
1347 PTIHandled.insert(PredCases[i].
Value);
1349 if (PredHasWeights || SuccHasWeights) {
1350 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1355 std::swap(PredCases[i], PredCases.back());
1356 PredCases.pop_back();
1363 for (
const ValueEqualityComparisonCase &Case : BBCases)
1364 if (PTIHandled.count(Case.Value)) {
1366 if (PredHasWeights || SuccHasWeights)
1367 Weights.
push_back(WeightsForHandled[Case.Value]);
1368 PredCases.push_back(Case);
1369 ++NewSuccessors[Case.Dest];
1370 PTIHandled.erase(Case.Value);
1375 for (ConstantInt *
I : PTIHandled) {
1376 if (PredHasWeights || SuccHasWeights)
1378 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1379 ++NewSuccessors[BBDefault];
1386 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1391 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1393 for (
auto I :
seq(NewSuccessor.second)) {
1397 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1398 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1405 "Should not end up here with unstable pointers");
1411 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1413 for (ValueEqualityComparisonCase &V : PredCases)
1416 if (PredHasWeights || SuccHasWeights)
1428 if (!InfLoopBlock) {
1436 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1443 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1445 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1450 ++NumFoldValueComparisonIntoPredecessors;
1458bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1461 Value *CV = isValueEqualityComparison(TI);
1462 assert(CV &&
"Not a comparison?");
1467 while (!Preds.empty()) {
1476 Value *PCV = isValueEqualityComparison(PTI);
1480 SmallSetVector<BasicBlock *, 4> FailBlocks;
1482 for (
auto *Succ : FailBlocks) {
1488 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1502 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1503 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1504 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1523 if (
I->mayReadFromMemory())
1555 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1563 if (J->getParent() == BB)
1585 if (C1->isMustTailCall() != C2->isMustTailCall())
1588 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1594 if (CB1->cannotMerge() || CB1->isConvergent())
1597 if (CB2->cannotMerge() || CB2->isConvergent())
1612 if (!I1->hasDbgRecords())
1614 using CurrentAndEndIt =
1615 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1621 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1622 return Pair.first == Pair.second;
1628 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1634 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1636 if (!
Other->hasDbgRecords())
1639 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1646 while (
none_of(Itrs, atEnd)) {
1647 bool HoistDVRs = allIdentical(Itrs);
1648 for (CurrentAndEndIt &Pair : Itrs) {
1662 if (I1->isIdenticalToWhenDefined(I2,
true))
1667 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1668 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1669 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1671 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1672 return I1->getOperand(0) == I2->
getOperand(1) &&
1738 auto &Context = BI->
getParent()->getContext();
1743 Value *Mask =
nullptr;
1744 Value *MaskFalse =
nullptr;
1745 Value *MaskTrue =
nullptr;
1746 if (Invert.has_value()) {
1747 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1748 Mask = Builder.CreateBitCast(
1753 MaskFalse = Builder.CreateBitCast(
1755 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1757 auto PeekThroughBitcasts = [](
Value *V) {
1759 V = BitCast->getOperand(0);
1762 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1764 if (!Invert.has_value())
1765 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1770 auto *Op0 =
I->getOperand(0);
1771 CallInst *MaskedLoadStore =
nullptr;
1774 auto *Ty =
I->getType();
1776 Value *PassThru =
nullptr;
1777 if (Invert.has_value())
1778 for (
User *U :
I->users()) {
1780 PassThru = Builder.CreateBitCast(
1784 Sel && Ins->getParent() == BB) {
1789 Builder.SetInsertPoint(Ins);
1792 MaskedLoadStore = Builder.CreateMaskedLoad(
1794 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1797 I->replaceAllUsesWith(NewLoadStore);
1800 auto *StoredVal = Builder.CreateBitCast(
1802 MaskedLoadStore = Builder.CreateMaskedStore(
1813 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1815 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1819 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1820 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1823 I->eraseFromParent();
1830 bool IsStore =
false;
1853bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1854 bool AllInstsEqOnly) {
1874 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1880 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1883 if (AllInstsEqOnly) {
1889 bool AllSame =
none_of(Succs, [&Succs](BasicBlock *Succ) {
1892 return !
Term->isSameOperationAs(Term0) ||
1899 LockstepReverseIterator<true> LRI(Succs);
1900 while (LRI.isValid()) {
1902 if (
any_of(*LRI, [I0](Instruction *
I) {
1917 unsigned NumSkipped = 0;
1920 if (SuccIterPairs.
size() > 2) {
1923 if (SuccIterPairs.
size() < 2)
1930 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1931 auto &BB1ItrPair = *SuccIterPairBegin++;
1932 auto OtherSuccIterPairRange =
1938 bool AllInstsAreIdentical =
true;
1939 bool HasTerminator =
I1->isTerminator();
1940 for (
auto &SuccIter : OtherSuccIterRange) {
1944 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1945 AllInstsAreIdentical =
false;
1948 SmallVector<Instruction *, 8> OtherInsts;
1949 for (
auto &SuccIter : OtherSuccIterRange)
1954 if (HasTerminator) {
1958 if (NumSkipped || !AllInstsAreIdentical) {
1963 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1967 if (AllInstsAreIdentical) {
1968 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1969 AllInstsAreIdentical =
1971 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1973 unsigned SkipFlagsBB2 = Pair.second;
1983 if (AllInstsAreIdentical) {
1993 for (
auto &SuccIter : OtherSuccIterRange) {
2001 assert(
Success &&
"We should not be trying to hoist callbases "
2002 "with non-intersectable attributes");
2014 NumHoistCommonCode += SuccIterPairs.
size();
2016 NumHoistCommonInstrs += SuccIterPairs.
size();
2025 for (
auto &SuccIterPair : SuccIterPairs) {
2034bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2035 Instruction *TI, Instruction *I1,
2036 SmallVectorImpl<Instruction *> &OtherSuccTIs) {
2045 auto *I2 = *OtherSuccTIs.
begin();
2065 for (PHINode &PN : Succ->
phis()) {
2066 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2067 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2068 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2088 if (!
NT->getType()->isVoidTy()) {
2089 I1->replaceAllUsesWith(NT);
2090 for (Instruction *OtherSuccTI : OtherSuccTIs)
2091 OtherSuccTI->replaceAllUsesWith(NT);
2095 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2101 for (
auto *OtherSuccTI : OtherSuccTIs)
2102 Locs.
push_back(OtherSuccTI->getDebugLoc());
2114 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2116 for (PHINode &PN : Succ->
phis()) {
2117 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2118 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2124 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2134 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2135 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2136 PN.setIncomingValue(i, SI);
2147 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2152 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2165 if (
I->isIntDivRem())
2180 std::optional<unsigned> NumUses;
2181 for (
auto *
I : Insts) {
2184 I->getType()->isTokenTy())
2189 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2197 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2201 NumUses =
I->getNumUses();
2202 else if (NumUses !=
I->getNumUses())
2208 for (
auto *
I : Insts) {
2222 for (
const Use &U : I0->
uses()) {
2223 auto It = PHIOperands.find(&U);
2224 if (It == PHIOperands.end())
2227 if (!
equal(Insts, It->second))
2239 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2240 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2241 if (HaveIndirectCalls) {
2242 if (!AllCallsAreIndirect)
2246 Value *Callee =
nullptr;
2250 Callee = CurrCallee;
2251 else if (Callee != CurrCallee)
2257 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2263 if (!
all_of(Insts, SameAsI0)) {
2269 for (
auto *
I : Insts)
2270 Ops.push_back(
I->getOperand(OI));
2280 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2285 for (
auto *BB : Blocks) {
2287 I =
I->getPrevNode();
2312 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2315 PN->insertBefore(BBEnd->begin());
2316 for (
auto *
I : Insts)
2317 PN->addIncoming(
I->getOperand(O),
I->getParent());
2326 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2329 for (
auto *
I : Insts)
2343 assert(
Success &&
"We should not be trying to sink callbases "
2344 "with non-intersectable attributes");
2355 PN->replaceAllUsesWith(I0);
2356 PN->eraseFromParent();
2360 for (
auto *
I : Insts) {
2365 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2366 I->replaceAllUsesWith(I0);
2367 I->eraseFromParent();
2417 bool HaveNonUnconditionalPredecessors =
false;
2420 if (PredBr && PredBr->isUnconditional())
2423 HaveNonUnconditionalPredecessors =
true;
2425 if (UnconditionalPreds.
size() < 2)
2438 for (
const Use &U : PN.incoming_values())
2439 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2440 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2442 Ops.push_back(*IncomingVals[Pred]);
2450 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2463 if (!followedByDeoptOrUnreachable) {
2465 auto IsMemOperand = [](
Use &U) {
2478 unsigned NumPHIInsts = 0;
2479 for (
Use &U : (*LRI)[0]->operands()) {
2480 auto It = PHIOperands.
find(&U);
2481 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2482 return InstructionsToSink.contains(V);
2489 if (IsMemOperand(U) &&
2490 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2497 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2498 return NumPHIInsts <= 1;
2515 while (Idx < ScanIdx) {
2516 if (!ProfitableToSinkInstruction(LRI)) {
2519 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2532 if (Idx < ScanIdx) {
2535 InstructionsToSink = InstructionsProfitableToSink;
2541 !ProfitableToSinkInstruction(LRI) &&
2542 "We already know that the last instruction is unprofitable to sink");
2550 for (
auto *
I : *LRI)
2551 InstructionsProfitableToSink.
erase(
I);
2552 if (!ProfitableToSinkInstruction(LRI)) {
2555 InstructionsToSink = InstructionsProfitableToSink;
2569 if (HaveNonUnconditionalPredecessors) {
2570 if (!followedByDeoptOrUnreachable) {
2578 bool Profitable =
false;
2579 while (Idx < ScanIdx) {
2613 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2615 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2623 NumSinkCommonInstrs++;
2627 ++NumSinkCommonCode;
2633struct CompatibleSets {
2634 using SetTy = SmallVector<InvokeInst *, 2>;
2640 SetTy &getCompatibleSet(InvokeInst *
II);
2642 void insert(InvokeInst *
II);
2645CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2650 for (CompatibleSets::SetTy &Set : Sets) {
2651 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2656 return Sets.emplace_back();
2659void CompatibleSets::insert(InvokeInst *
II) {
2660 getCompatibleSet(
II).emplace_back(
II);
2664 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2667 auto IsIllegalToMerge = [](InvokeInst *
II) {
2668 return II->cannotMerge() ||
II->isInlineAsm();
2670 if (
any_of(Invokes, IsIllegalToMerge))
2675 auto IsIndirectCall = [](InvokeInst *
II) {
return II->isIndirectCall(); };
2676 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2677 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2678 if (HaveIndirectCalls) {
2679 if (!AllCallsAreIndirect)
2684 for (InvokeInst *
II : Invokes) {
2685 Value *CurrCallee =
II->getCalledOperand();
2686 assert(CurrCallee &&
"There is always a called operand.");
2689 else if (Callee != CurrCallee)
2696 auto HasNormalDest = [](InvokeInst *
II) {
2699 if (
any_of(Invokes, HasNormalDest)) {
2702 if (!
all_of(Invokes, HasNormalDest))
2707 for (InvokeInst *
II : Invokes) {
2709 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2711 NormalBB = CurrNormalBB;
2712 else if (NormalBB != CurrNormalBB)
2720 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2729 for (InvokeInst *
II : Invokes) {
2731 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2733 UnwindBB = CurrUnwindBB;
2735 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2742 Invokes.front()->getUnwindDest(),
2743 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2748 const InvokeInst *II0 = Invokes.front();
2749 for (
auto *
II : Invokes.drop_front())
2754 auto IsIllegalToMergeArguments = [](
auto Ops) {
2755 Use &U0 = std::get<0>(
Ops);
2756 Use &U1 = std::get<1>(
Ops);
2762 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2763 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2764 IsIllegalToMergeArguments))
2776 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2782 bool HasNormalDest =
2787 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2791 II0->
getParent()->getIterator()->getNextNode();
2796 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2800 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2802 if (!HasNormalDest) {
2806 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2814 return MergedInvoke;
2828 SuccBBOfMergedInvoke});
2838 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2844 if (!IsIndirectCall)
2851 return II->getOperand(U.getOperandNo()) != U.get();
2870 Invokes.
front()->getParent());
2878 if (!MergedDebugLoc)
2879 MergedDebugLoc =
II->getDebugLoc();
2887 OrigSuccBB->removePredecessor(
II->getParent());
2893 assert(
Success &&
"Merged invokes with incompatible attributes");
2896 II->replaceAllUsesWith(MergedInvoke);
2897 II->eraseFromParent();
2901 ++NumInvokeSetsFormed;
2937 CompatibleSets Grouper;
2947 if (Invokes.
size() < 2)
2959class EphemeralValueTracker {
2960 SmallPtrSet<const Instruction *, 32> EphValues;
2962 bool isEphemeral(
const Instruction *
I) {
2965 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2966 all_of(
I->users(), [&](
const User *U) {
2967 return EphValues.count(cast<Instruction>(U));
2972 bool track(
const Instruction *
I) {
2973 if (isEphemeral(
I)) {
3024 unsigned MaxNumInstToLookAt = 9;
3028 if (!MaxNumInstToLookAt)
3030 --MaxNumInstToLookAt;
3040 if (
SI->getPointerOperand() == StorePtr &&
3041 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3044 return SI->getValueOperand();
3049 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3050 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3052 bool ExplicitlyDereferenceableOnly;
3057 (!ExplicitlyDereferenceableOnly ||
3059 LI->getDataLayout()))) {
3075 unsigned &SpeculatedInstructions,
3083 bool HaveRewritablePHIs =
false;
3085 Value *OrigV = PN.getIncomingValueForBlock(BB);
3086 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3093 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3102 HaveRewritablePHIs =
true;
3105 if (!OrigCE && !ThenCE)
3112 if (OrigCost + ThenCost > MaxCost)
3119 ++SpeculatedInstructions;
3120 if (SpeculatedInstructions > 1)
3124 return HaveRewritablePHIs;
3128 std::optional<bool> Invert,
3132 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3139 if (!Invert.has_value())
3142 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3146 return BIEndProb < Likely;
3186bool SimplifyCFGOpt::speculativelyExecuteBB(BranchInst *BI,
3187 BasicBlock *ThenBB) {
3203 bool Invert =
false;
3218 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3220 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3222 unsigned SpeculatedInstructions = 0;
3223 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3224 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3225 Value *SpeculatedStoreValue =
nullptr;
3226 StoreInst *SpeculatedStore =
nullptr;
3227 EphemeralValueTracker EphTracker;
3242 if (EphTracker.track(&
I))
3247 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3249 SpeculatedConditionalLoadsStores.
size() <
3253 if (IsSafeCheapLoadStore)
3254 SpeculatedConditionalLoadsStores.
push_back(&
I);
3256 ++SpeculatedInstructions;
3258 if (SpeculatedInstructions > 1)
3262 if (!IsSafeCheapLoadStore &&
3265 (SpeculatedStoreValue =
3268 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3274 if (!SpeculatedStore && SpeculatedStoreValue)
3280 for (Use &
Op :
I.operands()) {
3285 ++SinkCandidateUseCounts[OpI];
3292 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3293 if (Inst->hasNUses(
Count)) {
3294 ++SpeculatedInstructions;
3295 if (SpeculatedInstructions > 1)
3302 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3305 SpeculatedInstructions,
Cost,
TTI);
3306 if (!Convert ||
Cost > Budget)
3310 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3314 if (SpeculatedStoreValue) {
3318 Value *FalseV = SpeculatedStoreValue;
3322 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3352 for (DbgVariableRecord *DbgAssign :
3355 DbgAssign->replaceVariableLocationOp(OrigV, S);
3365 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3368 I.dropUBImplyingAttrsAndMetadata();
3371 if (EphTracker.contains(&
I)) {
3373 I.eraseFromParent();
3379 for (
auto &It : *ThenBB)
3384 !DVR || !DVR->isDbgAssign())
3385 It.dropOneDbgRecord(&DR);
3387 std::prev(ThenBB->end()));
3389 if (!SpeculatedConditionalLoadsStores.
empty())
3395 for (PHINode &PN : EndBB->
phis()) {
3396 unsigned OrigI = PN.getBasicBlockIndex(BB);
3397 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3398 Value *OrigV = PN.getIncomingValue(OrigI);
3399 Value *ThenV = PN.getIncomingValue(ThenI);
3408 Value *TrueV = ThenV, *FalseV = OrigV;
3412 PN.setIncomingValue(OrigI, V);
3413 PN.setIncomingValue(ThenI, V);
3417 for (Instruction *
I : SpeculatedPseudoProbes)
3418 I->eraseFromParent();
3431 if (!ReachesNonLocalUses.
insert(BB).second)
3446 EphemeralValueTracker EphTracker;
3453 if (CI->cannotDuplicate() || CI->isConvergent())
3466 for (
User *U :
I.users()) {
3469 if (UsedInBB == BB) {
3473 NonLocalUseBlocks.
insert(UsedInBB);
3487 if (
I &&
I->getParent() == To)
3503static std::optional<bool>
3524 KnownValues[CB].
insert(Pred);
3528 if (KnownValues.
empty())
3553 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3556 for (
const auto &Pair : KnownValues) {
3573 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3578 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3581 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3589 EdgeBB->setName(RealDest->
getName() +
".critedge");
3590 EdgeBB->moveBefore(RealDest);
3600 TranslateMap[
Cond] = CB;
3613 N->insertInto(EdgeBB, InsertPt);
3616 N->setName(BBI->getName() +
".c");
3627 if (!BBI->use_empty())
3628 TranslateMap[&*BBI] = V;
3629 if (!
N->mayHaveSideEffects()) {
3630 N->eraseFromParent();
3635 if (!BBI->use_empty())
3636 TranslateMap[&*BBI] =
N;
3642 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3643 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3644 SrcDbgCursor = std::next(BBI);
3646 N->cloneDebugInfoFrom(&*BBI);
3655 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3656 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3657 InsertPt->cloneDebugInfoFrom(BI);
3678 return std::nullopt;
3684bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(BranchInst *BI) {
3691 std::optional<bool>
Result;
3692 bool EverChanged =
false;
3698 }
while (Result == std::nullopt);
3707 bool SpeculateUnpredictables) {
3729 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3732 "Will have either one or two blocks to speculate.");
3739 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3740 if (!IsUnpredictable) {
3743 (TWeight + FWeight) != 0) {
3748 if (IfBlocks.
size() == 1) {
3750 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3751 if (BIBBProb >= Likely)
3754 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3763 if (IfCondPhiInst->getParent() == BB)
3771 unsigned NumPhis = 0;
3784 if (SpeculateUnpredictables && IsUnpredictable)
3785 Budget +=
TTI.getBranchMispredictPenalty();
3798 AggressiveInsts, Cost, Budget,
TTI, AC,
3799 ZeroCostInstructions) ||
3801 AggressiveInsts, Cost, Budget,
TTI, AC,
3802 ZeroCostInstructions))
3814 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3825 auto IsBinOpOrAnd = [](
Value *V) {
3842 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3855 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3857 <<
" F: " << IfFalse->
getName() <<
"\n");
3874 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3879 PN->eraseFromParent();
3885 Builder.CreateBr(BB);
3906 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
3907 if (
Opc == Instruction::And)
3908 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
3909 if (
Opc == Instruction::Or)
3910 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
3922 bool PredHasWeights =
3924 bool SuccHasWeights =
3926 if (PredHasWeights || SuccHasWeights) {
3927 if (!PredHasWeights)
3928 PredTrueWeight = PredFalseWeight = 1;
3929 if (!SuccHasWeights)
3930 SuccTrueWeight = SuccFalseWeight = 1;
3940static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3944 "Both blocks must end with a conditional branches.");
3946 "PredBB must be a predecessor of BB.");
3954 (PTWeight + PFWeight) != 0) {
3957 Likely =
TTI->getPredictableBranchThreshold();
3962 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3963 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3967 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3970 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3971 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3977 return std::nullopt;
3990 bool InvertPredCond;
3991 std::tie(CommonSucc,
Opc, InvertPredCond) =
3994 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4001 {LLVMContext::MD_annotation});
4004 if (InvertPredCond) {
4017 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4020 SuccTrueWeight, SuccFalseWeight)) {
4026 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4031 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4032 PredTrueWeight * SuccFalseWeight);
4038 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4039 PredFalseWeight * SuccTrueWeight);
4041 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4083 if (!MDWeights.
empty()) {
4084 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4089 ++NumFoldBranchToCommonDest;
4096 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4097 return U->getType()->isVectorTy();
4107 unsigned BonusInstThreshold) {
4121 Cond->getParent() != BB || !
Cond->hasOneUse())
4142 bool InvertPredCond;
4144 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4176 unsigned NumBonusInsts = 0;
4177 bool SawVectorOp =
false;
4178 const unsigned PredCount = Preds.
size();
4195 NumBonusInsts += PredCount;
4203 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4206 return PN->getIncomingBlock(U) == BB;
4207 return UI->
getParent() == BB &&
I.comesBefore(UI);
4211 if (!
all_of(
I.uses(), IsBCSSAUse))
4215 BonusInstThreshold *
4231 for (
auto *BB : {BB1, BB2}) {
4247 Value *AlternativeV =
nullptr) {
4273 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4274 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4282 if (!AlternativeV &&
4288 PHI->addIncoming(V, BB);
4298 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4307 if (!PStore || !QStore)
4328 if (
I.mayReadOrWriteMemory())
4330 for (
auto &
I : *QFB)
4331 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4334 for (
auto &
I : *QTB)
4335 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4339 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4355 if (
I.isTerminator())
4373 "When we run out of budget we will eagerly return from within the "
4374 "per-instruction loop.");
4378 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4380 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4381 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4417 InvertPCond ^= (PStore->
getParent() != PTB);
4418 InvertQCond ^= (QStore->
getParent() != QTB);
4439 {CombinedWeights[0], CombinedWeights[1]},
4503 bool InvertPCond =
false, InvertQCond =
false;
4509 if (QFB == PostBB) {
4528 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4531 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4539 for (
auto *BB : {PTB, PFB}) {
4544 PStoreAddresses.
insert(
SI->getPointerOperand());
4546 for (
auto *BB : {QTB, QFB}) {
4551 QStoreAddresses.
insert(
SI->getPointerOperand());
4557 auto &CommonAddresses = PStoreAddresses;
4560 for (
auto *Address : CommonAddresses)
4563 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4581 !BI->
getParent()->getSinglePredecessor())
4583 if (!IfFalseBB->
phis().empty())
4593 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4696 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4698 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4702 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4705 if (CommonDestProb >= Likely)
4715 unsigned NumPhis = 0;
4737 if (OtherDest == BB) {
4745 OtherDest = InfLoopBlock;
4757 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4761 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4765 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4780 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4781 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4784 SuccTrueWeight, SuccFalseWeight);
4786 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4787 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4788 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4789 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4793 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4794 PredOther * SuccCommon,
4795 PredOther * SuccOther};
4803 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4822 Value *BIV = PN.getIncomingValueForBlock(BB);
4823 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4824 Value *PBIV = PN.getIncomingValue(PBBIdx);
4828 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4829 PN.setIncomingValue(PBBIdx, NV);
4833 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4834 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4854bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4856 BasicBlock *FalseBB,
4857 uint32_t TrueWeight,
4858 uint32_t FalseWeight) {
4865 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4867 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
4870 for (BasicBlock *Succ :
successors(OldTerm)) {
4872 if (Succ == KeepEdge1)
4873 KeepEdge1 =
nullptr;
4874 else if (Succ == KeepEdge2)
4875 KeepEdge2 =
nullptr;
4880 if (Succ != TrueBB && Succ != FalseBB)
4881 RemovedSuccessors.
insert(Succ);
4889 if (!KeepEdge1 && !KeepEdge2) {
4890 if (TrueBB == FalseBB) {
4901 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4921 SmallVector<DominatorTree::UpdateType, 2> Updates;
4923 for (
auto *RemovedSuccessor : RemovedSuccessors)
4924 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4935bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
4940 if (!TrueVal || !FalseVal)
4945 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4946 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4949 uint32_t TrueWeight = 0, FalseWeight = 0;
4950 SmallVector<uint64_t, 8> Weights;
4954 if (Weights.
size() == 1 +
SI->getNumCases()) {
4956 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4958 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4963 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4972bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
4986 SmallVector<uint32_t> SelectBranchWeights(2);
4990 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
4991 SelectBranchWeights[0],
4992 SelectBranchWeights[1]);
5012bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5032 if (
SI->getCondition() != V)
5038 if (
SI->getDefaultDest() != BB) {
5039 ConstantInt *VVal =
SI->findCaseDest(BB);
5040 assert(VVal &&
"Should have a unique destination value");
5048 return requestResimplify();
5054 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5064 return requestResimplify();
5071 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5088 SmallVector<DominatorTree::UpdateType, 2> Updates;
5095 SwitchInstProfUpdateWrapper SIW(*SI);
5096 auto W0 = SIW.getSuccessorWeight(0);
5099 NewW = ((uint64_t(*W0) + 1) >> 1);
5100 SIW.setSuccessorWeight(0, *NewW);
5102 SIW.addCase(Cst, NewBB, NewW);
5104 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5113 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5122bool SimplifyCFGOpt::simplifyBranchOnICmpChain(BranchInst *BI,
5124 const DataLayout &
DL) {
5134 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5136 SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
5137 Value *CompVal = ConstantCompare.CompValue;
5138 unsigned UsedICmps = ConstantCompare.UsedICmps;
5139 Value *ExtraCase = ConstantCompare.Extra;
5140 bool TrueWhenEqual = ConstantCompare.IsEq;
5157 if (ExtraCase && Values.
size() < 2)
5160 SmallVector<uint32_t> BranchWeights;
5167 if (!TrueWhenEqual) {
5170 std::swap(BranchWeights[0], BranchWeights[1]);
5176 <<
" cases into SWITCH. BB is:\n"
5179 SmallVector<DominatorTree::UpdateType, 2> Updates;
5186 nullptr,
"switch.early.test");
5197 AssumptionCache *AC =
Options.AC;
5203 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5211 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5217 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5218 <<
"\nEXTRABB = " << *BB);
5226 "Should not end up here with unstable pointers");
5228 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5237 SmallVector<uint32_t> NewWeights(Values.
size() + 1);
5238 NewWeights[0] = BranchWeights[1];
5241 V = BranchWeights[0] / Values.
size();
5246 for (ConstantInt *Val : Values)
5247 New->addCase(Val, EdgeBB);
5255 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5264 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5268bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5270 return simplifyCommonResume(RI);
5274 return simplifySingleResume(RI);
5287 switch (IntrinsicID) {
5288 case Intrinsic::dbg_declare:
5289 case Intrinsic::dbg_value:
5290 case Intrinsic::dbg_label:
5291 case Intrinsic::lifetime_end:
5301bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5310 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5314 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5316 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5317 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5321 if (IncomingBB->getUniqueSuccessor() != BB)
5326 if (IncomingValue != LandingPad)
5330 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5331 TrivialUnwindBlocks.
insert(IncomingBB);
5335 if (TrivialUnwindBlocks.
empty())
5339 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5343 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5346 for (BasicBlock *Pred :
5357 TrivialBB->getTerminator()->eraseFromParent();
5358 new UnreachableInst(RI->
getContext(), TrivialBB);
5360 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5367 return !TrivialUnwindBlocks.empty();
5371bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5375 "Resume must unwind the exception that caused control to here");
5431 int Idx = DestPN.getBasicBlockIndex(BB);
5445 Value *SrcVal = DestPN.getIncomingValue(Idx);
5448 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5452 DestPN.addIncoming(
Incoming, Pred);
5479 std::vector<DominatorTree::UpdateType> Updates;
5483 if (UnwindDest ==
nullptr) {
5524 if (!SuccessorCleanupPad)
5533 SuccessorCleanupPad->eraseFromParent();
5542bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5559bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5591 BBI->dropDbgRecords();
5595 BBI->eraseFromParent();
5601 if (&BB->
front() != UI)
5604 std::vector<DominatorTree::UpdateType> Updates;
5607 for (BasicBlock *Predecessor : Preds) {
5614 [BB](
auto *
Successor) { return Successor == BB; })) {
5622 "The destinations are guaranteed to be different here.");
5623 CallInst *Assumption;
5639 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5641 SwitchInstProfUpdateWrapper SU(*SI);
5642 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5643 if (i->getCaseSuccessor() != BB) {
5648 i = SU.removeCase(i);
5653 if (DTU &&
SI->getDefaultDest() != BB)
5654 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5656 if (
II->getUnwindDest() == BB) {
5662 if (!CI->doesNotThrow())
5663 CI->setDoesNotThrow();
5667 if (CSI->getUnwindDest() == BB) {
5678 E = CSI->handler_end();
5681 CSI->removeHandler(
I);
5688 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5689 if (CSI->getNumHandlers() == 0) {
5690 if (CSI->hasUnwindDest()) {
5694 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5695 Updates.push_back({DominatorTree::Insert,
5696 PredecessorOfPredecessor,
5697 CSI->getUnwindDest()});
5698 Updates.push_back({DominatorTree::Delete,
5699 PredecessorOfPredecessor, Predecessor});
5702 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5709 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
5710 for (BasicBlock *EHPred : EHPreds)
5714 new UnreachableInst(CSI->getContext(), CSI->getIterator());
5715 CSI->eraseFromParent();
5720 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5721 "Expected to always have an unwind to BB.");
5723 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5751static std::optional<ContiguousCasesResult>
5758 const APInt &Min = Cases.
back()->getValue();
5759 const APInt &Max = Cases.
front()->getValue();
5761 size_t ContiguousOffset = Cases.
size() - 1;
5762 if (
Offset == ContiguousOffset) {
5780 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
5781 return L->getValue() != R->getValue() + 1;
5783 if (It == Cases.
end())
5784 return std::nullopt;
5785 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
5786 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
5790 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
5793 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
5801 return std::nullopt;
5806 bool RemoveOrigDefaultBlock =
true) {
5808 auto *BB = Switch->getParent();
5809 auto *OrigDefaultBlock = Switch->getDefaultDest();
5810 if (RemoveOrigDefaultBlock)
5811 OrigDefaultBlock->removePredecessor(BB);
5815 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5817 Switch->setDefaultDest(&*NewDefaultBlock);
5821 if (RemoveOrigDefaultBlock &&
5831bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
5833 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5835 bool HasDefault = !
SI->defaultDestUnreachable();
5837 auto *BB =
SI->getParent();
5839 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5844 for (
auto Case :
SI->cases()) {
5848 if (Dest == DestA) {
5854 if (Dest == DestB) {
5864 "Single-destination switch should have been folded.");
5866 assert(DestB !=
SI->getDefaultDest());
5867 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5871 std::optional<ContiguousCasesResult> ContiguousCases;
5874 if (!HasDefault && CasesA.
size() == 1)
5875 ContiguousCases = ContiguousCasesResult{
5883 else if (CasesB.
size() == 1)
5884 ContiguousCases = ContiguousCasesResult{
5893 else if (!HasDefault)
5897 if (!ContiguousCases)
5901 if (!ContiguousCases)
5904 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
5910 Max->getValue() - Min->getValue() + 1);
5913 assert(
Max->getValue() == Min->getValue());
5918 else if (NumCases->
isNullValue() && !Cases->empty()) {
5922 if (!
Offset->isNullValue())
5930 SmallVector<uint64_t, 8> Weights;
5932 if (Weights.
size() == 1 +
SI->getNumCases()) {
5933 uint64_t TrueWeight = 0;
5934 uint64_t FalseWeight = 0;
5935 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
5936 if (
SI->getSuccessor(
I) == Dest)
5937 TrueWeight += Weights[
I];
5939 FalseWeight += Weights[
I];
5941 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5951 for (
auto BBI = Dest->begin();
isa<PHINode>(BBI); ++BBI) {
5952 unsigned PreviousEdges = Cases->size();
5953 if (Dest ==
SI->getDefaultDest())
5955 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5958 for (
auto BBI = OtherDest->begin();
isa<PHINode>(BBI); ++BBI) {
5959 unsigned PreviousEdges = OtherCases->size();
5960 if (OtherDest ==
SI->getDefaultDest())
5962 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5971 auto *UnreachableDefault =
SI->getDefaultDest();
5974 SI->eraseFromParent();
5976 if (!HasDefault && DTU)
5977 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5993 unsigned MaxSignificantBitsInCond =
6000 for (
const auto &Case :
SI->cases()) {
6001 auto *
Successor = Case.getCaseSuccessor();
6008 const APInt &CaseVal = Case.getCaseValue()->getValue();
6011 DeadCases.
push_back(Case.getCaseValue());
6023 bool HasDefault = !
SI->defaultDestUnreachable();
6024 const unsigned NumUnknownBits =
6027 if (HasDefault && DeadCases.
empty() &&
6028 NumUnknownBits < 64 ) {
6029 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6030 if (
SI->getNumCases() == AllNumCases) {
6037 if (
SI->getNumCases() == AllNumCases - 1) {
6038 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6045 for (
const auto &Case :
SI->cases())
6046 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6057 if (DeadCases.
empty())
6063 assert(CaseI !=
SI->case_default() &&
6064 "Case was not found. Probably mistake in DeadCases forming.");
6066 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6071 std::vector<DominatorTree::UpdateType> Updates;
6072 for (
auto *
Successor : UniqueSuccessors)
6073 if (NumPerSuccessorCases[
Successor] == 0)
6094 if (!Branch || !Branch->isUnconditional())
6100 int Idx =
PHI.getBasicBlockIndex(BB);
6101 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6103 Value *InValue =
PHI.getIncomingValue(Idx);
6104 if (InValue != CaseValue)
6120 ForwardingNodesMap ForwardingNodes;
6123 for (
const auto &Case :
SI->cases()) {
6125 BasicBlock *CaseDest = Case.getCaseSuccessor();
6144 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6145 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6146 count(Phi.blocks(), SwitchBlock) == 1) {
6147 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6155 ForwardingNodes[Phi].push_back(PhiIdx);
6158 for (
auto &ForwardingNode : ForwardingNodes) {
6159 PHINode *Phi = ForwardingNode.first;
6165 for (
int Index : Indexes)
6166 Phi->setIncomingValue(Index,
SI->getCondition());
6176 if (
C->isThreadDependent())
6178 if (
C->isDLLImportDependent())
6194 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6221 if (
A->isAllOnesValue())
6223 if (
A->isNullValue())
6229 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6254 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6256 if (
I.isTerminator()) {
6258 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6261 CaseDest =
I.getSuccessor(0);
6268 for (
auto &
Use :
I.uses()) {
6271 if (
I->getParent() == CaseDest)
6274 if (Phi->getIncomingBlock(
Use) == CaseDest)
6287 *CommonDest = CaseDest;
6289 if (CaseDest != *CommonDest)
6294 int Idx =
PHI.getBasicBlockIndex(Pred);
6307 Res.push_back(std::make_pair(&
PHI, ConstVal));
6310 return Res.
size() > 0;
6316 SwitchCaseResultVectorTy &UniqueResults,
6318 for (
auto &
I : UniqueResults) {
6319 if (
I.first == Result) {
6320 I.second.push_back(CaseVal);
6321 return I.second.size();
6324 UniqueResults.push_back(
6335 SwitchCaseResultVectorTy &UniqueResults,
6339 uintptr_t MaxUniqueResults) {
6340 for (
const auto &
I :
SI->cases()) {
6354 const size_t NumCasesForResult =
6362 if (UniqueResults.size() > MaxUniqueResults)
6378 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6380 return DefaultResult ||
SI->defaultDestUnreachable();
6401 const bool HasBranchWeights =
6404 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6405 ResultVector[1].second.size() == 1) {
6406 ConstantInt *FirstCase = ResultVector[0].second[0];
6407 ConstantInt *SecondCase = ResultVector[1].second[0];
6408 Value *SelectValue = ResultVector[1].first;
6409 if (DefaultResult) {
6410 Value *ValueCompare =
6411 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6412 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6413 DefaultResult,
"switch.select");
6415 SI && HasBranchWeights) {
6422 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6426 Value *ValueCompare =
6427 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6428 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6429 SelectValue,
"switch.select");
6435 size_t FirstCasePos = (Condition !=
nullptr);
6436 size_t SecondCasePos = FirstCasePos + 1;
6437 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6439 {BranchWeights[FirstCasePos],
6440 DefaultCase + BranchWeights[SecondCasePos]},
6447 if (ResultVector.size() == 1 && DefaultResult) {
6449 unsigned CaseCount = CaseValues.
size();
6462 for (
auto *Case : CaseValues) {
6463 if (Case->getValue().slt(MinCaseVal->
getValue()))
6465 AndMask &= Case->getValue();
6475 if (FreeBits ==
Log2_32(CaseCount)) {
6476 Value *
And = Builder.CreateAnd(Condition, AndMask);
6477 Value *Cmp = Builder.CreateICmpEQ(
6480 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6496 for (
auto *Case : CaseValues)
6497 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6503 Condition = Builder.CreateSub(Condition, MinCaseVal);
6504 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6505 Value *Cmp = Builder.CreateICmpEQ(
6508 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6521 if (CaseValues.
size() == 2) {
6522 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6523 "switch.selectcmp.case1");
6524 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6525 "switch.selectcmp.case2");
6526 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6528 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6548 std::vector<DominatorTree::UpdateType> Updates;
6555 Builder.CreateBr(DestBB);
6559 PHI->removeIncomingValueIf(
6560 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6561 PHI->addIncoming(SelectValue, SelectBB);
6564 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6570 if (DTU && RemovedSuccessors.
insert(Succ).second)
6573 SI->eraseFromParent();
6588 SwitchCaseResultVectorTy UniqueResults;
6594 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6595 Builder.SetInsertPoint(
SI);
6598 [[maybe_unused]]
auto HasWeights =
6603 (BranchWeights.
size() >=
6604 UniqueResults.size() + (DefaultResult !=
nullptr)));
6607 Builder,
DL, BranchWeights);
6619class SwitchReplacement {
6626 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6627 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName);
6636 static bool wouldFitInRegister(
const DataLayout &
DL, uint64_t TableSize,
6643 bool isLookupTable();
6677 ConstantInt *BitMap =
nullptr;
6678 IntegerType *BitMapElementTy =
nullptr;
6681 ConstantInt *LinearOffset =
nullptr;
6682 ConstantInt *LinearMultiplier =
nullptr;
6683 bool LinearMapValWrapped =
false;
6691SwitchReplacement::SwitchReplacement(
6693 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
6694 Constant *DefaultValue,
const DataLayout &
DL,
const StringRef &FuncName)
6695 : DefaultValue(DefaultValue) {
6696 assert(Values.size() &&
"Can't build lookup table without values!");
6697 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6700 SingleValue = Values.begin()->second;
6702 ValueType = Values.begin()->second->getType();
6706 for (
const auto &[CaseVal, CaseRes] : Values) {
6709 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
6710 TableContents[Idx] = CaseRes;
6717 if (Values.size() < TableSize) {
6719 "Need a default value to fill the lookup table holes.");
6722 if (!TableContents[
I])
6723 TableContents[
I] = DefaultValue;
6729 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6730 SingleValue =
nullptr;
6736 Kind = SingleValueKind;
6743 bool LinearMappingPossible =
true;
6748 bool NonMonotonic =
false;
6749 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6766 LinearMappingPossible =
false;
6771 APInt Dist = Val - PrevVal;
6774 }
else if (Dist != DistToPrev) {
6775 LinearMappingPossible =
false;
6783 if (LinearMappingPossible) {
6785 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
6786 APInt M = LinearMultiplier->getValue();
6787 bool MayWrap =
true;
6788 if (
isIntN(M.getBitWidth(), TableSize - 1))
6789 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
6790 LinearMapValWrapped = NonMonotonic || MayWrap;
6791 Kind = LinearMapKind;
6797 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6799 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6801 TableInt <<=
IT->getBitWidth();
6805 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6808 BitMap = ConstantInt::get(M.getContext(), TableInt);
6809 BitMapElementTy =
IT;
6818 Kind = LookupTableKind;
6824 case SingleValueKind:
6826 case LinearMapKind: {
6830 false,
"switch.idx.cast");
6831 if (!LinearMultiplier->
isOne())
6832 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6834 !LinearMapValWrapped);
6836 if (!LinearOffset->
isZero())
6839 !LinearMapValWrapped);
6856 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
6857 "switch.shiftamt",
true,
true);
6860 Value *DownShifted =
6861 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6863 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6865 case LookupTableKind: {
6868 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
6869 true, GlobalVariable::PrivateLinkage,
6870 Initializer,
"switch.table." +
Func->getName());
6871 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6874 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
6875 Type *IndexTy =
DL.getIndexType(Table->getType());
6878 if (
Index->getType() != IndexTy) {
6879 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
6883 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
6886 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
6889 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
6895bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
6897 Type *ElementType) {
6905 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6907 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6913 if (
TTI.isTypeLegal(Ty))
6928 DL.fitsInLegalInteger(
IT->getBitWidth());
6931Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
6933bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
6944 return NumCases * 100 >= CaseRange * MinDensity;
6965 if (
SI->getNumCases() > TableSize)
6968 bool AllTablesFitInRegister =
true;
6969 bool HasIllegalType =
false;
6970 for (
const auto &Ty : ResultTypes) {
6975 AllTablesFitInRegister =
6976 AllTablesFitInRegister &&
6977 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
6982 if (HasIllegalType && !AllTablesFitInRegister)
6987 if (AllTablesFitInRegister)
7004 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7007 return all_of(ResultTypes, [&](
const auto &ResultType) {
7008 return SwitchReplacement::wouldFitInRegister(
7036 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
7058 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7063 for (
auto ValuePair : Values) {
7066 if (!CaseConst || CaseConst == DefaultConst ||
7067 (CaseConst != TrueConst && CaseConst != FalseConst))
7081 if (DefaultConst == FalseConst) {
7084 ++NumTableCmpReuses;
7087 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7088 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7091 ++NumTableCmpReuses;
7101 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7115 if (
SI->getNumCases() < 3)
7137 MinCaseVal = CaseVal;
7139 MaxCaseVal = CaseVal;
7156 It->second.push_back(std::make_pair(CaseVal,
Value));
7164 bool HasDefaultResults =
7166 DefaultResultsList,
DL,
TTI);
7167 for (
const auto &
I : DefaultResultsList) {
7170 DefaultResults[
PHI] = Result;
7174 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7177 if (UseSwitchConditionAsTableIndex) {
7179 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7184 TableIndexOffset = MinCaseVal;
7191 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7193 bool TableHasHoles = (NumResults < TableSize);
7198 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7206 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7209 if (
SI->getNumCases() < 4)
7211 if (!
DL.fitsInLegalInteger(TableSize))
7220 if (UseSwitchConditionAsTableIndex) {
7221 TableIndex =
SI->getCondition();
7222 if (HasDefaultResults) {
7234 all_of(ResultTypes, [&](
const auto &ResultType) {
7235 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7240 TableSize = std::max(UpperBound, TableSize);
7243 DefaultIsReachable =
false;
7251 const auto &ResultList = ResultLists[
PHI];
7253 Type *ResultType = ResultList.begin()->second->getType();
7258 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7260 PhiToReplacementMap.
insert({
PHI, Replacement});
7263 bool AnyLookupTables =
any_of(
7264 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7272 if (AnyLookupTables &&
7273 (!
TTI.shouldBuildLookupTables() ||
7277 Builder.SetInsertPoint(
SI);
7280 if (!UseSwitchConditionAsTableIndex) {
7283 bool MayWrap =
true;
7284 if (!DefaultIsReachable) {
7289 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7290 "switch.tableidx",
false,
7294 std::vector<DominatorTree::UpdateType> Updates;
7300 assert(MaxTableSize >= TableSize &&
7301 "It is impossible for a switch to have more entries than the max "
7302 "representable value of its input integer type's size.");
7307 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7312 Builder.SetInsertPoint(
SI);
7313 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7314 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7315 Builder.CreateBr(LookupBB);
7321 Value *Cmp = Builder.CreateICmpULT(
7322 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7324 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7325 CondBranch = RangeCheckBranch;
7331 Builder.SetInsertPoint(LookupBB);
7337 MaskBB->
setName(
"switch.hole_check");
7344 APInt MaskInt(TableSizePowOf2, 0);
7345 APInt One(TableSizePowOf2, 1);
7347 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7348 for (
const auto &Result : ResultList) {
7351 MaskInt |= One << Idx;
7353 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7360 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7361 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7362 Value *LoBit = Builder.CreateTrunc(
7364 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7369 Builder.SetInsertPoint(LookupBB);
7373 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7376 SI->getDefaultDest()->removePredecessor(BB,
7383 const ResultListTy &ResultList = ResultLists[
PHI];
7384 auto Replacement = PhiToReplacementMap.
at(
PHI);
7385 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7388 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7391 for (
auto *
User :
PHI->users()) {
7393 Replacement.getDefaultValue(), ResultList);
7397 PHI->addIncoming(Result, LookupBB);
7400 Builder.CreateBr(CommonDest);
7412 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7415 if (Succ ==
SI->getDefaultDest()) {
7416 if (HasBranchWeights)
7417 ToDefaultWeight += BranchWeights[
I];
7421 if (DTU && RemovedSuccessors.
insert(Succ).second)
7423 if (HasBranchWeights)
7424 ToLookupWeight += BranchWeights[
I];
7426 SI->eraseFromParent();
7427 if (HasBranchWeights)
7434 ++NumLookupTablesHoles;
7450 if (CondTy->getIntegerBitWidth() > 64 ||
7451 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7455 if (
SI->getNumCases() < 4)
7463 for (
const auto &
C :
SI->cases())
7464 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7472 int64_t
Base = Values[0];
7473 for (
auto &V : Values)
7486 unsigned Shift = 64;
7487 for (
auto &V : Values)
7491 for (
auto &V : Values)
7492 V = (int64_t)((
uint64_t)V >> Shift);
7509 Builder.SetInsertPoint(
SI);
7511 Builder.CreateSub(
SI->getCondition(), ConstantInt::get(Ty,
Base));
7512 Value *Rot = Builder.CreateIntrinsic(
7513 Ty, Intrinsic::fshl,
7514 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7515 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7517 for (
auto Case :
SI->cases()) {
7518 auto *Orig = Case.getCaseValue();
7519 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7538 Value *Condition =
SI->getCondition();
7542 if (CondTy->getIntegerBitWidth() > 64 ||
7543 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7555 if (
SI->getNumCases() < 4)
7561 if (!
SI->defaultDestUnreachable())
7566 for (
const auto &Case :
SI->cases()) {
7567 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7581 Builder.SetInsertPoint(
SI);
7584 for (
auto &Case :
SI->cases()) {
7585 auto *OrigValue = Case.getCaseValue();
7586 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7587 OrigValue->getValue().countr_zero()));
7591 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
7594 SI->setCondition(ConditionTrailingZeros);
7604 if (!Cmp || !Cmp->hasOneUse())
7615 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7618 if (
SI->getNumCases() == 2) {
7625 Succ =
SI->getDefaultDest();
7626 SuccWeight = Weights[0];
7628 for (
auto &Case :
SI->cases()) {
7629 std::optional<int64_t> Val =
7633 if (!Missing.erase(*Val))
7638 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7641 assert(Missing.size() == 1 &&
"Should have one case left");
7642 Res = *Missing.begin();
7643 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
7645 Unreachable =
SI->getDefaultDest();
7647 for (
auto &Case :
SI->cases()) {
7648 BasicBlock *NewSucc = Case.getCaseSuccessor();
7649 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7652 OtherSuccWeight += Weight;
7655 SuccWeight = Weight;
7656 }
else if (Succ == NewSucc) {
7662 for (
auto &Case :
SI->cases()) {
7663 std::optional<int64_t> Val =
7665 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7667 if (Case.getCaseSuccessor() == Succ) {
7689 if (Cmp->isSigned())
7692 MDNode *NewWeights =
nullptr;
7698 Builder.SetInsertPoint(
SI->getIterator());
7699 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
7700 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
7701 SI->getMetadata(LLVMContext::MD_unpredictable));
7705 SI->eraseFromParent();
7706 Cmp->eraseFromParent();
7707 if (DTU && Unreachable)
7739 "Only supporting unconditional branches for now");
7741 "Expected unconditional branches to have one successor");
7742 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7763 if (LHS == EKey || RHS == EKey || LHS == TKey || RHS == TKey)
7779 "Only supporting unconditional branches for now");
7786 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
7787 if (PredIVs[
A] != PredIVs[
B])
7796bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
7797 DomTreeUpdater *DTU) {
7803 SmallPtrSet<PHINode *, 8> Phis;
7804 SmallPtrSet<BasicBlock *, 8> Seen;
7805 DenseMap<PHINode *, SmallDenseMap<BasicBlock *, Value *, 8>> PhiPredIVs;
7806 DenseMap<BasicBlock *, SmallVector<unsigned, 32>> BBToSuccessorIndexes;
7810 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7815 if (BB->
size() != 1)
7825 if (!Seen.
insert(BB).second) {
7826 auto It = BBToSuccessorIndexes.
find(BB);
7827 if (It != BBToSuccessorIndexes.
end())
7828 It->second.emplace_back(
I);
7842 Cases.
emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs});
7843 BBToSuccessorIndexes[BB].emplace_back(
I);
7849 for (PHINode *Phi : Phis) {
7851 PhiPredIVs.
try_emplace(Phi,
Phi->getNumIncomingValues()).first->second;
7852 for (
auto &
IV :
Phi->incoming_values())
7853 IVs.insert({
Phi->getIncomingBlock(
IV),
IV.get()});
7864 DenseSet<const SwitchSuccWrapper *> ReplaceWith;
7869 bool MadeChange =
false;
7870 for (
auto &SSW : Cases) {
7877 Updates.
push_back({DominatorTree::Delete,
SI->getParent(), SSW.Dest});
7878 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7879 for (
unsigned Idx : Successors)
7880 SI->setSuccessor(Idx, (*It)->Dest);
7891bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
7894 if (isValueEqualityComparison(SI)) {
7898 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7899 return requestResimplify();
7903 if (simplifySwitchOnSelect(SI,
Select))
7904 return requestResimplify();
7909 if (foldValueComparisonIntoPredecessors(SI, Builder))
7910 return requestResimplify();
7916 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7917 return requestResimplify();
7921 return requestResimplify();
7924 return requestResimplify();
7927 return requestResimplify();
7930 return requestResimplify();
7937 if (
Options.ConvertSwitchToLookupTable &&
7939 return requestResimplify();
7942 return requestResimplify();
7945 return requestResimplify();
7948 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
7949 return requestResimplify();
7951 if (simplifyDuplicateSwitchArms(SI, DTU))
7952 return requestResimplify();
7957bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
7960 SmallVector<uint32_t> BranchWeights;
7964 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
7965 if (HasBranchWeights)
7970 SmallPtrSet<Value *, 8> Succs;
7971 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
7976 RemovedSuccs.
insert(Dest);
7986 std::vector<DominatorTree::UpdateType> Updates;
7987 Updates.reserve(RemovedSuccs.
size());
7988 for (
auto *RemovedSucc : RemovedSuccs)
7989 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8006 if (HasBranchWeights) {
8013 if (simplifyIndirectBrOnSelect(IBI, SI))
8014 return requestResimplify();
8050 if (BB == OtherPred)
8061 std::vector<DominatorTree::UpdateType> Updates;
8068 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8069 "unexpected successor");
8070 II->setUnwindDest(OtherPred);
8085 Builder.CreateUnreachable();
8094bool SimplifyCFGOpt::simplifyBranch(BranchInst *Branch,
IRBuilder<> &Builder) {
8095 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
8096 : simplifyCondBranch(
Branch, Builder);
8099bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
8111 bool NeedCanonicalLoop =
8125 if (
I->isTerminator() &&
8126 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8142 if (
Options.SpeculateBlocks &&
8145 return requestResimplify();
8153 if (!PPred || (PredPred && PredPred != PPred))
8190 if (!SuccBI || !SuccBI->isConditional())
8194 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8198 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8224 bool HasWeight =
false;
8229 BBTWeight = BBFWeight = 1;
8234 BB1TWeight = BB1FWeight = 1;
8239 BB2TWeight = BB2FWeight = 1;
8241 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8242 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8249bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI,
IRBuilder<> &Builder) {
8253 "Tautological conditional branch should have been eliminated already.");
8256 if (!
Options.SimplifyCondBranch ||
8261 if (isValueEqualityComparison(BI)) {
8266 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8267 return requestResimplify();
8273 if (foldValueComparisonIntoPredecessors(BI, Builder))
8274 return requestResimplify();
8277 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8278 return requestResimplify();
8283 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8296 return requestResimplify();
8302 if (
Options.SpeculateBlocks &&
8305 return requestResimplify();
8314 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8315 return requestResimplify();
8317 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8319 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8320 auto CanSpeculateConditionalLoadsStores = [&]() {
8322 for (Instruction &
I : *Succ) {
8323 if (
I.isTerminator()) {
8324 if (
I.getNumSuccessors() > 1)
8328 SpeculatedConditionalLoadsStores.
size() ==
8332 SpeculatedConditionalLoadsStores.
push_back(&
I);
8335 return !SpeculatedConditionalLoadsStores.
empty();
8338 if (CanSpeculateConditionalLoadsStores()) {
8340 std::nullopt,
nullptr);
8341 return requestResimplify();
8351 return requestResimplify();
8360 return requestResimplify();
8366 if (foldCondBranchOnValueKnownInPredecessor(BI))
8367 return requestResimplify();
8372 if (PBI != BI && PBI->isConditional())
8374 return requestResimplify();
8380 if (PBI != BI && PBI->isConditional())
8382 return requestResimplify();
8386 return requestResimplify();
8393 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8405 auto *Use = cast<Instruction>(U.getUser());
8407 switch (Use->getOpcode()) {
8410 case Instruction::GetElementPtr:
8411 case Instruction::Ret:
8412 case Instruction::BitCast:
8413 case Instruction::Load:
8414 case Instruction::Store:
8415 case Instruction::Call:
8416 case Instruction::CallBr:
8417 case Instruction::Invoke:
8418 case Instruction::UDiv:
8419 case Instruction::URem:
8423 case Instruction::SDiv:
8424 case Instruction::SRem:
8428 if (FindUse ==
I->use_end())
8430 auto &
Use = *FindUse;
8435 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8436 User->comesBefore(
I))
8450 if (
GEP->getPointerOperand() ==
I) {
8453 if (
GEP->getType()->isVectorTy())
8461 if (!
GEP->hasAllZeroIndices() &&
8462 (!
GEP->isInBounds() ||
8464 GEP->getPointerAddressSpace())))
8465 PtrValueMayBeModified =
true;
8471 bool HasNoUndefAttr =
8472 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8477 if (
C->isNullValue() && HasNoUndefAttr &&
8478 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8479 return !PtrValueMayBeModified;
8485 if (!LI->isVolatile())
8487 LI->getPointerAddressSpace());
8491 if (!
SI->isVolatile())
8493 SI->getPointerAddressSpace())) &&
8494 SI->getPointerOperand() ==
I;
8499 if (
I == Assume->getArgOperand(0))
8507 if (CB->getCalledOperand() ==
I)
8510 if (CB->isArgOperand(&
Use)) {
8511 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8514 CB->paramHasNonNullAttr(ArgIdx,
false))
8515 return !PtrValueMayBeModified;
8534 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8544 Builder.CreateUnreachable();
8551 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
8553 Assumption = Builder.CreateAssumption(
Cond);
8568 Builder.SetInsertPoint(Unreachable);
8570 Builder.CreateUnreachable();
8571 for (
const auto &Case :
SI->cases())
8572 if (Case.getCaseSuccessor() == BB) {
8574 Case.setSuccessor(Unreachable);
8576 if (
SI->getDefaultDest() == BB) {
8578 SI->setDefaultDest(Unreachable);
8592bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
8617 return requestResimplify();
8638 if (
Options.SpeculateBlocks &&
8645 Options.SpeculateUnpredictables))
8652 case Instruction::Br:
8655 case Instruction::Resume:
8658 case Instruction::CleanupRet:
8661 case Instruction::Switch:
8664 case Instruction::Unreachable:
8667 case Instruction::IndirectBr:
8675bool SimplifyCFGOpt::run(BasicBlock *BB) {
8685 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
unsigned unsigned DefaultVal
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 simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static bool isProfitableToSpeculate(const BranchInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static 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 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 bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static 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 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 const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI 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.
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 ...
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="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
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.
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.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
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<>...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, Function &F, StringRef PassName)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
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"))
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
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.
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 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
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.
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 ...
int popcount(T Value) noexcept
Count the number of set bits in a value.
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.