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 searched to prove that threading through "
206 "a loop header keeps the loop canonical"));
210 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
217STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
219 "Number of switch instructions turned into linear mapping");
221 "Number of switch instructions turned into lookup tables");
223 NumLookupTablesHoles,
224 "Number of switch instructions turned into lookup tables (holes checked)");
225STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
227 "Number of value comparisons folded into predecessor basic blocks");
229 "Number of branches folded into predecessor basic block");
232 "Number of common instruction 'blocks' hoisted up to the begin block");
234 "Number of common instructions hoisted up to the begin block");
236 "Number of common instruction 'blocks' sunk down to the end block");
238 "Number of common instructions sunk down to the end block");
239STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
241 "Number of invokes with empty resume blocks simplified into calls");
242STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
243STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
250using SwitchCaseResultVectorTy =
259struct ValueEqualityComparisonCase {
271 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
274class SimplifyCFGOpt {
275 const TargetTransformInfo &TTI;
277 const DataLayout &DL;
279 const SimplifyCFGOptions &Options;
282 Value *isValueEqualityComparison(Instruction *TI);
284 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
285 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
288 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
291 bool foldValueComparisonIntoPredecessors(Instruction *TI,
294 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
295 bool simplifySingleResume(ResumeInst *RI);
296 bool simplifyCommonResume(ResumeInst *RI);
297 bool simplifyCleanupReturn(CleanupReturnInst *RI);
298 bool simplifyUnreachable(UnreachableInst *UI);
299 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
300 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
301 bool simplifyIndirectBr(IndirectBrInst *IBI);
302 bool simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
303 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
304 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
306 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
308 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
311 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
312 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
313 Instruction *TI, Instruction *I1,
314 SmallVectorImpl<Instruction *> &OtherSuccTIs,
316 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
317 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
318 BasicBlock *TrueBB, BasicBlock *FalseBB,
319 uint32_t TrueWeight, uint32_t FalseWeight);
320 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
321 const DataLayout &DL);
322 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
323 bool simplifySwitchOnSelectRemap(SwitchInst *SI, SelectInst *
Select,
Value *
X,
324 ConstantInt *
C,
bool Negate);
325 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
326 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
327 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
330 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
332 const SimplifyCFGOptions &Opts)
333 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
334 assert((!DTU || !DTU->hasPostDomTree()) &&
335 "SimplifyCFG is not yet capable of maintaining validity of a "
336 "PostDomTree, so don't ask for it.");
339 bool simplifyOnce(BasicBlock *BB);
340 bool run(BasicBlock *BB);
343 bool requestResimplify() {
353isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
373 "Only for a pair of incoming blocks at the time!");
379 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
380 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
383 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
384 EquivalenceSet->contains(IV1))
407 if (!SI1Succs.
count(Succ))
413 FailBlocks->insert(Succ);
429 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
431 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
432 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
494 if (AggressiveInsts.
count(
I))
510 ZeroCostInstructions.
insert(OverflowInst);
512 }
else if (!ZeroCostInstructions.
contains(
I))
528 for (
Use &
Op :
I->operands())
530 TTI, AC, ZeroCostInstructions,
Depth + 1))
547 if (
DL.hasUnstableRepresentation(V->getType()))
556 return ConstantInt::get(
IntPtrTy, 0);
561 if (CE->getOpcode() == Instruction::IntToPtr)
585struct ConstantComparesGatherer {
586 const DataLayout &DL;
589 Value *CompValue =
nullptr;
592 Value *Extra =
nullptr;
598 unsigned UsedICmps = 0;
604 bool IgnoreFirstMatch =
false;
605 bool MultipleMatches =
false;
608 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
610 if (CompValue || !MultipleMatches)
615 IgnoreFirstMatch =
true;
619 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
620 ConstantComparesGatherer &
621 operator=(
const ConstantComparesGatherer &) =
delete;
626 bool setValueOnce(
Value *NewVal) {
627 if (IgnoreFirstMatch) {
628 IgnoreFirstMatch =
false;
631 if (CompValue && CompValue != NewVal) {
632 MultipleMatches =
true;
646 bool matchInstruction(Instruction *
I,
bool isEQ) {
653 if (!setValueOnce(Val))
673 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
717 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
719 if (!setValueOnce(RHSVal))
724 ConstantInt::get(
C->getContext(),
725 C->getValue() | Mask));
740 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
742 if (!setValueOnce(RHSVal))
746 Vals.push_back(ConstantInt::get(
C->getContext(),
747 C->getValue() & ~Mask));
768 Value *CandidateVal =
I->getOperand(0);
771 CandidateVal = RHSVal;
786 if (!setValueOnce(CandidateVal))
792 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
804 void gather(
Value *V) {
813 SmallVector<Value *, 8> DFT{Op0, Op1};
814 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
816 while (!DFT.
empty()) {
823 if (Visited.
insert(Op1).second)
825 if (Visited.
insert(Op0).second)
832 if (matchInstruction(
I, IsEq))
876 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
877 CV =
SI->getCondition();
879 if (BI->getCondition()->hasOneUse()) {
884 if (Trunc->hasNoUnsignedWrap())
885 CV = Trunc->getOperand(0);
892 Value *Ptr = PTII->getPointerOperand();
893 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
895 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
904BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
905 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
907 Cases.reserve(
SI->getNumCases());
908 for (
auto Case :
SI->cases())
909 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
910 Case.getCaseSuccessor()));
911 return SI->getDefaultDest();
916 ICmpInst::Predicate Pred;
922 Pred = ICmpInst::ICMP_NE;
927 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
935 std::vector<ValueEqualityComparisonCase> &Cases) {
941 std::vector<ValueEqualityComparisonCase> &C2) {
942 std::vector<ValueEqualityComparisonCase> *
V1 = &
C1, *V2 = &C2;
945 if (
V1->size() > V2->size())
950 if (
V1->size() == 1) {
953 for (
const ValueEqualityComparisonCase &
VECC : *V2)
954 if (TheVal ==
VECC.Value)
961 unsigned i1 = 0, i2 = 0, e1 =
V1->size(), e2 = V2->size();
962 while (i1 != e1 && i2 != e2) {
978bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
979 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
984 Value *ThisVal = isValueEqualityComparison(TI);
985 assert(ThisVal &&
"This isn't a value comparison!!");
986 if (ThisVal != PredVal)
993 std::vector<ValueEqualityComparisonCase> PredCases;
995 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
999 std::vector<ValueEqualityComparisonCase> ThisCases;
1000 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1015 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1021 ThisCases[0].Dest->removePredecessor(PredDef);
1024 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1031 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1038 SmallPtrSet<Constant *, 16> DeadCases;
1039 for (
const ValueEqualityComparisonCase &Case : PredCases)
1040 DeadCases.
insert(Case.Value);
1043 <<
"Through successor TI: " << *TI);
1045 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1048 auto *
Successor = i->getCaseSuccessor();
1051 if (DeadCases.
count(i->getCaseValue())) {
1060 std::vector<DominatorTree::UpdateType> Updates;
1061 for (
const auto &
I : NumPerSuccessorCases)
1063 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1073 ConstantInt *TIV =
nullptr;
1075 for (
const auto &[
Value, Dest] : PredCases)
1081 assert(TIV &&
"No edge from pred to succ?");
1086 for (
const auto &[
Value, Dest] : ThisCases)
1094 TheRealDest = ThisDef;
1096 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1101 if (Succ != CheckEdge) {
1102 if (Succ != TheRealDest)
1103 RemovedSuccs.
insert(Succ);
1106 CheckEdge =
nullptr;
1113 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1118 SmallVector<DominatorTree::UpdateType, 2> Updates;
1120 for (
auto *RemovedSucc : RemovedSuccs)
1121 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1132struct ConstantIntOrdering {
1133 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1134 return LHS->getValue().ult(
RHS->getValue());
1146 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1155 assert(MD &&
"Invalid branch-weight metadata");
1180 if (BonusInst.isTerminator())
1215 NewBonusInst->
takeName(&BonusInst);
1216 BonusInst.setName(NewBonusInst->
getName() +
".old");
1217 VMap[&BonusInst] = NewBonusInst;
1226 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1227 "If the user is not a PHI node, then it should be in the same "
1228 "block as, and come after, the original bonus instruction.");
1232 if (PN->getIncomingBlock(U) == BB)
1236 assert(PN->getIncomingBlock(U) == PredBlock &&
1237 "Not in block-closed SSA form?");
1238 U.set(NewBonusInst);
1248 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1249 PredDL.isSameSourceLocation(
DL)) {
1256bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1264 std::vector<ValueEqualityComparisonCase> BBCases;
1265 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1267 std::vector<ValueEqualityComparisonCase> PredCases;
1268 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1273 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1276 SmallVector<uint64_t, 8> Weights;
1280 if (PredHasWeights) {
1283 if (Weights.
size() != 1 + PredCases.size())
1284 PredHasWeights = SuccHasWeights =
false;
1285 }
else if (SuccHasWeights)
1289 Weights.
assign(1 + PredCases.size(), 1);
1291 SmallVector<uint64_t, 8> SuccWeights;
1292 if (SuccHasWeights) {
1295 if (SuccWeights.
size() != 1 + BBCases.size())
1296 PredHasWeights = SuccHasWeights =
false;
1297 }
else if (PredHasWeights)
1298 SuccWeights.
assign(1 + BBCases.size(), 1);
1300 if (PredDefault == BB) {
1303 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1304 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1305 if (PredCases[i].Dest != BB)
1306 PTIHandled.insert(PredCases[i].
Value);
1309 std::swap(PredCases[i], PredCases.back());
1311 if (PredHasWeights || SuccHasWeights) {
1313 Weights[0] += Weights[i + 1];
1318 PredCases.pop_back();
1324 if (PredDefault != BBDefault) {
1326 if (DTU && PredDefault != BB)
1327 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1328 PredDefault = BBDefault;
1329 ++NewSuccessors[BBDefault];
1332 unsigned CasesFromPred = Weights.
size();
1334 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1335 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1336 PredCases.push_back(BBCases[i]);
1337 ++NewSuccessors[BBCases[i].Dest];
1338 if (SuccHasWeights || PredHasWeights) {
1342 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1343 ValidTotalSuccWeight += SuccWeights[i + 1];
1347 if (SuccHasWeights || PredHasWeights) {
1348 ValidTotalSuccWeight += SuccWeights[0];
1350 for (
unsigned i = 1; i < CasesFromPred; ++i)
1351 Weights[i] *= ValidTotalSuccWeight;
1353 Weights[0] *= SuccWeights[0];
1359 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1360 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1361 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1362 if (PredCases[i].Dest == BB) {
1363 PTIHandled.insert(PredCases[i].
Value);
1365 if (PredHasWeights || SuccHasWeights) {
1366 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1371 std::swap(PredCases[i], PredCases.back());
1372 PredCases.pop_back();
1379 for (
const ValueEqualityComparisonCase &Case : BBCases)
1380 if (PTIHandled.count(Case.Value)) {
1382 if (PredHasWeights || SuccHasWeights)
1383 Weights.
push_back(WeightsForHandled[Case.Value]);
1384 PredCases.push_back(Case);
1385 ++NewSuccessors[Case.Dest];
1386 PTIHandled.erase(Case.Value);
1391 for (ConstantInt *
I : PTIHandled) {
1392 if (PredHasWeights || SuccHasWeights)
1394 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1395 ++NewSuccessors[BBDefault];
1402 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1407 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1409 for (
auto I :
seq(NewSuccessor.second)) {
1413 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1414 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1421 "Should not end up here with unstable pointers");
1427 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1429 for (ValueEqualityComparisonCase &V : PredCases)
1432 if (PredHasWeights || SuccHasWeights)
1440 if (MDNode *Unpredictable = PTI->
getMetadata(LLVMContext::MD_unpredictable))
1441 if (TI->
hasMetadata(LLVMContext::MD_unpredictable))
1442 NewSI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
1452 if (!InfLoopBlock) {
1460 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1467 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1469 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1474 ++NumFoldValueComparisonIntoPredecessors;
1482bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1485 Value *CV = isValueEqualityComparison(TI);
1486 assert(CV &&
"Not a comparison?");
1491 while (!Preds.empty()) {
1500 Value *PCV = isValueEqualityComparison(PTI);
1504 SmallSetVector<BasicBlock *, 4> FailBlocks;
1506 for (
auto *Succ : FailBlocks) {
1512 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1526 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1527 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1528 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1550 if (
I->mayReadFromMemory())
1582 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1590 if (J->getParent() == BB)
1612 if (
C1->isMustTailCall() != C2->isMustTailCall())
1615 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1621 if (CB1->cannotMerge() || CB1->isConvergent())
1624 if (CB2->cannotMerge() || CB2->isConvergent())
1639 if (!I1->hasDbgRecords())
1641 using CurrentAndEndIt =
1642 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1648 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1649 return Pair.first == Pair.second;
1655 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1661 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1663 if (!
Other->hasDbgRecords())
1666 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1673 while (
none_of(Itrs, atEnd)) {
1674 bool HoistDVRs = allIdentical(Itrs);
1675 for (CurrentAndEndIt &Pair : Itrs) {
1689 if (I1->isIdenticalToWhenDefined(I2,
true))
1694 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1695 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1696 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1698 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1699 return I1->getOperand(0) == I2->
getOperand(1) &&
1765 auto &Context = BI->
getParent()->getContext();
1770 Value *Mask =
nullptr;
1771 Value *MaskFalse =
nullptr;
1772 Value *MaskTrue =
nullptr;
1773 if (Invert.has_value()) {
1774 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1775 Mask = Builder.CreateBitCast(
1780 MaskFalse = Builder.CreateBitCast(
1782 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1784 auto PeekThroughBitcasts = [](
Value *V) {
1786 V = BitCast->getOperand(0);
1789 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1791 if (!Invert.has_value())
1792 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1797 auto *Op0 =
I->getOperand(0);
1798 CallInst *MaskedLoadStore =
nullptr;
1801 auto *Ty =
I->getType();
1803 Value *PassThru =
nullptr;
1804 if (Invert.has_value())
1805 for (
User *U :
I->users()) {
1807 PassThru = Builder.CreateBitCast(
1816 Builder.SetInsertPoint(Ins);
1819 MaskedLoadStore = Builder.CreateMaskedLoad(
1821 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range)) {
1830 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1833 I->replaceAllUsesWith(NewLoadStore);
1836 auto *StoredVal = Builder.CreateBitCast(
1838 MaskedLoadStore = Builder.CreateMaskedStore(
1847 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1851 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1852 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1855 I->eraseFromParent();
1862 bool IsStore =
false;
1885bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1886 bool AllInstsEqOnly) {
1902 for (
auto *Succ : UniqueSuccessors) {
1918 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1920 for (
auto *Succ : UniqueSuccessors) {
1924 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1927 if (AllInstsEqOnly) {
1933 unsigned Size0 = UniqueSuccessors[0]->size();
1934 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1938 Succ->
size() == Size0;
1942 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1943 while (LRI.isValid()) {
1945 if (
any_of(*LRI, [I0](Instruction *
I) {
1959 unsigned NumSkipped = 0;
1962 if (SuccIterPairs.
size() > 2) {
1965 if (SuccIterPairs.
size() < 2)
1972 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1973 auto &BB1ItrPair = *SuccIterPairBegin++;
1974 auto OtherSuccIterPairRange =
1980 bool AllInstsAreIdentical =
true;
1981 bool HasTerminator =
I1->isTerminator();
1982 for (
auto &SuccIter : OtherSuccIterRange) {
1986 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1987 AllInstsAreIdentical =
false;
1990 SmallVector<Instruction *, 8> OtherInsts;
1991 for (
auto &SuccIter : OtherSuccIterRange)
1996 if (HasTerminator) {
2000 if (NumSkipped || !AllInstsAreIdentical) {
2005 return hoistSuccIdenticalTerminatorToSwitchOrIf(
2006 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
2010 if (AllInstsAreIdentical) {
2011 unsigned SkipFlagsBB1 = BB1ItrPair.second;
2012 AllInstsAreIdentical =
2014 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
2016 unsigned SkipFlagsBB2 = Pair.second;
2031 AllInstsAreIdentical && CI && CI->isMustTailCall()) {
2032 AllInstsAreIdentical =
2033 NumSkipped == 0 &&
all_of(SuccIterPairs, [](
const SuccIterPair &
P) {
2038 if (AllInstsAreIdentical) {
2048 for (
auto &SuccIter : OtherSuccIterRange) {
2056 assert(
Success &&
"We should not be trying to hoist callbases "
2057 "with non-intersectable attributes");
2075 unsigned SkippedFlags = 0;
2076 for (
const SuccIterPair &
P : SuccIterPairs)
2077 SkippedFlags |=
P.second;
2080 I1->dropUBImplyingAttrsAndMetadata();
2083 NumHoistCommonCode += SuccIterPairs.size();
2085 NumHoistCommonInstrs += SuccIterPairs.size();
2094 for (
auto &SuccIterPair : SuccIterPairs) {
2103bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2104 Instruction *TI, Instruction *I1,
2105 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2115 auto *I2 = *OtherSuccTIs.
begin();
2135 for (PHINode &PN : Succ->
phis()) {
2136 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2137 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2138 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2158 if (!
NT->getType()->isVoidTy()) {
2159 I1->replaceAllUsesWith(NT);
2160 for (Instruction *OtherSuccTI : OtherSuccTIs)
2161 OtherSuccTI->replaceAllUsesWith(NT);
2165 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2171 for (
auto *OtherSuccTI : OtherSuccTIs)
2172 Locs.
push_back(OtherSuccTI->getDebugLoc());
2184 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2186 for (PHINode &PN : Succ->
phis()) {
2187 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2188 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2194 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2204 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2205 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2206 PN.setIncomingValue(i, SI);
2214 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
2218 if (DTU && VisitedSuccs.
insert(Succ).second)
2219 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2225 for (BasicBlock *Succ : UniqueSuccessors)
2226 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2240 if (
I->isIntDivRem())
2255 std::optional<unsigned> NumUses;
2256 for (
auto *
I : Insts) {
2259 I->getType()->isTokenTy())
2264 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2272 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2276 NumUses =
I->getNumUses();
2277 else if (NumUses !=
I->getNumUses())
2283 for (
auto *
I : Insts) {
2297 for (
const Use &U : I0->
uses()) {
2298 auto It = PHIOperands.find(&U);
2299 if (It == PHIOperands.end())
2302 if (!
equal(Insts, It->second))
2316 if (HaveIndirectCalls) {
2317 if (!AllCallsAreIndirect)
2321 Value *Callee =
nullptr;
2325 Callee = CurrCallee;
2326 else if (Callee != CurrCallee)
2332 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2338 if (!
all_of(Insts, SameAsI0)) {
2343 !
all_of(Insts, CanReplaceOperand))
2347 for (
auto *
I : Insts)
2348 Ops.push_back(
I->getOperand(OI));
2358 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2363 for (
auto *BB : Blocks) {
2365 I =
I->getPrevNode();
2390 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2393 PN->insertBefore(BBEnd->begin());
2394 for (
auto *
I : Insts)
2395 PN->addIncoming(
I->getOperand(O),
I->getParent());
2404 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2407 for (
auto *
I : Insts)
2427 assert(
Success &&
"We should not be trying to sink callbases "
2428 "with non-intersectable attributes");
2439 PN->replaceAllUsesWith(I0);
2440 PN->eraseFromParent();
2444 for (
auto *
I : Insts) {
2449 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2450 I->replaceAllUsesWith(I0);
2451 I->eraseFromParent();
2501 bool HaveNonUnconditionalPredecessors =
false;
2507 HaveNonUnconditionalPredecessors =
true;
2509 if (UnconditionalPreds.
size() < 2)
2522 for (
const Use &U : PN.incoming_values())
2523 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2524 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2526 Ops.push_back(*IncomingVals[Pred]);
2534 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2547 if (!followedByDeoptOrUnreachable) {
2549 auto IsMemOperand = [](
Use &U) {
2562 unsigned NumPHIInsts = 0;
2563 for (
Use &U : (*LRI)[0]->operands()) {
2564 auto It = PHIOperands.
find(&U);
2565 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2566 return InstructionsToSink.contains(V);
2573 if (IsMemOperand(U) &&
2574 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2581 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2582 return NumPHIInsts <= 1;
2599 while (Idx < ScanIdx) {
2600 if (!ProfitableToSinkInstruction(LRI)) {
2603 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2616 if (Idx < ScanIdx) {
2619 InstructionsToSink = InstructionsProfitableToSink;
2625 !ProfitableToSinkInstruction(LRI) &&
2626 "We already know that the last instruction is unprofitable to sink");
2634 for (
auto *
I : *LRI)
2635 InstructionsProfitableToSink.
erase(
I);
2636 if (!ProfitableToSinkInstruction(LRI)) {
2639 InstructionsToSink = InstructionsProfitableToSink;
2653 if (HaveNonUnconditionalPredecessors) {
2654 if (!followedByDeoptOrUnreachable) {
2662 bool Profitable =
false;
2663 while (Idx < ScanIdx) {
2697 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2699 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2707 NumSinkCommonInstrs++;
2711 ++NumSinkCommonCode;
2717struct CompatibleSets {
2718 using SetTy = SmallVector<InvokeInst *, 2>;
2724 SetTy &getCompatibleSet(InvokeInst *
II);
2726 void insert(InvokeInst *
II);
2729CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2734 for (CompatibleSets::SetTy &Set : Sets) {
2735 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2740 return Sets.emplace_back();
2743void CompatibleSets::insert(InvokeInst *
II) {
2744 getCompatibleSet(
II).emplace_back(
II);
2748 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2751 auto IsIllegalToMerge = [](InvokeInst *
II) {
2752 return II->cannotMerge() ||
II->isInlineAsm();
2754 if (
any_of(Invokes, IsIllegalToMerge))
2762 if (HaveIndirectCalls) {
2763 if (!AllCallsAreIndirect)
2768 for (InvokeInst *
II : Invokes) {
2769 Value *CurrCallee =
II->getCalledOperand();
2770 assert(CurrCallee &&
"There is always a called operand.");
2773 else if (Callee != CurrCallee)
2780 auto HasNormalDest = [](InvokeInst *
II) {
2783 if (
any_of(Invokes, HasNormalDest)) {
2786 if (!
all_of(Invokes, HasNormalDest))
2791 for (InvokeInst *
II : Invokes) {
2793 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2795 NormalBB = CurrNormalBB;
2796 else if (NormalBB != CurrNormalBB)
2804 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2813 for (InvokeInst *
II : Invokes) {
2815 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2817 UnwindBB = CurrUnwindBB;
2819 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2826 Invokes.front()->getUnwindDest(),
2827 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2832 const InvokeInst *II0 = Invokes.front();
2833 for (
auto *
II : Invokes.drop_front())
2838 auto IsIllegalToMergeArguments = [](
auto Ops) {
2839 Use &U0 = std::get<0>(
Ops);
2840 Use &U1 = std::get<1>(
Ops);
2846 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2847 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2848 IsIllegalToMergeArguments))
2860 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2866 bool HasNormalDest =
2871 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2875 II0->
getParent()->getIterator()->getNextNode();
2880 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2884 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2886 if (!HasNormalDest) {
2890 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2898 return MergedInvoke;
2912 SuccBBOfMergedInvoke});
2935 return II->getOperand(U.getOperandNo()) != U.get();
2954 Invokes.
front()->getParent());
2962 if (!MergedDebugLoc)
2963 MergedDebugLoc =
II->getDebugLoc();
2971 OrigSuccBB->removePredecessor(
II->getParent());
2977 assert(
Success &&
"Merged invokes with incompatible attributes");
2980 II->replaceAllUsesWith(MergedInvoke);
2981 II->eraseFromParent();
2985 ++NumInvokeSetsFormed;
3021 CompatibleSets Grouper;
3031 if (Invokes.
size() < 2)
3043class EphemeralValueTracker {
3044 SmallPtrSet<const Instruction *, 32> EphValues;
3046 bool isEphemeral(
const Instruction *
I) {
3049 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3050 all_of(
I->users(), [&](
const User *U) {
3051 return EphValues.count(cast<Instruction>(U));
3056 bool track(
const Instruction *
I) {
3057 if (isEphemeral(
I)) {
3110 unsigned MaxNumInstToLookAt = 9;
3114 if (!MaxNumInstToLookAt)
3116 --MaxNumInstToLookAt;
3129 if (
SI->getPointerOperand() == StorePtr &&
3130 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3131 SI->getAlign() >= StoreToHoist->
getAlign()) {
3133 PreviousAccess =
SI;
3134 return SI->getValueOperand();
3140 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3141 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3143 bool ExplicitlyDereferenceableOnly;
3151 (!ExplicitlyDereferenceableOnly ||
3155 PreviousAccess = LI;
3170 unsigned &SpeculatedInstructions,
3178 bool HaveRewritablePHIs =
false;
3180 Value *OrigV = PN.getIncomingValueForBlock(BB);
3181 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3188 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3197 HaveRewritablePHIs =
true;
3200 if (!OrigCE && !ThenCE)
3207 if (OrigCost + ThenCost > MaxCost)
3214 ++SpeculatedInstructions;
3215 if (SpeculatedInstructions > 1)
3219 return HaveRewritablePHIs;
3223 std::optional<bool> Invert,
3227 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3234 if (!Invert.has_value())
3237 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3241 return BIEndProb < Likely;
3281bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3282 BasicBlock *ThenBB) {
3293 bool Invert =
false;
3308 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3310 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3312 unsigned SpeculatedInstructions = 0;
3313 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3314 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3315 Value *SpeculatedStoreValue =
nullptr;
3316 StoreInst *SpeculatedStore =
nullptr;
3318 EphemeralValueTracker EphTracker;
3333 if (EphTracker.track(&
I))
3338 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3340 SpeculatedConditionalLoadsStores.
size() <
3344 if (IsSafeCheapLoadStore)
3345 SpeculatedConditionalLoadsStores.
push_back(&
I);
3347 ++SpeculatedInstructions;
3349 if (SpeculatedInstructions > 1)
3353 if (!IsSafeCheapLoadStore &&
3357 PreviousStoreAccess))))
3359 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3365 if (!SpeculatedStore && SpeculatedStoreValue)
3371 for (Use &
Op :
I.operands()) {
3376 ++SinkCandidateUseCounts[OpI];
3383 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3384 if (Inst->hasNUses(
Count)) {
3385 ++SpeculatedInstructions;
3386 if (SpeculatedInstructions > 1)
3393 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3396 SpeculatedInstructions,
Cost,
TTI);
3397 if (!Convert ||
Cost > Budget)
3401 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3406 if (SpeculatedStoreValue) {
3410 Value *FalseV = SpeculatedStoreValue;
3414 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3444 for (DbgVariableRecord *DbgAssign :
3447 DbgAssign->replaceVariableLocationOp(OrigV, S);
3457 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3459 I.dropUBImplyingAttrsAndMetadata();
3461 assert(PreviousStoreAccess &&
"Missing previous store access");
3464 I.dropUBImplyingAttrsAndMetadata();
3465 I.setAAMetadata(MergedAA);
3469 if (EphTracker.contains(&
I)) {
3471 I.eraseFromParent();
3477 for (
auto &It : *ThenBB)
3482 !DVR || !DVR->isDbgAssign())
3483 It.dropOneDbgRecord(&DR);
3485 std::prev(ThenBB->end()));
3487 if (!SpeculatedConditionalLoadsStores.
empty())
3493 for (PHINode &PN : EndBB->
phis()) {
3494 unsigned OrigI = PN.getBasicBlockIndex(BB);
3495 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3496 Value *OrigV = PN.getIncomingValue(OrigI);
3497 Value *ThenV = PN.getIncomingValue(ThenI);
3506 Value *TrueV = ThenV, *FalseV = OrigV;
3511 BrCond, TrueV, FalseV, PN.getFastMathFlagsOrNone(),
"spec.select", BI);
3512 PN.setIncomingValue(OrigI, V);
3513 PN.setIncomingValue(ThenI, V);
3517 for (Instruction *
I : SpeculatedPseudoProbes)
3518 I->eraseFromParent();
3531 if (!ReachesNonLocalUses.
insert(BB).second)
3550 if (!Header->hasNPredecessors(2))
3554 while (!Worklist.
empty()) {
3556 if (BB == Header || !Visited.
insert(BB).second)
3573 EphemeralValueTracker EphTracker;
3580 if (CI->cannotDuplicate() || CI->isConvergent())
3593 for (
User *U :
I.users()) {
3596 if (UsedInBB == BB) {
3600 NonLocalUseBlocks.
insert(UsedInBB);
3614 if (
I &&
I->getParent() == To)
3634 static constexpr unsigned MaxInstructionsToScan = 512;
3648 unsigned NumScannedInstructions = 0;
3649 while (!Worklist.
empty()) {
3653 if (!CanReachStop.
insert(BB).second)
3657 if (++NumScannedInstructions > MaxInstructionsToScan)
3661 BlocksWithUncontrolledConvergentCalls.
insert(BB);
3675 while (!Worklist.
empty()) {
3677 if (BB == StopBB || !CanReachStop.
contains(BB))
3680 if (!Visited.
insert(BB).second)
3683 if (BlocksWithUncontrolledConvergentCalls.
contains(BB))
3715 KnownValues[CB].
insert(Pred);
3719 if (KnownValues.
empty())
3744 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3747 for (
const auto &Pair : KnownValues) {
3764 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3767 if (KeepCanonicalLoop &&
3781 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3784 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3794 EdgeBB->setName(RealDest->
getName() +
".critedge");
3795 EdgeBB->moveBefore(RealDest);
3805 TranslateMap[
Cond] = CB;
3818 N->insertInto(EdgeBB, InsertPt);
3821 N->setName(BBI->getName() +
".c");
3832 if (!BBI->use_empty())
3833 TranslateMap[&*BBI] = V;
3834 if (!
N->mayHaveSideEffects()) {
3835 N->eraseFromParent();
3840 if (!BBI->use_empty())
3841 TranslateMap[&*BBI] =
N;
3847 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3848 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3849 SrcDbgCursor = std::next(BBI);
3851 N->cloneDebugInfoFrom(&*BBI);
3860 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3861 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3862 InsertPt->cloneDebugInfoFrom(BI);
3883 return std::nullopt;
3889bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3892 bool KeepCanonicalLoop =
3895 std::optional<bool>
Result;
3896 bool EverChanged =
false;
3902 }
while (Result == std::nullopt);
3911 bool SpeculateUnpredictables) {
3933 return isa<UncondBrInst>(IfBlock->getTerminator());
3936 "Will have either one or two blocks to speculate.");
3943 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3944 if (!IsUnpredictable) {
3947 (TWeight + FWeight) != 0) {
3952 if (IfBlocks.
size() == 1) {
3954 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3955 if (BIBBProb >= Likely)
3958 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3967 if (IfCondPhiInst->getParent() == BB)
3975 unsigned NumPhis = 0;
3988 if (SpeculateUnpredictables && IsUnpredictable)
3989 Budget +=
TTI.getBranchMispredictPenalty();
4002 AggressiveInsts, Cost, Budget,
TTI, AC,
4003 ZeroCostInstructions) ||
4005 AggressiveInsts, Cost, Budget,
TTI, AC,
4006 ZeroCostInstructions))
4019 auto IsBinOpOrAndEq = [](
Value *V) {
4055 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
4057 <<
" F: " << IfFalse->
getName() <<
"\n");
4074 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
4079 PN->eraseFromParent();
4085 Builder.CreateBr(BB);
4106 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
4107 if (
Opc == Instruction::And)
4108 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
4109 if (
Opc == Instruction::Or)
4110 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
4122 bool PredHasWeights =
4124 bool SuccHasWeights =
4126 if (PredHasWeights || SuccHasWeights) {
4127 if (!PredHasWeights)
4128 PredTrueWeight = PredFalseWeight = 1;
4129 if (!SuccHasWeights)
4130 SuccTrueWeight = SuccFalseWeight = 1;
4140static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
4143 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
4145 "PredBB must be a predecessor of BB.");
4153 (PTWeight + PFWeight) != 0) {
4156 Likely =
TTI->getPredictableBranchThreshold();
4161 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4162 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4166 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4169 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4170 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4176 return std::nullopt;
4189 bool InvertPredCond;
4190 std::tie(CommonSucc,
Opc, InvertPredCond) =
4193 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4201 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4206 if (InvertPredCond) {
4219 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4222 SuccTrueWeight, SuccFalseWeight)) {
4228 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4233 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4234 PredTrueWeight * SuccFalseWeight);
4240 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4241 PredFalseWeight * SuccTrueWeight);
4243 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4286 if (!MDWeights.
empty()) {
4287 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4295 ++NumFoldBranchToCommonDest;
4302 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4303 return U->getType()->isVectorTy();
4314 unsigned BonusInstThreshold) {
4323 Cond->getParent() != BB || !
Cond->hasOneUse())
4344 bool InvertPredCond;
4346 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4357 Cost +=
TTI->getArithmeticInstrCost(Instruction::Xor, Ty, CostKind);
4378 unsigned NumBonusInsts = 0;
4379 bool SawVectorOp =
false;
4380 const unsigned PredCount = Preds.
size();
4384 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4402 if (!
TTI ||
TTI->getInstructionCost(&
I, CostKind) !=
4404 NumBonusInsts += PredCount;
4412 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4415 return PN->getIncomingBlock(U) == BB;
4416 return UI->
getParent() == BB &&
I.comesBefore(UI);
4420 if (!
all_of(
I.uses(), IsBCSSAUse))
4424 BonusInstThreshold *
4440 for (
auto *BB : {BB1, BB2}) {
4456 Value *AlternativeV =
nullptr) {
4482 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4483 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4491 if (!AlternativeV &&
4497 PHI->addIncoming(V, BB);
4507 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4516 if (!PStore || !QStore)
4539 if (
I.mayReadOrWriteMemory())
4541 for (
auto &
I : *QFB)
4542 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4545 for (
auto &
I : *QTB)
4546 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4550 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4564 for (
auto &
I : *BB) {
4566 if (
I.isTerminator())
4584 "When we run out of budget we will eagerly return from within the "
4585 "per-instruction loop.");
4589 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4591 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4592 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4626 InvertPCond ^= (PStore->
getParent() != PTB);
4627 InvertQCond ^= (QStore->
getParent() != QTB);
4647 {CombinedWeights[0], CombinedWeights[1]},
4654 SI->copyMetadata(*QStore);
4660 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4663 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4726 bool InvertPCond =
false, InvertQCond =
false;
4732 if (QFB == PostBB) {
4751 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4754 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4762 for (
auto *BB : {PTB, PFB}) {
4767 PStoreAddresses.
insert(
SI->getPointerOperand());
4769 for (
auto *BB : {QTB, QFB}) {
4774 QStoreAddresses.
insert(
SI->getPointerOperand());
4780 auto &CommonAddresses = PStoreAddresses;
4783 for (
auto *Address : CommonAddresses)
4786 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4804 !BI->
getParent()->getSinglePredecessor())
4806 if (!IfFalseBB->
phis().empty())
4816 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4890 if (&*BB->
begin() != BI)
4918 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4920 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4924 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4927 if (CommonDestProb >= Likely)
4937 unsigned NumPhis = 0;
4959 if (OtherDest == BB) {
4967 OtherDest = InfLoopBlock;
4979 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4983 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4987 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
5002 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
5003 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
5006 SuccTrueWeight, SuccFalseWeight);
5008 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
5009 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
5010 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
5011 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
5015 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
5016 PredOther * SuccCommon,
5017 PredOther * SuccOther};
5024 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
5026 assert(
SI->getCondition() == PBICond);
5043 Value *BIV = PN.getIncomingValueForBlock(BB);
5044 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
5045 Value *PBIV = PN.getIncomingValue(PBBIdx);
5049 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
5050 PN.setIncomingValue(PBBIdx, NV);
5054 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
5055 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
5075bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
5077 BasicBlock *FalseBB,
5078 uint32_t TrueWeight,
5079 uint32_t FalseWeight) {
5086 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
5088 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
5091 for (BasicBlock *Succ :
successors(OldTerm)) {
5093 if (Succ == KeepEdge1)
5094 KeepEdge1 =
nullptr;
5095 else if (Succ == KeepEdge2)
5096 KeepEdge2 =
nullptr;
5101 if (Succ != TrueBB && Succ != FalseBB)
5102 RemovedSuccessors.
insert(Succ);
5110 if (!KeepEdge1 && !KeepEdge2) {
5111 if (TrueBB == FalseBB) {
5122 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
5142 SmallVector<DominatorTree::UpdateType, 2> Updates;
5144 for (
auto *RemovedSuccessor : RemovedSuccessors)
5145 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
5160bool SimplifyCFGOpt::simplifySwitchOnSelectRemap(SwitchInst *SI,
5162 ConstantInt *
C,
bool Negate) {
5173 BasicBlock *DestFork =
SI->findCaseValue(K)->getCaseSuccessor();
5174 auto CaseC =
SI->findCaseValue(
C);
5175 bool IsDefault = CaseC ==
SI->case_default();
5177 BasicBlock *OldDest = CaseC->getCaseSuccessor();
5182 SI->setCondition(
X);
5184 if (OldDest != DestFork) {
5188 SI->addCase(
C, DestFork);
5190 CaseC->setSuccessor(DestFork);
5197 bool OldDestStillTargeted =
any_of(
5198 successors(SI), [&](BasicBlock *Succ) {
return Succ == OldDest; });
5199 if (DTU && !OldDestStillTargeted)
5200 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
5205 SmallVector<uint32_t> SwitchWeights;
5213 bool SelectHasBranchWeights =
5218 if (SwitchHasBranchWeights && SelectHasBranchWeights &&
5226 SmallVector<uint64_t> NewSwitchWeights;
5227 NewSwitchWeights.reserve(SwitchWeights.
size());
5228 NewSwitchWeights.push_back(SwitchWeights[0] * SelectTotalWeight);
5229 for (
const auto &[SwitchCase, SwitchWeight] :
5231 if (SwitchCase.getCaseValue() ==
C) {
5233 }
else if (SwitchCase.getCaseValue() == K) {
5237 uint64_t ProbabilityKeyEqualsK = SwitchWeight * SelectTotalWeight;
5240 ProbabilityKeyEqualsK > ProbabilityXEqualsC
5241 ? ProbabilityKeyEqualsK - ProbabilityXEqualsC
5243 NewSwitchWeights.push_back(ProbabilityXEqualsK);
5245 NewSwitchWeights.push_back(SwitchWeight * SelectTotalWeight);
5249 }
else if (SwitchHasBranchWeights) {
5255 SI->setMetadata(LLVMContext::MD_prof,
nullptr);
5269bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
5274 if (
Select->hasOneUse() &&
5278 simplifySwitchOnSelectRemap(SI,
Select,
X,
C, Pred == ICmpInst::ICMP_NE))
5284 if (!TrueVal || !FalseVal)
5289 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
5290 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5293 uint32_t TrueWeight = 0, FalseWeight = 0;
5294 SmallVector<uint64_t, 8> Weights;
5298 if (Weights.
size() == 1 +
SI->getNumCases()) {
5300 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5302 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5307 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5316bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5330 SmallVector<uint32_t> SelectBranchWeights(2);
5333 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5334 SelectBranchWeights[0],
5335 SelectBranchWeights[1]);
5355bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5359 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5405bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5424 ConstantInt *NewCaseVal;
5432 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5438 SelectTrueVal = Builder.
getTrue();
5439 SelectFalseVal = Builder.
getFalse();
5442 SelectCond =
Select->getCondition();
5444 if (SelectCond != ICI)
5446 SelectTrueVal =
Select->getTrueValue();
5447 SelectFalseVal =
Select->getFalseValue();
5452 if (
SI->getCondition() != IcmpCond)
5458 if (
SI->getDefaultDest() != BB) {
5459 ConstantInt *VVal =
SI->findCaseDest(BB);
5460 assert(VVal &&
"Should have a unique destination value");
5468 return requestResimplify();
5474 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5476 if (Predicate == ICmpInst::ICMP_EQ)
5484 return requestResimplify();
5491 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5497 Value *DefaultCst = SelectFalseVal;
5498 Value *NewCst = SelectTrueVal;
5506 Select->replaceAllUsesWith(DefaultCst);
5507 Select->eraseFromParent();
5513 SmallVector<DominatorTree::UpdateType, 2> Updates;
5520 SwitchInstProfUpdateWrapper SIW(*SI);
5521 auto W0 = SIW.getSuccessorWeight(0);
5525 SIW.setSuccessorWeight(0, *NewW);
5527 SIW.addCase(NewCaseVal, NewBB, NewW);
5529 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5538 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5546bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5548 const DataLayout &
DL) {
5558 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5560 SmallVectorImpl<ConstantInt *> &
Values = ConstantCompare.Vals;
5561 Value *CompVal = ConstantCompare.CompValue;
5562 unsigned UsedICmps = ConstantCompare.UsedICmps;
5563 Value *ExtraCase = ConstantCompare.Extra;
5564 bool TrueWhenEqual = ConstantCompare.IsEq;
5581 if (ExtraCase &&
Values.size() < 2)
5584 SmallVector<uint32_t> BranchWeights;
5590 if (!TrueWhenEqual) {
5593 std::swap(BranchWeights[0], BranchWeights[1]);
5599 <<
" cases into SWITCH. BB is:\n"
5602 SmallVector<DominatorTree::UpdateType, 2> Updates;
5609 nullptr,
"switch.early.test");
5620 AssumptionCache *AC =
Options.AC;
5626 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5633 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5639 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5640 <<
"\nEXTRABB = " << *BB);
5648 "Should not end up here with unstable pointers");
5650 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5655 if (
Values.front()->getValue() -
Values.back()->getValue() ==
5658 Values.back()->getValue(),
Values.front()->getValue() + 1);
5660 ICmpInst::Predicate Pred;
5672 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5673 NewBI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5678 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5679 New->setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5684 SmallVector<uint32_t> NewWeights(
Values.size() + 1);
5685 NewWeights[0] = BranchWeights[1];
5688 V = BranchWeights[0] /
Values.size();
5695 for (ConstantInt *Val :
Values)
5696 New->addCase(Val, EdgeBB);
5704 for (
unsigned i = 0, e =
Values.size() - 1; i != e; ++i)
5714 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5718bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5720 return simplifyCommonResume(RI);
5724 return simplifySingleResume(RI);
5733 if (!
II ||
II->getIntrinsicID() != Intrinsic::lifetime_end)
5740bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5749 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5753 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues(); Idx !=
End;
5755 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5756 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5760 if (IncomingBB->getUniqueSuccessor() != BB)
5765 if (IncomingValue != LandingPad)
5769 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5770 TrivialUnwindBlocks.
insert(IncomingBB);
5774 if (TrivialUnwindBlocks.
empty())
5778 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5782 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5785 for (BasicBlock *Pred :
5796 TrivialBB->getTerminator()->eraseFromParent();
5797 new UnreachableInst(RI->
getContext(), TrivialBB);
5799 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5806 return !TrivialUnwindBlocks.empty();
5810bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5814 "Resume must unwind the exception that caused control to here");
5870 int Idx = DestPN.getBasicBlockIndex(BB);
5884 Value *SrcVal = DestPN.getIncomingValue(Idx);
5887 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5891 DestPN.addIncoming(Incoming, Pred);
5918 std::vector<DominatorTree::UpdateType> Updates;
5922 if (UnwindDest ==
nullptr) {
5963 if (!SuccessorCleanupPad)
5972 SuccessorCleanupPad->eraseFromParent();
5981bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5998bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
6030 BBI->dropDbgRecords();
6034 BBI->eraseFromParent();
6040 if (&BB->
front() != UI)
6043 std::vector<DominatorTree::UpdateType> Updates;
6046 for (BasicBlock *Predecessor : Preds) {
6054 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6065 "The destinations are guaranteed to be different here.");
6082 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6084 SwitchInstProfUpdateWrapper SU(*SI);
6085 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
6086 if (i->getCaseSuccessor() != BB) {
6091 i = SU.removeCase(i);
6096 if (DTU &&
SI->getDefaultDest() != BB)
6097 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6099 if (
II->getUnwindDest() == BB) {
6105 if (!CI->doesNotThrow())
6106 CI->setDoesNotThrow();
6110 if (CSI->getUnwindDest() == BB) {
6121 E = CSI->handler_end();
6124 CSI->removeHandler(
I);
6131 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6132 if (CSI->getNumHandlers() == 0) {
6133 if (CSI->hasUnwindDest()) {
6137 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
6138 Updates.push_back({DominatorTree::Insert,
6139 PredecessorOfPredecessor,
6140 CSI->getUnwindDest()});
6141 Updates.push_back({DominatorTree::Delete,
6142 PredecessorOfPredecessor, Predecessor});
6145 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
6152 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
6153 for (BasicBlock *EHPred : EHPreds)
6157 new UnreachableInst(CSI->getContext(), CSI->getIterator());
6158 CSI->eraseFromParent();
6163 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
6164 "Expected to always have an unwind to BB.");
6166 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6194static std::optional<ContiguousCasesResult>
6201 const APInt &Min = Cases.
back()->getValue();
6202 const APInt &Max = Cases.
front()->getValue();
6204 size_t ContiguousOffset = Cases.
size() - 1;
6205 if (
Offset == ContiguousOffset) {
6224 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
6225 return L->getValue() != R->getValue() + 1;
6227 if (It == Cases.
end())
6228 return std::nullopt;
6229 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
6230 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
6234 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
6237 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
6245 return std::nullopt;
6250 bool RemoveOrigDefaultBlock =
true) {
6252 auto *BB = Switch->getParent();
6253 auto *OrigDefaultBlock = Switch->getDefaultDest();
6254 if (RemoveOrigDefaultBlock)
6255 OrigDefaultBlock->removePredecessor(BB);
6259 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
6261 Switch->setDefaultDest(&*NewDefaultBlock);
6265 if (RemoveOrigDefaultBlock &&
6275bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
6277 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6279 bool HasDefault = !
SI->defaultDestUnreachable();
6281 auto *BB =
SI->getParent();
6283 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6288 for (
auto Case :
SI->cases()) {
6292 if (Dest == DestA) {
6298 if (Dest == DestB) {
6308 "Single-destination switch should have been folded.");
6310 assert(DestB !=
SI->getDefaultDest());
6311 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6315 std::optional<ContiguousCasesResult> ContiguousCases;
6318 if (!HasDefault && CasesA.
size() == 1)
6319 ContiguousCases = ContiguousCasesResult{
6327 else if (CasesB.
size() == 1)
6328 ContiguousCases = ContiguousCasesResult{
6337 else if (!HasDefault)
6341 if (!ContiguousCases)
6345 if (!ContiguousCases)
6348 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6354 Max->getValue() - Min->getValue() + 1);
6357 assert(
Max->getValue() == Min->getValue());
6362 else if (NumCases->
isNullValue() && !Cases->empty()) {
6366 if (!
Offset->isNullValue())
6374 SmallVector<uint64_t, 8> Weights;
6376 if (Weights.
size() == 1 +
SI->getNumCases()) {
6379 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6380 if (
SI->getSuccessor(
I) == Dest)
6381 TrueWeight += Weights[
I];
6383 FalseWeight += Weights[
I];
6385 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6396 unsigned PreviousEdges = Cases->size();
6397 if (Dest ==
SI->getDefaultDest())
6399 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6400 PHI.removeIncomingValue(
SI->getParent());
6403 unsigned PreviousEdges = OtherCases->size();
6404 if (OtherDest ==
SI->getDefaultDest())
6406 unsigned E = PreviousEdges - 1;
6410 for (
unsigned I = 0;
I !=
E; ++
I)
6411 PHI.removeIncomingValue(
SI->getParent());
6415 SmallVector<DominatorTree::UpdateType, 2> Updates;
6419 Updates.
push_back({DominatorTree::Delete, BB, OrigDefaultBlock});
6423 SI->eraseFromParent();
6426 Updates.
push_back({DominatorTree::Delete, BB, OtherDest});
6446 unsigned MaxSignificantBitsInCond =
6453 for (
const auto &Case :
SI->cases()) {
6454 auto *
Successor = Case.getCaseSuccessor();
6463 if (
Known.Zero.intersects(CaseVal) || !
Known.One.isSubsetOf(CaseVal) ||
6465 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6471 }
else if (IsKnownValuesValid)
6472 KnownValues.
erase(CaseC);
6479 bool HasDefault = !
SI->defaultDestUnreachable();
6480 const unsigned NumUnknownBits =
6483 if (HasDefault && DeadCases.
empty()) {
6489 if (NumUnknownBits < 64 ) {
6490 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6491 if (
SI->getNumCases() == AllNumCases) {
6498 if (
SI->getNumCases() == AllNumCases - 1) {
6499 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6501 if (CondTy->getIntegerBitWidth() > 64 ||
6502 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6506 for (
const auto &Case :
SI->cases())
6507 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6509 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6511 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6521 if (DeadCases.
empty())
6527 assert(CaseI !=
SI->case_default() &&
6528 "Case was not found. Probably mistake in DeadCases forming.");
6530 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6535 std::vector<DominatorTree::UpdateType> Updates;
6536 for (
auto *
Successor : UniqueSuccessors)
6537 if (NumPerSuccessorCases[
Successor] == 0)
6564 int Idx =
PHI.getBasicBlockIndex(BB);
6565 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6567 Value *InValue =
PHI.getIncomingValue(Idx);
6568 if (InValue != CaseValue)
6584 ForwardingNodesMap ForwardingNodes;
6587 for (
const auto &Case :
SI->cases()) {
6589 BasicBlock *CaseDest = Case.getCaseSuccessor();
6608 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6609 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6610 count(Phi.blocks(), SwitchBlock) == 1) {
6611 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6619 ForwardingNodes[Phi].push_back(PhiIdx);
6622 for (
auto &ForwardingNode : ForwardingNodes) {
6623 PHINode *Phi = ForwardingNode.first;
6629 for (
int Index : Indexes)
6630 Phi->setIncomingValue(Index,
SI->getCondition());
6640 if (
C->isThreadDependent())
6642 if (
C->isDLLImportDependent())
6650 if (
C->getType()->isScalableTy())
6661 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6688 if (
A->isAllOnesValue())
6690 if (
A->isNullValue())
6696 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6721 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6723 if (
I.isTerminator()) {
6725 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6728 CaseDest =
I.getSuccessor(0);
6735 for (
auto &
Use :
I.uses()) {
6738 if (
I->getParent() == CaseDest)
6741 if (Phi->getIncomingBlock(
Use) == CaseDest)
6754 *CommonDest = CaseDest;
6756 if (CaseDest != *CommonDest)
6761 int Idx =
PHI.getBasicBlockIndex(Pred);
6770 Res.push_back(std::make_pair(&
PHI, ConstVal));
6773 return Res.
size() > 0;
6779 SwitchCaseResultVectorTy &UniqueResults,
6781 for (
auto &
I : UniqueResults) {
6782 if (
I.first == Result) {
6783 I.second.push_back(CaseVal);
6784 return I.second.size();
6787 UniqueResults.push_back(
6798 SwitchCaseResultVectorTy &UniqueResults,
6802 for (
const auto &
I :
SI->cases()) {
6816 const size_t NumCasesForResult =
6824 if (UniqueResults.size() > MaxUniqueResults)
6840 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6842 return DefaultResult ||
SI->defaultDestUnreachable();
6863 const bool HasBranchWeights = !BranchWeights.
empty();
6865 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6866 ResultVector[1].second.size() == 1) {
6867 ConstantInt *FirstCase = ResultVector[0].second[0];
6868 ConstantInt *SecondCase = ResultVector[1].second[0];
6869 Value *SelectValue = ResultVector[1].first;
6870 if (DefaultResult) {
6871 Value *ValueCompare =
6872 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6873 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6874 DefaultResult,
"switch.select");
6876 SI && HasBranchWeights) {
6883 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6887 Value *ValueCompare =
6888 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6889 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6890 SelectValue,
"switch.select");
6896 size_t FirstCasePos = (Condition !=
nullptr);
6897 size_t SecondCasePos = FirstCasePos + 1;
6898 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6900 {BranchWeights[FirstCasePos],
6901 DefaultCase + BranchWeights[SecondCasePos]},
6908 if (ResultVector.size() == 1 && DefaultResult) {
6910 unsigned CaseCount = CaseValues.
size();
6923 for (
auto *Case : CaseValues) {
6924 if (Case->getValue().slt(MinCaseVal->
getValue()))
6926 AndMask &= Case->getValue();
6930 if (!AndMask.
isZero() &&
Known.getMaxValue().uge(AndMask)) {
6932 unsigned FreeBits =
Known.countMaxActiveBits() - AndMask.
popcount();
6936 if (FreeBits ==
Log2_32(CaseCount)) {
6937 Value *
And = Builder.CreateAnd(Condition, AndMask);
6938 Value *Cmp = Builder.CreateICmpEQ(
6941 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6957 for (
auto *Case : CaseValues)
6958 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6964 Condition = Builder.CreateSub(Condition, MinCaseVal);
6965 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6966 Value *Cmp = Builder.CreateICmpEQ(
6969 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6982 if (CaseValues.
size() == 2) {
6983 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6984 "switch.selectcmp.case1");
6985 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6986 "switch.selectcmp.case2");
6987 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6989 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
7009 std::vector<DominatorTree::UpdateType> Updates;
7016 Builder.CreateBr(DestBB);
7020 PHI->removeIncomingValueIf(
7021 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
7022 PHI->addIncoming(SelectValue, SelectBB);
7025 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
7031 if (DTU && RemovedSuccessors.
insert(Succ).second)
7034 SI->eraseFromParent();
7048 SwitchCaseResultVectorTy UniqueResults;
7054 assert(
PHI !=
nullptr &&
"PHI for value select not found");
7055 Builder.SetInsertPoint(
SI);
7057 [[maybe_unused]]
auto HasWeights =
7061 (BranchWeights.
size() >=
7062 UniqueResults.size() + (DefaultResult !=
nullptr)));
7065 Builder,
DL, BranchWeights);
7077class SwitchReplacement {
7085 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7086 Constant *DefaultValue,
const DataLayout &
DL,
7087 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
7096 static bool wouldFitInRegister(
const DataLayout &
DL,
uint64_t TableSize,
7103 bool isLookupTable();
7109 bool isValid()
const {
return Kind != InvalidKind; }
7146 ConstantInt *BitMap =
nullptr;
7147 IntegerType *BitMapElementTy =
nullptr;
7150 ConstantInt *LinearOffset =
nullptr;
7151 ConstantInt *LinearMultiplier =
nullptr;
7152 bool LinearMapValWrapped =
false;
7160SwitchReplacement::SwitchReplacement(
7162 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7163 Constant *DefaultValue,
const DataLayout &
DL,
7164 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
7165 : DefaultValue(DefaultValue) {
7166 assert(
Values.size() &&
"Can't build lookup table without values!");
7167 assert(TableSize >=
Values.size() &&
"Can't fit values in table!");
7170 SingleValue =
Values.begin()->second;
7176 for (
const auto &[CaseVal, CaseRes] :
Values) {
7180 TableContents[
Idx] = CaseRes;
7187 if (
Values.size() < TableSize) {
7189 "Need a default value to fill the lookup table holes.");
7192 if (!TableContents[
I])
7193 TableContents[
I] = DefaultValue;
7199 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
7200 SingleValue =
nullptr;
7206 Kind = SingleValueKind;
7213 bool LinearMappingPossible =
true;
7218 bool NonMonotonic =
false;
7219 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
7235 LinearMappingPossible =
false;
7240 APInt Dist = Val - PrevVal;
7243 }
else if (Dist != DistToPrev) {
7244 LinearMappingPossible =
false;
7252 if (LinearMappingPossible) {
7254 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
7255 APInt M = LinearMultiplier->getValue();
7256 bool MayWrap =
true;
7257 if (
isIntN(M.getBitWidth(), TableSize - 1))
7258 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
7259 LinearMapValWrapped = NonMonotonic || MayWrap;
7260 Kind = LinearMapKind;
7267 if (wouldFitInRegister(
DL, TableSize,
ValueType) &&
7270 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
7272 TableInt <<=
IT->getBitWidth();
7276 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
7279 BitMap = ConstantInt::get(M.getContext(), TableInt);
7280 BitMapElementTy =
IT;
7286 if (!
all_of(TableContents,
7298 unsigned NeededBitWidth =
7299 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7312 Kind = LookupTableKind;
7320 case SingleValueKind:
7322 case LinearMapKind: {
7326 false,
"switch.idx.cast");
7327 if (!LinearMultiplier->
isOne())
7328 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7330 !LinearMapValWrapped);
7332 if (!LinearOffset->
isZero())
7335 !LinearMapValWrapped);
7352 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7353 "switch.shiftamt",
true,
true);
7356 Value *DownShifted =
7357 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7359 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7361 case LookupTableKind: {
7364 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7365 true, GlobalVariable::PrivateLinkage,
7366 Initializer,
"switch.table." +
Func->getName());
7367 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7371 Type *IndexTy =
DL.getIndexType(
Table->getType());
7374 if (
Index->getType() != IndexTy) {
7375 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7379 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7382 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7386 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7395bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7397 Type *ElementType) {
7405 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7407 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7413 if (
TTI.isTypeLegal(Ty))
7428 DL.fitsInLegalInteger(
IT->getBitWidth());
7431Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7433bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7435bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7442 const uint64_t MinDensity = OptSize ? 40 : 10;
7447 return NumCases * 100 >= CaseRange * MinDensity;
7459static std::optional<unsigned>
7462 assert(
Values.size() > 1 &&
"expected multiple switch cases");
7464 return std::nullopt;
7469 for (
auto &V : ReducedValues) {
7471 ReducedValuesOr |= Reduced;
7472 V = (int64_t)Reduced;
7485 for (
auto &V : ReducedValues)
7486 V = (int64_t)((
uint64_t)V >> Shift);
7489 return std::nullopt;
7503 if (
SI->getNumCases() > TableSize)
7506 bool AllTablesFitInRegister =
true;
7507 bool HasIllegalType =
false;
7508 for (
const auto &Ty : ResultTypes) {
7513 AllTablesFitInRegister =
7514 AllTablesFitInRegister &&
7515 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7520 if (HasIllegalType && !AllTablesFitInRegister)
7525 if (AllTablesFitInRegister)
7533 SI->getFunction()->hasOptSize());
7543 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7546 return all_of(ResultTypes, [&](
const auto &ResultType) {
7547 return SwitchReplacement::wouldFitInRegister(
7597 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7602 for (
auto ValuePair :
Values) {
7605 if (!CaseConst || CaseConst == DefaultConst ||
7606 (CaseConst != TrueConst && CaseConst != FalseConst))
7620 if (DefaultConst == FalseConst) {
7623 ++NumTableCmpReuses;
7626 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7627 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7630 ++NumTableCmpReuses;
7640 bool ConvertSwitchToLookupTable) {
7641 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7655 if (
SI->getNumCases() < 3)
7677 MinCaseVal = CaseVal;
7679 MaxCaseVal = CaseVal;
7696 It->second.push_back(std::make_pair(CaseVal,
Value));
7705 &CommonDest, DefaultResultsList,
DL);
7706 for (
const auto &
I : DefaultResultsList) {
7709 DefaultResults[
PHI] = Result;
7713 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7716 if (UseSwitchConditionAsTableIndex) {
7718 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7723 TableIndexOffset = MinCaseVal;
7730 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7732 bool TableHasHoles = (NumResults < TableSize);
7737 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7745 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7748 if (
SI->getNumCases() < 4)
7750 if (!
DL.fitsInLegalInteger(TableSize))
7759 if (UseSwitchConditionAsTableIndex) {
7760 TableIndex =
SI->getCondition();
7761 if (HasDefaultResults) {
7773 all_of(ResultTypes, [&](
const auto &ResultType) {
7774 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7779 TableSize = std::max(UpperBound, TableSize);
7782 DefaultIsReachable =
false;
7790 const auto &ResultList = ResultLists[
PHI];
7792 Type *ResultType = ResultList.begin()->second->getType();
7797 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7798 ResultList, DefaultVal,
DL,
TTI, FuncName);
7799 if (!Replacement.isValid())
7801 PhiToReplacementMap.
insert({
PHI, Replacement});
7804 bool AnyLookupTables =
any_of(
7805 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7806 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7807 [](
auto &KV) {
return KV.second.isBitMap(); });
7815 if (AnyLookupTables &&
7816 (!
TTI.shouldBuildLookupTables() ||
7822 if (!ConvertSwitchToLookupTable &&
7823 (AnyLookupTables || AnyBitMaps || NeedMask))
7826 Builder.SetInsertPoint(
SI);
7829 if (!UseSwitchConditionAsTableIndex) {
7832 bool MayWrap =
true;
7833 if (!DefaultIsReachable) {
7838 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7839 "switch.tableidx",
false,
7843 std::vector<DominatorTree::UpdateType> Updates;
7849 assert(MaxTableSize >= TableSize &&
7850 "It is impossible for a switch to have more entries than the max "
7851 "representable value of its input integer type's size.");
7856 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7861 Builder.SetInsertPoint(
SI);
7862 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7863 const bool IsFullyCoveredLookupTable =
7864 !DefaultIsReachable || GeneratingCoveredLookupTable;
7865 if (IsFullyCoveredLookupTable) {
7866 Builder.CreateBr(LookupBB);
7872 Value *Cmp = Builder.CreateICmpULT(
7873 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7875 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7876 CondBranch = RangeCheckBranch;
7882 Builder.SetInsertPoint(LookupBB);
7888 MaskBB->
setName(
"switch.hole_check");
7895 APInt MaskInt(TableSizePowOf2, 0);
7896 APInt One(TableSizePowOf2, 1);
7898 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7899 for (
const auto &Result : ResultList) {
7902 MaskInt |= One << Idx;
7904 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7911 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7912 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7913 Value *LoBit = Builder.CreateTrunc(
7915 if (!IsFullyCoveredLookupTable)
7917 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7922 Builder.SetInsertPoint(LookupBB);
7926 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7929 SI->getDefaultDest()->removePredecessor(BB,
7936 const ResultListTy &ResultList = ResultLists[
PHI];
7937 auto Replacement = PhiToReplacementMap.
at(
PHI);
7938 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7941 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7944 for (
auto *
User :
PHI->users()) {
7946 Replacement.getDefaultValue(), ResultList);
7950 PHI->addIncoming(Result, LookupBB);
7953 Builder.CreateBr(CommonDest);
7958 const bool HasBranchWeights =
7965 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7968 if (Succ ==
SI->getDefaultDest()) {
7969 if (HasBranchWeights)
7970 ToDefaultWeight += BranchWeights[
I];
7974 if (DTU && RemovedSuccessors.
insert(Succ).second)
7976 if (HasBranchWeights)
7977 ToLookupWeight += BranchWeights[
I];
7979 SI->eraseFromParent();
7984 if ((NeedMask && !IsFullyCoveredLookupTable) &&
7987 else if (HasBranchWeights)
7994 ++NumLookupTablesHoles;
8010 if (CondTy->getIntegerBitWidth() > 64 ||
8011 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8015 if (
SI->getNumCases() < 4)
8023 for (
const auto &
C :
SI->cases())
8024 Values.push_back(
C.getCaseValue()->getValue().getSExtValue());
8028 bool OptSize =
SI->getFunction()->hasOptSize();
8035 std::optional<unsigned> Shift;
8065 Builder.SetInsertPoint(
SI);
8069 Value *Rot = Builder.CreateIntrinsic(
8070 Ty, Intrinsic::fshl,
8071 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - *Shift)});
8072 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
8074 for (
auto Case :
SI->cases()) {
8075 auto *Orig = Case.getCaseValue();
8076 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
8121 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
8122 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
8139 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
8142 return !Updates.
empty();
8162 if (
SI->defaultDestUnreachable())
8173 if (!
Known.isConstant())
8180 ConstantInt::get(
SI->getContext(),
Known.getConstant());
8182 if (CaseIt ==
SI->case_default()) {
8191 SI->case_default());
8193 assert(
SI->getNumCases() > 0 &&
"Switch should have at least one case");
8194 assert(
SI->findCaseValue(CaseVal) !=
SI->case_default() &&
8195 "Proven value should have a dedicated case");
8196 assert(
SI->defaultDestUnreachable());
8214 Value *Condition =
SI->getCondition();
8218 if (CondTy->getIntegerBitWidth() > 64 ||
8219 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8231 if (
SI->getNumCases() < 4)
8236 for (
const auto &Case :
SI->cases()) {
8237 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
8239 Values.push_back(CaseValue);
8249 SI->getFunction()->hasOptSize()))
8253 Builder.SetInsertPoint(
SI);
8255 if (!
SI->defaultDestUnreachable()) {
8258 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
8259 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
8261 auto *OrigBB =
SI->getParent();
8262 auto *DefaultCaseBB =
SI->getDefaultDest();
8264 auto It = OrigBB->getTerminator()->getIterator();
8276 NewWeights[1] = Weights[0] / 2;
8277 NewWeights[0] = OrigDenominator - NewWeights[1];
8289 Weights[0] = NewWeights[1];
8290 uint64_t CasesDenominator = OrigDenominator - Weights[0];
8292 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
8298 It->eraseFromParent();
8306 for (
auto &Case :
SI->cases()) {
8307 auto *OrigValue = Case.getCaseValue();
8308 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
8309 OrigValue->getValue().countr_zero()));
8313 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
8316 SI->setCondition(ConditionTrailingZeros);
8326 if (!Cmp || !Cmp->hasOneUse())
8337 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
8340 if (
SI->getNumCases() == 2) {
8347 Succ =
SI->getDefaultDest();
8348 SuccWeight = Weights[0];
8350 for (
auto &Case :
SI->cases()) {
8351 std::optional<int64_t> Val =
8355 if (!Missing.erase(*Val))
8360 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
8363 assert(Missing.size() == 1 &&
"Should have one case left");
8364 Res = *Missing.begin();
8365 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
8367 Unreachable =
SI->getDefaultDest();
8369 for (
auto &Case :
SI->cases()) {
8370 BasicBlock *NewSucc = Case.getCaseSuccessor();
8371 uint32_t Weight = Weights[Case.getSuccessorIndex()];
8374 OtherSuccWeight += Weight;
8377 SuccWeight = Weight;
8378 }
else if (Succ == NewSucc) {
8384 for (
auto &Case :
SI->cases()) {
8385 std::optional<int64_t> Val =
8387 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8389 if (Case.getCaseSuccessor() == Succ) {
8411 if (Cmp->isSigned())
8414 MDNode *NewWeights =
nullptr;
8420 Builder.SetInsertPoint(
SI->getIterator());
8421 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
8422 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8423 SI->getMetadata(LLVMContext::MD_unpredictable));
8427 SI->eraseFromParent();
8428 Cmp->eraseFromParent();
8429 if (DTU && Unreachable)
8454 assert(
BB &&
"Expected non-null BB");
8456 if (
BB->isEntryBlock())
8469 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8474 if (&
BB->front() != &
BB->back())
8489 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8500 return (*EBW->PhiPredIVs)[&Phi][BB];
8522 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8525 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8526 return PredIVs[
A] == PredIVs[
B];
8535 if (Candidates.
size() < 2)
8550 assert(Succ &&
"Expected unconditional BB");
8560 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8563 for (
auto &
IV : Phi->incoming_values())
8564 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8582 bool MadeChange =
false;
8596 if (!LivePreds.
contains(PredOfDead))
8603 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8604 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8609 T->replaceSuccessorWith(
Dead, Live);
8614 for (
const auto &EBW : BBs2Merge) {
8617 const auto &[It, Inserted] =
Keep.insert(&EBW);
8626 if (KeepBB == DeadBB)
8630 RedirectIncomingEdges(DeadBB, KeepBB);
8639 if (DTU && !Updates.
empty())
8645bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8646 DomTreeUpdater *DTU) {
8648 SmallSetVector<BasicBlock *, 16> FilteredArms(
8654bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8655 DomTreeUpdater *DTU) {
8666 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8672bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8675 if (isValueEqualityComparison(SI)) {
8679 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8680 return requestResimplify();
8684 if (simplifySwitchOnSelect(SI,
Select))
8685 return requestResimplify();
8689 if (SI == &*BB->
begin())
8690 if (foldValueComparisonIntoPredecessors(SI, Builder))
8691 return requestResimplify();
8697 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8698 return requestResimplify();
8702 return requestResimplify();
8705 return requestResimplify();
8708 return requestResimplify();
8711 return requestResimplify();
8716 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8718 Options.ConvertSwitchToLookupTable))
8719 return requestResimplify();
8722 return requestResimplify();
8725 return requestResimplify();
8728 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8729 return requestResimplify();
8733 if (simplifyDuplicateSwitchArms(SI, DTU))
8734 return requestResimplify();
8737 return requestResimplify();
8740 return requestResimplify();
8745bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8748 SmallVector<uint32_t> BranchWeights;
8751 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8752 if (HasBranchWeights)
8757 SmallPtrSet<Value *, 8> Succs;
8758 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8763 RemovedSuccs.
insert(Dest);
8773 std::vector<DominatorTree::UpdateType> Updates;
8774 Updates.reserve(RemovedSuccs.
size());
8775 for (
auto *RemovedSucc : RemovedSuccs)
8776 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8793 if (HasBranchWeights) {
8800 if (simplifyIndirectBrOnSelect(IBI, SI))
8801 return requestResimplify();
8833 if (BB == OtherPred)
8846 Value *V = PN.getIncomingValueForBlock(BB);
8847 Value *V2 = PN.getIncomingValueForBlock(OtherPred);
8848 return V == V2 || (V == LPad && V2 == LPad2);
8856 return PN.getIncomingValueForBlock(BB) == LPad;
8861 std::vector<DominatorTree::UpdateType> Updates;
8868 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8869 "unexpected successor");
8870 II->setUnwindDest(OtherPred);
8885 Builder.CreateUnreachable();
8894bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8906 bool NeedCanonicalLoop =
8920 if (
I->isTerminator() &&
8921 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8945 if (!PPred || (PredPred && PredPred != PPred))
8986 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8990 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
9020 bool HasWeight =
false;
9025 BBTWeight = BBFWeight = 1;
9030 BB1TWeight = BB1FWeight = 1;
9035 BB2TWeight = BB2FWeight = 1;
9037 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
9038 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
9045bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
9049 "Tautological conditional branch should have been eliminated already.");
9052 if (!
Options.SimplifyCondBranch ||
9057 if (isValueEqualityComparison(BI)) {
9062 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
9063 return requestResimplify();
9067 for (
auto &
I : *BB) {
9072 if (foldValueComparisonIntoPredecessors(BI, Builder))
9073 return requestResimplify();
9079 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
9092 return requestResimplify();
9098 if (
Options.SpeculateBlocks &&
9101 return requestResimplify();
9110 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
9111 return requestResimplify();
9113 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
9115 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
9116 auto CanSpeculateConditionalLoadsStores = [&]() {
9118 for (Instruction &
I : *Succ) {
9119 if (
I.isTerminator()) {
9120 if (
I.getNumSuccessors() > 1)
9124 SpeculatedConditionalLoadsStores.
size() ==
9128 SpeculatedConditionalLoadsStores.
push_back(&
I);
9131 return !SpeculatedConditionalLoadsStores.
empty();
9134 if (CanSpeculateConditionalLoadsStores()) {
9136 std::nullopt,
nullptr);
9137 return requestResimplify();
9147 return requestResimplify();
9156 return requestResimplify();
9162 if (foldCondBranchOnValueKnownInPredecessor(BI))
9163 return requestResimplify();
9170 return requestResimplify();
9178 return requestResimplify();
9182 return requestResimplify();
9189 assert(V->getType() ==
I->getType() &&
"Mismatched types");
9201 auto *Use = cast<Instruction>(U.getUser());
9204 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
9207 switch (Use->getOpcode()) {
9210 case Instruction::GetElementPtr:
9211 case Instruction::Ret:
9212 case Instruction::BitCast:
9213 case Instruction::Load:
9214 case Instruction::Store:
9215 case Instruction::Call:
9216 case Instruction::CallBr:
9217 case Instruction::Invoke:
9218 case Instruction::UDiv:
9219 case Instruction::URem:
9223 case Instruction::SDiv:
9224 case Instruction::SRem:
9228 if (FindUse ==
I->use_end())
9230 auto &
Use = *FindUse;
9244 if (
GEP->getPointerOperand() ==
I) {
9247 if (
GEP->getType()->isVectorTy())
9255 if (!
GEP->hasAllZeroIndices() &&
9256 (!
GEP->isInBounds() ||
9258 GEP->getPointerAddressSpace())))
9259 PtrValueMayBeModified =
true;
9265 bool HasNoUndefAttr =
9266 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
9271 if (
C->isNullValue() && HasNoUndefAttr &&
9272 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
9273 return !PtrValueMayBeModified;
9279 if (!LI->isVolatile())
9281 LI->getPointerAddressSpace());
9285 if (!
SI->isVolatile())
9287 SI->getPointerAddressSpace())) &&
9288 SI->getPointerOperand() ==
I;
9293 if (
I == Assume->getArgOperand(0))
9301 if (CB->getCalledOperand() ==
I)
9304 if (CB->isArgOperand(&
Use)) {
9305 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
9308 CB->paramHasNonNullAttr(ArgIdx,
false))
9309 return !PtrValueMayBeModified;
9328 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
9336 Builder.CreateUnreachable();
9337 T->eraseFromParent();
9349 Builder.CreateUnreachable();
9356 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
9358 Assumption = Builder.CreateAssumption(
Cond);
9373 Builder.SetInsertPoint(Unreachable);
9375 Builder.CreateUnreachable();
9376 for (
const auto &Case :
SI->cases())
9377 if (Case.getCaseSuccessor() == BB) {
9379 Case.setSuccessor(Unreachable);
9381 if (
SI->getDefaultDest() == BB) {
9383 SI->setDefaultDest(Unreachable);
9397bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9422 return requestResimplify();
9441 if (simplifyDuplicatePredecessors(BB, DTU))
9445 if (
Options.SpeculateBlocks &&
9452 Options.SpeculateUnpredictables))
9460 case Instruction::UncondBr:
9463 case Instruction::CondBr:
9466 case Instruction::Resume:
9469 case Instruction::CleanupRet:
9472 case Instruction::Switch:
9475 case Instruction::Unreachable:
9478 case Instruction::IndirectBr:
9486bool SimplifyCFGOpt::run(BasicBlock *BB) {
9496 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
static bool IsIndirectCall(const MachineInstr *MI)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
static cl::opt< uint32_t > SelectFalseWeight("profcheck-default-select-false-weight", cl::init(3U), cl::desc("When annotating `select` instructions, this value will be used " "for the second ('false') case."))
static cl::opt< uint32_t > SelectTrueWeight("profcheck-default-select-true-weight", cl::init(2U), cl::desc("When annotating `select` instructions, this value will be used " "for the first ('true') case."))
SmallVector< MachineOperand, 4 > Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange, bool OptSize)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool isProfitableToSpeculate(const CondBrInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(CondBrInst *BI, CondBrInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool reachesUncontrolledConvergentCallBeforeBlock(BasicBlock *From, BasicBlock *StopBB)
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static bool isSafeToThreadThroughLoopHeader(BasicBlock *Header, ArrayRef< BasicBlock * > PredBBs, BasicBlock *RealDest)
Return true if threading PredBBs through Header to RealDest eliminates the loop's single backedge.
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static void hoistConditionalLoadsStores(CondBrInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool simplifySwitchDefaultBranch(SwitchInst *SI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool extractPredSuccWeights(CondBrInst *PBI, CondBrInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static bool performBranchToCommonDestFolding(CondBrInst *BI, CondBrInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static std::optional< unsigned > getDenseSwitchRangeReductionShift(ArrayRef< int64_t > Values, int64_t Base, bool OptSize)
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool mergeConditionalStores(CondBrInst *PBI, CondBrInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeNestedCondBranch(CondBrInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool tryWidenCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool mergeIdenticalBBs(ArrayRef< BasicBlock * > Candidates, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static bool tryToMergeLandingPad(LandingPadInst *LPad, UncondBrInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, uintptr_t MaxUniqueResults)
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB, Instruction *&PreviousAccess)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool SimplifyCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isUncontrolledConvergentCall(CallBase *CB)
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool KeepCanonicalLoop)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, CondBrInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & front() const
Get the first element.
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasTerminator() const LLVM_READONLY
Returns whether the block has a terminator.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrPseudoProbe() const
Returns an iterator to the first instruction in this block that is not a PHINode or a pseudo operatio...
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isConvergent() const
Determine if the invoke is convergent.
Value * getConvergenceControlToken() const
Return the convergence control token for this call, if it exists.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
bool isEquality() const
Determine if this is an equals/not equals predicate.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Conditional Branch instruction.
static CondBrInst * Create(Value *Cond, BasicBlock *IfTrue, BasicBlock *IfFalse, InsertPosition InsertBefore=nullptr)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setCondition(Value *V)
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
ConstantFP - Floating Point Values [float, double].
ConstantFolder - Create constants with minimum, target independent, folding.
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
A constant pointer value that points to null.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
iterator find(const_arg_type_t< KeyT > Val)
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
void reserve(size_type NumEntries)
Grow the DenseMap so that it can contain at least NumEntries items before resizing again.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Implements a dense probed hash-table based set.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
LLVM_ABI CallInst * CreateAssumption(Value *Cond)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
UncondBrInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
LLVM_ABI void dropLocation()
Drop the instruction's debug location.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
iterator_range< user_iterator > users()
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
void insert_range(Range &&R)
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this store instruction.
Value * getPointerOperand()
Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Unconditional Branch instruction.
void setSuccessor(BasicBlock *NewSucc)
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i=0) const
'undef' values are things that do not have specified contents.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
LLVM_ABI bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
auto m_UMin(const Opnd0 &Op0, const Opnd1 &Op1)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
LLVM_ABI bool foldBranchToCommonDest(CondBrInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, AssumptionCache *AC=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > MaxLoopHeaderThreadingSearchBlocks("simplifycfg-max-loop-header-threading-search", cl::Hidden, cl::init(1024), cl::desc("Limit number of blocks searched to prove that threading through " "a loop header keeps the loop canonical"))
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
RelativeUniformCounterPtr Values
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
@ Known
Known to have no common set bits.
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
@ Load
The value being inserted comes from a load (InsertElement only).
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Function *CtxF=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr detail::StaticCastFunc< To > StaticCastTo
Function objects corresponding to the Cast types defined above.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI CondBrInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
LLVM_ABI void InvertBranch(CondBrInst *PBI, IRBuilderBase &Builder)
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible immediate values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
auto succ_size(const MachineBasicBlock *BB)
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
static cl::opt< unsigned > MaxJumpThreadingLiveBlocks("max-jump-threading-live-blocks", cl::Hidden, cl::init(24), cl::desc("Limit number of blocks a define in a threaded block is allowed " "to be live in"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
LLVM_ABI bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< T1, 2 > &B1, const SmallVector< T2, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Constant * ConstantFoldCastInstruction(unsigned opcode, Constant *V, Type *DestTy)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const SimplifyQuery &Q, bool IgnoreFree=false)
Equivalent to isDereferenceableAndAlignedPointer with an alignment of 1.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
@ Keep
No function return thunk.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, const SimplifyQuery &SQ, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two BBs are equal depends on the contents of the BasicBlock and the incoming values ...
SmallDenseMap< BasicBlock *, Value *, 8 > BB2ValueMap
DenseMap< PHINode *, BB2ValueMap > Phi2IVsMap
static bool canBeMerged(const BasicBlock *BB)
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static bool isEqual(const EqualBBWrapper *LHS, const EqualBBWrapper *RHS)
static unsigned getHashValue(const EqualBBWrapper *EBW)
An information struct used to provide DenseMap with the various necessary components for a given valu...
A MapVector that performs no allocations if smaller than a certain size.