96#define DEBUG_TYPE "simplifycfg"
101 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
104 "Temporary development switch used to gradually uplift SimplifyCFG "
105 "into preserving DomTree,"));
114 "Control the amount of phi node folding to perform (default = 2)"));
118 cl::desc(
"Control the maximal total instruction cost that we are willing "
119 "to speculatively execute to fold a 2-entry PHI node into a "
120 "select (default = 4)"));
124 cl::desc(
"Hoist common instructions up to the parent block"));
128 cl::desc(
"Hoist loads if the target supports conditional faulting"));
132 cl::desc(
"Hoist stores if the target supports conditional faulting"));
136 cl::desc(
"Control the maximal conditional load/store that we are willing "
137 "to speculatively execute to eliminate conditional branch "
143 cl::desc(
"Allow reordering across at most this many "
144 "instructions when hoisting"));
148 cl::desc(
"Sink common instructions down to the end block"));
152 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
156 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
157 "precede - hoist multiple conditional stores into a single "
158 "predicated store"));
162 cl::desc(
"When merging conditional stores, do so even if the resultant "
163 "basic blocks are unlikely to be if-converted as a result"));
167 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
172 cl::desc(
"Limit maximum recursion depth when calculating costs of "
173 "speculatively executed instructions"));
178 cl::desc(
"Max size of a block which is still considered "
179 "small enough to thread through"));
185 cl::desc(
"Maximum cost of combining conditions when "
186 "folding branches"));
189 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
191 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
192 "to fold branch to common destination when vector operations are "
197 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
201 cl::desc(
"Limit cases to analyze when converting a switch to select"));
205 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
212STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
214 "Number of switch instructions turned into linear mapping");
216 "Number of switch instructions turned into lookup tables");
218 NumLookupTablesHoles,
219 "Number of switch instructions turned into lookup tables (holes checked)");
220STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
222 "Number of value comparisons folded into predecessor basic blocks");
224 "Number of branches folded into predecessor basic block");
227 "Number of common instruction 'blocks' hoisted up to the begin block");
229 "Number of common instructions hoisted up to the begin block");
231 "Number of common instruction 'blocks' sunk down to the end block");
233 "Number of common instructions sunk down to the end block");
234STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
236 "Number of invokes with empty resume blocks simplified into calls");
237STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
238STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
245using SwitchCaseResultVectorTy =
254struct ValueEqualityComparisonCase {
266 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
269class SimplifyCFGOpt {
270 const TargetTransformInfo &TTI;
272 const DataLayout &DL;
274 const SimplifyCFGOptions &Options;
277 Value *isValueEqualityComparison(Instruction *TI);
279 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
280 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
283 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
286 bool foldValueComparisonIntoPredecessors(Instruction *TI,
289 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
290 bool simplifySingleResume(ResumeInst *RI);
291 bool simplifyCommonResume(ResumeInst *RI);
292 bool simplifyCleanupReturn(CleanupReturnInst *RI);
293 bool simplifyUnreachable(UnreachableInst *UI);
294 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
295 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
296 bool simplifyIndirectBr(IndirectBrInst *IBI);
297 bool simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
298 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
299 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
301 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
303 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
306 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
307 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
308 Instruction *TI, Instruction *I1,
309 SmallVectorImpl<Instruction *> &OtherSuccTIs,
311 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
312 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
313 BasicBlock *TrueBB, BasicBlock *FalseBB,
314 uint32_t TrueWeight, uint32_t FalseWeight);
315 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
316 const DataLayout &DL);
317 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
318 bool simplifySwitchOnSelectRemap(SwitchInst *SI, SelectInst *
Select,
Value *
X,
319 ConstantInt *
C,
bool Negate);
320 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
321 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
322 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
325 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
327 const SimplifyCFGOptions &Opts)
328 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
329 assert((!DTU || !DTU->hasPostDomTree()) &&
330 "SimplifyCFG is not yet capable of maintaining validity of a "
331 "PostDomTree, so don't ask for it.");
334 bool simplifyOnce(BasicBlock *BB);
335 bool run(BasicBlock *BB);
338 bool requestResimplify() {
348isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
368 "Only for a pair of incoming blocks at the time!");
374 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
375 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
378 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
379 EquivalenceSet->contains(IV1))
402 if (!SI1Succs.
count(Succ))
408 FailBlocks->insert(Succ);
424 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
426 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
427 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
489 if (AggressiveInsts.
count(
I))
505 ZeroCostInstructions.
insert(OverflowInst);
507 }
else if (!ZeroCostInstructions.
contains(
I))
523 for (
Use &
Op :
I->operands())
525 TTI, AC, ZeroCostInstructions,
Depth + 1))
542 if (
DL.hasUnstableRepresentation(V->getType()))
551 return ConstantInt::get(
IntPtrTy, 0);
556 if (CE->getOpcode() == Instruction::IntToPtr)
580struct ConstantComparesGatherer {
581 const DataLayout &DL;
584 Value *CompValue =
nullptr;
587 Value *Extra =
nullptr;
593 unsigned UsedICmps = 0;
599 bool IgnoreFirstMatch =
false;
600 bool MultipleMatches =
false;
603 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
605 if (CompValue || !MultipleMatches)
610 IgnoreFirstMatch =
true;
614 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
615 ConstantComparesGatherer &
616 operator=(
const ConstantComparesGatherer &) =
delete;
621 bool setValueOnce(
Value *NewVal) {
622 if (IgnoreFirstMatch) {
623 IgnoreFirstMatch =
false;
626 if (CompValue && CompValue != NewVal) {
627 MultipleMatches =
true;
641 bool matchInstruction(Instruction *
I,
bool isEQ) {
648 if (!setValueOnce(Val))
668 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
712 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
714 if (!setValueOnce(RHSVal))
719 ConstantInt::get(
C->getContext(),
720 C->getValue() | Mask));
735 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
737 if (!setValueOnce(RHSVal))
741 Vals.push_back(ConstantInt::get(
C->getContext(),
742 C->getValue() & ~Mask));
763 Value *CandidateVal =
I->getOperand(0);
766 CandidateVal = RHSVal;
781 if (!setValueOnce(CandidateVal))
787 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
799 void gather(
Value *V) {
808 SmallVector<Value *, 8> DFT{Op0, Op1};
809 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
811 while (!DFT.
empty()) {
818 if (Visited.
insert(Op1).second)
820 if (Visited.
insert(Op0).second)
827 if (matchInstruction(
I, IsEq))
871 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
872 CV =
SI->getCondition();
874 if (BI->getCondition()->hasOneUse()) {
879 if (Trunc->hasNoUnsignedWrap())
880 CV = Trunc->getOperand(0);
887 Value *Ptr = PTII->getPointerOperand();
888 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
890 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
899BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
900 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
902 Cases.reserve(
SI->getNumCases());
903 for (
auto Case :
SI->cases())
904 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
905 Case.getCaseSuccessor()));
906 return SI->getDefaultDest();
911 ICmpInst::Predicate Pred;
917 Pred = ICmpInst::ICMP_NE;
922 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
930 std::vector<ValueEqualityComparisonCase> &Cases) {
936 std::vector<ValueEqualityComparisonCase> &C2) {
937 std::vector<ValueEqualityComparisonCase> *
V1 = &C1, *V2 = &C2;
940 if (
V1->size() > V2->size())
945 if (
V1->size() == 1) {
948 for (
const ValueEqualityComparisonCase &
VECC : *V2)
949 if (TheVal ==
VECC.Value)
956 unsigned i1 = 0, i2 = 0, e1 =
V1->size(), e2 = V2->size();
957 while (i1 != e1 && i2 != e2) {
973bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
974 Instruction *TI, BasicBlock *Pred,
IRBuilder<> &Builder) {
979 Value *ThisVal = isValueEqualityComparison(TI);
980 assert(ThisVal &&
"This isn't a value comparison!!");
981 if (ThisVal != PredVal)
988 std::vector<ValueEqualityComparisonCase> PredCases;
990 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
994 std::vector<ValueEqualityComparisonCase> ThisCases;
995 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1010 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1016 ThisCases[0].Dest->removePredecessor(PredDef);
1019 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1026 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1033 SmallPtrSet<Constant *, 16> DeadCases;
1034 for (
const ValueEqualityComparisonCase &Case : PredCases)
1035 DeadCases.
insert(Case.Value);
1038 <<
"Through successor TI: " << *TI);
1040 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1043 auto *
Successor = i->getCaseSuccessor();
1046 if (DeadCases.
count(i->getCaseValue())) {
1055 std::vector<DominatorTree::UpdateType> Updates;
1056 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1058 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1068 ConstantInt *TIV =
nullptr;
1070 for (
const auto &[
Value, Dest] : PredCases)
1076 assert(TIV &&
"No edge from pred to succ?");
1081 for (
const auto &[
Value, Dest] : ThisCases)
1089 TheRealDest = ThisDef;
1091 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1096 if (Succ != CheckEdge) {
1097 if (Succ != TheRealDest)
1098 RemovedSuccs.
insert(Succ);
1101 CheckEdge =
nullptr;
1108 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1113 SmallVector<DominatorTree::UpdateType, 2> Updates;
1115 for (
auto *RemovedSucc : RemovedSuccs)
1116 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1127struct ConstantIntOrdering {
1128 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1129 return LHS->getValue().ult(
RHS->getValue());
1141 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1150 assert(MD &&
"Invalid branch-weight metadata");
1175 if (BonusInst.isTerminator())
1210 NewBonusInst->
takeName(&BonusInst);
1211 BonusInst.setName(NewBonusInst->
getName() +
".old");
1212 VMap[&BonusInst] = NewBonusInst;
1221 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1222 "If the user is not a PHI node, then it should be in the same "
1223 "block as, and come after, the original bonus instruction.");
1227 if (PN->getIncomingBlock(U) == BB)
1231 assert(PN->getIncomingBlock(U) == PredBlock &&
1232 "Not in block-closed SSA form?");
1233 U.set(NewBonusInst);
1243 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1244 PredDL.isSameSourceLocation(
DL)) {
1251bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1259 std::vector<ValueEqualityComparisonCase> BBCases;
1260 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1262 std::vector<ValueEqualityComparisonCase> PredCases;
1263 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1268 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1271 SmallVector<uint64_t, 8> Weights;
1275 if (PredHasWeights) {
1278 if (Weights.
size() != 1 + PredCases.size())
1279 PredHasWeights = SuccHasWeights =
false;
1280 }
else if (SuccHasWeights)
1284 Weights.
assign(1 + PredCases.size(), 1);
1286 SmallVector<uint64_t, 8> SuccWeights;
1287 if (SuccHasWeights) {
1290 if (SuccWeights.
size() != 1 + BBCases.size())
1291 PredHasWeights = SuccHasWeights =
false;
1292 }
else if (PredHasWeights)
1293 SuccWeights.
assign(1 + BBCases.size(), 1);
1295 if (PredDefault == BB) {
1298 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1299 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1300 if (PredCases[i].Dest != BB)
1301 PTIHandled.insert(PredCases[i].
Value);
1304 std::swap(PredCases[i], PredCases.back());
1306 if (PredHasWeights || SuccHasWeights) {
1308 Weights[0] += Weights[i + 1];
1313 PredCases.pop_back();
1319 if (PredDefault != BBDefault) {
1321 if (DTU && PredDefault != BB)
1322 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1323 PredDefault = BBDefault;
1324 ++NewSuccessors[BBDefault];
1327 unsigned CasesFromPred = Weights.
size();
1329 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1330 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1331 PredCases.push_back(BBCases[i]);
1332 ++NewSuccessors[BBCases[i].Dest];
1333 if (SuccHasWeights || PredHasWeights) {
1337 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1338 ValidTotalSuccWeight += SuccWeights[i + 1];
1342 if (SuccHasWeights || PredHasWeights) {
1343 ValidTotalSuccWeight += SuccWeights[0];
1345 for (
unsigned i = 1; i < CasesFromPred; ++i)
1346 Weights[i] *= ValidTotalSuccWeight;
1348 Weights[0] *= SuccWeights[0];
1354 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1355 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1356 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1357 if (PredCases[i].Dest == BB) {
1358 PTIHandled.insert(PredCases[i].
Value);
1360 if (PredHasWeights || SuccHasWeights) {
1361 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1366 std::swap(PredCases[i], PredCases.back());
1367 PredCases.pop_back();
1374 for (
const ValueEqualityComparisonCase &Case : BBCases)
1375 if (PTIHandled.count(Case.Value)) {
1377 if (PredHasWeights || SuccHasWeights)
1378 Weights.
push_back(WeightsForHandled[Case.Value]);
1379 PredCases.push_back(Case);
1380 ++NewSuccessors[Case.Dest];
1381 PTIHandled.erase(Case.Value);
1386 for (ConstantInt *
I : PTIHandled) {
1387 if (PredHasWeights || SuccHasWeights)
1389 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1390 ++NewSuccessors[BBDefault];
1397 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1402 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1404 for (
auto I :
seq(NewSuccessor.second)) {
1408 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1409 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1416 "Should not end up here with unstable pointers");
1422 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1424 for (ValueEqualityComparisonCase &V : PredCases)
1427 if (PredHasWeights || SuccHasWeights)
1439 if (!InfLoopBlock) {
1447 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1454 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1456 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1461 ++NumFoldValueComparisonIntoPredecessors;
1469bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1472 Value *CV = isValueEqualityComparison(TI);
1473 assert(CV &&
"Not a comparison?");
1478 while (!Preds.empty()) {
1487 Value *PCV = isValueEqualityComparison(PTI);
1491 SmallSetVector<BasicBlock *, 4> FailBlocks;
1493 for (
auto *Succ : FailBlocks) {
1499 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1513 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1514 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1515 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1537 if (
I->mayReadFromMemory())
1569 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1577 if (J->getParent() == BB)
1599 if (C1->isMustTailCall() != C2->isMustTailCall())
1602 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1608 if (CB1->cannotMerge() || CB1->isConvergent())
1611 if (CB2->cannotMerge() || CB2->isConvergent())
1626 if (!I1->hasDbgRecords())
1628 using CurrentAndEndIt =
1629 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1635 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1636 return Pair.first == Pair.second;
1642 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1648 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1650 if (!
Other->hasDbgRecords())
1653 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1660 while (
none_of(Itrs, atEnd)) {
1661 bool HoistDVRs = allIdentical(Itrs);
1662 for (CurrentAndEndIt &Pair : Itrs) {
1676 if (I1->isIdenticalToWhenDefined(I2,
true))
1681 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1682 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1683 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1685 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1686 return I1->getOperand(0) == I2->
getOperand(1) &&
1752 auto &Context = BI->
getParent()->getContext();
1757 Value *Mask =
nullptr;
1758 Value *MaskFalse =
nullptr;
1759 Value *MaskTrue =
nullptr;
1760 if (Invert.has_value()) {
1761 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1762 Mask = Builder.CreateBitCast(
1767 MaskFalse = Builder.CreateBitCast(
1769 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1771 auto PeekThroughBitcasts = [](
Value *V) {
1773 V = BitCast->getOperand(0);
1776 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1778 if (!Invert.has_value())
1779 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1784 auto *Op0 =
I->getOperand(0);
1785 CallInst *MaskedLoadStore =
nullptr;
1788 auto *Ty =
I->getType();
1790 Value *PassThru =
nullptr;
1791 if (Invert.has_value())
1792 for (
User *U :
I->users()) {
1794 PassThru = Builder.CreateBitCast(
1803 Builder.SetInsertPoint(Ins);
1806 MaskedLoadStore = Builder.CreateMaskedLoad(
1808 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1811 I->replaceAllUsesWith(NewLoadStore);
1814 auto *StoredVal = Builder.CreateBitCast(
1816 MaskedLoadStore = Builder.CreateMaskedStore(
1827 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1829 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1833 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1834 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1837 I->eraseFromParent();
1844 bool IsStore =
false;
1867bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1868 bool AllInstsEqOnly) {
1884 for (
auto *Succ : UniqueSuccessors) {
1900 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1902 for (
auto *Succ : UniqueSuccessors) {
1906 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1909 if (AllInstsEqOnly) {
1915 unsigned Size0 = UniqueSuccessors[0]->size();
1916 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1920 Succ->
size() == Size0;
1924 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1925 while (LRI.isValid()) {
1927 if (
any_of(*LRI, [I0](Instruction *
I) {
1941 unsigned NumSkipped = 0;
1944 if (SuccIterPairs.
size() > 2) {
1947 if (SuccIterPairs.
size() < 2)
1954 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1955 auto &BB1ItrPair = *SuccIterPairBegin++;
1956 auto OtherSuccIterPairRange =
1962 bool AllInstsAreIdentical =
true;
1963 bool HasTerminator =
I1->isTerminator();
1964 for (
auto &SuccIter : OtherSuccIterRange) {
1968 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1969 AllInstsAreIdentical =
false;
1972 SmallVector<Instruction *, 8> OtherInsts;
1973 for (
auto &SuccIter : OtherSuccIterRange)
1978 if (HasTerminator) {
1982 if (NumSkipped || !AllInstsAreIdentical) {
1987 return hoistSuccIdenticalTerminatorToSwitchOrIf(
1988 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
1992 if (AllInstsAreIdentical) {
1993 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1994 AllInstsAreIdentical =
1996 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1998 unsigned SkipFlagsBB2 = Pair.second;
2013 AllInstsAreIdentical && CI && CI->isMustTailCall()) {
2014 AllInstsAreIdentical =
2015 NumSkipped == 0 &&
all_of(SuccIterPairs, [](
const SuccIterPair &
P) {
2020 if (AllInstsAreIdentical) {
2030 for (
auto &SuccIter : OtherSuccIterRange) {
2038 assert(
Success &&
"We should not be trying to hoist callbases "
2039 "with non-intersectable attributes");
2051 NumHoistCommonCode += SuccIterPairs.
size();
2053 NumHoistCommonInstrs += SuccIterPairs.
size();
2062 for (
auto &SuccIterPair : SuccIterPairs) {
2071bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2072 Instruction *TI, Instruction *I1,
2073 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2083 auto *I2 = *OtherSuccTIs.
begin();
2103 for (PHINode &PN : Succ->
phis()) {
2104 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2105 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2106 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2126 if (!
NT->getType()->isVoidTy()) {
2127 I1->replaceAllUsesWith(NT);
2128 for (Instruction *OtherSuccTI : OtherSuccTIs)
2129 OtherSuccTI->replaceAllUsesWith(NT);
2133 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2139 for (
auto *OtherSuccTI : OtherSuccTIs)
2140 Locs.
push_back(OtherSuccTI->getDebugLoc());
2152 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2154 for (PHINode &PN : Succ->
phis()) {
2155 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2156 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2162 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2172 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2173 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2174 PN.setIncomingValue(i, SI);
2182 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
2186 if (DTU && VisitedSuccs.
insert(Succ).second)
2187 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2193 for (BasicBlock *Succ : UniqueSuccessors)
2194 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2208 if (
I->isIntDivRem())
2223 std::optional<unsigned> NumUses;
2224 for (
auto *
I : Insts) {
2227 I->getType()->isTokenTy())
2232 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2240 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2244 NumUses =
I->getNumUses();
2245 else if (NumUses !=
I->getNumUses())
2251 for (
auto *
I : Insts) {
2265 for (
const Use &U : I0->
uses()) {
2266 auto It = PHIOperands.find(&U);
2267 if (It == PHIOperands.end())
2270 if (!
equal(Insts, It->second))
2284 if (HaveIndirectCalls) {
2285 if (!AllCallsAreIndirect)
2289 Value *Callee =
nullptr;
2293 Callee = CurrCallee;
2294 else if (Callee != CurrCallee)
2300 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2306 if (!
all_of(Insts, SameAsI0)) {
2311 !
all_of(Insts, CanReplaceOperand))
2315 for (
auto *
I : Insts)
2316 Ops.push_back(
I->getOperand(OI));
2326 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2331 for (
auto *BB : Blocks) {
2333 I =
I->getPrevNode();
2358 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2361 PN->insertBefore(BBEnd->begin());
2362 for (
auto *
I : Insts)
2363 PN->addIncoming(
I->getOperand(O),
I->getParent());
2372 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2375 for (
auto *
I : Insts)
2389 assert(
Success &&
"We should not be trying to sink callbases "
2390 "with non-intersectable attributes");
2401 PN->replaceAllUsesWith(I0);
2402 PN->eraseFromParent();
2406 for (
auto *
I : Insts) {
2411 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2412 I->replaceAllUsesWith(I0);
2413 I->eraseFromParent();
2463 bool HaveNonUnconditionalPredecessors =
false;
2469 HaveNonUnconditionalPredecessors =
true;
2471 if (UnconditionalPreds.
size() < 2)
2484 for (
const Use &U : PN.incoming_values())
2485 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2486 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2488 Ops.push_back(*IncomingVals[Pred]);
2496 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2509 if (!followedByDeoptOrUnreachable) {
2511 auto IsMemOperand = [](
Use &U) {
2524 unsigned NumPHIInsts = 0;
2525 for (
Use &U : (*LRI)[0]->operands()) {
2526 auto It = PHIOperands.
find(&U);
2527 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2528 return InstructionsToSink.contains(V);
2535 if (IsMemOperand(U) &&
2536 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2543 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2544 return NumPHIInsts <= 1;
2561 while (Idx < ScanIdx) {
2562 if (!ProfitableToSinkInstruction(LRI)) {
2565 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2578 if (Idx < ScanIdx) {
2581 InstructionsToSink = InstructionsProfitableToSink;
2587 !ProfitableToSinkInstruction(LRI) &&
2588 "We already know that the last instruction is unprofitable to sink");
2596 for (
auto *
I : *LRI)
2597 InstructionsProfitableToSink.
erase(
I);
2598 if (!ProfitableToSinkInstruction(LRI)) {
2601 InstructionsToSink = InstructionsProfitableToSink;
2615 if (HaveNonUnconditionalPredecessors) {
2616 if (!followedByDeoptOrUnreachable) {
2624 bool Profitable =
false;
2625 while (Idx < ScanIdx) {
2659 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2661 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2669 NumSinkCommonInstrs++;
2673 ++NumSinkCommonCode;
2679struct CompatibleSets {
2680 using SetTy = SmallVector<InvokeInst *, 2>;
2686 SetTy &getCompatibleSet(InvokeInst *
II);
2688 void insert(InvokeInst *
II);
2691CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2696 for (CompatibleSets::SetTy &Set : Sets) {
2697 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2702 return Sets.emplace_back();
2705void CompatibleSets::insert(InvokeInst *
II) {
2706 getCompatibleSet(
II).emplace_back(
II);
2710 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2713 auto IsIllegalToMerge = [](InvokeInst *
II) {
2714 return II->cannotMerge() ||
II->isInlineAsm();
2716 if (
any_of(Invokes, IsIllegalToMerge))
2724 if (HaveIndirectCalls) {
2725 if (!AllCallsAreIndirect)
2730 for (InvokeInst *
II : Invokes) {
2731 Value *CurrCallee =
II->getCalledOperand();
2732 assert(CurrCallee &&
"There is always a called operand.");
2735 else if (Callee != CurrCallee)
2742 auto HasNormalDest = [](InvokeInst *
II) {
2745 if (
any_of(Invokes, HasNormalDest)) {
2748 if (!
all_of(Invokes, HasNormalDest))
2753 for (InvokeInst *
II : Invokes) {
2755 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2757 NormalBB = CurrNormalBB;
2758 else if (NormalBB != CurrNormalBB)
2766 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2775 for (InvokeInst *
II : Invokes) {
2777 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2779 UnwindBB = CurrUnwindBB;
2781 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2788 Invokes.front()->getUnwindDest(),
2789 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2794 const InvokeInst *II0 = Invokes.front();
2795 for (
auto *
II : Invokes.drop_front())
2800 auto IsIllegalToMergeArguments = [](
auto Ops) {
2801 Use &U0 = std::get<0>(
Ops);
2802 Use &U1 = std::get<1>(
Ops);
2808 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2809 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2810 IsIllegalToMergeArguments))
2822 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2828 bool HasNormalDest =
2833 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2837 II0->
getParent()->getIterator()->getNextNode();
2842 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2846 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2848 if (!HasNormalDest) {
2852 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2860 return MergedInvoke;
2874 SuccBBOfMergedInvoke});
2897 return II->getOperand(U.getOperandNo()) != U.get();
2916 Invokes.
front()->getParent());
2924 if (!MergedDebugLoc)
2925 MergedDebugLoc =
II->getDebugLoc();
2933 OrigSuccBB->removePredecessor(
II->getParent());
2939 assert(
Success &&
"Merged invokes with incompatible attributes");
2942 II->replaceAllUsesWith(MergedInvoke);
2943 II->eraseFromParent();
2947 ++NumInvokeSetsFormed;
2983 CompatibleSets Grouper;
2993 if (Invokes.
size() < 2)
3005class EphemeralValueTracker {
3006 SmallPtrSet<const Instruction *, 32> EphValues;
3008 bool isEphemeral(
const Instruction *
I) {
3011 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3012 all_of(
I->users(), [&](
const User *U) {
3013 return EphValues.count(cast<Instruction>(U));
3018 bool track(
const Instruction *
I) {
3019 if (isEphemeral(
I)) {
3070 unsigned MaxNumInstToLookAt = 9;
3074 if (!MaxNumInstToLookAt)
3076 --MaxNumInstToLookAt;
3089 if (
SI->getPointerOperand() == StorePtr &&
3090 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3093 return SI->getValueOperand();
3098 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3099 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3101 bool ExplicitlyDereferenceableOnly;
3109 (!ExplicitlyDereferenceableOnly ||
3127 unsigned &SpeculatedInstructions,
3135 bool HaveRewritablePHIs =
false;
3137 Value *OrigV = PN.getIncomingValueForBlock(BB);
3138 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3145 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3154 HaveRewritablePHIs =
true;
3157 if (!OrigCE && !ThenCE)
3164 if (OrigCost + ThenCost > MaxCost)
3171 ++SpeculatedInstructions;
3172 if (SpeculatedInstructions > 1)
3176 return HaveRewritablePHIs;
3180 std::optional<bool> Invert,
3184 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3191 if (!Invert.has_value())
3194 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3198 return BIEndProb < Likely;
3238bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3239 BasicBlock *ThenBB) {
3250 bool Invert =
false;
3265 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3267 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3269 unsigned SpeculatedInstructions = 0;
3270 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3271 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3272 Value *SpeculatedStoreValue =
nullptr;
3273 StoreInst *SpeculatedStore =
nullptr;
3274 EphemeralValueTracker EphTracker;
3289 if (EphTracker.track(&
I))
3294 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3296 SpeculatedConditionalLoadsStores.
size() <
3300 if (IsSafeCheapLoadStore)
3301 SpeculatedConditionalLoadsStores.
push_back(&
I);
3303 ++SpeculatedInstructions;
3305 if (SpeculatedInstructions > 1)
3309 if (!IsSafeCheapLoadStore &&
3312 (SpeculatedStoreValue =
3315 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3321 if (!SpeculatedStore && SpeculatedStoreValue)
3327 for (Use &
Op :
I.operands()) {
3332 ++SinkCandidateUseCounts[OpI];
3339 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3340 if (Inst->hasNUses(
Count)) {
3341 ++SpeculatedInstructions;
3342 if (SpeculatedInstructions > 1)
3349 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3352 SpeculatedInstructions,
Cost,
TTI);
3353 if (!Convert ||
Cost > Budget)
3357 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3362 if (SpeculatedStoreValue) {
3366 Value *FalseV = SpeculatedStoreValue;
3370 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3400 for (DbgVariableRecord *DbgAssign :
3403 DbgAssign->replaceVariableLocationOp(OrigV, S);
3413 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3416 I.dropUBImplyingAttrsAndMetadata();
3419 if (EphTracker.contains(&
I)) {
3421 I.eraseFromParent();
3427 for (
auto &It : *ThenBB)
3432 !DVR || !DVR->isDbgAssign())
3433 It.dropOneDbgRecord(&DR);
3435 std::prev(ThenBB->end()));
3437 if (!SpeculatedConditionalLoadsStores.
empty())
3443 for (PHINode &PN : EndBB->
phis()) {
3444 unsigned OrigI = PN.getBasicBlockIndex(BB);
3445 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3446 Value *OrigV = PN.getIncomingValue(OrigI);
3447 Value *ThenV = PN.getIncomingValue(ThenI);
3456 Value *TrueV = ThenV, *FalseV = OrigV;
3461 BrCond, TrueV, FalseV, PN.getFastMathFlagsOrNone(),
"spec.select", BI);
3462 PN.setIncomingValue(OrigI, V);
3463 PN.setIncomingValue(ThenI, V);
3467 for (Instruction *
I : SpeculatedPseudoProbes)
3468 I->eraseFromParent();
3481 if (!ReachesNonLocalUses.
insert(BB).second)
3496 EphemeralValueTracker EphTracker;
3503 if (CI->cannotDuplicate() || CI->isConvergent())
3516 for (
User *U :
I.users()) {
3519 if (UsedInBB == BB) {
3523 NonLocalUseBlocks.
insert(UsedInBB);
3537 if (
I &&
I->getParent() == To)
3557 static constexpr unsigned MaxInstructionsToScan = 512;
3571 unsigned NumScannedInstructions = 0;
3572 while (!Worklist.
empty()) {
3576 if (!CanReachStop.
insert(BB).second)
3580 if (++NumScannedInstructions > MaxInstructionsToScan)
3584 BlocksWithUncontrolledConvergentCalls.
insert(BB);
3598 while (!Worklist.
empty()) {
3600 if (BB == StopBB || !CanReachStop.
contains(BB))
3603 if (!Visited.
insert(BB).second)
3606 if (BlocksWithUncontrolledConvergentCalls.
contains(BB))
3638 KnownValues[CB].
insert(Pred);
3642 if (KnownValues.
empty())
3667 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3670 for (
const auto &Pair : KnownValues) {
3687 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3700 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3703 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3713 EdgeBB->setName(RealDest->
getName() +
".critedge");
3714 EdgeBB->moveBefore(RealDest);
3724 TranslateMap[
Cond] = CB;
3737 N->insertInto(EdgeBB, InsertPt);
3740 N->setName(BBI->getName() +
".c");
3751 if (!BBI->use_empty())
3752 TranslateMap[&*BBI] = V;
3753 if (!
N->mayHaveSideEffects()) {
3754 N->eraseFromParent();
3759 if (!BBI->use_empty())
3760 TranslateMap[&*BBI] =
N;
3766 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3767 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3768 SrcDbgCursor = std::next(BBI);
3770 N->cloneDebugInfoFrom(&*BBI);
3779 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3780 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3781 InsertPt->cloneDebugInfoFrom(BI);
3802 return std::nullopt;
3808bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3815 std::optional<bool>
Result;
3816 bool EverChanged =
false;
3822 }
while (Result == std::nullopt);
3831 bool SpeculateUnpredictables) {
3853 return isa<UncondBrInst>(IfBlock->getTerminator());
3856 "Will have either one or two blocks to speculate.");
3863 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3864 if (!IsUnpredictable) {
3867 (TWeight + FWeight) != 0) {
3872 if (IfBlocks.
size() == 1) {
3874 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3875 if (BIBBProb >= Likely)
3878 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3887 if (IfCondPhiInst->getParent() == BB)
3895 unsigned NumPhis = 0;
3908 if (SpeculateUnpredictables && IsUnpredictable)
3909 Budget +=
TTI.getBranchMispredictPenalty();
3922 AggressiveInsts, Cost, Budget,
TTI, AC,
3923 ZeroCostInstructions) ||
3925 AggressiveInsts, Cost, Budget,
TTI, AC,
3926 ZeroCostInstructions))
3939 auto IsBinOpOrAndEq = [](
Value *V) {
3962 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3975 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3977 <<
" F: " << IfFalse->
getName() <<
"\n");
3994 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
3999 PN->eraseFromParent();
4005 Builder.CreateBr(BB);
4026 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
4027 if (
Opc == Instruction::And)
4028 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
4029 if (
Opc == Instruction::Or)
4030 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
4042 bool PredHasWeights =
4044 bool SuccHasWeights =
4046 if (PredHasWeights || SuccHasWeights) {
4047 if (!PredHasWeights)
4048 PredTrueWeight = PredFalseWeight = 1;
4049 if (!SuccHasWeights)
4050 SuccTrueWeight = SuccFalseWeight = 1;
4060static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
4063 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
4065 "PredBB must be a predecessor of BB.");
4073 (PTWeight + PFWeight) != 0) {
4076 Likely =
TTI->getPredictableBranchThreshold();
4081 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4082 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4086 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4089 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4090 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4096 return std::nullopt;
4109 bool InvertPredCond;
4110 std::tie(CommonSucc,
Opc, InvertPredCond) =
4113 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4121 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4126 if (InvertPredCond) {
4139 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4142 SuccTrueWeight, SuccFalseWeight)) {
4148 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4153 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4154 PredTrueWeight * SuccFalseWeight);
4160 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4161 PredFalseWeight * SuccTrueWeight);
4163 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4205 if (!MDWeights.
empty()) {
4206 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4211 ++NumFoldBranchToCommonDest;
4218 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4219 return U->getType()->isVectorTy();
4230 unsigned BonusInstThreshold) {
4239 Cond->getParent() != BB || !
Cond->hasOneUse())
4260 bool InvertPredCond;
4262 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4294 unsigned NumBonusInsts = 0;
4295 bool SawVectorOp =
false;
4296 const unsigned PredCount = Preds.
size();
4300 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4320 NumBonusInsts += PredCount;
4328 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4331 return PN->getIncomingBlock(U) == BB;
4332 return UI->
getParent() == BB &&
I.comesBefore(UI);
4336 if (!
all_of(
I.uses(), IsBCSSAUse))
4340 BonusInstThreshold *
4356 for (
auto *BB : {BB1, BB2}) {
4372 Value *AlternativeV =
nullptr) {
4398 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4399 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4407 if (!AlternativeV &&
4413 PHI->addIncoming(V, BB);
4423 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4432 if (!PStore || !QStore)
4455 if (
I.mayReadOrWriteMemory())
4457 for (
auto &
I : *QFB)
4458 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4461 for (
auto &
I : *QTB)
4462 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4466 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4480 for (
auto &
I : *BB) {
4482 if (
I.isTerminator())
4500 "When we run out of budget we will eagerly return from within the "
4501 "per-instruction loop.");
4505 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4507 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4508 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4544 InvertPCond ^= (PStore->
getParent() != PTB);
4545 InvertQCond ^= (QStore->
getParent() != QTB);
4566 {CombinedWeights[0], CombinedWeights[1]},
4573 SI->copyMetadata(*QStore);
4579 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4582 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4645 bool InvertPCond =
false, InvertQCond =
false;
4651 if (QFB == PostBB) {
4670 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4673 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4681 for (
auto *BB : {PTB, PFB}) {
4686 PStoreAddresses.
insert(
SI->getPointerOperand());
4688 for (
auto *BB : {QTB, QFB}) {
4693 QStoreAddresses.
insert(
SI->getPointerOperand());
4699 auto &CommonAddresses = PStoreAddresses;
4702 for (
auto *Address : CommonAddresses)
4705 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4723 !BI->
getParent()->getSinglePredecessor())
4725 if (!IfFalseBB->
phis().empty())
4735 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4809 if (&*BB->
begin() != BI)
4837 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4839 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4843 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4846 if (CommonDestProb >= Likely)
4856 unsigned NumPhis = 0;
4878 if (OtherDest == BB) {
4886 OtherDest = InfLoopBlock;
4898 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
4902 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
4906 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4921 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4922 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4925 SuccTrueWeight, SuccFalseWeight);
4927 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4928 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4929 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4930 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4934 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4935 PredOther * SuccCommon,
4936 PredOther * SuccOther};
4944 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4946 assert(
SI->getCondition() == PBICond);
4963 Value *BIV = PN.getIncomingValueForBlock(BB);
4964 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
4965 Value *PBIV = PN.getIncomingValue(PBBIdx);
4969 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
4970 PN.setIncomingValue(PBBIdx, NV);
4974 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
4975 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
4995bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
4997 BasicBlock *FalseBB,
4998 uint32_t TrueWeight,
4999 uint32_t FalseWeight) {
5006 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
5008 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
5011 for (BasicBlock *Succ :
successors(OldTerm)) {
5013 if (Succ == KeepEdge1)
5014 KeepEdge1 =
nullptr;
5015 else if (Succ == KeepEdge2)
5016 KeepEdge2 =
nullptr;
5021 if (Succ != TrueBB && Succ != FalseBB)
5022 RemovedSuccessors.
insert(Succ);
5030 if (!KeepEdge1 && !KeepEdge2) {
5031 if (TrueBB == FalseBB) {
5042 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
5062 SmallVector<DominatorTree::UpdateType, 2> Updates;
5064 for (
auto *RemovedSuccessor : RemovedSuccessors)
5065 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
5080bool SimplifyCFGOpt::simplifySwitchOnSelectRemap(SwitchInst *SI,
5082 ConstantInt *
C,
bool Negate) {
5093 BasicBlock *DestFork =
SI->findCaseValue(K)->getCaseSuccessor();
5094 auto CaseC =
SI->findCaseValue(
C);
5095 bool IsDefault = CaseC ==
SI->case_default();
5097 BasicBlock *OldDest = CaseC->getCaseSuccessor();
5100 if (OldDest != DestFork) {
5102 SI->setMetadata(LLVMContext::MD_prof,
nullptr);
5106 SI->addCase(
C, DestFork);
5108 CaseC->setSuccessor(DestFork);
5115 bool OldDestStillTargeted =
any_of(
5116 successors(SI), [&](BasicBlock *Succ) {
return Succ == OldDest; });
5117 if (DTU && !OldDestStillTargeted)
5118 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
5123 SI->setCondition(
X);
5132bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
5137 if (
Select->hasOneUse() &&
5141 simplifySwitchOnSelectRemap(SI,
Select,
X,
C, Pred == ICmpInst::ICMP_NE))
5147 if (!TrueVal || !FalseVal)
5152 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
5153 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5156 uint32_t TrueWeight = 0, FalseWeight = 0;
5157 SmallVector<uint64_t, 8> Weights;
5161 if (Weights.
size() == 1 +
SI->getNumCases()) {
5163 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5165 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5170 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5179bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5193 SmallVector<uint32_t> SelectBranchWeights(2);
5197 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5198 SelectBranchWeights[0],
5199 SelectBranchWeights[1]);
5219bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5223 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5269bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5288 ConstantInt *NewCaseVal;
5296 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5302 SelectTrueVal = Builder.
getTrue();
5303 SelectFalseVal = Builder.
getFalse();
5306 SelectCond =
Select->getCondition();
5308 if (SelectCond != ICI)
5310 SelectTrueVal =
Select->getTrueValue();
5311 SelectFalseVal =
Select->getFalseValue();
5316 if (
SI->getCondition() != IcmpCond)
5322 if (
SI->getDefaultDest() != BB) {
5323 ConstantInt *VVal =
SI->findCaseDest(BB);
5324 assert(VVal &&
"Should have a unique destination value");
5332 return requestResimplify();
5338 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5340 if (Predicate == ICmpInst::ICMP_EQ)
5348 return requestResimplify();
5355 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5361 Value *DefaultCst = SelectFalseVal;
5362 Value *NewCst = SelectTrueVal;
5370 Select->replaceAllUsesWith(DefaultCst);
5371 Select->eraseFromParent();
5377 SmallVector<DominatorTree::UpdateType, 2> Updates;
5384 SwitchInstProfUpdateWrapper SIW(*SI);
5385 auto W0 = SIW.getSuccessorWeight(0);
5389 SIW.setSuccessorWeight(0, *NewW);
5391 SIW.addCase(NewCaseVal, NewBB, NewW);
5393 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5402 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5410bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5412 const DataLayout &
DL) {
5422 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5424 SmallVectorImpl<ConstantInt *> &
Values = ConstantCompare.Vals;
5425 Value *CompVal = ConstantCompare.CompValue;
5426 unsigned UsedICmps = ConstantCompare.UsedICmps;
5427 Value *ExtraCase = ConstantCompare.Extra;
5428 bool TrueWhenEqual = ConstantCompare.IsEq;
5445 if (ExtraCase &&
Values.size() < 2)
5448 SmallVector<uint32_t> BranchWeights;
5455 if (!TrueWhenEqual) {
5458 std::swap(BranchWeights[0], BranchWeights[1]);
5464 <<
" cases into SWITCH. BB is:\n"
5467 SmallVector<DominatorTree::UpdateType, 2> Updates;
5474 nullptr,
"switch.early.test");
5485 AssumptionCache *AC =
Options.AC;
5491 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5498 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5504 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5505 <<
"\nEXTRABB = " << *BB);
5513 "Should not end up here with unstable pointers");
5515 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5520 if (
Values.front()->getValue() -
Values.back()->getValue() ==
5523 Values.back()->getValue(),
Values.front()->getValue() + 1);
5525 ICmpInst::Predicate Pred;
5543 SmallVector<uint32_t> NewWeights(
Values.size() + 1);
5544 NewWeights[0] = BranchWeights[1];
5547 V = BranchWeights[0] /
Values.size();
5552 for (ConstantInt *Val :
Values)
5553 New->addCase(Val, EdgeBB);
5561 for (
unsigned i = 0, e =
Values.size() - 1; i != e; ++i)
5571 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5575bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5577 return simplifyCommonResume(RI);
5581 return simplifySingleResume(RI);
5594 switch (IntrinsicID) {
5595 case Intrinsic::dbg_declare:
5596 case Intrinsic::dbg_value:
5597 case Intrinsic::dbg_label:
5598 case Intrinsic::lifetime_end:
5608bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5617 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5621 for (
unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
5623 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5624 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5628 if (IncomingBB->getUniqueSuccessor() != BB)
5633 if (IncomingValue != LandingPad)
5637 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5638 TrivialUnwindBlocks.
insert(IncomingBB);
5642 if (TrivialUnwindBlocks.
empty())
5646 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5650 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5653 for (BasicBlock *Pred :
5664 TrivialBB->getTerminator()->eraseFromParent();
5665 new UnreachableInst(RI->
getContext(), TrivialBB);
5667 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5674 return !TrivialUnwindBlocks.empty();
5678bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5682 "Resume must unwind the exception that caused control to here");
5738 int Idx = DestPN.getBasicBlockIndex(BB);
5752 Value *SrcVal = DestPN.getIncomingValue(Idx);
5755 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5759 DestPN.addIncoming(Incoming, Pred);
5786 std::vector<DominatorTree::UpdateType> Updates;
5790 if (UnwindDest ==
nullptr) {
5831 if (!SuccessorCleanupPad)
5840 SuccessorCleanupPad->eraseFromParent();
5849bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
5866bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
5898 BBI->dropDbgRecords();
5902 BBI->eraseFromParent();
5908 if (&BB->
front() != UI)
5911 std::vector<DominatorTree::UpdateType> Updates;
5914 for (BasicBlock *Predecessor : Preds) {
5922 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5933 "The destinations are guaranteed to be different here.");
5934 CallInst *Assumption;
5950 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5952 SwitchInstProfUpdateWrapper SU(*SI);
5953 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5954 if (i->getCaseSuccessor() != BB) {
5959 i = SU.removeCase(i);
5964 if (DTU &&
SI->getDefaultDest() != BB)
5965 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5967 if (
II->getUnwindDest() == BB) {
5973 if (!CI->doesNotThrow())
5974 CI->setDoesNotThrow();
5978 if (CSI->getUnwindDest() == BB) {
5989 E = CSI->handler_end();
5992 CSI->removeHandler(
I);
5999 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6000 if (CSI->getNumHandlers() == 0) {
6001 if (CSI->hasUnwindDest()) {
6005 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
6006 Updates.push_back({DominatorTree::Insert,
6007 PredecessorOfPredecessor,
6008 CSI->getUnwindDest()});
6009 Updates.push_back({DominatorTree::Delete,
6010 PredecessorOfPredecessor, Predecessor});
6013 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
6020 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
6021 for (BasicBlock *EHPred : EHPreds)
6025 new UnreachableInst(CSI->getContext(), CSI->getIterator());
6026 CSI->eraseFromParent();
6031 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
6032 "Expected to always have an unwind to BB.");
6034 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6062static std::optional<ContiguousCasesResult>
6069 const APInt &Min = Cases.
back()->getValue();
6070 const APInt &Max = Cases.
front()->getValue();
6072 size_t ContiguousOffset = Cases.
size() - 1;
6073 if (
Offset == ContiguousOffset) {
6092 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
6093 return L->getValue() != R->getValue() + 1;
6095 if (It == Cases.
end())
6096 return std::nullopt;
6097 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
6098 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
6102 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
6105 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
6113 return std::nullopt;
6118 bool RemoveOrigDefaultBlock =
true) {
6120 auto *BB = Switch->getParent();
6121 auto *OrigDefaultBlock = Switch->getDefaultDest();
6122 if (RemoveOrigDefaultBlock)
6123 OrigDefaultBlock->removePredecessor(BB);
6127 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
6129 Switch->setDefaultDest(&*NewDefaultBlock);
6133 if (RemoveOrigDefaultBlock &&
6143bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
6145 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6147 bool HasDefault = !
SI->defaultDestUnreachable();
6149 auto *BB =
SI->getParent();
6151 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6156 for (
auto Case :
SI->cases()) {
6160 if (Dest == DestA) {
6166 if (Dest == DestB) {
6176 "Single-destination switch should have been folded.");
6178 assert(DestB !=
SI->getDefaultDest());
6179 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6183 std::optional<ContiguousCasesResult> ContiguousCases;
6186 if (!HasDefault && CasesA.
size() == 1)
6187 ContiguousCases = ContiguousCasesResult{
6195 else if (CasesB.
size() == 1)
6196 ContiguousCases = ContiguousCasesResult{
6205 else if (!HasDefault)
6209 if (!ContiguousCases)
6213 if (!ContiguousCases)
6216 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6222 Max->getValue() - Min->getValue() + 1);
6225 assert(
Max->getValue() == Min->getValue());
6230 else if (NumCases->
isNullValue() && !Cases->empty()) {
6234 if (!
Offset->isNullValue())
6242 SmallVector<uint64_t, 8> Weights;
6244 if (Weights.
size() == 1 +
SI->getNumCases()) {
6247 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6248 if (
SI->getSuccessor(
I) == Dest)
6249 TrueWeight += Weights[
I];
6251 FalseWeight += Weights[
I];
6253 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
6264 unsigned PreviousEdges = Cases->size();
6265 if (Dest ==
SI->getDefaultDest())
6267 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6268 PHI.removeIncomingValue(
SI->getParent());
6271 unsigned PreviousEdges = OtherCases->size();
6272 if (OtherDest ==
SI->getDefaultDest())
6274 unsigned E = PreviousEdges - 1;
6278 for (
unsigned I = 0;
I !=
E; ++
I)
6279 PHI.removeIncomingValue(
SI->getParent());
6283 SmallVector<DominatorTree::UpdateType, 2> Updates;
6287 Updates.
push_back({DominatorTree::Delete, BB, OrigDefaultBlock});
6291 SI->eraseFromParent();
6294 Updates.
push_back({DominatorTree::Delete, BB, OtherDest});
6314 unsigned MaxSignificantBitsInCond =
6321 for (
const auto &Case :
SI->cases()) {
6322 auto *
Successor = Case.getCaseSuccessor();
6331 if (
Known.Zero.intersects(CaseVal) || !
Known.One.isSubsetOf(CaseVal) ||
6333 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6339 }
else if (IsKnownValuesValid)
6340 KnownValues.
erase(CaseC);
6347 bool HasDefault = !
SI->defaultDestUnreachable();
6348 const unsigned NumUnknownBits =
6351 if (HasDefault && DeadCases.
empty()) {
6357 if (NumUnknownBits < 64 ) {
6358 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6359 if (
SI->getNumCases() == AllNumCases) {
6366 if (
SI->getNumCases() == AllNumCases - 1) {
6367 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6369 if (CondTy->getIntegerBitWidth() > 64 ||
6370 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6374 for (
const auto &Case :
SI->cases())
6375 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6377 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6379 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6389 if (DeadCases.
empty())
6395 assert(CaseI !=
SI->case_default() &&
6396 "Case was not found. Probably mistake in DeadCases forming.");
6398 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6403 std::vector<DominatorTree::UpdateType> Updates;
6404 for (
auto *
Successor : UniqueSuccessors)
6405 if (NumPerSuccessorCases[
Successor] == 0)
6432 int Idx =
PHI.getBasicBlockIndex(BB);
6433 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6435 Value *InValue =
PHI.getIncomingValue(Idx);
6436 if (InValue != CaseValue)
6452 ForwardingNodesMap ForwardingNodes;
6455 for (
const auto &Case :
SI->cases()) {
6457 BasicBlock *CaseDest = Case.getCaseSuccessor();
6476 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6477 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6478 count(Phi.blocks(), SwitchBlock) == 1) {
6479 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6487 ForwardingNodes[Phi].push_back(PhiIdx);
6490 for (
auto &ForwardingNode : ForwardingNodes) {
6491 PHINode *Phi = ForwardingNode.first;
6497 for (
int Index : Indexes)
6498 Phi->setIncomingValue(Index,
SI->getCondition());
6508 if (
C->isThreadDependent())
6510 if (
C->isDLLImportDependent())
6518 if (
C->getType()->isScalableTy())
6529 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6556 if (
A->isAllOnesValue())
6558 if (
A->isNullValue())
6564 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6589 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6591 if (
I.isTerminator()) {
6593 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6596 CaseDest =
I.getSuccessor(0);
6603 for (
auto &
Use :
I.uses()) {
6606 if (
I->getParent() == CaseDest)
6609 if (Phi->getIncomingBlock(
Use) == CaseDest)
6622 *CommonDest = CaseDest;
6624 if (CaseDest != *CommonDest)
6629 int Idx =
PHI.getBasicBlockIndex(Pred);
6642 Res.push_back(std::make_pair(&
PHI, ConstVal));
6645 return Res.
size() > 0;
6651 SwitchCaseResultVectorTy &UniqueResults,
6653 for (
auto &
I : UniqueResults) {
6654 if (
I.first == Result) {
6655 I.second.push_back(CaseVal);
6656 return I.second.size();
6659 UniqueResults.push_back(
6670 SwitchCaseResultVectorTy &UniqueResults,
6675 for (
const auto &
I :
SI->cases()) {
6689 const size_t NumCasesForResult =
6697 if (UniqueResults.size() > MaxUniqueResults)
6713 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6715 return DefaultResult ||
SI->defaultDestUnreachable();
6736 const bool HasBranchWeights =
6739 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6740 ResultVector[1].second.size() == 1) {
6741 ConstantInt *FirstCase = ResultVector[0].second[0];
6742 ConstantInt *SecondCase = ResultVector[1].second[0];
6743 Value *SelectValue = ResultVector[1].first;
6744 if (DefaultResult) {
6745 Value *ValueCompare =
6746 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6747 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6748 DefaultResult,
"switch.select");
6750 SI && HasBranchWeights) {
6757 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6761 Value *ValueCompare =
6762 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6763 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6764 SelectValue,
"switch.select");
6770 size_t FirstCasePos = (Condition !=
nullptr);
6771 size_t SecondCasePos = FirstCasePos + 1;
6772 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6774 {BranchWeights[FirstCasePos],
6775 DefaultCase + BranchWeights[SecondCasePos]},
6782 if (ResultVector.size() == 1 && DefaultResult) {
6784 unsigned CaseCount = CaseValues.
size();
6797 for (
auto *Case : CaseValues) {
6798 if (Case->getValue().slt(MinCaseVal->
getValue()))
6800 AndMask &= Case->getValue();
6804 if (!AndMask.
isZero() &&
Known.getMaxValue().uge(AndMask)) {
6806 unsigned FreeBits =
Known.countMaxActiveBits() - AndMask.
popcount();
6810 if (FreeBits ==
Log2_32(CaseCount)) {
6811 Value *
And = Builder.CreateAnd(Condition, AndMask);
6812 Value *Cmp = Builder.CreateICmpEQ(
6815 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6831 for (
auto *Case : CaseValues)
6832 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6838 Condition = Builder.CreateSub(Condition, MinCaseVal);
6839 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6840 Value *Cmp = Builder.CreateICmpEQ(
6843 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6856 if (CaseValues.
size() == 2) {
6857 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
6858 "switch.selectcmp.case1");
6859 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
6860 "switch.selectcmp.case2");
6861 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6863 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6883 std::vector<DominatorTree::UpdateType> Updates;
6890 Builder.CreateBr(DestBB);
6894 PHI->removeIncomingValueIf(
6895 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
6896 PHI->addIncoming(SelectValue, SelectBB);
6899 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
6905 if (DTU && RemovedSuccessors.
insert(Succ).second)
6908 SI->eraseFromParent();
6923 SwitchCaseResultVectorTy UniqueResults;
6929 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6930 Builder.SetInsertPoint(
SI);
6933 [[maybe_unused]]
auto HasWeights =
6938 (BranchWeights.
size() >=
6939 UniqueResults.size() + (DefaultResult !=
nullptr)));
6942 Builder,
DL, BranchWeights);
6954class SwitchReplacement {
6961 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
6962 Constant *DefaultValue,
const DataLayout &
DL,
6963 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
6972 static bool wouldFitInRegister(
const DataLayout &
DL,
uint64_t TableSize,
6979 bool isLookupTable();
7016 ConstantInt *BitMap =
nullptr;
7017 IntegerType *BitMapElementTy =
nullptr;
7020 ConstantInt *LinearOffset =
nullptr;
7021 ConstantInt *LinearMultiplier =
nullptr;
7022 bool LinearMapValWrapped =
false;
7030SwitchReplacement::SwitchReplacement(
7032 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7033 Constant *DefaultValue,
const DataLayout &
DL,
7034 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
7035 : DefaultValue(DefaultValue) {
7036 assert(
Values.size() &&
"Can't build lookup table without values!");
7037 assert(TableSize >=
Values.size() &&
"Can't fit values in table!");
7040 SingleValue =
Values.begin()->second;
7046 for (
const auto &[CaseVal, CaseRes] :
Values) {
7049 uint64_t Idx = (CaseVal->getValue() -
Offset->getValue()).getLimitedValue();
7050 TableContents[Idx] = CaseRes;
7057 if (
Values.size() < TableSize) {
7059 "Need a default value to fill the lookup table holes.");
7062 if (!TableContents[
I])
7063 TableContents[
I] = DefaultValue;
7069 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
7070 SingleValue =
nullptr;
7076 Kind = SingleValueKind;
7083 bool LinearMappingPossible =
true;
7088 bool NonMonotonic =
false;
7089 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
7106 LinearMappingPossible =
false;
7111 APInt Dist = Val - PrevVal;
7114 }
else if (Dist != DistToPrev) {
7115 LinearMappingPossible =
false;
7123 if (LinearMappingPossible) {
7125 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
7126 APInt M = LinearMultiplier->getValue();
7127 bool MayWrap =
true;
7128 if (
isIntN(M.getBitWidth(), TableSize - 1))
7129 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
7130 LinearMapValWrapped = NonMonotonic || MayWrap;
7131 Kind = LinearMapKind;
7137 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
7139 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
7141 TableInt <<=
IT->getBitWidth();
7145 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
7148 BitMap = ConstantInt::get(M.getContext(), TableInt);
7149 BitMapElementTy =
IT;
7160 unsigned NeededBitWidth =
7161 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7174 Kind = LookupTableKind;
7180 case SingleValueKind:
7182 case LinearMapKind: {
7186 false,
"switch.idx.cast");
7187 if (!LinearMultiplier->
isOne())
7188 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7190 !LinearMapValWrapped);
7192 if (!LinearOffset->
isZero())
7195 !LinearMapValWrapped);
7212 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7213 "switch.shiftamt",
true,
true);
7216 Value *DownShifted =
7217 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7219 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7221 case LookupTableKind: {
7224 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7225 true, GlobalVariable::PrivateLinkage,
7226 Initializer,
"switch.table." +
Func->getName());
7227 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7231 Type *IndexTy =
DL.getIndexType(
Table->getType());
7234 if (
Index->getType() != IndexTy) {
7235 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7239 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7242 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7246 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7255bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7257 Type *ElementType) {
7265 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7267 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7273 if (
TTI.isTypeLegal(Ty))
7288 DL.fitsInLegalInteger(
IT->getBitWidth());
7291Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7293bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7295bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7302 const uint64_t MinDensity = OptSize ? 40 : 10;
7307 return NumCases * 100 >= CaseRange * MinDensity;
7319static std::optional<unsigned>
7322 assert(
Values.size() > 1 &&
"expected multiple switch cases");
7324 return std::nullopt;
7329 for (
auto &V : ReducedValues) {
7331 ReducedValuesOr |= Reduced;
7332 V = (int64_t)Reduced;
7345 for (
auto &V : ReducedValues)
7346 V = (int64_t)((
uint64_t)V >> Shift);
7349 return std::nullopt;
7363 if (
SI->getNumCases() > TableSize)
7366 bool AllTablesFitInRegister =
true;
7367 bool HasIllegalType =
false;
7368 for (
const auto &Ty : ResultTypes) {
7373 AllTablesFitInRegister =
7374 AllTablesFitInRegister &&
7375 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7380 if (HasIllegalType && !AllTablesFitInRegister)
7385 if (AllTablesFitInRegister)
7393 SI->getFunction()->hasOptSize());
7403 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7406 return all_of(ResultTypes, [&](
const auto &ResultType) {
7407 return SwitchReplacement::wouldFitInRegister(
7457 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7462 for (
auto ValuePair :
Values) {
7465 if (!CaseConst || CaseConst == DefaultConst ||
7466 (CaseConst != TrueConst && CaseConst != FalseConst))
7480 if (DefaultConst == FalseConst) {
7483 ++NumTableCmpReuses;
7486 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7487 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7490 ++NumTableCmpReuses;
7500 bool ConvertSwitchToLookupTable) {
7501 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7515 if (
SI->getNumCases() < 3)
7537 MinCaseVal = CaseVal;
7539 MaxCaseVal = CaseVal;
7556 It->second.push_back(std::make_pair(CaseVal,
Value));
7564 bool HasDefaultResults =
7566 DefaultResultsList,
DL,
TTI);
7567 for (
const auto &
I : DefaultResultsList) {
7570 DefaultResults[
PHI] = Result;
7574 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7577 if (UseSwitchConditionAsTableIndex) {
7579 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7584 TableIndexOffset = MinCaseVal;
7591 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7593 bool TableHasHoles = (NumResults < TableSize);
7598 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7606 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7609 if (
SI->getNumCases() < 4)
7611 if (!
DL.fitsInLegalInteger(TableSize))
7620 if (UseSwitchConditionAsTableIndex) {
7621 TableIndex =
SI->getCondition();
7622 if (HasDefaultResults) {
7634 all_of(ResultTypes, [&](
const auto &ResultType) {
7635 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7640 TableSize = std::max(UpperBound, TableSize);
7643 DefaultIsReachable =
false;
7651 const auto &ResultList = ResultLists[
PHI];
7653 Type *ResultType = ResultList.begin()->second->getType();
7658 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7659 ResultList, DefaultVal,
DL,
TTI, FuncName);
7660 PhiToReplacementMap.
insert({
PHI, Replacement});
7663 bool AnyLookupTables =
any_of(
7664 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7665 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7666 [](
auto &KV) {
return KV.second.isBitMap(); });
7674 if (AnyLookupTables &&
7675 (!
TTI.shouldBuildLookupTables() ||
7681 if (!ConvertSwitchToLookupTable &&
7682 (AnyLookupTables || AnyBitMaps || NeedMask))
7685 Builder.SetInsertPoint(
SI);
7688 if (!UseSwitchConditionAsTableIndex) {
7691 bool MayWrap =
true;
7692 if (!DefaultIsReachable) {
7697 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7698 "switch.tableidx",
false,
7702 std::vector<DominatorTree::UpdateType> Updates;
7708 assert(MaxTableSize >= TableSize &&
7709 "It is impossible for a switch to have more entries than the max "
7710 "representable value of its input integer type's size.");
7715 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7720 Builder.SetInsertPoint(
SI);
7721 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7722 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7723 Builder.CreateBr(LookupBB);
7729 Value *Cmp = Builder.CreateICmpULT(
7730 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7732 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7733 CondBranch = RangeCheckBranch;
7739 Builder.SetInsertPoint(LookupBB);
7745 MaskBB->
setName(
"switch.hole_check");
7752 APInt MaskInt(TableSizePowOf2, 0);
7753 APInt One(TableSizePowOf2, 1);
7755 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7756 for (
const auto &Result : ResultList) {
7759 MaskInt |= One << Idx;
7761 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7768 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7769 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7770 Value *LoBit = Builder.CreateTrunc(
7772 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7777 Builder.SetInsertPoint(LookupBB);
7781 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7784 SI->getDefaultDest()->removePredecessor(BB,
7791 const ResultListTy &ResultList = ResultLists[
PHI];
7792 auto Replacement = PhiToReplacementMap.
at(
PHI);
7793 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7796 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7799 for (
auto *
User :
PHI->users()) {
7801 Replacement.getDefaultValue(), ResultList);
7805 PHI->addIncoming(Result, LookupBB);
7808 Builder.CreateBr(CommonDest);
7820 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7823 if (Succ ==
SI->getDefaultDest()) {
7824 if (HasBranchWeights)
7825 ToDefaultWeight += BranchWeights[
I];
7829 if (DTU && RemovedSuccessors.
insert(Succ).second)
7831 if (HasBranchWeights)
7832 ToLookupWeight += BranchWeights[
I];
7834 SI->eraseFromParent();
7835 if (HasBranchWeights)
7842 ++NumLookupTablesHoles;
7858 if (CondTy->getIntegerBitWidth() > 64 ||
7859 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7863 if (
SI->getNumCases() < 4)
7871 for (
const auto &
C :
SI->cases())
7872 Values.push_back(
C.getCaseValue()->getValue().getSExtValue());
7876 bool OptSize =
SI->getFunction()->hasOptSize();
7883 std::optional<unsigned> Shift;
7913 Builder.SetInsertPoint(
SI);
7917 Value *Rot = Builder.CreateIntrinsic(
7918 Ty, Intrinsic::fshl,
7919 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - *Shift)});
7920 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
7922 for (
auto Case :
SI->cases()) {
7923 auto *Orig = Case.getCaseValue();
7924 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7969 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
7970 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
7987 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
7990 return !Updates.
empty();
8010 if (
SI->defaultDestUnreachable())
8021 if (!
Known.isConstant())
8028 ConstantInt::get(
SI->getContext(),
Known.getConstant());
8030 if (CaseIt ==
SI->case_default()) {
8039 SI->case_default());
8041 assert(
SI->getNumCases() > 0 &&
"Switch should have at least one case");
8042 assert(
SI->findCaseValue(CaseVal) !=
SI->case_default() &&
8043 "Proven value should have a dedicated case");
8044 assert(
SI->defaultDestUnreachable());
8062 Value *Condition =
SI->getCondition();
8066 if (CondTy->getIntegerBitWidth() > 64 ||
8067 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8079 if (
SI->getNumCases() < 4)
8084 for (
const auto &Case :
SI->cases()) {
8085 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
8087 Values.push_back(CaseValue);
8097 SI->getFunction()->hasOptSize()))
8101 Builder.SetInsertPoint(
SI);
8103 if (!
SI->defaultDestUnreachable()) {
8106 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
8107 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
8109 auto *OrigBB =
SI->getParent();
8110 auto *DefaultCaseBB =
SI->getDefaultDest();
8112 auto It = OrigBB->getTerminator()->getIterator();
8125 NewWeights[1] = Weights[0] / 2;
8126 NewWeights[0] = OrigDenominator - NewWeights[1];
8138 Weights[0] = NewWeights[1];
8139 uint64_t CasesDenominator = OrigDenominator - Weights[0];
8141 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
8147 It->eraseFromParent();
8155 for (
auto &Case :
SI->cases()) {
8156 auto *OrigValue = Case.getCaseValue();
8157 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
8158 OrigValue->getValue().countr_zero()));
8162 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
8165 SI->setCondition(ConditionTrailingZeros);
8175 if (!Cmp || !Cmp->hasOneUse())
8186 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
8189 if (
SI->getNumCases() == 2) {
8196 Succ =
SI->getDefaultDest();
8197 SuccWeight = Weights[0];
8199 for (
auto &Case :
SI->cases()) {
8200 std::optional<int64_t> Val =
8204 if (!Missing.erase(*Val))
8209 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
8212 assert(Missing.size() == 1 &&
"Should have one case left");
8213 Res = *Missing.begin();
8214 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
8216 Unreachable =
SI->getDefaultDest();
8218 for (
auto &Case :
SI->cases()) {
8219 BasicBlock *NewSucc = Case.getCaseSuccessor();
8220 uint32_t Weight = Weights[Case.getSuccessorIndex()];
8223 OtherSuccWeight += Weight;
8226 SuccWeight = Weight;
8227 }
else if (Succ == NewSucc) {
8233 for (
auto &Case :
SI->cases()) {
8234 std::optional<int64_t> Val =
8236 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8238 if (Case.getCaseSuccessor() == Succ) {
8260 if (Cmp->isSigned())
8263 MDNode *NewWeights =
nullptr;
8269 Builder.SetInsertPoint(
SI->getIterator());
8270 Value *ICmp = Builder.CreateICmp(Pred, Cmp->getLHS(), Cmp->getRHS());
8271 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8272 SI->getMetadata(LLVMContext::MD_unpredictable));
8276 SI->eraseFromParent();
8277 Cmp->eraseFromParent();
8278 if (DTU && Unreachable)
8303 assert(
BB &&
"Expected non-null BB");
8305 if (
BB->isEntryBlock())
8318 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8323 if (&
BB->front() != &
BB->back())
8338 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8349 return (*EBW->PhiPredIVs)[&Phi][BB];
8371 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8374 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8375 return PredIVs[
A] == PredIVs[
B];
8384 if (Candidates.
size() < 2)
8399 assert(Succ &&
"Expected unconditional BB");
8409 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8412 for (
auto &
IV : Phi->incoming_values())
8413 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8431 bool MadeChange =
false;
8445 if (!LivePreds.
contains(PredOfDead))
8452 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8453 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8458 T->replaceSuccessorWith(
Dead, Live);
8463 for (
const auto &EBW : BBs2Merge) {
8466 const auto &[It, Inserted] =
Keep.insert(&EBW);
8475 if (KeepBB == DeadBB)
8479 RedirectIncomingEdges(DeadBB, KeepBB);
8488 if (DTU && !Updates.
empty())
8494bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8495 DomTreeUpdater *DTU) {
8497 SmallSetVector<BasicBlock *, 16> FilteredArms(
8503bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8504 DomTreeUpdater *DTU) {
8515 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8521bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8524 if (isValueEqualityComparison(SI)) {
8528 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8529 return requestResimplify();
8533 if (simplifySwitchOnSelect(SI,
Select))
8534 return requestResimplify();
8538 if (SI == &*BB->
begin())
8539 if (foldValueComparisonIntoPredecessors(SI, Builder))
8540 return requestResimplify();
8546 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8547 return requestResimplify();
8551 return requestResimplify();
8554 return requestResimplify();
8557 return requestResimplify();
8560 return requestResimplify();
8565 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8567 Options.ConvertSwitchToLookupTable))
8568 return requestResimplify();
8571 return requestResimplify();
8574 return requestResimplify();
8577 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8578 return requestResimplify();
8582 if (simplifyDuplicateSwitchArms(SI, DTU))
8583 return requestResimplify();
8586 return requestResimplify();
8589 return requestResimplify();
8594bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8597 SmallVector<uint32_t> BranchWeights;
8601 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8602 if (HasBranchWeights)
8607 SmallPtrSet<Value *, 8> Succs;
8608 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8613 RemovedSuccs.
insert(Dest);
8623 std::vector<DominatorTree::UpdateType> Updates;
8624 Updates.reserve(RemovedSuccs.
size());
8625 for (
auto *RemovedSucc : RemovedSuccs)
8626 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8643 if (HasBranchWeights) {
8650 if (simplifyIndirectBrOnSelect(IBI, SI))
8651 return requestResimplify();
8687 if (BB == OtherPred)
8698 std::vector<DominatorTree::UpdateType> Updates;
8705 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8706 "unexpected successor");
8707 II->setUnwindDest(OtherPred);
8722 Builder.CreateUnreachable();
8731bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8743 bool NeedCanonicalLoop =
8757 if (
I->isTerminator() &&
8758 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8782 if (!PPred || (PredPred && PredPred != PPred))
8823 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
8827 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8857 bool HasWeight =
false;
8862 BBTWeight = BBFWeight = 1;
8867 BB1TWeight = BB1FWeight = 1;
8872 BB2TWeight = BB2FWeight = 1;
8874 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8875 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8882bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
8886 "Tautological conditional branch should have been eliminated already.");
8889 if (!
Options.SimplifyCondBranch ||
8894 if (isValueEqualityComparison(BI)) {
8899 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8900 return requestResimplify();
8904 for (
auto &
I : *BB) {
8909 if (foldValueComparisonIntoPredecessors(BI, Builder))
8910 return requestResimplify();
8916 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8929 return requestResimplify();
8935 if (
Options.SpeculateBlocks &&
8938 return requestResimplify();
8947 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8948 return requestResimplify();
8950 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8952 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
8953 auto CanSpeculateConditionalLoadsStores = [&]() {
8955 for (Instruction &
I : *Succ) {
8956 if (
I.isTerminator()) {
8957 if (
I.getNumSuccessors() > 1)
8961 SpeculatedConditionalLoadsStores.
size() ==
8965 SpeculatedConditionalLoadsStores.
push_back(&
I);
8968 return !SpeculatedConditionalLoadsStores.
empty();
8971 if (CanSpeculateConditionalLoadsStores()) {
8973 std::nullopt,
nullptr);
8974 return requestResimplify();
8984 return requestResimplify();
8993 return requestResimplify();
8999 if (foldCondBranchOnValueKnownInPredecessor(BI))
9000 return requestResimplify();
9007 return requestResimplify();
9015 return requestResimplify();
9019 return requestResimplify();
9026 assert(V->getType() ==
I->getType() &&
"Mismatched types");
9038 auto *Use = cast<Instruction>(U.getUser());
9041 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
9044 switch (Use->getOpcode()) {
9047 case Instruction::GetElementPtr:
9048 case Instruction::Ret:
9049 case Instruction::BitCast:
9050 case Instruction::Load:
9051 case Instruction::Store:
9052 case Instruction::Call:
9053 case Instruction::CallBr:
9054 case Instruction::Invoke:
9055 case Instruction::UDiv:
9056 case Instruction::URem:
9060 case Instruction::SDiv:
9061 case Instruction::SRem:
9065 if (FindUse ==
I->use_end())
9067 auto &
Use = *FindUse;
9081 if (
GEP->getPointerOperand() ==
I) {
9084 if (
GEP->getType()->isVectorTy())
9092 if (!
GEP->hasAllZeroIndices() &&
9093 (!
GEP->isInBounds() ||
9095 GEP->getPointerAddressSpace())))
9096 PtrValueMayBeModified =
true;
9102 bool HasNoUndefAttr =
9103 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
9108 if (
C->isNullValue() && HasNoUndefAttr &&
9109 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
9110 return !PtrValueMayBeModified;
9116 if (!LI->isVolatile())
9118 LI->getPointerAddressSpace());
9122 if (!
SI->isVolatile())
9124 SI->getPointerAddressSpace())) &&
9125 SI->getPointerOperand() ==
I;
9130 if (
I == Assume->getArgOperand(0))
9138 if (CB->getCalledOperand() ==
I)
9141 if (CB->isArgOperand(&
Use)) {
9142 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
9145 CB->paramHasNonNullAttr(ArgIdx,
false))
9146 return !PtrValueMayBeModified;
9165 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
9173 Builder.CreateUnreachable();
9174 T->eraseFromParent();
9186 Builder.CreateUnreachable();
9193 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
9195 Assumption = Builder.CreateAssumption(
Cond);
9210 Builder.SetInsertPoint(Unreachable);
9212 Builder.CreateUnreachable();
9213 for (
const auto &Case :
SI->cases())
9214 if (Case.getCaseSuccessor() == BB) {
9216 Case.setSuccessor(Unreachable);
9218 if (
SI->getDefaultDest() == BB) {
9220 SI->setDefaultDest(Unreachable);
9234bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9259 return requestResimplify();
9278 if (simplifyDuplicatePredecessors(BB, DTU))
9282 if (
Options.SpeculateBlocks &&
9289 Options.SpeculateUnpredictables))
9297 case Instruction::UncondBr:
9300 case Instruction::CondBr:
9303 case Instruction::Resume:
9306 case Instruction::CleanupRet:
9309 case Instruction::Switch:
9312 case Instruction::Unreachable:
9315 case Instruction::IndirectBr:
9323bool SimplifyCFGOpt::run(BasicBlock *BB) {
9333 }
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...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static 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.
const SmallVectorImpl< MachineOperand > & Cond
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 getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(CondBrInst *BI, CondBrInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool reachesUncontrolledConvergentCallBeforeBlock(BasicBlock *From, BasicBlock *StopBB)
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static void hoistConditionalLoadsStores(CondBrInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool simplifySwitchDefaultBranch(SwitchInst *SI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, ArrayRef< uint32_t > BranchWeights)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool 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 initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
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 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 removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isUncontrolledConvergentCall(CallBase *CB)
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, CondBrInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & front() const
Get the first element.
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; 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.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
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.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
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.
static DebugLoc getDropped()
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
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)