96#define DEBUG_TYPE "simplifycfg"
101 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
104 "Temporary development switch used to gradually uplift SimplifyCFG "
105 "into preserving DomTree,"));
114 "Control the amount of phi node folding to perform (default = 2)"));
118 cl::desc(
"Control the maximal total instruction cost that we are willing "
119 "to speculatively execute to fold a 2-entry PHI node into a "
120 "select (default = 4)"));
124 cl::desc(
"Hoist common instructions up to the parent block"));
128 cl::desc(
"Hoist loads if the target supports conditional faulting"));
132 cl::desc(
"Hoist stores if the target supports conditional faulting"));
136 cl::desc(
"Control the maximal conditional load/store that we are willing "
137 "to speculatively execute to eliminate conditional branch "
143 cl::desc(
"Allow reordering across at most this many "
144 "instructions when hoisting"));
148 cl::desc(
"Sink common instructions down to the end block"));
152 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
156 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
157 "precede - hoist multiple conditional stores into a single "
158 "predicated store"));
162 cl::desc(
"When merging conditional stores, do so even if the resultant "
163 "basic blocks are unlikely to be if-converted as a result"));
167 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
172 cl::desc(
"Limit maximum recursion depth when calculating costs of "
173 "speculatively executed instructions"));
178 cl::desc(
"Max size of a block which is still considered "
179 "small enough to thread through"));
185 cl::desc(
"Maximum cost of combining conditions when "
186 "folding branches"));
189 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
191 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
192 "to fold branch to common destination when vector operations are "
197 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
201 cl::desc(
"Limit cases to analyze when converting a switch to select"));
205 cl::desc(
"Limit number of blocks searched to prove that threading through "
206 "a loop header keeps the loop canonical"));
210 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
217STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
219 "Number of switch instructions turned into linear mapping");
221 "Number of switch instructions turned into lookup tables");
223 NumLookupTablesHoles,
224 "Number of switch instructions turned into lookup tables (holes checked)");
225STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
227 "Number of value comparisons folded into predecessor basic blocks");
229 "Number of branches folded into predecessor basic block");
232 "Number of common instruction 'blocks' hoisted up to the begin block");
234 "Number of common instructions hoisted up to the begin block");
236 "Number of common instruction 'blocks' sunk down to the end block");
238 "Number of common instructions sunk down to the end block");
239STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
241 "Number of invokes with empty resume blocks simplified into calls");
242STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
243STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
250using SwitchCaseResultVectorTy =
259struct ValueEqualityComparisonCase {
271 bool operator==(BasicBlock *RHSDest)
const {
return Dest == RHSDest; }
274class SimplifyCFGOpt {
275 const TargetTransformInfo &TTI;
277 const DataLayout &DL;
279 const SimplifyCFGOptions &Options;
282 Value *isValueEqualityComparison(Instruction *TI);
284 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
285 bool simplifyEqualityComparisonWithOnlyPredecessor(Instruction *TI,
288 bool performValueComparisonIntoPredecessorFolding(Instruction *TI,
Value *&CV,
291 bool foldValueComparisonIntoPredecessors(Instruction *TI,
294 bool simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder);
295 bool simplifySingleResume(ResumeInst *RI);
296 bool simplifyCommonResume(ResumeInst *RI);
297 bool simplifyCleanupReturn(CleanupReturnInst *RI);
298 bool simplifyUnreachable(UnreachableInst *UI);
299 bool simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder);
300 bool simplifyDuplicateSwitchArms(SwitchInst *SI, DomTreeUpdater *DTU);
301 bool simplifyIndirectBr(IndirectBrInst *IBI);
302 bool simplifyUncondBranch(UncondBrInst *BI,
IRBuilder<> &Builder);
303 bool simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder);
304 bool foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI);
306 bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
308 bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
311 bool hoistCommonCodeFromSuccessors(Instruction *TI,
bool AllInstsEqOnly);
312 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
313 Instruction *TI, Instruction *I1,
314 SmallVectorImpl<Instruction *> &OtherSuccTIs,
316 bool speculativelyExecuteBB(CondBrInst *BI, BasicBlock *ThenBB);
317 bool simplifyTerminatorOnSelect(Instruction *OldTerm,
Value *
Cond,
318 BasicBlock *TrueBB, BasicBlock *FalseBB,
319 uint32_t TrueWeight, uint32_t FalseWeight);
320 bool simplifyBranchOnICmpChain(CondBrInst *BI,
IRBuilder<> &Builder,
321 const DataLayout &DL);
322 bool simplifySwitchOnSelect(SwitchInst *SI, SelectInst *
Select);
323 bool simplifySwitchOnSelectRemap(SwitchInst *SI, SelectInst *
Select,
Value *
X,
324 ConstantInt *
C,
bool Negate);
325 bool simplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
326 bool turnSwitchRangeIntoICmp(SwitchInst *SI,
IRBuilder<> &Builder);
327 bool simplifyDuplicatePredecessors(BasicBlock *Succ, DomTreeUpdater *DTU);
330 SimplifyCFGOpt(
const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
332 const SimplifyCFGOptions &Opts)
333 : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
334 assert((!DTU || !DTU->hasPostDomTree()) &&
335 "SimplifyCFG is not yet capable of maintaining validity of a "
336 "PostDomTree, so don't ask for it.");
339 bool simplifyOnce(BasicBlock *BB);
340 bool run(BasicBlock *BB);
343 bool requestResimplify() {
353isSelectInRoleOfConjunctionOrDisjunction(
const SelectInst *
SI) {
373 "Only for a pair of incoming blocks at the time!");
379 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
380 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
383 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
384 EquivalenceSet->contains(IV1))
407 if (!SI1Succs.
count(Succ))
413 FailBlocks->insert(Succ);
429 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
431 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
432 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
494 if (AggressiveInsts.
count(
I))
510 ZeroCostInstructions.
insert(OverflowInst);
512 }
else if (!ZeroCostInstructions.
contains(
I))
528 for (
Use &
Op :
I->operands())
530 TTI, AC, ZeroCostInstructions,
Depth + 1))
547 if (
DL.hasUnstableRepresentation(
V->getType()))
556 return ConstantInt::get(
IntPtrTy, 0);
561 if (CE->getOpcode() == Instruction::IntToPtr)
585struct ConstantComparesGatherer {
586 const DataLayout &DL;
589 Value *CompValue =
nullptr;
592 Value *Extra =
nullptr;
598 unsigned UsedICmps = 0;
604 bool IgnoreFirstMatch =
false;
605 bool MultipleMatches =
false;
608 ConstantComparesGatherer(Instruction *
Cond,
const DataLayout &DL) : DL(DL) {
610 if (CompValue || !MultipleMatches)
615 IgnoreFirstMatch =
true;
619 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
620 ConstantComparesGatherer &
621 operator=(
const ConstantComparesGatherer &) =
delete;
626 bool setValueOnce(
Value *NewVal) {
627 if (IgnoreFirstMatch) {
628 IgnoreFirstMatch =
false;
631 if (CompValue && CompValue != NewVal) {
632 MultipleMatches =
true;
646 bool matchInstruction(Instruction *
I,
bool isEQ) {
653 if (!setValueOnce(Val))
673 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
717 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
719 if (!setValueOnce(RHSVal))
724 ConstantInt::get(
C->getContext(),
725 C->getValue() | Mask));
740 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
742 if (!setValueOnce(RHSVal))
746 Vals.push_back(ConstantInt::get(
C->getContext(),
747 C->getValue() & ~Mask));
768 Value *CandidateVal =
I->getOperand(0);
771 CandidateVal = RHSVal;
786 if (!setValueOnce(CandidateVal))
792 Vals.push_back(ConstantInt::get(
I->getContext(), Tmp));
813 SmallVector<Value *, 8> DFT{Op0, Op1};
814 SmallPtrSet<Value *, 8> Visited{
V, Op0, Op1};
816 while (!DFT.
empty()) {
823 if (Visited.
insert(Op1).second)
825 if (Visited.
insert(Op0).second)
832 if (matchInstruction(
I, IsEq))
873 CV =
SI->getCondition();
875 if (BI->getCondition()->hasOneUse()) {
880 if (
Trunc->hasNoUnsignedWrap())
881 CV =
Trunc->getOperand(0);
888 Value *Ptr = PTII->getPointerOperand();
889 if (
DL.hasUnstableRepresentation(Ptr->
getType()))
891 if (PTII->getType() ==
DL.getIntPtrType(Ptr->
getType()))
900BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
901 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
903 Cases.reserve(
SI->getNumCases());
904 for (
auto Case :
SI->cases())
905 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
906 Case.getCaseSuccessor()));
907 return SI->getDefaultDest();
912 ICmpInst::Predicate
Pred;
918 Pred = ICmpInst::ICMP_NE;
923 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
931 std::vector<ValueEqualityComparisonCase> &Cases) {
937 std::vector<ValueEqualityComparisonCase> &C2) {
938 std::vector<ValueEqualityComparisonCase> *
V1 = &
C1, *V2 = &C2;
941 if (
V1->size() > V2->size())
946 if (
V1->size() == 1) {
949 for (
const ValueEqualityComparisonCase &
VECC : *V2)
950 if (TheVal ==
VECC.Value)
957 unsigned i1 = 0, i2 = 0, e1 =
V1->size(), e2 = V2->size();
958 while (i1 != e1 && i2 != e2) {
976bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
978 Value *PredVal = isValueEqualityComparison(
Pred->getTerminator());
982 Value *ThisVal = isValueEqualityComparison(TI);
983 assert(ThisVal &&
"This isn't a value comparison!!");
984 if (ThisVal != PredVal)
991 std::vector<ValueEqualityComparisonCase> PredCases;
993 getValueEqualityComparisonCases(
Pred->getTerminator(), PredCases);
998 std::vector<ValueEqualityComparisonCase> ThisCases;
999 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1007 if (PredDef == TIBB) {
1018 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1024 ThisCases[0].Dest->removePredecessor(TIBB);
1027 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1033 DTU->
applyUpdates({{DominatorTree::Delete, TIBB, ThisCases[0].Dest}});
1040 SmallPtrSet<Constant *, 16> DeadCases;
1041 for (
const ValueEqualityComparisonCase &Case : PredCases)
1042 DeadCases.
insert(Case.Value);
1045 <<
"Through successor TI: " << *TI);
1047 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
1050 auto *
Successor = i->getCaseSuccessor();
1053 if (DeadCases.
count(i->getCaseValue())) {
1062 std::vector<DominatorTree::UpdateType> Updates;
1063 for (
const auto &
I : NumPerSuccessorCases)
1065 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1075 ConstantInt *TIV =
nullptr;
1076 for (
const auto &[
Value, Dest] : PredCases)
1082 assert(TIV &&
"No edge from pred to succ?");
1086 for (
const auto &[
Value, Dest] : ThisCases)
1094 TheRealDest = ThisDef;
1096 SmallPtrSet<BasicBlock *, 2> RemovedSuccs;
1101 if (Succ != CheckEdge) {
1102 if (Succ != TheRealDest)
1103 RemovedSuccs.
insert(Succ);
1106 CheckEdge =
nullptr;
1113 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1118 SmallVector<DominatorTree::UpdateType, 2> Updates;
1120 for (
auto *RemovedSucc : RemovedSuccs)
1121 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1132struct ConstantIntOrdering {
1133 bool operator()(
const ConstantInt *
LHS,
const ConstantInt *
RHS)
const {
1134 return LHS->getValue().ult(
RHS->getValue());
1146 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1155 assert(MD &&
"Invalid branch-weight metadata");
1180 if (BonusInst.isTerminator())
1215 NewBonusInst->
takeName(&BonusInst);
1216 BonusInst.setName(NewBonusInst->
getName() +
".old");
1217 VMap[&BonusInst] = NewBonusInst;
1226 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1227 "If the user is not a PHI node, then it should be in the same "
1228 "block as, and come after, the original bonus instruction.");
1232 if (PN->getIncomingBlock(U) == BB)
1236 assert(PN->getIncomingBlock(U) == PredBlock &&
1237 "Not in block-closed SSA form?");
1238 U.set(NewBonusInst);
1248 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1249 PredDL.isSameSourceLocation(
DL)) {
1256bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1264 std::vector<ValueEqualityComparisonCase> BBCases;
1265 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1267 std::vector<ValueEqualityComparisonCase> PredCases;
1268 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1273 SmallMapVector<BasicBlock *, int, 8> NewSuccessors;
1276 SmallVector<uint64_t, 8> Weights;
1280 if (PredHasWeights) {
1283 if (Weights.
size() != 1 + PredCases.size())
1284 PredHasWeights = SuccHasWeights =
false;
1285 }
else if (SuccHasWeights)
1289 Weights.
assign(1 + PredCases.size(), 1);
1291 SmallVector<uint64_t, 8> SuccWeights;
1292 if (SuccHasWeights) {
1295 if (SuccWeights.
size() != 1 + BBCases.size())
1296 PredHasWeights = SuccHasWeights =
false;
1297 }
else if (PredHasWeights)
1298 SuccWeights.
assign(1 + BBCases.size(), 1);
1300 if (PredDefault == BB) {
1303 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1304 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1305 if (PredCases[i].Dest != BB)
1306 PTIHandled.insert(PredCases[i].
Value);
1309 std::swap(PredCases[i], PredCases.back());
1311 if (PredHasWeights || SuccHasWeights) {
1313 Weights[0] += Weights[i + 1];
1318 PredCases.pop_back();
1324 if (PredDefault != BBDefault) {
1326 if (DTU && PredDefault != BB)
1327 Updates.
push_back({DominatorTree::Delete,
Pred, PredDefault});
1328 PredDefault = BBDefault;
1329 ++NewSuccessors[BBDefault];
1332 unsigned CasesFromPred = Weights.
size();
1334 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1335 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1336 PredCases.push_back(BBCases[i]);
1337 ++NewSuccessors[BBCases[i].Dest];
1338 if (SuccHasWeights || PredHasWeights) {
1342 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1343 ValidTotalSuccWeight += SuccWeights[i + 1];
1347 if (SuccHasWeights || PredHasWeights) {
1348 ValidTotalSuccWeight += SuccWeights[0];
1350 for (
unsigned i = 1; i < CasesFromPred; ++i)
1351 Weights[i] *= ValidTotalSuccWeight;
1353 Weights[0] *= SuccWeights[0];
1359 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1360 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1361 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1362 if (PredCases[i].Dest == BB) {
1363 PTIHandled.insert(PredCases[i].
Value);
1365 if (PredHasWeights || SuccHasWeights) {
1366 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1371 std::swap(PredCases[i], PredCases.back());
1372 PredCases.pop_back();
1379 for (
const ValueEqualityComparisonCase &Case : BBCases)
1380 if (PTIHandled.count(Case.Value)) {
1382 if (PredHasWeights || SuccHasWeights)
1383 Weights.
push_back(WeightsForHandled[Case.Value]);
1384 PredCases.push_back(Case);
1385 ++NewSuccessors[Case.Dest];
1386 PTIHandled.erase(Case.Value);
1391 for (ConstantInt *
I : PTIHandled) {
1392 if (PredHasWeights || SuccHasWeights)
1394 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1395 ++NewSuccessors[BBDefault];
1402 SmallPtrSet<BasicBlock *, 2> SuccsOfPred;
1407 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1409 for (
auto I :
seq(NewSuccessor.second)) {
1413 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1414 Updates.
push_back({DominatorTree::Insert,
Pred, NewSuccessor.first});
1421 "Should not end up here with unstable pointers");
1427 SwitchInst *NewSI = Builder.
CreateSwitch(CV, PredDefault, PredCases.size());
1429 for (ValueEqualityComparisonCase &
V : PredCases)
1432 if (PredHasWeights || SuccHasWeights)
1440 if (MDNode *Unpredictable = PTI->
getMetadata(LLVMContext::MD_unpredictable))
1441 if (TI->
hasMetadata(LLVMContext::MD_unpredictable))
1442 NewSI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
1452 if (!InfLoopBlock) {
1460 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1467 Updates.
push_back({DominatorTree::Insert,
Pred, InfLoopBlock});
1474 ++NumFoldValueComparisonIntoPredecessors;
1482bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(Instruction *TI,
1485 Value *CV = isValueEqualityComparison(TI);
1486 assert(CV &&
"Not a comparison?");
1497 while (!Preds.empty()) {
1506 Value *PCV = isValueEqualityComparison(PTI);
1510 SmallSetVector<BasicBlock *, 4> FailBlocks;
1512 for (
auto *Succ : FailBlocks) {
1518 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1532 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1533 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1534 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1556 if (
I->mayReadFromMemory())
1588 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1596 if (J->getParent() == BB)
1618 if (
C1->isMustTailCall() != C2->isMustTailCall())
1621 if (!
TTI.isProfitableToHoist(I1) || !
TTI.isProfitableToHoist(I2))
1627 if (CB1->cannotMerge() || CB1->isConvergent())
1630 if (CB2->cannotMerge() || CB2->isConvergent())
1645 if (!I1->hasDbgRecords())
1647 using CurrentAndEndIt =
1648 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1654 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1655 return Pair.first == Pair.second;
1661 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1667 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1669 if (!
Other->hasDbgRecords())
1672 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1679 while (
none_of(Itrs, atEnd)) {
1680 bool HoistDVRs = allIdentical(Itrs);
1681 for (CurrentAndEndIt &Pair : Itrs) {
1695 if (I1->isIdenticalToWhenDefined(I2,
true))
1700 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1701 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1702 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1704 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1705 return I1->getOperand(0) == I2->
getOperand(1) &&
1771 auto &Context = BI->
getParent()->getContext();
1776 Value *Mask =
nullptr;
1777 Value *MaskFalse =
nullptr;
1778 Value *MaskTrue =
nullptr;
1779 if (Invert.has_value()) {
1780 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1781 Mask = Builder.CreateBitCast(
1786 MaskFalse = Builder.CreateBitCast(
1788 MaskTrue = Builder.CreateBitCast(
Cond, VCondTy);
1790 auto PeekThroughBitcasts = [](
Value *
V) {
1792 V = BitCast->getOperand(0);
1795 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1797 if (!Invert.has_value())
1798 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1803 auto *Op0 =
I->getOperand(0);
1804 CallInst *MaskedLoadStore =
nullptr;
1807 auto *Ty =
I->getType();
1809 Value *PassThru =
nullptr;
1810 if (Invert.has_value())
1811 for (
User *U :
I->users()) {
1813 PassThru = Builder.CreateBitCast(
1822 Builder.SetInsertPoint(Ins);
1825 MaskedLoadStore = Builder.CreateMaskedLoad(
1827 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range)) {
1836 Value *NewLoadStore = Builder.CreateBitCast(MaskedLoadStore, Ty);
1839 I->replaceAllUsesWith(NewLoadStore);
1842 auto *StoredVal = Builder.CreateBitCast(
1844 MaskedLoadStore = Builder.CreateMaskedStore(
1853 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1857 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1858 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1861 I->eraseFromParent();
1868 bool IsStore =
false;
1891bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(Instruction *TI,
1892 bool AllInstsEqOnly) {
1908 for (
auto *Succ : UniqueSuccessors) {
1924 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1926 for (
auto *Succ : UniqueSuccessors) {
1930 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1933 if (AllInstsEqOnly) {
1939 unsigned Size0 = UniqueSuccessors[0]->size();
1940 Instruction *Term0 = UniqueSuccessors[0]->getTerminator();
1944 Succ->
size() == Size0;
1948 LockstepReverseIterator<true> LRI(UniqueSuccessors.getArrayRef());
1949 while (LRI.isValid()) {
1951 if (
any_of(*LRI, [I0](Instruction *
I) {
1965 unsigned NumSkipped = 0;
1968 if (SuccIterPairs.
size() > 2) {
1971 if (SuccIterPairs.
size() < 2)
1978 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1979 auto &BB1ItrPair = *SuccIterPairBegin++;
1980 auto OtherSuccIterPairRange =
1986 bool AllInstsAreIdentical =
true;
1987 bool HasTerminator =
I1->isTerminator();
1988 for (
auto &SuccIter : OtherSuccIterRange) {
1992 MMRAMetadata(*I1) != MMRAMetadata(*I2)))
1993 AllInstsAreIdentical =
false;
1996 SmallVector<Instruction *, 8> OtherInsts;
1997 for (
auto &SuccIter : OtherSuccIterRange)
2002 if (HasTerminator) {
2006 if (NumSkipped || !AllInstsAreIdentical) {
2011 return hoistSuccIdenticalTerminatorToSwitchOrIf(
2012 TI, I1, OtherInsts, UniqueSuccessors.getArrayRef()) ||
2016 if (AllInstsAreIdentical) {
2017 unsigned SkipFlagsBB1 = BB1ItrPair.second;
2018 AllInstsAreIdentical =
2020 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
2022 unsigned SkipFlagsBB2 = Pair.second;
2037 AllInstsAreIdentical && CI && CI->isMustTailCall()) {
2038 AllInstsAreIdentical =
2039 NumSkipped == 0 &&
all_of(SuccIterPairs, [](
const SuccIterPair &
P) {
2044 if (AllInstsAreIdentical) {
2054 for (
auto &SuccIter : OtherSuccIterRange) {
2062 assert(
Success &&
"We should not be trying to hoist callbases "
2063 "with non-intersectable attributes");
2081 unsigned SkippedFlags = 0;
2082 for (
const SuccIterPair &
P : SuccIterPairs)
2083 SkippedFlags |=
P.second;
2086 I1->dropUBImplyingAttrsAndMetadata();
2089 NumHoistCommonCode += SuccIterPairs.size();
2091 NumHoistCommonInstrs += SuccIterPairs.size();
2100 for (
auto &SuccIterPair : SuccIterPairs) {
2109bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2110 Instruction *TI, Instruction *I1,
2111 SmallVectorImpl<Instruction *> &OtherSuccTIs,
2121 auto *I2 = *OtherSuccTIs.
begin();
2141 for (PHINode &PN : Succ->
phis()) {
2142 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2143 for (Instruction *OtherSuccTI : OtherSuccTIs) {
2144 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2164 if (!
NT->getType()->isVoidTy()) {
2165 I1->replaceAllUsesWith(NT);
2166 for (Instruction *OtherSuccTI : OtherSuccTIs)
2167 OtherSuccTI->replaceAllUsesWith(NT);
2171 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2177 for (
auto *OtherSuccTI : OtherSuccTIs)
2178 Locs.
push_back(OtherSuccTI->getDebugLoc());
2190 std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
2192 for (PHINode &PN : Succ->
phis()) {
2193 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2194 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2200 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2210 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2211 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2212 PN.setIncomingValue(i, SI);
2220 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
2224 if (DTU && VisitedSuccs.
insert(Succ).second)
2225 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2231 for (BasicBlock *Succ : UniqueSuccessors)
2232 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2246 if (
I->isIntDivRem())
2261 std::optional<unsigned> NumUses;
2262 for (
auto *
I : Insts) {
2265 I->getType()->isTokenTy())
2270 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2278 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2282 NumUses =
I->getNumUses();
2283 else if (NumUses !=
I->getNumUses())
2289 for (
auto *
I : Insts) {
2303 for (
const Use &U : I0->
uses()) {
2304 auto It = PHIOperands.find(&U);
2305 if (It == PHIOperands.end())
2308 if (!
equal(Insts, It->second))
2322 if (HaveIndirectCalls) {
2323 if (!AllCallsAreIndirect)
2327 Value *Callee =
nullptr;
2331 Callee = CurrCallee;
2332 else if (Callee != CurrCallee)
2338 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2344 if (!
all_of(Insts, SameAsI0)) {
2349 !
all_of(Insts, CanReplaceOperand))
2353 for (
auto *
I : Insts)
2354 Ops.push_back(
I->getOperand(OI));
2364 auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
2369 for (
auto *BB : Blocks) {
2371 I =
I->getPrevNode();
2396 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2399 PN->insertBefore(BBEnd->begin());
2400 for (
auto *
I : Insts)
2401 PN->addIncoming(
I->getOperand(O),
I->getParent());
2410 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2413 for (
auto *
I : Insts)
2433 assert(
Success &&
"We should not be trying to sink callbases "
2434 "with non-intersectable attributes");
2445 PN->replaceAllUsesWith(I0);
2446 PN->eraseFromParent();
2450 for (
auto *
I : Insts) {
2455 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2456 I->replaceAllUsesWith(I0);
2457 I->eraseFromParent();
2507 bool HaveNonUnconditionalPredecessors =
false;
2513 HaveNonUnconditionalPredecessors =
true;
2515 if (UnconditionalPreds.
size() < 2)
2528 for (
const Use &U : PN.incoming_values())
2529 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2530 auto &
Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2532 Ops.push_back(*IncomingVals[
Pred]);
2540 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2553 if (!followedByDeoptOrUnreachable) {
2555 auto IsMemOperand = [](
Use &U) {
2568 unsigned NumPHIInsts = 0;
2569 for (
Use &U : (*LRI)[0]->operands()) {
2570 auto It = PHIOperands.
find(&U);
2572 return InstructionsToSink.contains(V);
2579 if (IsMemOperand(U) &&
2580 any_of(It->second, [](
Value *
V) { return isa<GEPOperator>(V); }))
2587 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2588 return NumPHIInsts <= 1;
2605 while (Idx < ScanIdx) {
2606 if (!ProfitableToSinkInstruction(LRI)) {
2609 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2622 if (Idx < ScanIdx) {
2625 InstructionsToSink = InstructionsProfitableToSink;
2631 !ProfitableToSinkInstruction(LRI) &&
2632 "We already know that the last instruction is unprofitable to sink");
2640 for (
auto *
I : *LRI)
2641 InstructionsProfitableToSink.
erase(
I);
2642 if (!ProfitableToSinkInstruction(LRI)) {
2645 InstructionsToSink = InstructionsProfitableToSink;
2659 if (HaveNonUnconditionalPredecessors) {
2660 if (!followedByDeoptOrUnreachable) {
2668 bool Profitable =
false;
2669 while (Idx < ScanIdx) {
2703 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2705 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2713 NumSinkCommonInstrs++;
2717 ++NumSinkCommonCode;
2723struct CompatibleSets {
2724 using SetTy = SmallVector<InvokeInst *, 2>;
2730 SetTy &getCompatibleSet(InvokeInst *
II);
2732 void insert(InvokeInst *
II);
2735CompatibleSets::SetTy &CompatibleSets::getCompatibleSet(InvokeInst *
II) {
2740 for (CompatibleSets::SetTy &Set : Sets) {
2741 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2746 return Sets.emplace_back();
2749void CompatibleSets::insert(InvokeInst *
II) {
2750 getCompatibleSet(
II).emplace_back(
II);
2754 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2757 auto IsIllegalToMerge = [](InvokeInst *
II) {
2758 return II->cannotMerge() ||
II->isInlineAsm();
2760 if (
any_of(Invokes, IsIllegalToMerge))
2768 if (HaveIndirectCalls) {
2769 if (!AllCallsAreIndirect)
2774 for (InvokeInst *
II : Invokes) {
2775 Value *CurrCallee =
II->getCalledOperand();
2776 assert(CurrCallee &&
"There is always a called operand.");
2779 else if (Callee != CurrCallee)
2786 auto HasNormalDest = [](InvokeInst *
II) {
2789 if (
any_of(Invokes, HasNormalDest)) {
2792 if (!
all_of(Invokes, HasNormalDest))
2797 for (InvokeInst *
II : Invokes) {
2799 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2801 NormalBB = CurrNormalBB;
2802 else if (NormalBB != CurrNormalBB)
2810 NormalBB, {Invokes[0]->getParent(), Invokes[1]->getParent()},
2820 auto HasOnlyIncomingPHIUses = [NormalBB](InvokeInst *
II) {
2821 return all_of(
II->uses(), [NormalBB,
II](
const Use &U) {
2822 auto *PN = dyn_cast<PHINode>(U.getUser());
2823 return PN && PN->getParent() == NormalBB &&
2824 PN->getIncomingBlock(U) == II->getParent();
2827 if (!
all_of(Invokes, HasOnlyIncomingPHIUses))
2835 for (InvokeInst *
II : Invokes) {
2837 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2839 UnwindBB = CurrUnwindBB;
2841 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2848 Invokes.front()->getUnwindDest(),
2849 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2854 const InvokeInst *II0 = Invokes.front();
2855 for (
auto *
II : Invokes.drop_front())
2860 auto IsIllegalToMergeArguments = [](
auto Ops) {
2861 Use &U0 = std::get<0>(
Ops);
2862 Use &U1 = std::get<1>(
Ops);
2868 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2869 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2870 IsIllegalToMergeArguments))
2882 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2888 bool HasNormalDest =
2893 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2897 II0->
getParent()->getIterator()->getNextNode();
2902 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2906 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2908 if (!HasNormalDest) {
2912 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2920 return MergedInvoke;
2934 SuccBBOfMergedInvoke});
2957 return II->getOperand(U.getOperandNo()) != U.get();
2976 Invokes.
front()->getParent());
2984 if (!MergedDebugLoc)
2985 MergedDebugLoc =
II->getDebugLoc();
2993 OrigSuccBB->removePredecessor(
II->getParent());
2999 assert(
Success &&
"Merged invokes with incompatible attributes");
3002 II->replaceAllUsesWith(MergedInvoke);
3003 II->eraseFromParent();
3007 ++NumInvokeSetsFormed;
3043 CompatibleSets Grouper;
3053 if (Invokes.
size() < 2)
3065class EphemeralValueTracker {
3066 SmallPtrSet<const Instruction *, 32> EphValues;
3068 bool isEphemeral(
const Instruction *
I) {
3071 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3072 all_of(
I->users(), [&](
const User *U) {
3073 return EphValues.count(cast<Instruction>(U));
3078 bool track(
const Instruction *
I) {
3079 if (isEphemeral(
I)) {
3132 unsigned MaxNumInstToLookAt = 9;
3136 if (!MaxNumInstToLookAt)
3138 --MaxNumInstToLookAt;
3151 if (
SI->getPointerOperand() == StorePtr &&
3152 SI->getValueOperand()->getType() == StoreTy &&
SI->isSimple() &&
3153 SI->getAlign() >= StoreToHoist->
getAlign()) {
3155 PreviousAccess =
SI;
3156 return SI->getValueOperand();
3162 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3163 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3165 bool ExplicitlyDereferenceableOnly;
3173 (!ExplicitlyDereferenceableOnly ||
3177 PreviousAccess = LI;
3192 unsigned &SpeculatedInstructions,
3200 bool HaveRewritablePHIs =
false;
3202 Value *OrigV = PN.getIncomingValueForBlock(BB);
3203 Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
3210 Cost +=
TTI.getCmpSelInstrCost(Instruction::Select, PN.getType(),
3219 HaveRewritablePHIs =
true;
3222 if (!OrigCE && !ThenCE)
3229 if (OrigCost + ThenCost > MaxCost)
3236 ++SpeculatedInstructions;
3237 if (SpeculatedInstructions > 1)
3241 return HaveRewritablePHIs;
3245 std::optional<bool> Invert,
3249 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3256 if (!Invert.has_value())
3259 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3263 return BIEndProb < Likely;
3303bool SimplifyCFGOpt::speculativelyExecuteBB(CondBrInst *BI,
3304 BasicBlock *ThenBB) {
3315 bool Invert =
false;
3330 SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
3332 SmallVector<Instruction *, 4> SpeculatedPseudoProbes;
3334 unsigned SpeculatedInstructions = 0;
3335 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3336 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
3337 Value *SpeculatedStoreValue =
nullptr;
3338 StoreInst *SpeculatedStore =
nullptr;
3340 EphemeralValueTracker EphTracker;
3355 if (EphTracker.track(&
I))
3360 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3362 SpeculatedConditionalLoadsStores.
size() <
3366 if (IsSafeCheapLoadStore)
3367 SpeculatedConditionalLoadsStores.
push_back(&
I);
3369 ++SpeculatedInstructions;
3371 if (SpeculatedInstructions > 1)
3375 if (!IsSafeCheapLoadStore &&
3379 PreviousStoreAccess))))
3381 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3387 if (!SpeculatedStore && SpeculatedStoreValue)
3393 for (Use &
Op :
I.operands()) {
3398 ++SinkCandidateUseCounts[OpI];
3405 for (
const auto &[Inst,
Count] : SinkCandidateUseCounts)
3406 if (Inst->hasNUses(
Count)) {
3407 ++SpeculatedInstructions;
3408 if (SpeculatedInstructions > 1)
3415 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3418 SpeculatedInstructions,
Cost,
TTI);
3419 if (!Convert ||
Cost > Budget)
3423 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3428 if (SpeculatedStoreValue) {
3432 Value *FalseV = SpeculatedStoreValue;
3436 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3466 for (DbgVariableRecord *DbgAssign :
3469 DbgAssign->replaceVariableLocationOp(OrigV, S);
3479 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3481 I.dropUBImplyingAttrsAndMetadata();
3483 assert(PreviousStoreAccess &&
"Missing previous store access");
3486 I.dropUBImplyingAttrsAndMetadata();
3487 I.setAAMetadata(MergedAA);
3491 if (EphTracker.contains(&
I)) {
3493 I.eraseFromParent();
3499 for (
auto &It : *ThenBB)
3504 !DVR || !DVR->isDbgAssign())
3505 It.dropOneDbgRecord(&DR);
3507 std::prev(ThenBB->end()));
3509 if (!SpeculatedConditionalLoadsStores.
empty())
3515 for (PHINode &PN : EndBB->
phis()) {
3516 unsigned OrigI = PN.getBasicBlockIndex(BB);
3517 unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
3518 Value *OrigV = PN.getIncomingValue(OrigI);
3519 Value *ThenV = PN.getIncomingValue(ThenI);
3528 Value *TrueV = ThenV, *FalseV = OrigV;
3533 BrCond, TrueV, FalseV, PN.getFastMathFlagsOrNone(),
"spec.select", BI);
3534 PN.setIncomingValue(OrigI,
V);
3535 PN.setIncomingValue(ThenI,
V);
3539 for (Instruction *
I : SpeculatedPseudoProbes)
3540 I->eraseFromParent();
3553 if (!ReachesNonLocalUses.
insert(BB).second)
3572 if (!Header->hasNPredecessors(2))
3576 while (!Worklist.
empty()) {
3578 if (BB == Header || !Visited.
insert(BB).second)
3595 EphemeralValueTracker EphTracker;
3602 if (CI->cannotDuplicate() || CI->isConvergent())
3615 for (
User *U :
I.users()) {
3618 if (UsedInBB == BB) {
3622 NonLocalUseBlocks.
insert(UsedInBB);
3636 if (
I &&
I->getParent() == To)
3656 static constexpr unsigned MaxInstructionsToScan = 512;
3670 unsigned NumScannedInstructions = 0;
3671 while (!Worklist.
empty()) {
3675 if (!CanReachStop.
insert(BB).second)
3679 if (++NumScannedInstructions > MaxInstructionsToScan)
3683 BlocksWithUncontrolledConvergentCalls.
insert(BB);
3697 while (!Worklist.
empty()) {
3699 if (BB == StopBB || !CanReachStop.
contains(BB))
3702 if (!Visited.
insert(BB).second)
3705 if (BlocksWithUncontrolledConvergentCalls.
contains(BB))
3741 if (KnownValues.
empty())
3766 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3769 for (
const auto &Pair : KnownValues) {
3786 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3789 if (KeepCanonicalLoop &&
3803 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3806 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3816 EdgeBB->setName(RealDest->
getName() +
".critedge");
3817 EdgeBB->moveBefore(RealDest);
3827 TranslateMap[
Cond] = CB;
3840 N->insertInto(EdgeBB, InsertPt);
3843 N->setName(BBI->getName() +
".c");
3854 if (!BBI->use_empty())
3855 TranslateMap[&*BBI] =
V;
3856 if (!
N->mayHaveSideEffects()) {
3857 N->eraseFromParent();
3862 if (!BBI->use_empty())
3863 TranslateMap[&*BBI] =
N;
3869 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3870 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3871 SrcDbgCursor = std::next(BBI);
3873 N->cloneDebugInfoFrom(&*BBI);
3882 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3883 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3884 InsertPt->cloneDebugInfoFrom(BI);
3905 return std::nullopt;
3911bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(CondBrInst *BI) {
3914 bool KeepCanonicalLoop =
3917 std::optional<bool>
Result;
3918 bool EverChanged =
false;
3924 }
while (Result == std::nullopt);
3933 bool SpeculateUnpredictables) {
3955 return isa<UncondBrInst>(IfBlock->getTerminator());
3958 "Will have either one or two blocks to speculate.");
3965 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3966 if (!IsUnpredictable) {
3969 (TWeight + FWeight) != 0) {
3974 if (IfBlocks.
size() == 1) {
3976 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3977 if (BIBBProb >= Likely)
3980 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3989 if (IfCondPhiInst->getParent() == BB)
3997 unsigned NumPhis = 0;
4010 if (SpeculateUnpredictables && IsUnpredictable)
4011 Budget +=
TTI.getBranchMispredictPenalty();
4024 AggressiveInsts, Cost, Budget,
TTI, AC,
4025 ZeroCostInstructions) ||
4027 AggressiveInsts, Cost, Budget,
TTI, AC,
4028 ZeroCostInstructions))
4041 auto IsBinOpOrAndEq = [](
Value *
V) {
4077 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
4079 <<
" F: " << IfFalse->
getName() <<
"\n");
4096 Value *Sel = Builder.CreateSelectFMF(IfCond, TrueVal, FalseVal,
4101 PN->eraseFromParent();
4107 Builder.CreateBr(BB);
4128 return Builder.CreateBinOp(
Opc,
LHS,
RHS, Name);
4129 if (
Opc == Instruction::And)
4130 return Builder.CreateLogicalAnd(
LHS,
RHS, Name);
4131 if (
Opc == Instruction::Or)
4132 return Builder.CreateLogicalOr(
LHS,
RHS, Name);
4144 bool PredHasWeights =
4146 bool SuccHasWeights =
4148 if (PredHasWeights || SuccHasWeights) {
4149 if (!PredHasWeights)
4150 PredTrueWeight = PredFalseWeight = 1;
4151 if (!SuccHasWeights)
4152 SuccTrueWeight = SuccFalseWeight = 1;
4162static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
4165 assert(BI && PBI &&
"Both blocks must end with a conditional branches.");
4167 "PredBB must be a predecessor of BB.");
4175 (PTWeight + PFWeight) != 0) {
4178 Likely =
TTI->getPredictableBranchThreshold();
4183 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4184 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4188 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4191 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4192 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4198 return std::nullopt;
4211 bool InvertPredCond;
4212 std::tie(CommonSucc,
Opc, InvertPredCond) =
4215 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4223 I->copyMetadata(*BB->
getTerminator(), LLVMContext::MD_annotation);
4228 if (InvertPredCond) {
4241 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4244 SuccTrueWeight, SuccFalseWeight)) {
4250 MDWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4255 MDWeights.
push_back(PredFalseWeight * (SuccFalseWeight + SuccTrueWeight) +
4256 PredTrueWeight * SuccFalseWeight);
4262 MDWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4263 PredFalseWeight * SuccTrueWeight);
4265 MDWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4308 if (!MDWeights.
empty()) {
4309 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
4317 ++NumFoldBranchToCommonDest;
4324 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4325 return U->getType()->isVectorTy();
4336 unsigned BonusInstThreshold) {
4345 Cond->getParent() != BB || !
Cond->hasOneUse())
4366 bool InvertPredCond;
4368 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4379 Cost +=
TTI->getArithmeticInstrCost(Instruction::Xor, Ty, CostKind);
4400 unsigned NumBonusInsts = 0;
4401 bool SawVectorOp =
false;
4402 const unsigned PredCount = Preds.
size();
4406 PredCount == 1 ? Preds[0]->getTerminator() :
nullptr;
4424 if (!
TTI ||
TTI->getInstructionCost(&
I, CostKind) !=
4426 NumBonusInsts += PredCount;
4434 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4437 return PN->getIncomingBlock(U) == BB;
4438 return UI->
getParent() == BB &&
I.comesBefore(UI);
4442 if (!
all_of(
I.uses(), IsBCSSAUse))
4446 BonusInstThreshold *
4462 for (
auto *BB : {BB1, BB2}) {
4478 Value *AlternativeV =
nullptr) {
4504 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4505 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4513 if (!AlternativeV &&
4519 PHI->addIncoming(
V, BB);
4529 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4538 if (!PStore || !QStore)
4561 if (
I.mayReadOrWriteMemory())
4563 for (
auto &
I : *QFB)
4564 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4567 for (
auto &
I : *QTB)
4568 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4572 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4586 for (
auto &
I : *BB) {
4588 if (
I.isTerminator())
4606 "When we run out of budget we will eagerly return from within the "
4607 "per-instruction loop.");
4611 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4613 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4614 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4648 InvertPCond ^= (PStore->
getParent() != PTB);
4649 InvertQCond ^= (QStore->
getParent() != QTB);
4669 {CombinedWeights[0], CombinedWeights[1]},
4676 SI->copyMetadata(*QStore);
4682 DbgAssign->replaceVariableLocationOp(PStore->
getValueOperand(), QPHI);
4685 DbgAssign->replaceVariableLocationOp(QStore->
getValueOperand(), QPHI);
4748 bool InvertPCond =
false, InvertQCond =
false;
4754 if (QFB == PostBB) {
4773 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4776 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4784 for (
auto *BB : {PTB, PFB}) {
4789 PStoreAddresses.
insert(
SI->getPointerOperand());
4791 for (
auto *BB : {QTB, QFB}) {
4796 QStoreAddresses.
insert(
SI->getPointerOperand());
4802 auto &CommonAddresses = PStoreAddresses;
4805 for (
auto *Address : CommonAddresses)
4808 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4826 !BI->
getParent()->getSinglePredecessor())
4828 if (!IfFalseBB->
phis().empty())
4838 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4912 if (&*BB->
begin() != BI)
4940 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4942 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4946 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4949 if (CommonDestProb >= Likely)
4959 unsigned NumPhis = 0;
4981 if (OtherDest == BB) {
4989 OtherDest = InfLoopBlock;
5001 PBICond = Builder.CreateNot(PBICond, PBICond->
getName() +
".not");
5005 BICond = Builder.CreateNot(BICond, BICond->
getName() +
".not");
5009 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
5024 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
5025 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
5028 SuccTrueWeight, SuccFalseWeight);
5030 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
5031 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
5032 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
5033 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
5037 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
5038 PredOther * SuccCommon,
5039 PredOther * SuccOther};
5046 assert(isSelectInRoleOfConjunctionOrDisjunction(
SI));
5048 assert(
SI->getCondition() == PBICond);
5065 Value *BIV = PN.getIncomingValueForBlock(BB);
5066 unsigned PBBIdx = PN.getBasicBlockIndex(PBI->
getParent());
5067 Value *PBIV = PN.getIncomingValue(PBBIdx);
5071 Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->
getName() +
".mux"));
5072 PN.setIncomingValue(PBBIdx, NV);
5076 uint64_t TrueWeight = PBIOp ? PredFalseWeight : PredTrueWeight;
5077 uint64_t FalseWeight = PBIOp ? PredTrueWeight : PredFalseWeight;
5097bool SimplifyCFGOpt::simplifyTerminatorOnSelect(Instruction *OldTerm,
5099 BasicBlock *FalseBB,
5100 uint32_t TrueWeight,
5101 uint32_t FalseWeight) {
5108 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
5110 SmallSetVector<BasicBlock *, 2> RemovedSuccessors;
5113 for (BasicBlock *Succ :
successors(OldTerm)) {
5115 if (Succ == KeepEdge1)
5116 KeepEdge1 =
nullptr;
5117 else if (Succ == KeepEdge2)
5118 KeepEdge2 =
nullptr;
5123 if (Succ != TrueBB && Succ != FalseBB)
5124 RemovedSuccessors.
insert(Succ);
5132 if (!KeepEdge1 && !KeepEdge2) {
5133 if (TrueBB == FalseBB) {
5144 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
5164 SmallVector<DominatorTree::UpdateType, 2> Updates;
5166 for (
auto *RemovedSuccessor : RemovedSuccessors)
5167 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
5182bool SimplifyCFGOpt::simplifySwitchOnSelectRemap(SwitchInst *SI,
5184 ConstantInt *
C,
bool Negate) {
5195 BasicBlock *DestFork =
SI->findCaseValue(K)->getCaseSuccessor();
5196 auto CaseC =
SI->findCaseValue(
C);
5197 bool IsDefault = CaseC ==
SI->case_default();
5199 BasicBlock *OldDest = CaseC->getCaseSuccessor();
5204 SI->setCondition(
X);
5206 if (OldDest != DestFork) {
5210 SI->addCase(
C, DestFork);
5212 CaseC->setSuccessor(DestFork);
5219 bool OldDestStillTargeted =
any_of(
5220 successors(SI), [&](BasicBlock *Succ) {
return Succ == OldDest; });
5221 if (DTU && !OldDestStillTargeted)
5222 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
5227 SmallVector<uint32_t> SwitchWeights;
5235 bool SelectHasBranchWeights =
5240 if (SwitchHasBranchWeights && SelectHasBranchWeights &&
5248 SmallVector<uint64_t> NewSwitchWeights;
5249 NewSwitchWeights.reserve(SwitchWeights.
size());
5250 NewSwitchWeights.push_back(SwitchWeights[0] * SelectTotalWeight);
5251 for (
const auto &[SwitchCase, SwitchWeight] :
5253 if (SwitchCase.getCaseValue() ==
C) {
5255 }
else if (SwitchCase.getCaseValue() == K) {
5259 uint64_t ProbabilityKeyEqualsK = SwitchWeight * SelectTotalWeight;
5262 ProbabilityKeyEqualsK > ProbabilityXEqualsC
5263 ? ProbabilityKeyEqualsK - ProbabilityXEqualsC
5265 NewSwitchWeights.push_back(ProbabilityXEqualsK);
5267 NewSwitchWeights.push_back(SwitchWeight * SelectTotalWeight);
5271 }
else if (SwitchHasBranchWeights) {
5277 SI->setMetadata(LLVMContext::MD_prof,
nullptr);
5291bool SimplifyCFGOpt::simplifySwitchOnSelect(SwitchInst *SI,
5296 if (
Select->hasOneUse() &&
5300 simplifySwitchOnSelectRemap(SI,
Select,
X,
C,
Pred == ICmpInst::ICMP_NE))
5306 if (!TrueVal || !FalseVal)
5311 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
5312 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
5315 uint32_t TrueWeight = 0, FalseWeight = 0;
5316 SmallVector<uint64_t, 8> Weights;
5320 if (Weights.
size() == 1 +
SI->getNumCases()) {
5322 (uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
5324 (uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
5329 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
5338bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
5352 SmallVector<uint32_t> SelectBranchWeights(2);
5355 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB,
5356 SelectBranchWeights[0],
5357 SelectBranchWeights[1]);
5377bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5381 return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI,
nullptr, Builder);
5427bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
5446 ConstantInt *NewCaseVal;
5454 Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
5460 SelectTrueVal = Builder.
getTrue();
5461 SelectFalseVal = Builder.
getFalse();
5464 SelectCond =
Select->getCondition();
5466 if (SelectCond != ICI)
5468 SelectTrueVal =
Select->getTrueValue();
5469 SelectFalseVal =
Select->getFalseValue();
5474 if (
SI->getCondition() != IcmpCond)
5480 if (
SI->getDefaultDest() != BB) {
5481 ConstantInt *VVal =
SI->findCaseDest(BB);
5482 assert(VVal &&
"Should have a unique destination value");
5490 return requestResimplify();
5496 if (
SI->findCaseValue(NewCaseVal) !=
SI->case_default()) {
5498 if (Predicate == ICmpInst::ICMP_EQ)
5506 return requestResimplify();
5513 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5519 Value *DefaultCst = SelectFalseVal;
5520 Value *NewCst = SelectTrueVal;
5528 Select->replaceAllUsesWith(DefaultCst);
5529 Select->eraseFromParent();
5535 SmallVector<DominatorTree::UpdateType, 2> Updates;
5542 SwitchInstProfUpdateWrapper SIW(*SI);
5543 auto W0 = SIW.getSuccessorWeight(0);
5547 SIW.setSuccessorWeight(0, *NewW);
5549 SIW.addCase(NewCaseVal, NewBB, NewW);
5560 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5568bool SimplifyCFGOpt::simplifyBranchOnICmpChain(CondBrInst *BI,
5570 const DataLayout &
DL) {
5580 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5582 SmallVectorImpl<ConstantInt *> &
Values = ConstantCompare.Vals;
5583 Value *CompVal = ConstantCompare.CompValue;
5584 unsigned UsedICmps = ConstantCompare.UsedICmps;
5585 Value *ExtraCase = ConstantCompare.Extra;
5586 bool TrueWhenEqual = ConstantCompare.IsEq;
5603 if (ExtraCase &&
Values.size() < 2)
5606 SmallVector<uint32_t> BranchWeights;
5612 if (!TrueWhenEqual) {
5615 std::swap(BranchWeights[0], BranchWeights[1]);
5621 <<
" cases into SWITCH. BB is:\n"
5624 SmallVector<DominatorTree::UpdateType, 2> Updates;
5631 nullptr,
"switch.early.test");
5642 AssumptionCache *AC =
Options.AC;
5648 auto *Br = TrueWhenEqual ? Builder.
CreateCondBr(ExtraCase, EdgeBB, NewBB)
5655 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5661 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5662 <<
"\nEXTRABB = " << *BB);
5670 "Should not end up here with unstable pointers");
5672 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5677 if (
Values.front()->getValue() -
Values.back()->getValue() ==
5680 Values.back()->getValue(),
Values.front()->getValue() + 1);
5682 ICmpInst::Predicate
Pred;
5694 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5695 NewBI->
setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5700 if (MDNode *Unpredictable = BI->
getMetadata(LLVMContext::MD_unpredictable))
5701 New->setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
5706 SmallVector<uint32_t> NewWeights(
Values.size() + 1);
5707 NewWeights[0] = BranchWeights[1];
5710 V = BranchWeights[0] /
Values.size();
5717 for (ConstantInt *Val :
Values)
5718 New->addCase(Val, EdgeBB);
5726 for (
unsigned i = 0, e =
Values.size() - 1; i != e; ++i)
5736 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5740bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI,
IRBuilder<> &Builder) {
5742 return simplifyCommonResume(RI);
5746 return simplifySingleResume(RI);
5755 if (!
II ||
II->getIntrinsicID() != Intrinsic::lifetime_end)
5762bool SimplifyCFGOpt::simplifyCommonResume(ResumeInst *RI) {
5771 SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
5775 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues(); Idx !=
End;
5777 auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
5778 auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
5782 if (IncomingBB->getUniqueSuccessor() != BB)
5787 if (IncomingValue != LandingPad)
5791 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5792 TrivialUnwindBlocks.
insert(IncomingBB);
5796 if (TrivialUnwindBlocks.
empty())
5800 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5804 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5807 for (BasicBlock *
Pred :
5818 TrivialBB->getTerminator()->eraseFromParent();
5819 new UnreachableInst(RI->
getContext(), TrivialBB);
5821 DTU->
applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5828 return !TrivialUnwindBlocks.empty();
5832bool SimplifyCFGOpt::simplifySingleResume(ResumeInst *RI) {
5836 "Resume must unwind the exception that caused control to here");
5892 int Idx = DestPN.getBasicBlockIndex(BB);
5906 Value *SrcVal = DestPN.getIncomingValue(Idx);
5909 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5913 DestPN.addIncoming(Incoming,
Pred);
5940 std::vector<DominatorTree::UpdateType> Updates;
5944 if (UnwindDest ==
nullptr) {
5985 if (!SuccessorCleanupPad)
5994 SuccessorCleanupPad->eraseFromParent();
6003bool SimplifyCFGOpt::simplifyCleanupReturn(CleanupReturnInst *RI) {
6020bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
6052 BBI->dropDbgRecords();
6056 BBI->eraseFromParent();
6062 if (&BB->
front() != UI)
6065 std::vector<DominatorTree::UpdateType> Updates;
6068 for (BasicBlock *Predecessor : Preds) {
6076 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6087 "The destinations are guaranteed to be different here.");
6104 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6106 SwitchInstProfUpdateWrapper SU(*SI);
6107 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
6108 if (i->getCaseSuccessor() != BB) {
6113 i = SU.removeCase(i);
6118 if (DTU &&
SI->getDefaultDest() != BB)
6119 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6121 if (
II->getUnwindDest() == BB) {
6127 if (!CI->doesNotThrow())
6128 CI->setDoesNotThrow();
6132 if (CSI->getUnwindDest() == BB) {
6143 E = CSI->handler_end();
6146 CSI->removeHandler(
I);
6153 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6154 if (CSI->getNumHandlers() == 0) {
6155 if (CSI->hasUnwindDest()) {
6159 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
6160 Updates.push_back({DominatorTree::Insert,
6161 PredecessorOfPredecessor,
6162 CSI->getUnwindDest()});
6163 Updates.push_back({DominatorTree::Delete,
6164 PredecessorOfPredecessor, Predecessor});
6167 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
6174 SmallVector<BasicBlock *, 8> EHPreds(
predecessors(Predecessor));
6175 for (BasicBlock *EHPred : EHPreds)
6179 new UnreachableInst(CSI->getContext(), CSI->getIterator());
6180 CSI->eraseFromParent();
6185 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
6186 "Expected to always have an unwind to BB.");
6188 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
6216static std::optional<ContiguousCasesResult>
6223 const APInt &Min = Cases.
back()->getValue();
6224 const APInt &Max = Cases.
front()->getValue();
6226 size_t ContiguousOffset = Cases.
size() - 1;
6227 if (
Offset == ContiguousOffset) {
6246 std::adjacent_find(Cases.
begin(), Cases.
end(), [](
auto L,
auto R) {
6247 return L->getValue() != R->getValue() + 1;
6249 if (It == Cases.
end())
6250 return std::nullopt;
6251 auto [OtherMax, OtherMin] = std::make_pair(*It, *std::next(It));
6252 if ((Max - OtherMax->getValue()) + (OtherMin->getValue() - Min) ==
6256 ConstantInt::get(OtherMin->getType(), OtherMin->getValue() + 1)),
6259 ConstantInt::get(OtherMax->getType(), OtherMax->getValue() - 1)),
6267 return std::nullopt;
6272 bool RemoveOrigDefaultBlock =
true) {
6274 auto *BB = Switch->getParent();
6275 auto *OrigDefaultBlock = Switch->getDefaultDest();
6276 if (RemoveOrigDefaultBlock)
6277 OrigDefaultBlock->removePredecessor(BB);
6281 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
6283 Switch->setDefaultDest(&*NewDefaultBlock);
6287 if (RemoveOrigDefaultBlock &&
6297bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(SwitchInst *SI,
6299 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
6301 bool HasDefault = !
SI->defaultDestUnreachable();
6303 auto *BB =
SI->getParent();
6305 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
6310 for (
auto Case :
SI->cases()) {
6314 if (Dest == DestA) {
6320 if (Dest == DestB) {
6330 "Single-destination switch should have been folded.");
6332 assert(DestB !=
SI->getDefaultDest());
6333 assert(!CasesB.
empty() &&
"There must be non-default cases.");
6337 std::optional<ContiguousCasesResult> ContiguousCases;
6340 if (!HasDefault && CasesA.
size() == 1)
6341 ContiguousCases = ContiguousCasesResult{
6349 else if (CasesB.
size() == 1)
6350 ContiguousCases = ContiguousCasesResult{
6359 else if (!HasDefault)
6363 if (!ContiguousCases)
6367 if (!ContiguousCases)
6370 auto [Min,
Max, Dest, OtherDest, Cases, OtherCases] = *ContiguousCases;
6376 Max->getValue() - Min->getValue() + 1);
6379 assert(
Max->getValue() == Min->getValue());
6384 else if (NumCases->
isNullValue() && !Cases->empty()) {
6388 if (!
Offset->isNullValue())
6396 SmallVector<uint64_t, 8> Weights;
6399 "expected number of branch weights to be equal to the number of "
6400 "switch destinations");
6403 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
6404 if (
SI->getSuccessor(
I) == Dest)
6405 TrueWeight += Weights[
I];
6407 FalseWeight += Weights[
I];
6417 unsigned PreviousEdges = Cases->size();
6418 if (Dest ==
SI->getDefaultDest())
6420 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
6421 PHI.removeIncomingValue(
SI->getParent());
6424 unsigned PreviousEdges = OtherCases->size();
6425 if (OtherDest ==
SI->getDefaultDest())
6427 unsigned E = PreviousEdges - 1;
6431 for (
unsigned I = 0;
I !=
E; ++
I)
6432 PHI.removeIncomingValue(
SI->getParent());
6436 SmallVector<DominatorTree::UpdateType, 2> Updates;
6440 Updates.
push_back({DominatorTree::Delete, BB, OrigDefaultBlock});
6444 SI->eraseFromParent();
6447 Updates.
push_back({DominatorTree::Delete, BB, OtherDest});
6467 unsigned MaxSignificantBitsInCond =
6474 for (
const auto &Case :
SI->cases()) {
6475 auto *
Successor = Case.getCaseSuccessor();
6484 if (
Known.Zero.intersects(CaseVal) || !
Known.One.isSubsetOf(CaseVal) ||
6486 (IsKnownValuesValid && !KnownValues.
contains(CaseC))) {
6492 }
else if (IsKnownValuesValid)
6493 KnownValues.
erase(CaseC);
6500 bool HasDefault = !
SI->defaultDestUnreachable();
6501 const unsigned NumUnknownBits =
6504 if (HasDefault && DeadCases.
empty()) {
6510 if (NumUnknownBits < 64 ) {
6511 uint64_t AllNumCases = 1ULL << NumUnknownBits;
6512 if (
SI->getNumCases() == AllNumCases) {
6519 if (
SI->getNumCases() == AllNumCases - 1) {
6520 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
6522 if (CondTy->getIntegerBitWidth() > 64 ||
6523 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6527 for (
const auto &Case :
SI->cases())
6528 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
6530 ConstantInt::get(
Cond->getType(), MissingCaseVal));
6532 SIW.
addCase(MissingCase,
SI->getDefaultDest(),
6542 if (DeadCases.
empty())
6548 assert(CaseI !=
SI->case_default() &&
6549 "Case was not found. Probably mistake in DeadCases forming.");
6551 CaseI->getCaseSuccessor()->removePredecessor(
SI->getParent());
6556 std::vector<DominatorTree::UpdateType> Updates;
6557 for (
auto *
Successor : UniqueSuccessors)
6558 if (NumPerSuccessorCases[
Successor] == 0)
6585 int Idx =
PHI.getBasicBlockIndex(BB);
6586 assert(Idx >= 0 &&
"PHI has no entry for predecessor?");
6588 Value *InValue =
PHI.getIncomingValue(Idx);
6589 if (InValue != CaseValue)
6605 ForwardingNodesMap ForwardingNodes;
6608 for (
const auto &Case :
SI->cases()) {
6610 BasicBlock *CaseDest = Case.getCaseSuccessor();
6629 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6630 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6631 count(Phi.blocks(), SwitchBlock) == 1) {
6632 Phi.setIncomingValue(SwitchBBIdx,
SI->getCondition());
6640 ForwardingNodes[Phi].push_back(PhiIdx);
6643 for (
auto &ForwardingNode : ForwardingNodes) {
6644 PHINode *Phi = ForwardingNode.first;
6650 for (
int Index : Indexes)
6651 Phi->setIncomingValue(Index,
SI->getCondition());
6661 if (
C->isThreadDependent())
6663 if (
C->isDLLImportDependent())
6671 if (
C->getType()->isScalableTy())
6682 if (!
TTI.shouldBuildLookupTablesForConstant(
C))
6709 if (
A->isAllOnesValue())
6711 if (
A->isNullValue())
6717 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
6742 ConstantPool.insert(std::make_pair(
SI->getCondition(), CaseVal));
6744 if (
I.isTerminator()) {
6746 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6749 CaseDest =
I.getSuccessor(0);
6756 for (
auto &
Use :
I.uses()) {
6759 if (
I->getParent() == CaseDest)
6762 if (Phi->getIncomingBlock(
Use) == CaseDest)
6775 *CommonDest = CaseDest;
6777 if (CaseDest != *CommonDest)
6782 int Idx =
PHI.getBasicBlockIndex(
Pred);
6791 Res.push_back(std::make_pair(&
PHI, ConstVal));
6794 return Res.
size() > 0;
6800 SwitchCaseResultVectorTy &UniqueResults,
6802 for (
auto &
I : UniqueResults) {
6803 if (
I.first == Result) {
6804 I.second.push_back(CaseVal);
6805 return I.second.size();
6808 UniqueResults.push_back(
6819 SwitchCaseResultVectorTy &UniqueResults,
6823 for (
const auto &
I :
SI->cases()) {
6837 const size_t NumCasesForResult =
6845 if (UniqueResults.size() > MaxUniqueResults)
6861 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6863 return DefaultResult ||
SI->defaultDestUnreachable();
6885 const bool HasBranchWeights = !BranchWeights.
empty();
6887 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6888 ResultVector[1].second.size() == 1) {
6889 ConstantInt *FirstCase = ResultVector[0].second[0];
6890 ConstantInt *SecondCase = ResultVector[1].second[0];
6891 Value *SelectValue = ResultVector[1].first;
6892 if (DefaultResult) {
6893 Value *ValueCompare =
6894 Builder.CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6895 SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
6896 DefaultResult,
"switch.select");
6898 SI && HasBranchWeights) {
6905 *
SI, {BranchWeights[2], BranchWeights[0] + BranchWeights[1]},
6909 Value *ValueCompare =
6910 Builder.CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6911 Value *Ret = Builder.CreateSelect(ValueCompare, ResultVector[0].first,
6912 SelectValue,
"switch.select");
6918 size_t FirstCasePos = (Condition !=
nullptr);
6919 size_t SecondCasePos = FirstCasePos + 1;
6920 uint32_t DefaultCase = (Condition !=
nullptr) ? BranchWeights[0] : 0;
6922 {BranchWeights[FirstCasePos],
6923 DefaultCase + BranchWeights[SecondCasePos]},
6930 if (ResultVector.size() == 1 && DefaultResult) {
6932 unsigned CaseCount = CaseValues.
size();
6945 for (
auto *Case : CaseValues) {
6946 if (Case->getValue().slt(MinCaseVal->
getValue()))
6948 AndMask &= Case->getValue();
6952 if (!AndMask.
isZero() &&
Known.getMaxValue().uge(AndMask)) {
6954 unsigned FreeBits =
Known.countMaxActiveBits() - AndMask.
popcount();
6958 if (FreeBits ==
Log2_32(CaseCount)) {
6959 Value *
And = Builder.CreateAnd(Condition, AndMask);
6960 Value *Cmp = Builder.CreateICmpEQ(
6963 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6979 for (
auto *Case : CaseValues)
6980 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6986 Condition = Builder.CreateSub(Condition, MinCaseVal);
6987 Value *
And = Builder.CreateAnd(Condition, ~BitMask,
"switch.and");
6988 Value *Cmp = Builder.CreateICmpEQ(
6991 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
7004 if (CaseValues.
size() == 2) {
7005 Value *Cmp1 = Builder.CreateICmpEQ(Condition, CaseValues[0],
7006 "switch.selectcmp.case1");
7007 Value *Cmp2 = Builder.CreateICmpEQ(Condition, CaseValues[1],
7008 "switch.selectcmp.case2");
7009 Value *Cmp = Builder.CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
7011 Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
7031 std::vector<DominatorTree::UpdateType> Updates;
7038 Builder.CreateBr(DestBB);
7042 PHI->removeIncomingValueIf(
7043 [&](
unsigned Idx) {
return PHI->getIncomingBlock(Idx) == SelectBB; });
7044 PHI->addIncoming(SelectValue, SelectBB);
7047 for (
unsigned i = 0, e =
SI->getNumSuccessors(); i < e; ++i) {
7053 if (DTU && RemovedSuccessors.
insert(Succ).second)
7056 SI->eraseFromParent();
7071 SwitchCaseResultVectorTy UniqueResults;
7077 assert(
PHI !=
nullptr &&
"PHI for value select not found");
7078 Builder.SetInsertPoint(
SI);
7080 [[maybe_unused]]
auto HasWeights =
7084 (BranchWeights.
size() >=
7085 UniqueResults.size() + (DefaultResult !=
nullptr)));
7088 Builder,
DL, AC,
SI, BranchWeights);
7100class SwitchReplacement {
7108 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7109 Constant *DefaultValue,
const DataLayout &
DL,
7110 const TargetTransformInfo &
TTI,
const StringRef &FuncName);
7119 static bool wouldFitInRegister(
const DataLayout &
DL,
uint64_t TableSize,
7126 bool isLookupTable();
7132 bool isValid()
const {
return Kind != InvalidKind; }
7169 ConstantInt *BitMap =
nullptr;
7170 IntegerType *BitMapElementTy =
nullptr;
7173 ConstantInt *LinearOffset =
nullptr;
7174 ConstantInt *LinearMultiplier =
nullptr;
7175 bool LinearMapValWrapped =
false;
7183SwitchReplacement::SwitchReplacement(
7185 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &
Values,
7186 Constant *DefaultValue,
const DataLayout &
DL,
7187 const TargetTransformInfo &
TTI,
const StringRef &FuncName)
7188 : DefaultValue(DefaultValue) {
7189 assert(
Values.size() &&
"Can't build lookup table without values!");
7190 assert(TableSize >=
Values.size() &&
"Can't fit values in table!");
7193 SingleValue =
Values.begin()->second;
7199 for (
const auto &[CaseVal, CaseRes] :
Values) {
7203 TableContents[
Idx] = CaseRes;
7210 if (
Values.size() < TableSize) {
7212 "Need a default value to fill the lookup table holes.");
7215 if (!TableContents[
I])
7216 TableContents[
I] = DefaultValue;
7222 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
7223 SingleValue =
nullptr;
7229 Kind = SingleValueKind;
7236 bool LinearMappingPossible =
true;
7241 bool NonMonotonic =
false;
7242 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
7258 LinearMappingPossible =
false;
7263 APInt Dist = Val - PrevVal;
7266 }
else if (Dist != DistToPrev) {
7267 LinearMappingPossible =
false;
7275 if (LinearMappingPossible) {
7277 LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
7278 APInt M = LinearMultiplier->getValue();
7279 bool MayWrap =
true;
7280 if (
isIntN(M.getBitWidth(), TableSize - 1))
7281 (void)M.
smul_ov(
APInt(M.getBitWidth(), TableSize - 1), MayWrap);
7282 LinearMapValWrapped = NonMonotonic || MayWrap;
7283 Kind = LinearMapKind;
7290 if (wouldFitInRegister(
DL, TableSize,
ValueType) &&
7293 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
7295 TableInt <<=
IT->getBitWidth();
7299 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
7302 BitMap = ConstantInt::get(M.getContext(), TableInt);
7303 BitMapElementTy =
IT;
7309 if (!
all_of(TableContents,
7321 unsigned NeededBitWidth =
7322 std::max(
TTI.getMinimumLookupTableEntryBitWidth(),
7335 Kind = LookupTableKind;
7343 case SingleValueKind:
7345 case LinearMapKind: {
7349 false,
"switch.idx.cast");
7350 if (!LinearMultiplier->
isOne())
7351 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
7353 !LinearMapValWrapped);
7355 if (!LinearOffset->
isZero())
7358 !LinearMapValWrapped);
7375 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->
getBitWidth()),
7376 "switch.shiftamt",
true,
true);
7379 Value *DownShifted =
7380 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
7382 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
7384 case LookupTableKind: {
7387 new GlobalVariable(*
Func->getParent(), Initializer->
getType(),
7388 true, GlobalVariable::PrivateLinkage,
7389 Initializer,
"switch.table." +
Func->getName());
7390 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
7394 Type *IndexTy =
DL.getIndexType(
Table->getType());
7397 if (
Index->getType() != IndexTy) {
7398 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
7402 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
7405 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
7409 Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
7418bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
7420 Type *ElementType) {
7428 if (TableSize >= UINT_MAX /
IT->getBitWidth())
7430 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
7436 if (
TTI.isTypeLegal(Ty))
7451 DL.fitsInLegalInteger(
IT->getBitWidth());
7454Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
7456bool SwitchReplacement::isLookupTable() {
return Kind == LookupTableKind; }
7458bool SwitchReplacement::isBitMap() {
return Kind == BitMapKind; }
7465 const uint64_t MinDensity = OptSize ? 40 : 10;
7470 return NumCases * 100 >= CaseRange * MinDensity;
7482static std::optional<unsigned>
7485 assert(
Values.size() > 1 &&
"expected multiple switch cases");
7487 return std::nullopt;
7492 for (
auto &
V : ReducedValues) {
7494 ReducedValuesOr |= Reduced;
7495 V = (int64_t)Reduced;
7508 for (
auto &
V : ReducedValues)
7512 return std::nullopt;
7526 if (
SI->getNumCases() > TableSize)
7529 bool AllTablesFitInRegister =
true;
7530 bool HasIllegalType =
false;
7531 for (
const auto &Ty : ResultTypes) {
7536 AllTablesFitInRegister =
7537 AllTablesFitInRegister &&
7538 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
7543 if (HasIllegalType && !AllTablesFitInRegister)
7548 if (AllTablesFitInRegister)
7556 SI->getFunction()->hasOptSize());
7566 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
7569 return all_of(ResultTypes, [&](
const auto &ResultType) {
7570 return SwitchReplacement::wouldFitInRegister(
7620 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
7625 for (
auto ValuePair :
Values) {
7628 if (!CaseConst || CaseConst == DefaultConst ||
7629 (CaseConst != TrueConst && CaseConst != FalseConst))
7639 if (
Pred != BranchBlock &&
Pred->getUniquePredecessor() != BranchBlock)
7643 if (DefaultConst == FalseConst) {
7646 ++NumTableCmpReuses;
7649 Value *InvertedTableCmp = BinaryOperator::CreateXor(
7650 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
7653 ++NumTableCmpReuses;
7663 bool ConvertSwitchToLookupTable) {
7664 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
7678 if (
SI->getNumCases() < 3)
7700 MinCaseVal = CaseVal;
7702 MaxCaseVal = CaseVal;
7719 It->second.push_back(std::make_pair(CaseVal,
Value));
7728 &CommonDest, DefaultResultsList,
DL);
7729 for (
const auto &
I : DefaultResultsList) {
7732 DefaultResults[
PHI] = Result;
7736 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7739 if (UseSwitchConditionAsTableIndex) {
7741 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7746 TableIndexOffset = MinCaseVal;
7753 bool DefaultIsReachable = !
SI->defaultDestUnreachable();
7755 bool TableHasHoles = (NumResults < TableSize);
7760 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7768 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7771 if (
SI->getNumCases() < 4)
7773 if (!
DL.fitsInLegalInteger(TableSize))
7782 if (UseSwitchConditionAsTableIndex) {
7783 TableIndex =
SI->getCondition();
7784 if (HasDefaultResults) {
7796 all_of(ResultTypes, [&](
const auto &ResultType) {
7797 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7802 TableSize = std::max(UpperBound, TableSize);
7805 DefaultIsReachable =
false;
7813 const auto &ResultList = ResultLists[
PHI];
7815 Type *ResultType = ResultList.begin()->second->getType();
7820 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7821 ResultList, DefaultVal,
DL,
TTI, FuncName);
7822 if (!Replacement.isValid())
7824 PhiToReplacementMap.
insert({
PHI, Replacement});
7827 bool AnyLookupTables =
any_of(
7828 PhiToReplacementMap, [](
auto &KV) {
return KV.second.isLookupTable(); });
7829 bool AnyBitMaps =
any_of(PhiToReplacementMap,
7830 [](
auto &KV) {
return KV.second.isBitMap(); });
7838 if (AnyLookupTables &&
7839 (!
TTI.shouldBuildLookupTables() ||
7845 if (!ConvertSwitchToLookupTable &&
7846 (AnyLookupTables || AnyBitMaps || NeedMask))
7849 Builder.SetInsertPoint(
SI);
7852 if (!UseSwitchConditionAsTableIndex) {
7855 bool MayWrap =
true;
7856 if (!DefaultIsReachable) {
7861 TableIndex = Builder.CreateSub(
SI->getCondition(), TableIndexOffset,
7862 "switch.tableidx",
false,
7866 std::vector<DominatorTree::UpdateType> Updates;
7872 assert(MaxTableSize >= TableSize &&
7873 "It is impossible for a switch to have more entries than the max "
7874 "representable value of its input integer type's size.");
7879 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7884 Builder.SetInsertPoint(
SI);
7885 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7886 const bool IsFullyCoveredLookupTable =
7887 !DefaultIsReachable || GeneratingCoveredLookupTable;
7888 if (IsFullyCoveredLookupTable) {
7889 Builder.CreateBr(LookupBB);
7895 Value *Cmp = Builder.CreateICmpULT(
7896 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7898 Builder.CreateCondBr(Cmp, LookupBB,
SI->getDefaultDest());
7899 CondBranch = RangeCheckBranch;
7905 Builder.SetInsertPoint(LookupBB);
7911 MaskBB->
setName(
"switch.hole_check");
7918 APInt MaskInt(TableSizePowOf2, 0);
7919 APInt One(TableSizePowOf2, 1);
7921 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7922 for (
const auto &Result : ResultList) {
7925 MaskInt |= One << Idx;
7927 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7934 Builder.CreateZExtOrTrunc(TableIndex, MapTy,
"switch.maskindex");
7935 Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7936 Value *LoBit = Builder.CreateTrunc(
7938 if (!IsFullyCoveredLookupTable)
7940 CondBranch = Builder.CreateCondBr(LoBit, LookupBB,
SI->getDefaultDest());
7945 Builder.SetInsertPoint(LookupBB);
7949 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7952 SI->getDefaultDest()->removePredecessor(BB,
7959 const ResultListTy &ResultList = ResultLists[
PHI];
7960 auto Replacement = PhiToReplacementMap.
at(
PHI);
7961 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7964 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7967 for (
auto *
User :
PHI->users()) {
7969 Replacement.getDefaultValue(), ResultList);
7973 PHI->addIncoming(Result, LookupBB);
7976 Builder.CreateBr(CommonDest);
7981 const bool HasBranchWeights =
7988 for (
unsigned I = 0,
E =
SI->getNumSuccessors();
I <
E; ++
I) {
7991 if (Succ ==
SI->getDefaultDest()) {
7992 if (HasBranchWeights)
7993 ToDefaultWeight += BranchWeights[
I];
7997 if (DTU && RemovedSuccessors.
insert(Succ).second)
7999 if (HasBranchWeights)
8000 ToLookupWeight += BranchWeights[
I];
8002 SI->eraseFromParent();
8007 if ((NeedMask && !IsFullyCoveredLookupTable) &&
8010 else if (HasBranchWeights)
8017 ++NumLookupTablesHoles;
8033 if (CondTy->getIntegerBitWidth() > 64 ||
8034 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8038 if (
SI->getNumCases() < 4)
8046 for (
const auto &
C :
SI->cases())
8047 Values.push_back(
C.getCaseValue()->getValue().getSExtValue());
8051 bool OptSize =
SI->getFunction()->hasOptSize();
8058 std::optional<unsigned> Shift;
8088 Builder.SetInsertPoint(
SI);
8092 Value *Rot = Builder.CreateIntrinsic(
8093 Ty, Intrinsic::fshl,
8094 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - *Shift)});
8095 SI->replaceUsesOfWith(
SI->getCondition(), Rot);
8097 for (
auto Case :
SI->cases()) {
8098 auto *Orig = Case.getCaseValue();
8099 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
8144 for (
auto I =
SI->case_begin(),
E =
SI->case_end();
I !=
E;) {
8145 if (!
I->getCaseValue()->getValue().ugt(
Constant->getValue())) {
8162 if (!
SI->defaultDestUnreachable() || Case ==
SI->case_default()) {
8165 return !Updates.
empty();
8185 if (
SI->defaultDestUnreachable())
8196 if (!
Known.isConstant())
8203 ConstantInt::get(
SI->getContext(),
Known.getConstant());
8205 if (CaseIt ==
SI->case_default()) {
8214 SI->case_default());
8216 assert(
SI->getNumCases() > 0 &&
"Switch should have at least one case");
8217 assert(
SI->findCaseValue(CaseVal) !=
SI->case_default() &&
8218 "Proven value should have a dedicated case");
8219 assert(
SI->defaultDestUnreachable());
8237 Value *Condition =
SI->getCondition();
8241 if (CondTy->getIntegerBitWidth() > 64 ||
8242 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
8254 if (
SI->getNumCases() < 4)
8259 for (
const auto &Case :
SI->cases()) {
8260 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
8262 Values.push_back(CaseValue);
8272 SI->getFunction()->hasOptSize()))
8276 Builder.SetInsertPoint(
SI);
8278 if (!
SI->defaultDestUnreachable()) {
8281 auto *PopC = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Condition);
8282 auto *IsPow2 = Builder.CreateICmpEQ(PopC, ConstantInt::get(CondTy, 1));
8284 auto *OrigBB =
SI->getParent();
8285 auto *DefaultCaseBB =
SI->getDefaultDest();
8287 auto It = OrigBB->getTerminator()->getIterator();
8299 NewWeights[1] = Weights[0] / 2;
8300 NewWeights[0] = OrigDenominator - NewWeights[1];
8312 Weights[0] = NewWeights[1];
8313 uint64_t CasesDenominator = OrigDenominator - Weights[0];
8315 W = NewWeights[0] *
static_cast<double>(W) / CasesDenominator;
8321 It->eraseFromParent();
8329 for (
auto &Case :
SI->cases()) {
8330 auto *OrigValue = Case.getCaseValue();
8331 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
8332 OrigValue->getValue().countr_zero()));
8336 auto *ConditionTrailingZeros = Builder.CreateIntrinsic(
8339 SI->setCondition(ConditionTrailingZeros);
8349 if (!Cmp || !Cmp->hasOneUse())
8360 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
8363 if (
SI->getNumCases() == 2) {
8370 Succ =
SI->getDefaultDest();
8371 SuccWeight = Weights[0];
8373 for (
auto &Case :
SI->cases()) {
8374 std::optional<int64_t> Val =
8378 if (!Missing.erase(*Val))
8383 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
8386 assert(Missing.size() == 1 &&
"Should have one case left");
8387 Res = *Missing.begin();
8388 }
else if (
SI->getNumCases() == 3 &&
SI->defaultDestUnreachable()) {
8390 Unreachable =
SI->getDefaultDest();
8392 for (
auto &Case :
SI->cases()) {
8393 BasicBlock *NewSucc = Case.getCaseSuccessor();
8394 uint32_t Weight = Weights[Case.getSuccessorIndex()];
8397 OtherSuccWeight += Weight;
8400 SuccWeight = Weight;
8401 }
else if (Succ == NewSucc) {
8407 for (
auto &Case :
SI->cases()) {
8408 std::optional<int64_t> Val =
8410 if (!Val || (Val != 1 && Val != 0 && Val != -1))
8412 if (Case.getCaseSuccessor() == Succ) {
8434 if (Cmp->isSigned())
8437 MDNode *NewWeights =
nullptr;
8443 Builder.SetInsertPoint(
SI->getIterator());
8444 Value *ICmp = Builder.CreateICmp(
Pred, Cmp->getLHS(), Cmp->getRHS());
8445 Builder.CreateCondBr(ICmp, Succ,
OtherSucc, NewWeights,
8446 SI->getMetadata(LLVMContext::MD_unpredictable));
8450 SI->eraseFromParent();
8451 Cmp->eraseFromParent();
8452 if (DTU && Unreachable)
8477 assert(
BB &&
"Expected non-null BB");
8479 if (
BB->isEntryBlock())
8492 if (
BB->hasAddressTaken() ||
BB->isEHPad())
8497 if (&
BB->front() != &
BB->back())
8512 assert(BB->
size() == 1 &&
"Expected just a single branch in the BB");
8523 return (*EBW->PhiPredIVs)[&Phi][BB];
8545 auto IfPhiIVMatch = [&](
PHINode &Phi) {
8548 auto &PredIVs = (*LHS->PhiPredIVs)[&Phi];
8549 return PredIVs[
A] == PredIVs[
B];
8558 if (Candidates.
size() < 2)
8573 assert(Succ &&
"Expected unconditional BB");
8583 PhiPredIVs.
try_emplace(Phi, Phi->getNumIncomingValues()).first->second;
8586 for (
auto &
IV : Phi->incoming_values())
8587 IVs.insert({Phi->getIncomingBlock(
IV),
IV.get()});
8605 bool MadeChange =
false;
8619 if (!LivePreds.
contains(PredOfDead))
8626 Live->printAsOperand(
dbgs());
dbgs() <<
" for ";
8627 Live->getSingleSuccessor()->printAsOperand(
dbgs());
8632 T->replaceSuccessorWith(
Dead, Live);
8637 for (
const auto &EBW : BBs2Merge) {
8640 const auto &[It, Inserted] =
Keep.insert(&EBW);
8649 if (KeepBB == DeadBB)
8653 RedirectIncomingEdges(DeadBB, KeepBB);
8662 if (DTU && !Updates.
empty())
8668bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI,
8669 DomTreeUpdater *DTU) {
8671 SmallSetVector<BasicBlock *, 16> FilteredArms(
8677bool SimplifyCFGOpt::simplifyDuplicatePredecessors(BasicBlock *BB,
8678 DomTreeUpdater *DTU) {
8689 SmallSetVector<BasicBlock *, 8> FilteredPreds(
8695bool SimplifyCFGOpt::simplifySwitch(SwitchInst *SI,
IRBuilder<> &Builder) {
8698 if (isValueEqualityComparison(SI)) {
8703 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
8704 return requestResimplify();
8708 if (simplifySwitchOnSelect(SI,
Select))
8709 return requestResimplify();
8713 if (SI == &*BB->
begin())
8714 if (foldValueComparisonIntoPredecessors(SI, Builder))
8715 return requestResimplify();
8721 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
8722 return requestResimplify();
8726 return requestResimplify();
8729 return requestResimplify();
8732 return requestResimplify();
8735 return requestResimplify();
8740 if (
Options.ConvertSwitchToArithmetic ||
Options.ConvertSwitchToLookupTable)
8742 Options.ConvertSwitchToLookupTable))
8743 return requestResimplify();
8746 return requestResimplify();
8749 return requestResimplify();
8752 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
8753 return requestResimplify();
8757 if (simplifyDuplicateSwitchArms(SI, DTU))
8758 return requestResimplify();
8761 return requestResimplify();
8764 return requestResimplify();
8769bool SimplifyCFGOpt::simplifyIndirectBr(IndirectBrInst *IBI) {
8772 SmallVector<uint32_t> BranchWeights;
8775 DenseMap<const BasicBlock *, uint64_t> TargetWeight;
8776 if (HasBranchWeights)
8781 SmallPtrSet<Value *, 8> Succs;
8782 SmallSetVector<BasicBlock *, 8> RemovedSuccs;
8787 RemovedSuccs.
insert(Dest);
8797 std::vector<DominatorTree::UpdateType> Updates;
8798 Updates.reserve(RemovedSuccs.
size());
8799 for (
auto *RemovedSucc : RemovedSuccs)
8800 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
8817 if (HasBranchWeights) {
8824 if (simplifyIndirectBrOnSelect(IBI, SI))
8825 return requestResimplify();
8857 if (BB == OtherPred)
8870 Value *V = PN.getIncomingValueForBlock(BB);
8871 Value *V2 = PN.getIncomingValueForBlock(OtherPred);
8872 return V == V2 || (V == LPad && V2 == LPad2);
8880 return PN.getIncomingValueForBlock(BB) == LPad;
8885 std::vector<DominatorTree::UpdateType> Updates;
8892 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
8893 "unexpected successor");
8894 II->setUnwindDest(OtherPred);
8909 Builder.CreateUnreachable();
8918bool SimplifyCFGOpt::simplifyUncondBranch(UncondBrInst *BI,
8930 bool NeedCanonicalLoop =
8944 if (
I->isTerminator() &&
8945 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
8969 if (!PPred || (PredPred && PredPred != PPred))
9010 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
9014 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
9044 bool HasWeight =
false;
9049 BBTWeight = BBFWeight = 1;
9054 BB1TWeight = BB1FWeight = 1;
9059 BB2TWeight = BB2FWeight = 1;
9061 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
9062 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
9069bool SimplifyCFGOpt::simplifyCondBranch(CondBrInst *BI,
IRBuilder<> &Builder) {
9073 "Tautological conditional branch should have been eliminated already.");
9076 if (!
Options.SimplifyCondBranch ||
9081 if (isValueEqualityComparison(BI)) {
9086 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
9087 return requestResimplify();
9091 for (
auto &
I : *BB) {
9096 if (foldValueComparisonIntoPredecessors(BI, Builder))
9097 return requestResimplify();
9103 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
9116 return requestResimplify();
9122 if (
Options.SpeculateBlocks &&
9125 return requestResimplify();
9134 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
9135 return requestResimplify();
9137 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
9139 SmallVector<Instruction *, 2> SpeculatedConditionalLoadsStores;
9140 auto CanSpeculateConditionalLoadsStores = [&]() {
9142 for (Instruction &
I : *Succ) {
9143 if (
I.isTerminator()) {
9144 if (
I.getNumSuccessors() > 1)
9148 SpeculatedConditionalLoadsStores.
size() ==
9152 SpeculatedConditionalLoadsStores.
push_back(&
I);
9155 return !SpeculatedConditionalLoadsStores.
empty();
9158 if (CanSpeculateConditionalLoadsStores()) {
9160 std::nullopt,
nullptr);
9161 return requestResimplify();
9171 return requestResimplify();
9180 return requestResimplify();
9186 if (foldCondBranchOnValueKnownInPredecessor(BI))
9187 return requestResimplify();
9194 return requestResimplify();
9202 return requestResimplify();
9206 return requestResimplify();
9213 assert(
V->getType() ==
I->getType() &&
"Mismatched types");
9225 auto *Use = cast<Instruction>(U.getUser());
9228 if (Use->getParent() != I->getParent() || Use == I || Use->comesBefore(I))
9231 switch (Use->getOpcode()) {
9234 case Instruction::GetElementPtr:
9235 case Instruction::Ret:
9236 case Instruction::BitCast:
9237 case Instruction::Load:
9238 case Instruction::Store:
9239 case Instruction::Call:
9240 case Instruction::CallBr:
9241 case Instruction::Invoke:
9242 case Instruction::UDiv:
9243 case Instruction::URem:
9247 case Instruction::SDiv:
9248 case Instruction::SRem:
9252 if (FindUse ==
I->use_end())
9254 auto &
Use = *FindUse;
9268 if (
GEP->getPointerOperand() ==
I) {
9271 if (
GEP->getType()->isVectorTy())
9279 if (!
GEP->hasAllZeroIndices() &&
9280 (!
GEP->isInBounds() ||
9282 GEP->getPointerAddressSpace())))
9283 PtrValueMayBeModified =
true;
9289 bool HasNoUndefAttr =
9290 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
9295 if (
C->isNullValue() && HasNoUndefAttr &&
9296 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
9297 return !PtrValueMayBeModified;
9303 if (!LI->isVolatile())
9305 LI->getPointerAddressSpace());
9309 if (!
SI->isVolatile())
9311 SI->getPointerAddressSpace())) &&
9312 SI->getPointerOperand() ==
I;
9317 if (
I == Assume->getArgOperand(0))
9325 if (CB->getCalledOperand() ==
I)
9328 if (CB->isArgOperand(&
Use)) {
9329 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
9332 CB->paramHasNonNullAttr(ArgIdx,
false))
9333 return !PtrValueMayBeModified;
9352 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
9360 Builder.CreateUnreachable();
9361 T->eraseFromParent();
9373 Builder.CreateUnreachable();
9380 Assumption = Builder.CreateAssumption(Builder.CreateNot(
Cond));
9382 Assumption = Builder.CreateAssumption(
Cond);
9397 Builder.SetInsertPoint(Unreachable);
9399 Builder.CreateUnreachable();
9400 for (
const auto &Case :
SI->cases())
9401 if (Case.getCaseSuccessor() == BB) {
9403 Case.setSuccessor(Unreachable);
9405 if (
SI->getDefaultDest() == BB) {
9407 SI->setDefaultDest(Unreachable);
9421bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
9446 return requestResimplify();
9465 if (simplifyDuplicatePredecessors(BB, DTU))
9469 if (
Options.SpeculateBlocks &&
9476 Options.SpeculateUnpredictables))
9484 case Instruction::UncondBr:
9487 case Instruction::CondBr:
9490 case Instruction::Resume:
9493 case Instruction::CleanupRet:
9496 case Instruction::Switch:
9499 case Instruction::Unreachable:
9502 case Instruction::IndirectBr:
9510bool SimplifyCFGOpt::run(BasicBlock *BB) {
9520 }
while (Resimplify);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
static MachineBasicBlock * OtherSucc(MachineBasicBlock *MBB, MachineBasicBlock *Succ)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Function Alias Analysis Results
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
static bool IsIndirectCall(const MachineInstr *MI)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
static constexpr Value * getValue(Ty &ValueOrUse)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
static cl::opt< uint32_t > SelectFalseWeight("profcheck-default-select-false-weight", cl::init(3U), cl::desc("When annotating `select` instructions, this value will be used " "for the second ('false') case."))
static cl::opt< uint32_t > SelectTrueWeight("profcheck-default-select-true-weight", cl::init(2U), cl::desc("When annotating `select` instructions, this value will be used " "for the first ('true') case."))
SmallVector< MachineOperand, 4 > Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static std::optional< ContiguousCasesResult > findContiguousCases(Value *Condition, SmallVectorImpl< ConstantInt * > &Cases, SmallVectorImpl< ConstantInt * > &OtherCases, BasicBlock *Dest, BasicBlock *OtherDest)
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange, bool OptSize)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI, bool ConvertSwitchToLookupTable)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool isProfitableToSpeculate(const CondBrInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(CondBrInst *BI, CondBrInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool simplifySwitchDefaultBranch(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
static bool forwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static PHINode * findPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool reachesUncontrolledConvergentCallBeforeBlock(BasicBlock *From, BasicBlock *StopBB)
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static bool isSafeToThreadThroughLoopHeader(BasicBlock *Header, ArrayRef< BasicBlock * > PredBBs, BasicBlock *RealDest)
Return true if threading PredBBs through Header to RealDest eliminates the loop's single backedge.
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static void hoistConditionalLoadsStores(CondBrInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool extractPredSuccWeights(CondBrInst *PBI, CondBrInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}...
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static bool performBranchToCommonDestFolding(CondBrInst *BI, CondBrInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static std::optional< unsigned > getDenseSwitchRangeReductionShift(ArrayRef< int64_t > Values, int64_t Base, bool OptSize)
SmallPtrSet< BasicBlock *, 8 > BlocksSet
static unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool mergeConditionalStores(CondBrInst *PBI, CondBrInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool mergeNestedCondBranch(CondBrInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL, AssumptionCache *AC, const Instruction *CtxI, ArrayRef< uint32_t > BranchWeights)
static bool tryWidenCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool mergeIdenticalBBs(ArrayRef< BasicBlock * > Candidates, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static bool tryToMergeLandingPad(LandingPadInst *LPad, UncondBrInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, uintptr_t MaxUniqueResults)
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB, Instruction *&PreviousAccess)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool SimplifyCondBranchToCondBranch(CondBrInst *PBI, CondBrInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isUncontrolledConvergentCall(CallBase *CB)
static bool simplifySwitchWhenUMin(SwitchInst *SI, DomTreeUpdater *DTU)
Tries to transform the switch when the condition is umin with a constant.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(CondBrInst *BI, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool KeepCanonicalLoop)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, CondBrInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & front() const
Get the first element.
size_t size() const
Get the array size.
bool empty() const
Check if the array is empty.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM_ABI bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasTerminator() const LLVM_READONLY
Returns whether the block has a terminator.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrPseudoProbe() const
Returns an iterator to the first instruction in this block that is not a PHINode or a pseudo operatio...
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
LLVM_ABI bool isLandingPad() const
Return true if this basic block is a landing pad.
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BasicBlock * getBasicBlock() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
bool isConvergent() const
Determine if the invoke is convergent.
Value * getConvergenceControlToken() const
Return the convergence control token for this call, if it exists.
bool isDataOperand(const Use *U) const
bool tryIntersectAttributes(const CallBase *Other)
Try to intersect the attributes from 'this' CallBase and the 'Other' CallBase.
This class represents a function call, abstracting a target machine's calling convention.
mapped_iterator< op_iterator, DerefFnTy > handler_iterator
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
bool isEquality() const
Determine if this is an equals/not equals predicate.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Conditional Branch instruction.
static CondBrInst * Create(Value *Cond, BasicBlock *IfTrue, BasicBlock *IfFalse, InsertPosition InsertBefore=nullptr)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setCondition(Value *V)
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
ConstantFP - Floating Point Values [float, double].
ConstantFolder - Create constants with minimum, target independent, folding.
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
A constant pointer value that points to null.
This class represents a range of values.
LLVM_ABI bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
LLVM_ABI ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
This is an important base class in LLVM.
static LLVM_ABI Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
LLVM_ABI bool isOneValue() const
Returns true if the value is one.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
iterator find(const_arg_type_t< KeyT > Val)
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
void reserve(size_type NumEntries)
Grow the DenseMap so that it can contain at least NumEntries items before resizing again.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Implements a dense probed hash-table based set.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
CondBrInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
ConstantInt * getTrue()
Get the constant value for i1 true.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(const DebugLoc &L)
Set location information used by debugging information.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
LLVM_ABI CallInst * CreateAssumption(Value *Cond)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", bool HasSameSign=false)
UncondBrInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
LLVM_ABI void dropLocation()
Drop the instruction's debug location.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
iterator_range< user_iterator > users()
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
Iterates through instructions in a set of blocks in reverse order from the first non-terminator.
LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
void insert_range(Range &&R)
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
bool isAtomic() const
Return true if this store has an atomic ordering.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this store instruction.
Value * getPointerOperand()
Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
LLVM_ABI void replaceDefaultDest(SwitchInst::CaseIt I)
Replace the default destination by given case.
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
BasicBlock * getSuccessor(unsigned idx) const
void setCondition(Value *V)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
CaseIteratorImpl< CaseHandle > CaseIt
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Unconditional Branch instruction.
void setSuccessor(BasicBlock *NewSucc)
static UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i=0) const
'undef' values are things that do not have specified contents.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
LLVM_ABI bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
auto m_UMin(const Opnd0 &Op0, const Opnd1 &Op1)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_bind< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
constexpr auto not_equal_to(T &&Arg)
Functor variant of std::not_equal_to that can be used as a UnaryPredicate in functional algorithms li...
LLVM_ABI bool foldBranchToCommonDest(CondBrInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, AssumptionCache *AC=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > MaxLoopHeaderThreadingSearchBlocks("simplifycfg-max-loop-header-threading-search", cl::Hidden, cl::init(1024), cl::desc("Limit number of blocks searched to prove that threading through " "a loop header keeps the loop canonical"))
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
LLVM_ABI bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
RelativeUniformCounterPtr Values
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
@ Known
Known to have no common set bits.
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
@ Load
The value being inserted comes from a load (InsertElement only).
auto accumulate(R &&Range, E &&Init)
Wrapper for std::accumulate.
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Function *CtxF=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
static cl::opt< bool > HoistStoresWithCondFaulting("simplifycfg-hoist-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist stores if the target supports conditional faulting"))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr detail::StaticCastFunc< To > StaticCastTo
Function objects corresponding to the Cast types defined above.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
LLVM_ABI CondBrInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
LLVM_ABI void InvertBranch(CondBrInst *PBI, IRBuilderBase &Builder)
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI bool collectPossibleValues(const Value *V, SmallPtrSetImpl< const Constant * > &Constants, unsigned MaxCount, bool AllowUndefOrPoison=true)
Enumerates all possible immediate values of V and inserts them into the set Constants.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
auto succ_size(const MachineBasicBlock *BB)
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
static cl::opt< unsigned > MaxJumpThreadingLiveBlocks("max-jump-threading-live-blocks", cl::Hidden, cl::init(24), cl::desc("Limit number of blocks a define in a threaded block is allowed " "to be live in"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
LLVM_ABI bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
auto sum_of(R &&Range, E Init=E{0})
Returns the sum of all values in Range with Init initial value.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
SmallVector< uint64_t, 2 > getDisjunctionWeights(const SmallVector< T1, 2 > &B1, const SmallVector< T2, 2 > &B2)
Get the branch weights of a branch conditioned on b1 || b2, where b1 and b2 are 2 booleans that are t...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Constant * ConstantFoldCastInstruction(unsigned opcode, Constant *V, Type *DestTy)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const SimplifyQuery &Q, bool IgnoreFree=false)
Equivalent to isDereferenceableAndAlignedPointer with an alignment of 1.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
static cl::opt< bool > HoistLoadsWithCondFaulting("simplifycfg-hoist-loads-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads if the target supports conditional faulting"))
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
@ Keep
No function return thunk.
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, const SimplifyQuery &SQ, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVectorImpl< ConstantInt * > * Cases
SmallVectorImpl< ConstantInt * > * OtherCases
Checking whether two BBs are equal depends on the contents of the BasicBlock and the incoming values ...
SmallDenseMap< BasicBlock *, Value *, 8 > BB2ValueMap
DenseMap< PHINode *, BB2ValueMap > Phi2IVsMap
static bool canBeMerged(const BasicBlock *BB)
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static bool isEqual(const EqualBBWrapper *LHS, const EqualBBWrapper *RHS)
static unsigned getHashValue(const EqualBBWrapper *EBW)
An information struct used to provide DenseMap with the various necessary components for a given valu...
A MapVector that performs no allocations if smaller than a certain size.