94using namespace PatternMatch;
96#define DEBUG_TYPE "simplifycfg"
99 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
102 "Temporary development switch used to gradually uplift SimplifyCFG "
103 "into preserving DomTree,"));
112 "Control the amount of phi node folding to perform (default = 2)"));
116 cl::desc(
"Control the maximal total instruction cost that we are willing "
117 "to speculatively execute to fold a 2-entry PHI node into a "
118 "select (default = 4)"));
122 cl::desc(
"Hoist common instructions up to the parent block"));
126 cl::desc(
"Hoist loads if the target supports conditional faulting"));
130 cl::desc(
"Hoist stores if the target supports conditional faulting"));
134 cl::desc(
"Control the maximal conditional load/store that we are willing "
135 "to speculatively execute to eliminate conditional branch "
141 cl::desc(
"Allow reordering across at most this many "
142 "instructions when hoisting"));
146 cl::desc(
"Sink common instructions down to the end block"));
150 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
154 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
155 "precede - hoist multiple conditional stores into a single "
156 "predicated store"));
160 cl::desc(
"When merging conditional stores, do so even if the resultant "
161 "basic blocks are unlikely to be if-converted as a result"));
165 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
170 cl::desc(
"Limit maximum recursion depth when calculating costs of "
171 "speculatively executed instructions"));
176 cl::desc(
"Max size of a block which is still considered "
177 "small enough to thread through"));
183 cl::desc(
"Maximum cost of combining conditions when "
184 "folding branches"));
187 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
189 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
190 "to fold branch to common destination when vector operations are "
195 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
199 cl::desc(
"Limit cases to analyze when converting a switch to select"));
203 cl::desc(
"Limit number of blocks a define in a threaded block is allowed "
206STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
208 "Number of switch instructions turned into linear mapping");
210 "Number of switch instructions turned into lookup tables");
212 NumLookupTablesHoles,
213 "Number of switch instructions turned into lookup tables (holes checked)");
214STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
216 "Number of value comparisons folded into predecessor basic blocks");
218 "Number of branches folded into predecessor basic block");
221 "Number of common instruction 'blocks' hoisted up to the begin block");
223 "Number of common instructions hoisted up to the begin block");
225 "Number of common instruction 'blocks' sunk down to the end block");
227 "Number of common instructions sunk down to the end block");
228STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
230 "Number of invokes with empty resume blocks simplified into calls");
231STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
232STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
239using SwitchCaseResultVectorTy =
248struct ValueEqualityComparisonCase {
255 bool operator<(ValueEqualityComparisonCase RHS)
const {
263class SimplifyCFGOpt {
273 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
274 bool simplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
277 bool performValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
280 bool foldValueComparisonIntoPredecessors(
Instruction *TI,
294 bool foldCondBranchOnValueKnownInPredecessor(
BranchInst *BI);
296 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
299 bool hoistCommonCodeFromSuccessors(
Instruction *TI,
bool AllInstsEqOnly);
300 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
317 :
TTI(
TTI), DTU(DTU),
DL(
DL), LoopHeaders(LoopHeaders), Options(Opts) {
319 "SimplifyCFG is not yet capable of maintaining validity of a "
320 "PostDomTree, so don't ask for it.");
327 bool requestResimplify() {
346 "Only for a pair of incoming blocks at the time!");
352 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
353 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
356 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
357 EquivalenceSet->contains(IV1))
380 if (!SI1Succs.
count(Succ))
386 FailBlocks->insert(Succ);
402 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
404 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
405 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
467 if (AggressiveInsts.
count(
I))
483 ZeroCostInstructions.
insert(OverflowInst);
485 }
else if (!ZeroCostInstructions.
contains(
I))
501 for (
Use &
Op :
I->operands())
503 TTI, AC, ZeroCostInstructions,
Depth + 1))
515 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
516 DL.isNonIntegralPointerType(V->getType()))
521 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
524 if (isa<ConstantPointerNull>(V))
525 return ConstantInt::get(PtrTy, 0);
529 if (CE->getOpcode() == Instruction::IntToPtr)
530 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
535 return cast<ConstantInt>(
553struct ConstantComparesGatherer {
557 Value *CompValue =
nullptr;
560 Value *Extra =
nullptr;
566 unsigned UsedICmps = 0;
572 bool IgnoreFirstMatch =
false;
573 bool MultipleMatches =
false;
578 if (CompValue || !MultipleMatches)
583 IgnoreFirstMatch =
true;
587 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
588 ConstantComparesGatherer &
589 operator=(
const ConstantComparesGatherer &) =
delete;
594 bool setValueOnce(
Value *NewVal) {
595 if (IgnoreFirstMatch) {
596 IgnoreFirstMatch =
false;
599 if (CompValue && CompValue != NewVal) {
600 MultipleMatches =
true;
618 if (!setValueOnce(Val))
627 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
638 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
682 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
684 if (!setValueOnce(RHSVal))
689 ConstantInt::get(
C->getContext(),
690 C->getValue() | Mask));
705 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
707 if (!setValueOnce(RHSVal))
711 Vals.
push_back(ConstantInt::get(
C->getContext(),
712 C->getValue() & ~Mask));
733 Value *CandidateVal =
I->getOperand(0);
736 CandidateVal = RHSVal;
751 if (!setValueOnce(CandidateVal))
756 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
767 void gather(
Value *V) {
779 while (!DFT.empty()) {
780 V = DFT.pop_back_val();
786 if (Visited.insert(Op1).second)
788 if (Visited.insert(Op0).second)
795 if (matchInstruction(
I, IsEq))
819 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
820 Cond = dyn_cast<Instruction>(SI->getCondition());
821 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
822 if (BI->isConditional())
823 Cond = dyn_cast<Instruction>(BI->getCondition());
825 Cond = dyn_cast<Instruction>(IBI->getAddress());
837 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
840 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
841 CV =
SI->getCondition();
842 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
843 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
844 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
847 }
else if (
auto *Trunc = dyn_cast<TruncInst>(BI->getCondition())) {
848 if (Trunc->hasNoUnsignedWrap())
849 CV = Trunc->getOperand(0);
856 Value *
Ptr = PTII->getPointerOperand();
857 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
866BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
867 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
868 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
869 Cases.reserve(
SI->getNumCases());
870 for (
auto Case :
SI->cases())
871 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
872 Case.getCaseSuccessor()));
873 return SI->getDefaultDest();
880 if (
auto *ICI = dyn_cast<ICmpInst>(
Cond)) {
884 Pred = ICmpInst::ICMP_NE;
885 auto *Trunc = cast<TruncInst>(
Cond);
886 C = ConstantInt::get(cast<IntegerType>(Trunc->getOperand(0)->getType()), 0);
889 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
897 std::vector<ValueEqualityComparisonCase> &Cases) {
903 std::vector<ValueEqualityComparisonCase> &C2) {
904 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
907 if (V1->size() > V2->size())
912 if (V1->size() == 1) {
915 for (
const ValueEqualityComparisonCase &VECC : *V2)
916 if (TheVal == VECC.
Value)
923 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
924 while (i1 != e1 && i2 != e2) {
945 SI->setMetadata(LLVMContext::MD_prof,
N);
951 uint32_t FalseWeight,
bool IsExpected) {
952 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
956 if (TrueWeight || FalseWeight)
959 I->setMetadata(LLVMContext::MD_prof,
N);
967bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
973 Value *ThisVal = isValueEqualityComparison(TI);
974 assert(ThisVal &&
"This isn't a value comparison!!");
975 if (ThisVal != PredVal)
982 std::vector<ValueEqualityComparisonCase> PredCases;
984 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
988 std::vector<ValueEqualityComparisonCase> ThisCases;
989 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
1001 if (isa<BranchInst>(TI)) {
1004 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1010 ThisCases[0].Dest->removePredecessor(PredDef);
1013 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1020 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1028 for (
const ValueEqualityComparisonCase &Case : PredCases)
1029 DeadCases.
insert(Case.Value);
1032 <<
"Through successor TI: " << *TI);
1037 auto *
Successor = i->getCaseSuccessor();
1040 if (DeadCases.
count(i->getCaseValue())) {
1049 std::vector<DominatorTree::UpdateType> Updates;
1050 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1052 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1053 DTU->applyUpdates(Updates);
1064 for (
const auto &[
Value, Dest] : PredCases)
1070 assert(TIV &&
"No edge from pred to succ?");
1075 for (
const auto &[
Value, Dest] : ThisCases)
1083 TheRealDest = ThisDef;
1090 if (Succ != CheckEdge) {
1091 if (Succ != TheRealDest)
1092 RemovedSuccs.
insert(Succ);
1095 CheckEdge =
nullptr;
1102 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1109 for (
auto *RemovedSucc : RemovedSuccs)
1110 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1111 DTU->applyUpdates(Updates);
1121struct ConstantIntOrdering {
1123 return LHS->getValue().ult(
RHS->getValue());
1135 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1144 assert(MD &&
"Invalid branch-weight metadata");
1150 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1164 if (Max > UINT_MAX) {
1179 if (BonusInst.isTerminator())
1209 NewBonusInst->
takeName(&BonusInst);
1210 BonusInst.setName(NewBonusInst->
getName() +
".old");
1211 VMap[&BonusInst] = NewBonusInst;
1217 auto *UI = cast<Instruction>(U.getUser());
1218 auto *PN = dyn_cast<PHINode>(UI);
1220 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1221 "If the user is not a PHI node, then it should be in the same "
1222 "block as, and come after, the original bonus instruction.");
1226 if (PN->getIncomingBlock(U) == BB)
1230 assert(PN->getIncomingBlock(U) == PredBlock &&
1231 "Not in block-closed SSA form?");
1232 U.set(NewBonusInst);
1242 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1243 PredDL.isSameSourceLocation(
DL)) {
1250bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1258 std::vector<ValueEqualityComparisonCase> BBCases;
1259 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1261 std::vector<ValueEqualityComparisonCase> PredCases;
1262 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1274 if (PredHasWeights) {
1277 if (Weights.
size() != 1 + PredCases.size())
1278 PredHasWeights = SuccHasWeights =
false;
1279 }
else if (SuccHasWeights)
1283 Weights.
assign(1 + PredCases.size(), 1);
1286 if (SuccHasWeights) {
1289 if (SuccWeights.
size() != 1 + BBCases.size())
1290 PredHasWeights = SuccHasWeights =
false;
1291 }
else if (PredHasWeights)
1292 SuccWeights.
assign(1 + BBCases.size(), 1);
1294 if (PredDefault == BB) {
1297 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1298 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1299 if (PredCases[i].Dest != BB)
1300 PTIHandled.insert(PredCases[i].
Value);
1303 std::swap(PredCases[i], PredCases.back());
1305 if (PredHasWeights || SuccHasWeights) {
1307 Weights[0] += Weights[i + 1];
1312 PredCases.pop_back();
1318 if (PredDefault != BBDefault) {
1320 if (DTU && PredDefault != BB)
1321 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1322 PredDefault = BBDefault;
1323 ++NewSuccessors[BBDefault];
1326 unsigned CasesFromPred = Weights.
size();
1328 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1329 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1330 PredCases.push_back(BBCases[i]);
1331 ++NewSuccessors[BBCases[i].Dest];
1332 if (SuccHasWeights || PredHasWeights) {
1336 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1337 ValidTotalSuccWeight += SuccWeights[i + 1];
1341 if (SuccHasWeights || PredHasWeights) {
1342 ValidTotalSuccWeight += SuccWeights[0];
1344 for (
unsigned i = 1; i < CasesFromPred; ++i)
1345 Weights[i] *= ValidTotalSuccWeight;
1347 Weights[0] *= SuccWeights[0];
1353 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1354 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1355 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1356 if (PredCases[i].Dest == BB) {
1359 if (PredHasWeights || SuccHasWeights) {
1360 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1365 std::swap(PredCases[i], PredCases.back());
1366 PredCases.pop_back();
1373 for (
const ValueEqualityComparisonCase &Case : BBCases)
1374 if (PTIHandled.count(Case.Value)) {
1376 if (PredHasWeights || SuccHasWeights)
1377 Weights.
push_back(WeightsForHandled[Case.Value]);
1378 PredCases.push_back(Case);
1379 ++NewSuccessors[Case.Dest];
1380 PTIHandled.
erase(Case.Value);
1386 if (PredHasWeights || SuccHasWeights)
1388 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1389 ++NewSuccessors[BBDefault];
1401 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1403 for (
auto I :
seq(NewSuccessor.second)) {
1407 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1408 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1421 for (ValueEqualityComparisonCase &V : PredCases)
1424 if (PredHasWeights || SuccHasWeights) {
1441 if (!InfLoopBlock) {
1449 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1456 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1458 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1460 DTU->applyUpdates(Updates);
1463 ++NumFoldValueComparisonIntoPredecessors;
1471bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(
Instruction *TI,
1474 Value *CV = isValueEqualityComparison(TI);
1475 assert(CV &&
"Not a comparison?");
1477 bool Changed =
false;
1480 while (!Preds.empty()) {
1489 Value *PCV = isValueEqualityComparison(PTI);
1495 for (
auto *Succ : FailBlocks) {
1501 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1515 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1516 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1517 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1536 if (
I->mayReadFromMemory())
1540 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1557 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1567 if (
auto *CB = dyn_cast<CallBase>(
I))
1568 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1575 if (
auto *J = dyn_cast<Instruction>(
Op))
1576 if (J->getParent() == BB)
1595 auto *C1 = dyn_cast<CallInst>(I1);
1596 auto *C2 = dyn_cast<CallInst>(I2);
1598 if (C1->isMustTailCall() != C2->isMustTailCall())
1606 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1607 if (CB1->cannotMerge() || CB1->isConvergent())
1609 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1610 if (CB2->cannotMerge() || CB2->isConvergent())
1625 if (!I1->hasDbgRecords())
1627 using CurrentAndEndIt =
1628 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1634 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1635 return Pair.first == Pair.second;
1641 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1647 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1649 if (!
Other->hasDbgRecords())
1652 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1659 while (
none_of(Itrs, atEnd)) {
1660 bool HoistDVRs = allIdentical(Itrs);
1661 for (CurrentAndEndIt &Pair : Itrs) {
1675 if (I1->isIdenticalToWhenDefined(I2,
true))
1678 if (
auto *Cmp1 = dyn_cast<CmpInst>(I1))
1679 if (
auto *Cmp2 = dyn_cast<CmpInst>(I2))
1680 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1681 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1682 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1684 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1685 return I1->getOperand(0) == I2->
getOperand(1) &&
1756 Value *Mask =
nullptr;
1757 Value *MaskFalse =
nullptr;
1758 Value *MaskTrue =
nullptr;
1759 if (Invert.has_value()) {
1760 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1770 auto PeekThroughBitcasts = [](
Value *V) {
1771 while (
auto *BitCast = dyn_cast<BitCastInst>(V))
1772 V = BitCast->getOperand(0);
1775 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1777 if (!Invert.has_value())
1778 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1783 auto *Op0 =
I->getOperand(0);
1784 CallInst *MaskedLoadStore =
nullptr;
1785 if (
auto *LI = dyn_cast<LoadInst>(
I)) {
1787 auto *Ty =
I->getType();
1789 Value *PassThru =
nullptr;
1790 if (Invert.has_value())
1791 for (
User *U :
I->users()) {
1792 if ((PN = dyn_cast<PHINode>(U))) {
1796 }
else if (
auto *Ins = cast<Instruction>(U);
1797 Sel && Ins->getParent() == BB) {
1810 I->replaceAllUsesWith(NewLoadStore);
1816 StoredVal,
I->getOperand(1), cast<StoreInst>(
I)->getAlign(), Mask);
1826 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1828 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1832 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1833 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1836 I->eraseFromParent();
1843 bool IsStore =
false;
1844 if (
auto *L = dyn_cast<LoadInst>(
I)) {
1847 }
else if (
auto *S = dyn_cast<StoreInst>(
I)) {
1866bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
Instruction *TI,
1867 bool AllInstsEqOnly) {
1887 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1891 if (isa<PHINode>(*SuccItr))
1893 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1896 if (AllInstsEqOnly) {
1905 return !
Term->isSameOperationAs(Term0) ||
1907 Succs[0]->size() != Succ->
size();
1913 while (LRI.isValid()) {
1930 unsigned NumSkipped = 0;
1933 if (SuccIterPairs.
size() > 2) {
1935 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1936 if (SuccIterPairs.
size() < 2)
1940 bool Changed =
false;
1943 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1944 auto &BB1ItrPair = *SuccIterPairBegin++;
1945 auto OtherSuccIterPairRange =
1951 bool AllInstsAreIdentical =
true;
1952 bool HasTerminator =
I1->isTerminator();
1953 for (
auto &SuccIter : OtherSuccIterRange) {
1958 AllInstsAreIdentical =
false;
1962 for (
auto &SuccIter : OtherSuccIterRange)
1967 if (HasTerminator) {
1971 if (NumSkipped || !AllInstsAreIdentical) {
1976 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1980 if (AllInstsAreIdentical) {
1981 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1982 AllInstsAreIdentical =
1984 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1986 unsigned SkipFlagsBB2 = Pair.second;
1996 if (AllInstsAreIdentical) {
2006 for (
auto &SuccIter : OtherSuccIterRange) {
2012 if (
auto *CB = dyn_cast<CallBase>(I1)) {
2013 bool Success = CB->tryIntersectAttributes(cast<CallBase>(I2));
2014 assert(
Success &&
"We should not be trying to hoist callbases "
2015 "with non-intersectable attributes");
2027 NumHoistCommonCode += SuccIterPairs.
size();
2029 NumHoistCommonInstrs += SuccIterPairs.
size();
2038 for (
auto &SuccIterPair : SuccIterPairs) {
2047bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2051 auto *BI = dyn_cast<BranchInst>(TI);
2053 bool Changed =
false;
2058 auto *I2 = *OtherSuccTIs.
begin();
2074 if (isa<CallBrInst>(I1))
2079 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2081 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2101 if (!
NT->getType()->isVoidTy()) {
2102 I1->replaceAllUsesWith(NT);
2104 OtherSuccTI->replaceAllUsesWith(NT);
2108 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2114 for (
auto *OtherSuccTI : OtherSuccTIs)
2115 Locs.
push_back(OtherSuccTI->getDebugLoc());
2127 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
2130 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2131 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2137 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2142 isa<FPMathOperator>(PN) ? &PN :
nullptr,
2147 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2148 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2149 PN.setIncomingValue(i, SI);
2160 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2165 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2169 DTU->applyUpdates(Updates);
2178 if (
I->isIntDivRem())
2180 return !isa<IntrinsicInst>(
I);
2193 std::optional<unsigned> NumUses;
2194 for (
auto *
I : Insts) {
2196 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
2197 I->getType()->isTokenTy())
2202 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2209 if (
const auto *
C = dyn_cast<CallBase>(
I))
2210 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2214 NumUses =
I->getNumUses();
2215 else if (NumUses !=
I->getNumUses())
2221 for (
auto *
I : Insts) {
2235 for (
const Use &U : I0->
uses()) {
2236 auto It = PHIOperands.find(&U);
2237 if (It == PHIOperands.end())
2240 if (!
equal(Insts, It->second))
2248 if (isa<CallBase>(I0)) {
2250 return cast<CallBase>(
I)->isIndirectCall();
2252 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2253 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2254 if (HaveIndirectCalls) {
2255 if (!AllCallsAreIndirect)
2259 Value *Callee =
nullptr;
2261 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2263 Callee = CurrCallee;
2264 else if (Callee != CurrCallee)
2270 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2276 if (!
all_of(Insts, SameAsI0)) {
2282 for (
auto *
I : Insts)
2283 Ops.push_back(
I->getOperand(OI));
2293 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2298 for (
auto *BB :
Blocks) {
2300 I =
I->getPrevNode();
2325 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2328 PN->insertBefore(BBEnd->begin());
2329 for (
auto *
I : Insts)
2330 PN->addIncoming(
I->getOperand(O),
I->getParent());
2339 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2342 for (
auto *
I : Insts)
2354 if (
auto *CB = dyn_cast<CallBase>(I0)) {
2355 bool Success = CB->tryIntersectAttributes(cast<CallBase>(
I));
2356 assert(
Success &&
"We should not be trying to sink callbases "
2357 "with non-intersectable attributes");
2367 auto *PN = cast<PHINode>(U);
2368 PN->replaceAllUsesWith(I0);
2369 PN->eraseFromParent();
2373 for (
auto *
I : Insts) {
2378 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2379 I->replaceAllUsesWith(I0);
2380 I->eraseFromParent();
2430 bool HaveNonUnconditionalPredecessors =
false;
2432 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2433 if (PredBr && PredBr->isUnconditional())
2436 HaveNonUnconditionalPredecessors =
true;
2438 if (UnconditionalPreds.
size() < 2)
2451 for (
const Use &U : PN.incoming_values())
2452 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2453 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2455 Ops.push_back(*IncomingVals[Pred]);
2463 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2476 if (!followedByDeoptOrUnreachable) {
2478 auto IsMemOperand = [](
Use &U) {
2479 auto *
I = cast<Instruction>(U.getUser());
2480 if (isa<LoadInst>(
I))
2482 if (isa<StoreInst>(
I))
2491 unsigned NumPHIInsts = 0;
2492 for (
Use &U : (*LRI)[0]->operands()) {
2493 auto It = PHIOperands.
find(&U);
2494 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2495 return InstructionsToSink.contains(V);
2502 if (IsMemOperand(U) &&
2503 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2510 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2511 return NumPHIInsts <= 1;
2528 while (
Idx < ScanIdx) {
2529 if (!ProfitableToSinkInstruction(LRI)) {
2532 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2545 if (
Idx < ScanIdx) {
2548 InstructionsToSink = InstructionsProfitableToSink;
2554 !ProfitableToSinkInstruction(LRI) &&
2555 "We already know that the last instruction is unprofitable to sink");
2563 for (
auto *
I : *LRI)
2564 InstructionsProfitableToSink.
erase(
I);
2565 if (!ProfitableToSinkInstruction(LRI)) {
2568 InstructionsToSink = InstructionsProfitableToSink;
2580 bool Changed =
false;
2582 if (HaveNonUnconditionalPredecessors) {
2583 if (!followedByDeoptOrUnreachable) {
2591 bool Profitable =
false;
2592 while (
Idx < ScanIdx) {
2626 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2628 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2636 NumSinkCommonInstrs++;
2640 ++NumSinkCommonCode;
2646struct CompatibleSets {
2664 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2669 return Sets.emplace_back();
2673 getCompatibleSet(
II).emplace_back(
II);
2677 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2681 return II->cannotMerge() ||
II->isInlineAsm();
2683 if (
any_of(Invokes, IsIllegalToMerge))
2688 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2689 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2690 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2691 if (HaveIndirectCalls) {
2692 if (!AllCallsAreIndirect)
2698 Value *CurrCallee =
II->getCalledOperand();
2699 assert(CurrCallee &&
"There is always a called operand.");
2702 else if (Callee != CurrCallee)
2710 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2712 if (
any_of(Invokes, HasNormalDest)) {
2715 if (!
all_of(Invokes, HasNormalDest))
2722 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2724 NormalBB = CurrNormalBB;
2725 else if (NormalBB != CurrNormalBB)
2733 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2744 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2746 UnwindBB = CurrUnwindBB;
2748 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2755 Invokes.front()->getUnwindDest(),
2756 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2762 for (
auto *
II : Invokes.drop_front())
2767 auto IsIllegalToMergeArguments = [](
auto Ops) {
2768 Use &U0 = std::get<0>(Ops);
2769 Use &U1 = std::get<1>(Ops);
2775 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2776 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2777 IsIllegalToMergeArguments))
2789 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2795 bool HasNormalDest =
2796 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2800 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2804 II0->
getParent()->getIterator()->getNextNode();
2809 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2811 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2813 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2815 if (!HasNormalDest) {
2819 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2827 return MergedInvoke;
2835 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2841 SuccBBOfMergedInvoke});
2848 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2851 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2854 for (
Use &U : MergedInvoke->operands()) {
2856 if (MergedInvoke->isCallee(&U)) {
2857 if (!IsIndirectCall)
2859 }
else if (!MergedInvoke->isDataOperand(&U))
2864 return II->getOperand(
U.getOperandNo()) !=
U.get();
2871 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2883 Invokes.front()->getParent());
2891 if (!MergedDebugLoc)
2892 MergedDebugLoc =
II->getDebugLoc();
2900 OrigSuccBB->removePredecessor(
II->getParent());
2905 bool Success = MergedInvoke->tryIntersectAttributes(
II);
2906 assert(
Success &&
"Merged invokes with incompatible attributes");
2909 II->replaceAllUsesWith(MergedInvoke);
2910 II->eraseFromParent();
2913 MergedInvoke->setDebugLoc(MergedDebugLoc);
2914 ++NumInvokeSetsFormed;
2917 DTU->applyUpdates(Updates);
2944 bool Changed =
false;
2950 CompatibleSets Grouper;
2956 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2960 if (Invokes.
size() < 2)
2972class EphemeralValueTracker {
2976 if (isa<AssumeInst>(
I))
2978 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2980 return EphValues.count(cast<Instruction>(U));
2986 if (isEphemeral(
I)) {
3025 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
3037 unsigned MaxNumInstToLookAt = 9;
3041 if (!MaxNumInstToLookAt)
3043 --MaxNumInstToLookAt;
3046 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
3049 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
3053 if (SI->getPointerOperand() == StorePtr &&
3054 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
3055 SI->getAlign() >= StoreToHoist->
getAlign())
3057 return SI->getValueOperand();
3061 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
3062 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3063 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3065 bool ExplicitlyDereferenceableOnly;
3069 CaptureComponents::Provenance)) &&
3070 (!ExplicitlyDereferenceableOnly ||
3072 LI->getDataLayout()))) {
3088 unsigned &SpeculatedInstructions,
3096 bool HaveRewritablePHIs =
false;
3115 HaveRewritablePHIs =
true;
3118 if (!OrigCE && !ThenCE)
3125 if (OrigCost + ThenCost > MaxCost)
3132 ++SpeculatedInstructions;
3133 if (SpeculatedInstructions > 1)
3137 return HaveRewritablePHIs;
3141 std::optional<bool> Invert,
3145 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3152 if (!Invert.has_value())
3155 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3159 return BIEndProb < Likely;
3199bool SimplifyCFGOpt::speculativelyExecuteBB(
BranchInst *BI,
3206 if (isa<FCmpInst>(BrCond))
3216 bool Invert =
false;
3235 unsigned SpeculatedInstructions = 0;
3236 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3238 Value *SpeculatedStoreValue =
nullptr;
3240 EphemeralValueTracker EphTracker;
3245 if (isa<PseudoProbeInst>(
I)) {
3255 if (EphTracker.track(&
I))
3260 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3262 SpeculatedConditionalLoadsStores.
size() <
3266 if (IsSafeCheapLoadStore)
3267 SpeculatedConditionalLoadsStores.
push_back(&
I);
3269 ++SpeculatedInstructions;
3271 if (SpeculatedInstructions > 1)
3275 if (!IsSafeCheapLoadStore &&
3278 (SpeculatedStoreValue =
3281 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3287 if (!SpeculatedStore && SpeculatedStoreValue)
3288 SpeculatedStore = cast<StoreInst>(&
I);
3293 for (
Use &
Op :
I.operands()) {
3298 ++SinkCandidateUseCounts[OpI];
3305 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3306 if (Inst->hasNUses(Count)) {
3307 ++SpeculatedInstructions;
3308 if (SpeculatedInstructions > 1)
3315 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3318 SpeculatedInstructions,
Cost,
TTI);
3319 if (!Convert ||
Cost > Budget)
3323 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3327 if (SpeculatedStoreValue) {
3331 Value *FalseV = SpeculatedStoreValue;
3335 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3336 Sel = cast<Instruction>(S);
3368 DbgAssign->replaceVariableLocationOp(OrigV, S);
3378 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3381 I.dropUBImplyingAttrsAndMetadata();
3384 if (EphTracker.contains(&
I)) {
3386 I.eraseFromParent();
3392 for (
auto &It : *ThenBB)
3398 It.dropOneDbgRecord(&DR);
3400 std::prev(ThenBB->end()));
3402 if (!SpeculatedConditionalLoadsStores.
empty())
3421 Value *TrueV = ThenV, *FalseV = OrigV;
3431 I->eraseFromParent();
3444 if (!ReachesNonLocalUses.
insert(BB).second)
3459 EphemeralValueTracker EphTracker;
3465 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3466 if (CI->cannotDuplicate() || CI->isConvergent())
3472 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3479 for (
User *U :
I.users()) {
3482 if (UsedInBB == BB) {
3483 if (isa<PHINode>(UI))
3486 NonLocalUseBlocks.
insert(UsedInBB);
3499 auto *
I = dyn_cast<Instruction>(V);
3500 if (
I &&
I->getParent() == To)
3504 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3516static std::optional<bool>
3532 if (
auto *CB = dyn_cast<ConstantInt>(U))
3537 KnownValues[CB].
insert(Pred);
3541 if (KnownValues.
empty())
3566 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3569 for (
const auto &Pair : KnownValues) {
3586 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3591 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3594 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3602 EdgeBB->setName(RealDest->
getName() +
".critedge");
3603 EdgeBB->moveBefore(RealDest);
3613 TranslateMap[
Cond] = CB;
3619 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3626 N->insertInto(EdgeBB, InsertPt);
3629 N->setName(BBI->getName() +
".c");
3640 if (!BBI->use_empty())
3641 TranslateMap[&*BBI] = V;
3642 if (!
N->mayHaveSideEffects()) {
3643 N->eraseFromParent();
3648 if (!BBI->use_empty())
3649 TranslateMap[&*BBI] =
N;
3655 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3656 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3657 SrcDbgCursor = std::next(BBI);
3659 N->cloneDebugInfoFrom(&*BBI);
3662 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3668 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3669 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3670 InsertPt->cloneDebugInfoFrom(BI);
3673 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3679 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3680 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3691 return std::nullopt;
3697bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(
BranchInst *BI) {
3704 std::optional<bool>
Result;
3705 bool EverChanged =
false;
3711 }
while (Result == std::nullopt);
3720 bool SpeculateUnpredictables) {
3735 if (isa<ConstantInt>(IfCond))
3742 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3745 "Will have either one or two blocks to speculate.");
3752 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3753 if (!IsUnpredictable) {
3756 (TWeight + FWeight) != 0) {
3761 if (IfBlocks.
size() == 1) {
3763 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3764 if (BIBBProb >= Likely)
3767 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3775 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3776 if (IfCondPhiInst->getParent() == BB)
3784 unsigned NumPhis = 0;
3797 if (SpeculateUnpredictables && IsUnpredictable)
3800 bool Changed =
false;
3811 AggressiveInsts,
Cost, Budget,
TTI, AC,
3812 ZeroCostInstructions) ||
3814 AggressiveInsts,
Cost, Budget,
TTI, AC,
3815 ZeroCostInstructions))
3821 PN = dyn_cast<PHINode>(BB->
begin());
3827 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3838 auto IsBinOpOrAnd = [](
Value *V) {
3855 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3868 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3870 <<
" F: " << IfFalse->
getName() <<
"\n");
3888 isa<FPMathOperator>(PN) ? PN :
nullptr,
3892 PN->eraseFromParent();
3902 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3920 if (
Opc == Instruction::And)
3922 if (
Opc == Instruction::Or)
3935 bool PredHasWeights =
3937 bool SuccHasWeights =
3939 if (PredHasWeights || SuccHasWeights) {
3940 if (!PredHasWeights)
3941 PredTrueWeight = PredFalseWeight = 1;
3942 if (!SuccHasWeights)
3943 SuccTrueWeight = SuccFalseWeight = 1;
3953static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3957 "Both blocks must end with a conditional branches.");
3959 "PredBB must be a predecessor of BB.");
3967 (PTWeight + PFWeight) != 0) {
3975 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3976 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3980 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3983 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3984 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3990 return std::nullopt;
4003 bool InvertPredCond;
4004 std::tie(CommonSucc,
Opc, InvertPredCond) =
4007 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4014 {LLVMContext::MD_annotation});
4017 if (InvertPredCond) {
4030 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4032 SuccTrueWeight, SuccFalseWeight)) {
4039 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4045 (SuccFalseWeight + SuccTrueWeight) +
4046 PredTrueWeight * SuccFalseWeight);
4052 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4053 PredFalseWeight * SuccTrueWeight);
4055 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4073 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
4074 {DominatorTree::Delete, PredBlock, BB}});
4099 ++NumFoldBranchToCommonDest;
4106 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4107 return U->getType()->isVectorTy();
4117 unsigned BonusInstThreshold) {
4130 if (!
Cond || !isa<CmpInst, BinaryOperator, SelectInst, TruncInst>(
Cond) ||
4131 Cond->getParent() != BB || !
Cond->hasOneUse())
4141 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
4152 bool InvertPredCond;
4154 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4186 unsigned NumBonusInsts = 0;
4187 bool SawVectorOp =
false;
4188 const unsigned PredCount = Preds.
size();
4194 if (isa<BranchInst>(
I))
4205 NumBonusInsts += PredCount;
4213 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4214 auto *UI = cast<Instruction>(U.getUser());
4215 if (
auto *PN = dyn_cast<PHINode>(UI))
4217 return UI->
getParent() == BB &&
I.comesBefore(UI);
4221 if (!
all_of(
I.uses(), IsBCSSAUse))
4225 BonusInstThreshold *
4231 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4241 for (
auto *BB : {BB1, BB2}) {
4245 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4257 Value *AlternativeV =
nullptr) {
4275 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4276 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4277 PHI = cast<PHINode>(
I);
4283 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4284 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4292 if (!AlternativeV &&
4293 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4298 PHI->addIncoming(V, BB);
4308 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4317 if (!PStore || !QStore)
4338 if (
I.mayReadOrWriteMemory())
4340 for (
auto &
I : *QFB)
4341 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4344 for (
auto &
I : *QTB)
4345 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4349 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4365 if (
I.isTerminator())
4369 if (
auto *S = dyn_cast<StoreInst>(&
I))
4373 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4383 "When we run out of budget we will eagerly return from within the "
4384 "per-instruction loop.");
4388 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4390 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4391 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4427 InvertPCond ^= (PStore->
getParent() != PTB);
4428 InvertQCond ^= (QStore->
getParent() != QTB);
4499 bool InvertPCond =
false, InvertQCond =
false;
4505 if (QFB == PostBB) {
4524 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4527 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4535 for (
auto *BB : {PTB, PFB}) {
4540 PStoreAddresses.
insert(SI->getPointerOperand());
4542 for (
auto *BB : {QTB, QFB}) {
4547 QStoreAddresses.
insert(SI->getPointerOperand());
4553 auto &CommonAddresses = PStoreAddresses;
4555 bool Changed =
false;
4556 for (
auto *
Address : CommonAddresses)
4559 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4577 !BI->
getParent()->getSinglePredecessor())
4579 if (!IfFalseBB->
phis().empty())
4589 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4600 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4601 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4612 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4613 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4692 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4694 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4698 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4701 if (CommonDestProb >= Likely)
4711 unsigned NumPhis = 0;
4733 if (OtherDest == BB) {
4740 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4741 OtherDest = InfLoopBlock;
4761 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4776 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4777 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4780 SuccTrueWeight, SuccFalseWeight);
4782 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4783 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4784 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4785 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4789 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4790 PredOther * SuccCommon,
4791 PredOther * SuccOther};
4820 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4821 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4822 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4823 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4826 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4827 PredOther * SuccCommon};
4850bool SimplifyCFGOpt::simplifyTerminatorOnSelect(
Instruction *OldTerm,
4861 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4868 if (Succ == KeepEdge1)
4869 KeepEdge1 =
nullptr;
4870 else if (Succ == KeepEdge2)
4871 KeepEdge2 =
nullptr;
4876 if (Succ != TrueBB && Succ != FalseBB)
4877 RemovedSuccessors.
insert(Succ);
4885 if (!KeepEdge1 && !KeepEdge2) {
4886 if (TrueBB == FalseBB) {
4894 if (TrueWeight != FalseWeight)
4897 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4919 for (
auto *RemovedSuccessor : RemovedSuccessors)
4920 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4921 DTU->applyUpdates(Updates);
4931bool SimplifyCFGOpt::simplifySwitchOnSelect(
SwitchInst *SI,
4936 if (!TrueVal || !FalseVal)
4941 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4942 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4945 uint32_t TrueWeight = 0, FalseWeight = 0;
4950 if (Weights.
size() == 1 +
SI->getNumCases()) {
4952 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4954 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4959 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4968bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4981 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
5002bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5022 if (
SI->getCondition() != V)
5028 if (
SI->getDefaultDest() != BB) {
5030 assert(VVal &&
"Should have a unique destination value");
5038 return requestResimplify();
5044 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5054 return requestResimplify();
5061 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5086 auto W0 = SIW.getSuccessorWeight(0);
5090 SIW.setSuccessorWeight(0, *NewW);
5092 SIW.addCase(Cst, NewBB, NewW);
5094 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5103 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5104 DTU->applyUpdates(Updates);
5112bool SimplifyCFGOpt::simplifyBranchOnICmpChain(
BranchInst *BI,
5124 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5127 Value *CompVal = ConstantCompare.CompValue;
5128 unsigned UsedICmps = ConstantCompare.UsedICmps;
5129 Value *ExtraCase = ConstantCompare.Extra;
5130 bool TrueWhenEqual = ConstantCompare.IsEq;
5147 if (ExtraCase && Values.
size() < 2)
5162 <<
" cases into SWITCH. BB is:\n"
5172 nullptr,
"switch.early.test");
5196 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5202 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5203 <<
"\nEXTRABB = " << *BB);
5211 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5219 New->addCase(Val, EdgeBB);
5225 PHINode *PN = cast<PHINode>(BBI);
5227 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5234 DTU->applyUpdates(Updates);
5236 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5242 return simplifyCommonResume(RI);
5243 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHIIt()) &&
5246 return simplifySingleResume(RI);
5254 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5259 switch (IntrinsicID) {
5260 case Intrinsic::dbg_declare:
5261 case Intrinsic::dbg_value:
5262 case Intrinsic::dbg_label:
5263 case Intrinsic::lifetime_end:
5273bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5283 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5286 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5288 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5289 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5293 if (IncomingBB->getUniqueSuccessor() != BB)
5296 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHIIt());
5298 if (IncomingValue != LandingPad)
5302 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5303 TrivialUnwindBlocks.
insert(IncomingBB);
5307 if (TrivialUnwindBlocks.
empty())
5311 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5315 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5329 TrivialBB->getTerminator()->eraseFromParent();
5332 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5339 return !TrivialUnwindBlocks.empty();
5343bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5347 "Resume must unwind the exception that caused control to here");
5351 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5387 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5403 int Idx = DestPN.getBasicBlockIndex(BB);
5417 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5418 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5420 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5424 DestPN.addIncoming(
Incoming, Pred);
5451 std::vector<DominatorTree::UpdateType> Updates;
5455 if (UnwindDest ==
nullptr) {
5467 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5468 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5495 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5496 if (!SuccessorCleanupPad)
5505 SuccessorCleanupPad->eraseFromParent();
5534 bool Changed =
false;
5563 BBI->dropDbgRecords();
5567 BBI->eraseFromParent();
5573 if (&BB->
front() != UI)
5576 std::vector<DominatorTree::UpdateType> Updates;
5582 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5586 [BB](
auto *
Successor) { return Successor == BB; })) {
5594 "The destinations are guaranteed to be different here.");
5605 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5611 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5612 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5614 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5615 if (i->getCaseSuccessor() != BB) {
5620 i = SU.removeCase(i);
5625 if (DTU &&
SI->getDefaultDest() != BB)
5626 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5627 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5628 if (
II->getUnwindDest() == BB) {
5630 DTU->applyUpdates(Updates);
5634 if (!CI->doesNotThrow())
5635 CI->setDoesNotThrow();
5638 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5639 if (CSI->getUnwindDest() == BB) {
5641 DTU->applyUpdates(Updates);
5650 E = CSI->handler_end();
5653 CSI->removeHandler(
I);
5660 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5661 if (CSI->getNumHandlers() == 0) {
5662 if (CSI->hasUnwindDest()) {
5666 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5667 Updates.push_back({DominatorTree::Insert,
5668 PredecessorOfPredecessor,
5669 CSI->getUnwindDest()});
5670 Updates.push_back({DominatorTree::Delete,
5671 PredecessorOfPredecessor, Predecessor});
5674 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5678 DTU->applyUpdates(Updates);
5687 CSI->eraseFromParent();
5690 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5692 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5693 "Expected to always have an unwind to BB.");
5695 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5703 DTU->applyUpdates(Updates);
5718 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5719 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5727 bool RemoveOrigDefaultBlock =
true) {
5729 auto *BB = Switch->getParent();
5730 auto *OrigDefaultBlock = Switch->getDefaultDest();
5731 if (RemoveOrigDefaultBlock)
5732 OrigDefaultBlock->removePredecessor(BB);
5736 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5738 Switch->setDefaultDest(&*NewDefaultBlock);
5741 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5742 if (RemoveOrigDefaultBlock &&
5744 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5752bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(
SwitchInst *SI,
5754 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5756 bool HasDefault = !
SI->defaultDestUnreachable();
5758 auto *BB =
SI->getParent();
5761 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5766 for (
auto Case :
SI->cases()) {
5770 if (Dest == DestA) {
5776 if (Dest == DestB) {
5786 "Single-destination switch should have been folded.");
5788 assert(DestB !=
SI->getDefaultDest());
5789 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5797 ContiguousCases = &CasesA;
5798 ContiguousDest = DestA;
5801 ContiguousCases = &CasesB;
5802 ContiguousDest = DestB;
5811 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5814 if (!
Offset->isNullValue())
5829 if (Weights.
size() == 1 +
SI->getNumCases()) {
5832 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5833 if (
SI->getSuccessor(
I) == ContiguousDest)
5834 TrueWeight += Weights[
I];
5836 FalseWeight += Weights[
I];
5838 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5847 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5848 unsigned PreviousEdges = ContiguousCases->
size();
5849 if (ContiguousDest ==
SI->getDefaultDest())
5851 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5852 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5854 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5855 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5856 if (OtherDest ==
SI->getDefaultDest())
5858 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5859 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5867 auto *UnreachableDefault =
SI->getDefaultDest();
5870 SI->eraseFromParent();
5872 if (!HasDefault && DTU)
5873 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5889 unsigned MaxSignificantBitsInCond =
5896 for (
const auto &Case : SI->cases()) {
5897 auto *
Successor = Case.getCaseSuccessor();
5904 const APInt &CaseVal = Case.getCaseValue()->getValue();
5907 DeadCases.
push_back(Case.getCaseValue());
5919 bool HasDefault = !SI->defaultDestUnreachable();
5920 const unsigned NumUnknownBits =
5923 if (HasDefault && DeadCases.
empty() &&
5924 NumUnknownBits < 64 ) {
5925 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5926 if (SI->getNumCases() == AllNumCases) {
5933 if (SI->getNumCases() == AllNumCases - 1) {
5934 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5941 for (
const auto &Case : SI->cases())
5942 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5944 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5953 if (DeadCases.
empty())
5959 assert(CaseI != SI->case_default() &&
5960 "Case was not found. Probably mistake in DeadCases forming.");
5962 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5967 std::vector<DominatorTree::UpdateType> Updates;
5968 for (
auto *
Successor : UniqueSuccessors)
5969 if (NumPerSuccessorCases[
Successor] == 0)
5970 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5990 if (!Branch || !Branch->isUnconditional())
5996 int Idx =
PHI.getBasicBlockIndex(BB);
5997 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
6000 if (InValue != CaseValue)
6016 ForwardingNodesMap ForwardingNodes;
6018 bool Changed =
false;
6019 for (
const auto &Case : SI->cases()) {
6021 BasicBlock *CaseDest = Case.getCaseSuccessor();
6040 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6041 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6042 count(Phi.blocks(), SwitchBlock) == 1) {
6043 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
6051 ForwardingNodes[Phi].push_back(PhiIdx);
6054 for (
auto &ForwardingNode : ForwardingNodes) {
6055 PHINode *Phi = ForwardingNode.first;
6061 for (
int Index : Indexes)
6062 Phi->setIncomingValue(Index, SI->getCondition());
6072 if (
C->isThreadDependent())
6074 if (
C->isDLLImportDependent())
6077 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
6078 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
6079 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
6085 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
6101 if (
Constant *
C = dyn_cast<Constant>(V))
6117 if (
A->isAllOnesValue())
6119 if (
A->isNullValue())
6125 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
6150 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
6152 if (
I.isTerminator()) {
6154 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6157 CaseDest =
I.getSuccessor(0);
6164 for (
auto &
Use :
I.uses()) {
6167 if (
I->getParent() == CaseDest)
6170 if (Phi->getIncomingBlock(
Use) == CaseDest)
6183 *CommonDest = CaseDest;
6185 if (CaseDest != *CommonDest)
6190 int Idx =
PHI.getBasicBlockIndex(Pred);
6203 Res.push_back(std::make_pair(&
PHI, ConstVal));
6206 return Res.size() > 0;
6212 SwitchCaseResultVectorTy &UniqueResults,
6214 for (
auto &
I : UniqueResults) {
6215 if (
I.first == Result) {
6216 I.second.push_back(CaseVal);
6217 return I.second.size();
6220 UniqueResults.push_back(
6231 SwitchCaseResultVectorTy &UniqueResults,
6235 uintptr_t MaxUniqueResults) {
6236 for (
const auto &
I : SI->cases()) {
6250 const size_t NumCasesForResult =
6258 if (UniqueResults.size() > MaxUniqueResults)
6269 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6274 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6276 return DefaultResult || SI->defaultDestUnreachable();
6293 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6294 ResultVector[1].second.size() == 1) {
6295 ConstantInt *FirstCase = ResultVector[0].second[0];
6296 ConstantInt *SecondCase = ResultVector[1].second[0];
6297 Value *SelectValue = ResultVector[1].first;
6298 if (DefaultResult) {
6299 Value *ValueCompare =
6300 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6301 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6302 DefaultResult,
"switch.select");
6304 Value *ValueCompare =
6305 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6306 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6307 SelectValue,
"switch.select");
6311 if (ResultVector.size() == 1 && DefaultResult) {
6313 unsigned CaseCount = CaseValues.
size();
6326 for (
auto *Case : CaseValues) {
6327 if (Case->getValue().slt(MinCaseVal->
getValue()))
6329 AndMask &= Case->getValue();
6339 if (FreeBits ==
Log2_32(CaseCount)) {
6343 return Builder.
CreateSelect(Cmp, ResultVector[0].first,
6350 for (
auto *Case : CaseValues)
6351 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6357 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6361 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6366 if (CaseValues.
size() == 2) {
6368 "switch.selectcmp.case1");
6370 "switch.selectcmp.case2");
6371 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6372 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6385 std::vector<DominatorTree::UpdateType> Updates;
6391 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6396 PHI->removeIncomingValueIf(
6397 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6398 PHI->addIncoming(SelectValue, SelectBB);
6401 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6407 if (DTU && RemovedSuccessors.
insert(Succ).second)
6408 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6410 SI->eraseFromParent();
6425 SwitchCaseResultVectorTy UniqueResults;
6431 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6433 Value *SelectValue =
6446class SwitchReplacement {
6507 bool LinearMapValWrapped =
false;
6515SwitchReplacement::SwitchReplacement(
6519 : DefaultValue(DefaultValue) {
6520 assert(Values.size() &&
"Can't build lookup table without values!");
6521 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6524 SingleValue = Values.begin()->second;
6526 ValueType = Values.begin()->second->getType();
6530 for (
const auto &[CaseVal, CaseRes] : Values) {
6534 TableContents[
Idx] = CaseRes;
6536 if (SingleValue && !isa<PoisonValue>(CaseRes) && CaseRes != SingleValue)
6537 SingleValue = isa<PoisonValue>(SingleValue) ? CaseRes :
nullptr;
6541 if (Values.size() < TableSize) {
6543 "Need a default value to fill the lookup table holes.");
6546 if (!TableContents[
I])
6547 TableContents[
I] = DefaultValue;
6551 bool DefaultValueIsPoison = isa<PoisonValue>(DefaultValue);
6553 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6554 SingleValue =
nullptr;
6560 Kind = SingleValueKind;
6567 bool LinearMappingPossible =
true;
6572 bool NonMonotonic =
false;
6573 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6576 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6578 if (!ConstVal && isa<PoisonValue>(TableContents[
I])) {
6584 ConstVal = dyn_cast<ConstantInt>(Values[0].second);
6590 LinearMappingPossible =
false;
6595 APInt Dist = Val - PrevVal;
6598 }
else if (Dist != DistToPrev) {
6599 LinearMappingPossible =
false;
6607 if (LinearMappingPossible) {
6608 LinearOffset = cast<ConstantInt>(TableContents[0]);
6609 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6610 APInt M = LinearMultiplier->getValue();
6611 bool MayWrap =
true;
6612 if (
isIntN(
M.getBitWidth(), TableSize - 1))
6613 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6614 LinearMapValWrapped = NonMonotonic || MayWrap;
6615 Kind = LinearMapKind;
6622 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6624 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6626 TableInt <<=
IT->getBitWidth();
6628 if (!isa<UndefValue>(TableContents[
I - 1])) {
6629 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6630 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6633 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6634 BitMapElementTy =
IT;
6641 auto *TableTy = ArrayType::get(
ValueType, TableSize);
6644 Kind = LookupTableKind;
6650 case SingleValueKind:
6652 case LinearMapKind: {
6655 false,
"switch.idx.cast");
6656 if (!LinearMultiplier->isOne())
6657 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6659 !LinearMapValWrapped);
6661 if (!LinearOffset->isZero())
6664 !LinearMapValWrapped);
6680 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6681 "switch.shiftamt",
true,
true);
6684 Value *DownShifted =
6685 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6687 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6689 case LookupTableKind: {
6692 true, GlobalVariable::PrivateLinkage,
6693 Initializer,
"switch.table." +
Func->getName());
6694 Table->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6697 Table->setAlignment(
DL.getPrefTypeAlign(
ValueType));
6698 Type *IndexTy =
DL.getIndexType(Table->getType());
6699 auto *ArrayTy = cast<ArrayType>(Table->getValueType());
6701 if (
Index->getType() != IndexTy) {
6702 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
6704 if (
auto *Zext = dyn_cast<ZExtInst>(Index))
6706 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
6709 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
6712 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
6718bool SwitchReplacement::wouldFitInRegister(
const DataLayout &
DL,
6720 Type *ElementType) {
6721 auto *
IT = dyn_cast<IntegerType>(ElementType);
6728 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6730 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6739 auto *
IT = dyn_cast<IntegerType>(Ty);
6751 DL.fitsInLegalInteger(
IT->getBitWidth());
6754Constant *SwitchReplacement::getDefaultValue() {
return DefaultValue; }
6765 return NumCases * 100 >= CaseRange * MinDensity;
6786 if (SI->getNumCases() > TableSize)
6789 bool AllTablesFitInRegister =
true;
6790 bool HasIllegalType =
false;
6791 for (
const auto &Ty : ResultTypes) {
6796 AllTablesFitInRegister =
6797 AllTablesFitInRegister &&
6798 SwitchReplacement::wouldFitInRegister(
DL, TableSize, Ty);
6803 if (HasIllegalType && !AllTablesFitInRegister)
6808 if (AllTablesFitInRegister)
6825 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6828 return all_of(ResultTypes, [&](
const auto &ResultType) {
6829 return SwitchReplacement::wouldFitInRegister(
6857 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6879 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6884 for (
auto ValuePair : Values) {
6887 if (!CaseConst || CaseConst == DefaultConst ||
6888 (CaseConst != TrueConst && CaseConst != FalseConst))
6902 if (DefaultConst == FalseConst) {
6905 ++NumTableCmpReuses;
6908 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6909 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6912 ++NumTableCmpReuses;
6922 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6941 if (SI->getNumCases() < 3)
6946 assert(!SI->cases().empty());
6963 MinCaseVal = CaseVal;
6965 MaxCaseVal = CaseVal;
6970 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6982 It->second.push_back(std::make_pair(CaseVal,
Value));
6990 bool HasDefaultResults =
6992 DefaultResultsList,
DL,
TTI);
6993 for (
const auto &
I : DefaultResultsList) {
6996 DefaultResults[
PHI] = Result;
7000 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7003 if (UseSwitchConditionAsTableIndex) {
7005 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7010 TableIndexOffset = MinCaseVal;
7017 bool DefaultIsReachable = !SI->defaultDestUnreachable();
7019 bool TableHasHoles = (NumResults < TableSize);
7024 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7032 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7035 if (SI->getNumCases() < 4)
7037 if (!
DL.fitsInLegalInteger(TableSize))
7046 if (UseSwitchConditionAsTableIndex) {
7047 TableIndex = SI->getCondition();
7048 if (HasDefaultResults) {
7060 all_of(ResultTypes, [&](
const auto &ResultType) {
7061 return SwitchReplacement::wouldFitInRegister(
DL, UpperBound,
7066 TableSize = std::max(UpperBound, TableSize);
7069 DefaultIsReachable =
false;
7077 const auto &ResultList = ResultLists[
PHI];
7079 Type *ResultType = ResultList.begin()->second->getType();
7084 SwitchReplacement Replacement(*Fn->
getParent(), TableSize, TableIndexOffset,
7086 PhiToReplacementMap.
insert({
PHI, Replacement});
7092 if (!UseSwitchConditionAsTableIndex) {
7095 bool MayWrap =
true;
7096 if (!DefaultIsReachable) {
7101 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
7102 "switch.tableidx",
false,
7106 std::vector<DominatorTree::UpdateType> Updates;
7112 assert(MaxTableSize >= TableSize &&
7113 "It is impossible for a switch to have more entries than the max "
7114 "representable value of its input integer type's size.");
7119 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7124 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7125 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7128 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7133 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7135 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
7137 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7147 MaskBB->
setName(
"switch.hole_check");
7154 APInt MaskInt(TableSizePowOf2, 0);
7155 APInt One(TableSizePowOf2, 1);
7157 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7158 for (
const auto &Result : ResultList) {
7161 MaskInt |= One <<
Idx;
7163 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7171 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7174 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
7176 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
7177 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
7183 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7186 SI->getDefaultDest()->removePredecessor(BB,
7189 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
7193 const ResultListTy &ResultList = ResultLists[
PHI];
7194 auto Replacement = PhiToReplacementMap.
at(
PHI);
7195 auto *Result = Replacement.replaceSwitch(TableIndex, Builder,
DL, Fn);
7198 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7201 for (
auto *
User :
PHI->users()) {
7203 Replacement.getDefaultValue(), ResultList);
7207 PHI->addIncoming(Result, LookupBB);
7212 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
7216 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
7219 if (Succ == SI->getDefaultDest())
7222 if (DTU && RemovedSuccessors.
insert(Succ).second)
7223 Updates.push_back({DominatorTree::Delete, BB, Succ});
7225 SI->eraseFromParent();
7232 ++NumLookupTablesHoles;
7247 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
7248 if (CondTy->getIntegerBitWidth() > 64 ||
7249 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7253 if (SI->getNumCases() < 4)
7261 for (
const auto &
C : SI->cases())
7262 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7270 int64_t
Base = Values[0];
7271 for (
auto &V : Values)
7284 unsigned Shift = 64;
7285 for (
auto &V : Values)
7289 for (
auto &V : Values)
7290 V = (int64_t)((
uint64_t)V >> Shift);
7306 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7309 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7311 Ty, Intrinsic::fshl,
7312 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7313 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7315 for (
auto Case : SI->cases()) {
7316 auto *Orig = Case.getCaseValue();
7317 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7318 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty,
Sub.lshr(Shift))));
7336 Value *Condition = SI->getCondition();
7338 auto *CondTy = cast<IntegerType>(Condition->
getType());
7340 if (CondTy->getIntegerBitWidth() > 64 ||
7341 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7353 if (SI->getNumCases() < 4)
7359 if (!SI->defaultDestUnreachable())
7364 for (
const auto &Case : SI->cases()) {
7365 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7382 for (
auto &Case : SI->cases()) {
7383 auto *OrigValue = Case.getCaseValue();
7384 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7385 OrigValue->getValue().countr_zero()));
7392 SI->setCondition(ConditionTrailingZeros);
7401 auto *Cmp = dyn_cast<CmpIntrinsic>(SI->getCondition());
7402 if (!Cmp || !Cmp->hasOneUse())
7413 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7416 if (SI->getNumCases() == 2) {
7423 Succ = SI->getDefaultDest();
7424 SuccWeight = Weights[0];
7426 for (
auto &Case : SI->cases()) {
7427 std::optional<int64_t> Val =
7431 if (!Missing.erase(*Val))
7436 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7439 assert(Missing.size() == 1 &&
"Should have one case left");
7440 Res = *Missing.begin();
7441 }
else if (SI->getNumCases() == 3 && SI->defaultDestUnreachable()) {
7443 Unreachable = SI->getDefaultDest();
7445 for (
auto &Case : SI->cases()) {
7446 BasicBlock *NewSucc = Case.getCaseSuccessor();
7447 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7450 OtherSuccWeight += Weight;
7453 SuccWeight = Weight;
7454 }
else if (Succ == NewSucc) {
7460 for (
auto &Case : SI->cases()) {
7461 std::optional<int64_t> Val =
7463 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7465 if (Case.getCaseSuccessor() == Succ) {
7478 Pred = ICmpInst::ICMP_UGT;
7481 Pred = ICmpInst::ICMP_EQ;
7484 Pred = ICmpInst::ICMP_ULT;
7487 if (Cmp->isSigned())
7490 MDNode *NewWeights =
nullptr;
7492 NewWeights =
MDBuilder(SI->getContext())
7499 SI->getMetadata(LLVMContext::MD_unpredictable));
7503 SI->eraseFromParent();
7504 Cmp->eraseFromParent();
7505 if (DTU && Unreachable)
7506 DTU->
applyUpdates({{DominatorTree::Delete, BB, Unreachable}});
7537 "Only supporting unconditional branches for now");
7539 "Expected unconditional branches to have one successor");
7540 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7561 if (
LHS == EKey ||
RHS == EKey ||
LHS == TKey ||
RHS == TKey)
7574 BranchInst *ABI = cast<BranchInst>(
A->getTerminator());
7575 BranchInst *BBI = cast<BranchInst>(
B->getTerminator());
7577 "Only supporting unconditional branches for now");
7584 auto &PredIVs = (*
LHS->PhiPredIVs)[&Phi];
7585 if (PredIVs[
A] != PredIVs[
B])
7594bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *SI,
7608 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7613 if (BB->
size() != 1)
7623 if (!Seen.
insert(BB).second) {
7624 auto It = BBToSuccessorIndexes.
find(BB);
7625 if (It != BBToSuccessorIndexes.
end())
7626 It->second.emplace_back(
I);
7641 BBToSuccessorIndexes[BB].emplace_back(
I);
7649 PhiPredIVs.
try_emplace(Phi,
Phi->getNumIncomingValues()).first->second;
7650 for (
auto &
IV :
Phi->incoming_values())
7651 IVs.insert({
Phi->getIncomingBlock(
IV),
IV.get()});
7667 bool MadeChange =
false;
7668 for (
auto &SSW : Cases) {
7676 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7677 for (
unsigned Idx : Successors)
7678 SI->setSuccessor(
Idx, (*It)->Dest);
7692 if (isValueEqualityComparison(SI)) {
7696 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7697 return requestResimplify();
7701 if (simplifySwitchOnSelect(SI,
Select))
7702 return requestResimplify();
7707 if (foldValueComparisonIntoPredecessors(SI, Builder))
7708 return requestResimplify();
7714 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7715 return requestResimplify();
7719 return requestResimplify();
7722 return requestResimplify();
7725 return requestResimplify();
7728 return requestResimplify();
7735 if (
Options.ConvertSwitchToLookupTable &&
7737 return requestResimplify();
7740 return requestResimplify();
7743 return requestResimplify();
7746 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
7747 return requestResimplify();
7749 if (simplifyDuplicateSwitchArms(SI, DTU))
7750 return requestResimplify();
7757 bool Changed =
false;
7766 RemovedSuccs.
insert(Dest);
7776 std::vector<DominatorTree::UpdateType> Updates;
7778 for (
auto *RemovedSucc : RemovedSuccs)
7798 if (simplifyIndirectBrOnSelect(IBI, SI))
7799 return requestResimplify();
7831 if (isa<PHINode>(*Succ->
begin()))
7835 if (BB == OtherPred)
7846 std::vector<DominatorTree::UpdateType> Updates;
7853 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7854 "unexpected successor");
7855 II->setUnwindDest(OtherPred);
7880 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7881 : simplifyCondBranch(
Branch, Builder);
7884bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7896 bool NeedCanonicalLoop =
7907 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7910 if (
I->isTerminator() &&
7911 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7927 if (
Options.SpeculateBlocks &&
7930 return requestResimplify();
7938 if (!PPred || (PredPred && PredPred != PPred))
7975 if (!SuccBI || !SuccBI->isConditional())
7979 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7980 !isa<PHINode>(Succ1->
front()) && !isa<PHINode>(Succ2->
front());
7983 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
8009 bool HasWeight =
false;
8014 BBTWeight = BBFWeight = 1;
8019 BB1TWeight = BB1FWeight = 1;
8024 BB2TWeight = BB2FWeight = 1;
8026 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8027 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8038 "Tautological conditional branch should have been eliminated already.");
8041 if (!
Options.SimplifyCondBranch ||
8046 if (isValueEqualityComparison(BI)) {
8051 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8052 return requestResimplify();
8058 if (foldValueComparisonIntoPredecessors(BI, Builder))
8059 return requestResimplify();
8062 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8063 return requestResimplify();
8068 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8081 return requestResimplify();
8087 if (
Options.SpeculateBlocks &&
8090 return requestResimplify();
8099 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8100 return requestResimplify();
8102 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8105 auto CanSpeculateConditionalLoadsStores = [&]() {
8108 if (
I.isTerminator()) {
8109 if (
I.getNumSuccessors() > 1)
8113 SpeculatedConditionalLoadsStores.
size() ==
8117 SpeculatedConditionalLoadsStores.
push_back(&
I);
8120 return !SpeculatedConditionalLoadsStores.
empty();
8123 if (CanSpeculateConditionalLoadsStores()) {
8125 std::nullopt,
nullptr);
8126 return requestResimplify();
8136 return requestResimplify();
8145 return requestResimplify();
8151 if (foldCondBranchOnValueKnownInPredecessor(BI))
8152 return requestResimplify();
8157 if (PBI != BI && PBI->isConditional())
8159 return requestResimplify();
8164 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
8165 if (PBI != BI && PBI->isConditional())
8167 return requestResimplify();
8171 return requestResimplify();
8178 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8186 if (
C->isNullValue() || isa<UndefValue>(
C)) {
8190 auto *Use = cast<Instruction>(U.getUser());
8192 switch (Use->getOpcode()) {
8195 case Instruction::GetElementPtr:
8196 case Instruction::Ret:
8197 case Instruction::BitCast:
8198 case Instruction::Load:
8199 case Instruction::Store:
8200 case Instruction::Call:
8201 case Instruction::CallBr:
8202 case Instruction::Invoke:
8203 case Instruction::UDiv:
8204 case Instruction::URem:
8208 case Instruction::SDiv:
8209 case Instruction::SRem:
8213 if (FindUse ==
I->use_end())
8215 auto &
Use = *FindUse;
8220 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8221 User->comesBefore(
I))
8235 if (
GEP->getPointerOperand() ==
I) {
8238 if (
GEP->getType()->isVectorTy())
8246 if (!
GEP->hasAllZeroIndices() &&
8247 (!
GEP->isInBounds() ||
8249 GEP->getPointerAddressSpace())))
8250 PtrValueMayBeModified =
true;
8256 bool HasNoUndefAttr =
8257 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8259 if (isa<UndefValue>(
C) && HasNoUndefAttr)
8262 if (
C->isNullValue() && HasNoUndefAttr &&
8263 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8264 return !PtrValueMayBeModified;
8270 if (!LI->isVolatile())
8272 LI->getPointerAddressSpace());
8276 if (!SI->isVolatile())
8278 SI->getPointerAddressSpace())) &&
8279 SI->getPointerOperand() ==
I;
8282 if (
auto *Assume = dyn_cast<AssumeInst>(
User)) {
8284 if (
I == Assume->getArgOperand(0))
8288 if (
auto *CB = dyn_cast<CallBase>(
User)) {
8292 if (CB->getCalledOperand() ==
I)
8295 if (CB->isArgOperand(&
Use)) {
8296 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8298 if (isa<ConstantPointerNull>(
C) &&
8299 CB->paramHasNonNullAttr(ArgIdx,
false))
8300 return !PtrValueMayBeModified;
8302 if (isa<UndefValue>(
C) && CB->isPassingUndefUB(ArgIdx))
8319 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8348 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
8356 for (
const auto &Case : SI->cases())
8357 if (Case.getCaseSuccessor() == BB) {
8359 Case.setSuccessor(Unreachable);
8361 if (SI->getDefaultDest() == BB) {
8363 SI->setDefaultDest(Unreachable);
8377bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
8378 bool Changed =
false;
8402 return requestResimplify();
8423 if (
Options.SpeculateBlocks &&
8427 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
8430 Options.SpeculateUnpredictables))
8437 case Instruction::Br:
8438 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
8440 case Instruction::Resume:
8441 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
8443 case Instruction::CleanupRet:
8444 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
8446 case Instruction::Switch:
8447 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
8449 case Instruction::Unreachable:
8450 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
8452 case Instruction::IndirectBr:
8453 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
8461 bool Changed =
false;
8469 Changed |= simplifyOnce(BB);
8470 }
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)
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
std::optional< std::vector< StOtherPiece > > Other
DenseMap< Block *, BlockRelaxAux > Blocks
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.
This file implements a map that provides insertion order iteration.
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
MachineInstr unsigned OpIdx
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
unsigned unsigned DefaultVal
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static void addPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static bool validLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static bool simplifySwitchLookup(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static bool isProfitableToSpeculate(const BranchInst *BI, std::optional< bool > Invert, const TargetTransformInfo &TTI)
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool valuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static 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"))
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static void hoistConditionalLoadsStores(BranchInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert, Instruction *Sel)
If the target supports conditional faulting, we look for the following pattern:
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static 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"))
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static void cloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static int constantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder, const DataLayout &DL)
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"))
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 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"))
static bool simplifySwitchOfCmpIntrinsic(SwitchInst *SI, IRBuilderBase &Builder, DomTreeUpdater *DTU)
Fold switch over ucmp/scmp intrinsic to br if two of the switch arms have the same destination.
static bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallVector< Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}{Tru...
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)"))
static Constant * constantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static bool tryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static bool areIdenticalUpToCommutativity(const Instruction *I1, const Instruction *I2)
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"))
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 void setBranchWeights(SwitchInst *SI, ArrayRef< uint32_t > Weights, bool IsExpected)
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool reduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static bool safeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
@ SkipImplicitControlFlow
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
static bool incomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
static void fitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool sinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static bool casesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB, BlocksSet &NonLocalUseBlocks)
Return true if we can thread a branch across this block.
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static bool foldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL, bool SpeculateUnpredictables)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool findReaching(BasicBlock *BB, BasicBlock *DefBB, BlocksSet &ReachesNonLocalUses)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallVector< Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
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 unsigned skippedInstrFlags(Instruction *I)
static bool mergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static void eraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static void eliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static std::optional< bool > foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static 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"))
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static void mergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static void getBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool mergeNestedCondBranch(BranchInst *BI, DomTreeUpdater *DTU)
Fold the following pattern: bb0: br i1 cond1, label bb1, label bb2 bb1: br i1 cond2,...
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static Constant * lookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static 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 bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
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"))
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 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"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
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)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static 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"))
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
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 bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, SmallPtrSetImpl< Instruction * > &ZeroCostInstructions, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static const uint32_t IV[8]
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
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...
LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
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.
const Function * getParent() const
Return the enclosing method, or null if none.
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.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
LLVM_ABI bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
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.
The address of a basic block.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
This class represents a function call, abstracting a target machine's calling convention.
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getPredicate() const
Return the predicate for this instruction.
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
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 LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
LLVM_ABI ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
LLVM_ABI bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
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...
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
LLVM_ABI void removeFromParent()
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isSameSourceLocation(const DebugLoc &Other) const
Return true if the source locations match, ignoring isImplicitCode and source atom info.
static DebugLoc getTemporary()
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
static LLVM_ABI DebugLoc getMergedLocations(ArrayRef< DebugLoc > Locs)
Try to combine the vector of locations passed as input in a single one.
static DebugLoc getDropped()
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
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.
bool hasPostDomTree() const
Returns true if it holds a PostDomTreeT.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
UnreachableInst * CreateUnreachable()
LLVM_ABI Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
LLVM_ABI CallInst * CreateMaskedLoad(Type *Ty, Value *Ptr, Align Alignment, Value *Mask, Value *PassThru=nullptr, const Twine &Name="")
Create a call to Masked Load intrinsic.
LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
LLVM_ABI CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
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="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
LLVM_ABI CallInst * CreateMaskedStore(Value *Val, Value *Ptr, Align Alignment, Value *Mask)
Create a call to Masked Store intrinsic.
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
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 * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="", bool IsDisjoint=false)
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
LLVM_ABI void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
LLVM_ABI void dropUBImplyingAttrsAndMetadata(ArrayRef< unsigned > Keep={})
Drop any attributes or metadata that can cause immediate undefined behavior.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)
Merge 2 debug locations and apply it to the Instruction.
LLVM_ABI void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
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.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
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.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
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.
This class represents a cast from a pointer to an integer.
Resume the propagation of an exception.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
LLVM_ABI void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
LLVM_ABI CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
LLVM_ABI SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
bool isPointerTy() const
True if this is an instance of PointerType.
static LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
LLVM_ABI unsigned getIntegerBitWidth() const
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
LLVM_ABI void set(Value *Val)
User * getUser() const
Returns the User that contains this Use.
LLVM_ABI unsigned getOperandNo() const
Return the operand # of this use in its User.
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
LLVM_ABI Value(Type *Ty, unsigned scid)
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
Return a range of dbg_assign records for which Inst performs the assignment they encode.
LLVM_ABI void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
NodeAddr< FuncNode * > Func
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)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
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...
LLVM_ABI BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
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<>...
auto successors(const MachineBasicBlock *BB)
constexpr from_range_t from_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
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.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
LLVM_ABI bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
LLVM_ABI void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
LLVM_ABI bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
LLVM_ABI Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
auto succ_size(const MachineBasicBlock *BB)
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
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.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ Sub
Subtraction of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
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.
constexpr unsigned BitWidth
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto predecessors(const MachineBasicBlock *BB)
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
LLVM_ABI unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Get the upper bound on bit size for this Value Op as a signed integer.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
LLVM_ABI bool foldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool pred_empty(const BasicBlock *BB)
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
LLVM_ABI bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
bool capturesNothing(CaptureComponents CC)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)
Remap source location atom.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)
Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
LLVM_ABI void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Checking whether two cases of SI are equal depends on the contents of the BasicBlock and the incoming...
DenseMap< PHINode *, SmallDenseMap< BasicBlock *, Value *, 8 > > * PhiPredIVs
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const SwitchSuccWrapper * getEmptyKey()
static const SwitchSuccWrapper * getTombstoneKey()
static unsigned getHashValue(const SwitchSuccWrapper *SSW)
static bool isEqual(const SwitchSuccWrapper *LHS, const SwitchSuccWrapper *RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
A MapVector that performs no allocations if smaller than a certain size.