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 (!((ICI = dyn_cast<ICmpInst>(
I)) &&
629 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
673 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
675 if (!setValueOnce(RHSVal))
680 ConstantInt::get(
C->getContext(),
681 C->getValue() | Mask));
696 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
698 if (!setValueOnce(RHSVal))
702 Vals.
push_back(ConstantInt::get(
C->getContext(),
703 C->getValue() & ~Mask));
724 Value *CandidateVal =
I->getOperand(0);
727 CandidateVal = RHSVal;
742 if (!setValueOnce(CandidateVal))
747 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
758 void gather(
Value *V) {
770 while (!DFT.empty()) {
771 V = DFT.pop_back_val();
777 if (Visited.insert(Op1).second)
779 if (Visited.insert(Op0).second)
786 if (matchInstruction(
I, IsEq))
810 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
811 Cond = dyn_cast<Instruction>(SI->getCondition());
812 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
813 if (BI->isConditional())
814 Cond = dyn_cast<Instruction>(BI->getCondition());
816 Cond = dyn_cast<Instruction>(IBI->getAddress());
828 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
831 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
832 CV =
SI->getCondition();
833 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
834 if (BI->isConditional() && BI->getCondition()->hasOneUse()) {
835 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
838 }
else if (
auto *Trunc = dyn_cast<TruncInst>(BI->getCondition())) {
839 if (Trunc->hasNoUnsignedWrap())
840 CV = Trunc->getOperand(0);
847 Value *
Ptr = PTII->getPointerOperand();
848 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
857BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
858 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
859 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
860 Cases.reserve(
SI->getNumCases());
861 for (
auto Case :
SI->cases())
862 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
863 Case.getCaseSuccessor()));
864 return SI->getDefaultDest();
871 if (
auto *ICI = dyn_cast<ICmpInst>(
Cond)) {
875 Pred = ICmpInst::ICMP_NE;
876 auto *Trunc = cast<TruncInst>(
Cond);
877 C = ConstantInt::get(cast<IntegerType>(Trunc->getOperand(0)->getType()), 0);
880 Cases.push_back(ValueEqualityComparisonCase(
C, Succ));
888 std::vector<ValueEqualityComparisonCase> &Cases) {
894 std::vector<ValueEqualityComparisonCase> &C2) {
895 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
898 if (V1->size() > V2->size())
903 if (V1->size() == 1) {
906 for (
const ValueEqualityComparisonCase &VECC : *V2)
907 if (TheVal == VECC.
Value)
914 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
915 while (i1 != e1 && i2 != e2) {
936 SI->setMetadata(LLVMContext::MD_prof,
N);
942 uint32_t FalseWeight,
bool IsExpected) {
943 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
947 if (TrueWeight || FalseWeight)
950 I->setMetadata(LLVMContext::MD_prof,
N);
958bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
964 Value *ThisVal = isValueEqualityComparison(TI);
965 assert(ThisVal &&
"This isn't a value comparison!!");
966 if (ThisVal != PredVal)
973 std::vector<ValueEqualityComparisonCase> PredCases;
975 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
979 std::vector<ValueEqualityComparisonCase> ThisCases;
980 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
992 if (isa<BranchInst>(TI)) {
995 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
1001 ThisCases[0].Dest->removePredecessor(PredDef);
1004 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1011 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
1019 for (
const ValueEqualityComparisonCase &Case : PredCases)
1020 DeadCases.
insert(Case.Value);
1023 <<
"Through successor TI: " << *TI);
1028 auto *
Successor = i->getCaseSuccessor();
1031 if (DeadCases.
count(i->getCaseValue())) {
1040 std::vector<DominatorTree::UpdateType> Updates;
1041 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
1043 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
1044 DTU->applyUpdates(Updates);
1055 for (
const auto &[
Value, Dest] : PredCases)
1061 assert(TIV &&
"No edge from pred to succ?");
1066 for (
const auto &[
Value, Dest] : ThisCases)
1074 TheRealDest = ThisDef;
1081 if (Succ != CheckEdge) {
1082 if (Succ != TheRealDest)
1083 RemovedSuccs.
insert(Succ);
1086 CheckEdge =
nullptr;
1093 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1100 for (
auto *RemovedSucc : RemovedSuccs)
1101 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1102 DTU->applyUpdates(Updates);
1112struct ConstantIntOrdering {
1114 return LHS->getValue().ult(
RHS->getValue());
1126 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1135 assert(MD &&
"Invalid branch-weight metadata");
1141 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1155 if (Max > UINT_MAX) {
1170 if (BonusInst.isTerminator())
1200 NewBonusInst->
takeName(&BonusInst);
1201 BonusInst.setName(NewBonusInst->
getName() +
".old");
1202 VMap[&BonusInst] = NewBonusInst;
1208 auto *UI = cast<Instruction>(U.getUser());
1209 auto *PN = dyn_cast<PHINode>(UI);
1211 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1212 "If the user is not a PHI node, then it should be in the same "
1213 "block as, and come after, the original bonus instruction.");
1217 if (PN->getIncomingBlock(U) == BB)
1221 assert(PN->getIncomingBlock(U) == PredBlock &&
1222 "Not in block-closed SSA form?");
1223 U.set(NewBonusInst);
1233 if (!PredDL->getAtomGroup() &&
DL &&
DL->getAtomGroup() &&
1234 PredDL.isSameSourceLocation(
DL)) {
1241bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1249 std::vector<ValueEqualityComparisonCase> BBCases;
1250 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1252 std::vector<ValueEqualityComparisonCase> PredCases;
1253 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1265 if (PredHasWeights) {
1268 if (Weights.
size() != 1 + PredCases.size())
1269 PredHasWeights = SuccHasWeights =
false;
1270 }
else if (SuccHasWeights)
1274 Weights.
assign(1 + PredCases.size(), 1);
1277 if (SuccHasWeights) {
1280 if (SuccWeights.
size() != 1 + BBCases.size())
1281 PredHasWeights = SuccHasWeights =
false;
1282 }
else if (PredHasWeights)
1283 SuccWeights.
assign(1 + BBCases.size(), 1);
1285 if (PredDefault == BB) {
1288 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1289 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1290 if (PredCases[i].Dest != BB)
1291 PTIHandled.insert(PredCases[i].
Value);
1294 std::swap(PredCases[i], PredCases.back());
1296 if (PredHasWeights || SuccHasWeights) {
1298 Weights[0] += Weights[i + 1];
1303 PredCases.pop_back();
1309 if (PredDefault != BBDefault) {
1311 if (DTU && PredDefault != BB)
1312 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1313 PredDefault = BBDefault;
1314 ++NewSuccessors[BBDefault];
1317 unsigned CasesFromPred = Weights.
size();
1319 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1320 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1321 PredCases.push_back(BBCases[i]);
1322 ++NewSuccessors[BBCases[i].Dest];
1323 if (SuccHasWeights || PredHasWeights) {
1327 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1328 ValidTotalSuccWeight += SuccWeights[i + 1];
1332 if (SuccHasWeights || PredHasWeights) {
1333 ValidTotalSuccWeight += SuccWeights[0];
1335 for (
unsigned i = 1; i < CasesFromPred; ++i)
1336 Weights[i] *= ValidTotalSuccWeight;
1338 Weights[0] *= SuccWeights[0];
1344 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1345 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1346 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1347 if (PredCases[i].Dest == BB) {
1350 if (PredHasWeights || SuccHasWeights) {
1351 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1356 std::swap(PredCases[i], PredCases.back());
1357 PredCases.pop_back();
1364 for (
const ValueEqualityComparisonCase &Case : BBCases)
1365 if (PTIHandled.count(Case.Value)) {
1367 if (PredHasWeights || SuccHasWeights)
1368 Weights.
push_back(WeightsForHandled[Case.Value]);
1369 PredCases.push_back(Case);
1370 ++NewSuccessors[Case.Dest];
1371 PTIHandled.
erase(Case.Value);
1377 if (PredHasWeights || SuccHasWeights)
1379 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1380 ++NewSuccessors[BBDefault];
1392 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1394 for (
auto I :
seq(NewSuccessor.second)) {
1398 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1399 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1412 for (ValueEqualityComparisonCase &V : PredCases)
1415 if (PredHasWeights || SuccHasWeights) {
1432 if (!InfLoopBlock) {
1440 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1447 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1449 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1451 DTU->applyUpdates(Updates);
1454 ++NumFoldValueComparisonIntoPredecessors;
1462bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(
Instruction *TI,
1465 Value *CV = isValueEqualityComparison(TI);
1466 assert(CV &&
"Not a comparison?");
1468 bool Changed =
false;
1471 while (!Preds.empty()) {
1480 Value *PCV = isValueEqualityComparison(PTI);
1486 for (
auto *Succ : FailBlocks) {
1492 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1506 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1507 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1508 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1527 if (
I->mayReadFromMemory())
1531 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1548 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1558 if (
auto *CB = dyn_cast<CallBase>(
I))
1559 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1566 if (
auto *J = dyn_cast<Instruction>(
Op))
1567 if (J->getParent() == BB)
1586 auto *C1 = dyn_cast<CallInst>(I1);
1587 auto *C2 = dyn_cast<CallInst>(I2);
1589 if (C1->isMustTailCall() != C2->isMustTailCall())
1597 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1598 if (CB1->cannotMerge() || CB1->isConvergent())
1600 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1601 if (CB2->cannotMerge() || CB2->isConvergent())
1616 if (!I1->hasDbgRecords())
1618 using CurrentAndEndIt =
1619 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1625 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1626 return Pair.first == Pair.second;
1632 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1638 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1640 if (!
Other->hasDbgRecords())
1643 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1650 while (
none_of(Itrs, atEnd)) {
1651 bool HoistDVRs = allIdentical(Itrs);
1652 for (CurrentAndEndIt &Pair : Itrs) {
1666 if (I1->isIdenticalToWhenDefined(I2,
true))
1669 if (
auto *Cmp1 = dyn_cast<CmpInst>(I1))
1670 if (
auto *Cmp2 = dyn_cast<CmpInst>(I2))
1671 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1672 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1673 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1675 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1676 return I1->getOperand(0) == I2->
getOperand(1) &&
1747 Value *Mask =
nullptr;
1748 Value *MaskFalse =
nullptr;
1749 Value *MaskTrue =
nullptr;
1750 if (Invert.has_value()) {
1751 IRBuilder<> Builder(Sel ? Sel : SpeculatedConditionalLoadsStores.
back());
1761 auto PeekThroughBitcasts = [](
Value *V) {
1762 while (
auto *BitCast = dyn_cast<BitCastInst>(V))
1763 V = BitCast->getOperand(0);
1766 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1768 if (!Invert.has_value())
1769 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1774 auto *Op0 =
I->getOperand(0);
1775 CallInst *MaskedLoadStore =
nullptr;
1776 if (
auto *LI = dyn_cast<LoadInst>(
I)) {
1778 auto *Ty =
I->getType();
1780 Value *PassThru =
nullptr;
1781 if (Invert.has_value())
1782 for (
User *U :
I->users()) {
1783 if ((PN = dyn_cast<PHINode>(U))) {
1787 }
else if (
auto *Ins = cast<Instruction>(U);
1788 Sel && Ins->getParent() == BB) {
1801 I->replaceAllUsesWith(NewLoadStore);
1807 StoredVal,
I->getOperand(1), cast<StoreInst>(
I)->getAlign(), Mask);
1817 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1819 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1823 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1824 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1827 I->eraseFromParent();
1834 bool IsStore =
false;
1835 if (
auto *L = dyn_cast<LoadInst>(
I)) {
1838 }
else if (
auto *S = dyn_cast<StoreInst>(
I)) {
1857bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
Instruction *TI,
1858 bool AllInstsEqOnly) {
1878 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1882 if (isa<PHINode>(*SuccItr))
1884 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1887 if (AllInstsEqOnly) {
1896 return !
Term->isSameOperationAs(Term0) ||
1898 Succs[0]->size() != Succ->
size();
1904 while (LRI.isValid()) {
1921 unsigned NumSkipped = 0;
1924 if (SuccIterPairs.
size() > 2) {
1926 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1927 if (SuccIterPairs.
size() < 2)
1931 bool Changed =
false;
1934 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1935 auto &BB1ItrPair = *SuccIterPairBegin++;
1936 auto OtherSuccIterPairRange =
1942 bool AllInstsAreIdentical =
true;
1943 bool HasTerminator =
I1->isTerminator();
1944 for (
auto &SuccIter : OtherSuccIterRange) {
1949 AllInstsAreIdentical =
false;
1953 for (
auto &SuccIter : OtherSuccIterRange)
1958 if (HasTerminator) {
1962 if (NumSkipped || !AllInstsAreIdentical) {
1967 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1971 if (AllInstsAreIdentical) {
1972 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1973 AllInstsAreIdentical =
1975 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1977 unsigned SkipFlagsBB2 = Pair.second;
1987 if (AllInstsAreIdentical) {
1997 for (
auto &SuccIter : OtherSuccIterRange) {
2003 if (
auto *CB = dyn_cast<CallBase>(I1)) {
2004 bool Success = CB->tryIntersectAttributes(cast<CallBase>(I2));
2005 assert(
Success &&
"We should not be trying to hoist callbases "
2006 "with non-intersectable attributes");
2018 NumHoistCommonCode += SuccIterPairs.
size();
2020 NumHoistCommonInstrs += SuccIterPairs.
size();
2029 for (
auto &SuccIterPair : SuccIterPairs) {
2038bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2042 auto *BI = dyn_cast<BranchInst>(TI);
2044 bool Changed =
false;
2049 auto *I2 = *OtherSuccTIs.
begin();
2065 if (isa<CallBrInst>(I1))
2070 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2072 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2092 if (!
NT->getType()->isVoidTy()) {
2093 I1->replaceAllUsesWith(NT);
2095 OtherSuccTI->replaceAllUsesWith(NT);
2099 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2105 for (
auto *OtherSuccTI : OtherSuccTIs)
2106 Locs.
push_back(OtherSuccTI->getDebugLoc());
2118 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
2121 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2122 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2128 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2133 isa<FPMathOperator>(PN) ? &PN :
nullptr,
2138 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2139 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2140 PN.setIncomingValue(i, SI);
2151 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2156 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2160 DTU->applyUpdates(Updates);
2169 if (
I->isIntDivRem())
2171 return !isa<IntrinsicInst>(
I);
2184 std::optional<unsigned> NumUses;
2185 for (
auto *
I : Insts) {
2187 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
2188 I->getType()->isTokenTy())
2193 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2200 if (
const auto *
C = dyn_cast<CallBase>(
I))
2201 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2205 NumUses =
I->getNumUses();
2206 else if (NumUses !=
I->getNumUses())
2212 for (
auto *
I : Insts) {
2226 for (
const Use &U : I0->
uses()) {
2227 auto It = PHIOperands.find(&U);
2228 if (It == PHIOperands.end())
2231 if (!
equal(Insts, It->second))
2239 if (isa<CallBase>(I0)) {
2241 return cast<CallBase>(
I)->isIndirectCall();
2243 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2244 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2245 if (HaveIndirectCalls) {
2246 if (!AllCallsAreIndirect)
2250 Value *Callee =
nullptr;
2252 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2254 Callee = CurrCallee;
2255 else if (Callee != CurrCallee)
2261 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2267 if (!
all_of(Insts, SameAsI0)) {
2273 for (
auto *
I : Insts)
2274 Ops.push_back(
I->getOperand(OI));
2284 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2289 for (
auto *BB :
Blocks) {
2291 I =
I->getPrevNode();
2316 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2319 PN->insertBefore(BBEnd->begin());
2320 for (
auto *
I : Insts)
2321 PN->addIncoming(
I->getOperand(O),
I->getParent());
2330 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2333 for (
auto *
I : Insts)
2345 if (
auto *CB = dyn_cast<CallBase>(I0)) {
2346 bool Success = CB->tryIntersectAttributes(cast<CallBase>(
I));
2347 assert(
Success &&
"We should not be trying to sink callbases "
2348 "with non-intersectable attributes");
2358 auto *PN = cast<PHINode>(U);
2359 PN->replaceAllUsesWith(I0);
2360 PN->eraseFromParent();
2364 for (
auto *
I : Insts) {
2369 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2370 I->replaceAllUsesWith(I0);
2371 I->eraseFromParent();
2421 bool HaveNonUnconditionalPredecessors =
false;
2423 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2424 if (PredBr && PredBr->isUnconditional())
2427 HaveNonUnconditionalPredecessors =
true;
2429 if (UnconditionalPreds.
size() < 2)
2442 for (
const Use &U : PN.incoming_values())
2443 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2444 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2446 Ops.push_back(*IncomingVals[Pred]);
2454 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2467 if (!followedByDeoptOrUnreachable) {
2469 auto IsMemOperand = [](
Use &U) {
2470 auto *
I = cast<Instruction>(U.getUser());
2471 if (isa<LoadInst>(
I))
2473 if (isa<StoreInst>(
I))
2482 unsigned NumPHIInsts = 0;
2483 for (
Use &U : (*LRI)[0]->operands()) {
2484 auto It = PHIOperands.
find(&U);
2485 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2486 return InstructionsToSink.contains(V);
2493 if (IsMemOperand(U) &&
2494 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2501 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2502 return NumPHIInsts <= 1;
2519 while (
Idx < ScanIdx) {
2520 if (!ProfitableToSinkInstruction(LRI)) {
2523 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2536 if (
Idx < ScanIdx) {
2539 InstructionsToSink = InstructionsProfitableToSink;
2545 !ProfitableToSinkInstruction(LRI) &&
2546 "We already know that the last instruction is unprofitable to sink");
2554 for (
auto *
I : *LRI)
2555 InstructionsProfitableToSink.
erase(
I);
2556 if (!ProfitableToSinkInstruction(LRI)) {
2559 InstructionsToSink = InstructionsProfitableToSink;
2571 bool Changed =
false;
2573 if (HaveNonUnconditionalPredecessors) {
2574 if (!followedByDeoptOrUnreachable) {
2582 bool Profitable =
false;
2583 while (
Idx < ScanIdx) {
2617 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2619 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2627 NumSinkCommonInstrs++;
2631 ++NumSinkCommonCode;
2637struct CompatibleSets {
2655 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2660 return Sets.emplace_back();
2664 getCompatibleSet(
II).emplace_back(
II);
2668 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2672 return II->cannotMerge() ||
II->isInlineAsm();
2674 if (
any_of(Invokes, IsIllegalToMerge))
2679 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2680 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2681 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2682 if (HaveIndirectCalls) {
2683 if (!AllCallsAreIndirect)
2689 Value *CurrCallee =
II->getCalledOperand();
2690 assert(CurrCallee &&
"There is always a called operand.");
2693 else if (Callee != CurrCallee)
2701 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2703 if (
any_of(Invokes, HasNormalDest)) {
2706 if (!
all_of(Invokes, HasNormalDest))
2713 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2715 NormalBB = CurrNormalBB;
2716 else if (NormalBB != CurrNormalBB)
2724 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2735 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2737 UnwindBB = CurrUnwindBB;
2739 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2746 Invokes.front()->getUnwindDest(),
2747 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2753 for (
auto *
II : Invokes.drop_front())
2758 auto IsIllegalToMergeArguments = [](
auto Ops) {
2759 Use &U0 = std::get<0>(Ops);
2760 Use &U1 = std::get<1>(Ops);
2766 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2767 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2768 IsIllegalToMergeArguments))
2780 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2786 bool HasNormalDest =
2787 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2791 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2795 II0->
getParent()->getIterator()->getNextNode();
2800 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2802 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2804 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2806 if (!HasNormalDest) {
2810 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2818 return MergedInvoke;
2826 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2832 SuccBBOfMergedInvoke});
2839 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2842 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2845 for (
Use &U : MergedInvoke->operands()) {
2847 if (MergedInvoke->isCallee(&U)) {
2848 if (!IsIndirectCall)
2850 }
else if (!MergedInvoke->isDataOperand(&U))
2855 return II->getOperand(
U.getOperandNo()) !=
U.get();
2862 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2874 Invokes.front()->getParent());
2882 if (!MergedDebugLoc)
2883 MergedDebugLoc =
II->getDebugLoc();
2891 OrigSuccBB->removePredecessor(
II->getParent());
2896 bool Success = MergedInvoke->tryIntersectAttributes(
II);
2897 assert(
Success &&
"Merged invokes with incompatible attributes");
2900 II->replaceAllUsesWith(MergedInvoke);
2901 II->eraseFromParent();
2904 MergedInvoke->setDebugLoc(MergedDebugLoc);
2905 ++NumInvokeSetsFormed;
2908 DTU->applyUpdates(Updates);
2935 bool Changed =
false;
2941 CompatibleSets Grouper;
2947 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2951 if (Invokes.
size() < 2)
2963class EphemeralValueTracker {
2967 if (isa<AssumeInst>(
I))
2969 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2971 return EphValues.count(cast<Instruction>(U));
2977 if (isEphemeral(
I)) {
3016 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
3028 unsigned MaxNumInstToLookAt = 9;
3032 if (!MaxNumInstToLookAt)
3034 --MaxNumInstToLookAt;
3037 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
3040 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
3044 if (SI->getPointerOperand() == StorePtr &&
3045 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
3046 SI->getAlign() >= StoreToHoist->
getAlign())
3048 return SI->getValueOperand();
3052 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
3053 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3054 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3056 bool ExplicitlyDereferenceableOnly;
3060 CaptureComponents::Provenance)) &&
3061 (!ExplicitlyDereferenceableOnly ||
3063 LI->getDataLayout()))) {
3079 unsigned &SpeculatedInstructions,
3087 bool HaveRewritablePHIs =
false;
3106 HaveRewritablePHIs =
true;
3109 if (!OrigCE && !ThenCE)
3116 if (OrigCost + ThenCost > MaxCost)
3123 ++SpeculatedInstructions;
3124 if (SpeculatedInstructions > 1)
3128 return HaveRewritablePHIs;
3132 std::optional<bool> Invert,
3136 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3143 if (!Invert.has_value())
3146 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3150 return BIEndProb < Likely;
3190bool SimplifyCFGOpt::speculativelyExecuteBB(
BranchInst *BI,
3197 if (isa<FCmpInst>(BrCond))
3207 bool Invert =
false;
3226 unsigned SpeculatedInstructions = 0;
3227 bool HoistLoadsStores =
Options.HoistLoadsStoresWithCondFaulting;
3229 Value *SpeculatedStoreValue =
nullptr;
3231 EphemeralValueTracker EphTracker;
3236 if (isa<PseudoProbeInst>(
I)) {
3246 if (EphTracker.track(&
I))
3251 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3253 SpeculatedConditionalLoadsStores.
size() <
3257 if (IsSafeCheapLoadStore)
3258 SpeculatedConditionalLoadsStores.
push_back(&
I);
3260 ++SpeculatedInstructions;
3262 if (SpeculatedInstructions > 1)
3266 if (!IsSafeCheapLoadStore &&
3269 (SpeculatedStoreValue =
3272 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3278 if (!SpeculatedStore && SpeculatedStoreValue)
3279 SpeculatedStore = cast<StoreInst>(&
I);
3284 for (
Use &
Op :
I.operands()) {
3289 ++SinkCandidateUseCounts[OpI];
3296 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3297 if (Inst->hasNUses(Count)) {
3298 ++SpeculatedInstructions;
3299 if (SpeculatedInstructions > 1)
3306 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3309 SpeculatedInstructions,
Cost,
TTI);
3310 if (!Convert ||
Cost > Budget)
3314 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3318 if (SpeculatedStoreValue) {
3322 Value *FalseV = SpeculatedStoreValue;
3326 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3327 Sel = cast<Instruction>(S);
3359 DbgAssign->replaceVariableLocationOp(OrigV, S);
3369 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3372 I.dropUBImplyingAttrsAndMetadata();
3375 if (EphTracker.contains(&
I)) {
3377 I.eraseFromParent();
3383 for (
auto &It : *ThenBB)
3389 It.dropOneDbgRecord(&DR);
3391 std::prev(ThenBB->end()));
3393 if (!SpeculatedConditionalLoadsStores.
empty())
3412 Value *TrueV = ThenV, *FalseV = OrigV;
3422 I->eraseFromParent();
3435 if (!ReachesNonLocalUses.
insert(BB).second)
3450 EphemeralValueTracker EphTracker;
3456 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3457 if (CI->cannotDuplicate() || CI->isConvergent())
3463 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3470 for (
User *U :
I.users()) {
3473 if (UsedInBB == BB) {
3474 if (isa<PHINode>(UI))
3477 NonLocalUseBlocks.
insert(UsedInBB);
3490 auto *
I = dyn_cast<Instruction>(V);
3491 if (
I &&
I->getParent() == To)
3495 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3507static std::optional<bool>
3523 if (
auto *CB = dyn_cast<ConstantInt>(U))
3528 KnownValues[CB].
insert(Pred);
3532 if (KnownValues.
empty())
3557 if (!
findReaching(UseBB, BB, ReachesNonLocalUseBlocks))
3560 for (
const auto &Pair : KnownValues) {
3577 if (ReachesNonLocalUseBlocks.
contains(RealDest))
3582 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3585 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3593 EdgeBB->setName(RealDest->
getName() +
".critedge");
3594 EdgeBB->moveBefore(RealDest);
3604 TranslateMap[
Cond] = CB;
3610 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3617 N->insertInto(EdgeBB, InsertPt);
3620 N->setName(BBI->getName() +
".c");
3631 if (!BBI->use_empty())
3632 TranslateMap[&*BBI] = V;
3633 if (!
N->mayHaveSideEffects()) {
3634 N->eraseFromParent();
3639 if (!BBI->use_empty())
3640 TranslateMap[&*BBI] =
N;
3646 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3647 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3648 SrcDbgCursor = std::next(BBI);
3650 N->cloneDebugInfoFrom(&*BBI);
3653 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3659 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3660 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3661 InsertPt->cloneDebugInfoFrom(BI);
3664 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3670 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3671 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3682 return std::nullopt;
3688bool SimplifyCFGOpt::foldCondBranchOnValueKnownInPredecessor(
BranchInst *BI) {
3695 std::optional<bool>
Result;
3696 bool EverChanged =
false;
3702 }
while (Result == std::nullopt);
3711 bool SpeculateUnpredictables) {
3726 if (isa<ConstantInt>(IfCond))
3733 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3736 "Will have either one or two blocks to speculate.");
3743 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3744 if (!IsUnpredictable) {
3747 (TWeight + FWeight) != 0) {
3752 if (IfBlocks.
size() == 1) {
3754 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3755 if (BIBBProb >= Likely)
3758 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3766 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3767 if (IfCondPhiInst->getParent() == BB)
3775 unsigned NumPhis = 0;
3788 if (SpeculateUnpredictables && IsUnpredictable)
3791 bool Changed =
false;
3802 AggressiveInsts,
Cost, Budget,
TTI, AC,
3803 ZeroCostInstructions) ||
3805 AggressiveInsts,
Cost, Budget,
TTI, AC,
3806 ZeroCostInstructions))
3812 PN = dyn_cast<PHINode>(BB->
begin());
3818 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3829 auto IsBinOpOrAnd = [](
Value *V) {
3846 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3859 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3861 <<
" F: " << IfFalse->
getName() <<
"\n");
3879 isa<FPMathOperator>(PN) ? PN :
nullptr,
3883 PN->eraseFromParent();
3893 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3911 if (
Opc == Instruction::And)
3913 if (
Opc == Instruction::Or)
3926 bool PredHasWeights =
3928 bool SuccHasWeights =
3930 if (PredHasWeights || SuccHasWeights) {
3931 if (!PredHasWeights)
3932 PredTrueWeight = PredFalseWeight = 1;
3933 if (!SuccHasWeights)
3934 SuccTrueWeight = SuccFalseWeight = 1;
3944static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3948 "Both blocks must end with a conditional branches.");
3950 "PredBB must be a predecessor of BB.");
3958 (PTWeight + PFWeight) != 0) {
3966 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3967 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3971 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3974 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3975 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3981 return std::nullopt;
3994 bool InvertPredCond;
3995 std::tie(CommonSucc,
Opc, InvertPredCond) =
3998 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4005 {LLVMContext::MD_annotation});
4008 if (InvertPredCond) {
4021 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4023 SuccTrueWeight, SuccFalseWeight)) {
4030 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4036 (SuccFalseWeight + SuccTrueWeight) +
4037 PredTrueWeight * SuccFalseWeight);
4043 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4044 PredFalseWeight * SuccTrueWeight);
4046 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4064 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
4065 {DominatorTree::Delete, PredBlock, BB}});
4090 ++NumFoldBranchToCommonDest;
4097 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4098 return U->getType()->isVectorTy();
4108 unsigned BonusInstThreshold) {
4121 if (!
Cond || !isa<CmpInst, BinaryOperator, SelectInst, TruncInst>(
Cond) ||
4122 Cond->getParent() != BB || !
Cond->hasOneUse())
4132 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
4143 bool InvertPredCond;
4145 std::tie(CommonSucc,
Opc, InvertPredCond) = *Recipe;
4177 unsigned NumBonusInsts = 0;
4178 bool SawVectorOp =
false;
4179 const unsigned PredCount = Preds.
size();
4185 if (isa<BranchInst>(
I))
4196 NumBonusInsts += PredCount;
4204 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4205 auto *UI = cast<Instruction>(U.getUser());
4206 if (
auto *PN = dyn_cast<PHINode>(UI))
4208 return UI->
getParent() == BB &&
I.comesBefore(UI);
4212 if (!
all_of(
I.uses(), IsBCSSAUse))
4216 BonusInstThreshold *
4222 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4232 for (
auto *BB : {BB1, BB2}) {
4236 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4248 Value *AlternativeV =
nullptr) {
4266 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4267 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4268 PHI = cast<PHINode>(
I);
4274 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4275 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4283 if (!AlternativeV &&
4284 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4289 PHI->addIncoming(V, BB);
4299 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4308 if (!PStore || !QStore)
4329 if (
I.mayReadOrWriteMemory())
4331 for (
auto &
I : *QFB)
4332 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4335 for (
auto &
I : *QTB)
4336 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4340 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4356 if (
I.isTerminator())
4360 if (
auto *S = dyn_cast<StoreInst>(&
I))
4364 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4374 "When we run out of budget we will eagerly return from within the "
4375 "per-instruction loop.");
4379 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4381 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4382 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4418 InvertPCond ^= (PStore->
getParent() != PTB);
4419 InvertQCond ^= (QStore->
getParent() != QTB);
4490 bool InvertPCond =
false, InvertQCond =
false;
4496 if (QFB == PostBB) {
4515 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4518 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4526 for (
auto *BB : {PTB, PFB}) {
4531 PStoreAddresses.
insert(SI->getPointerOperand());
4533 for (
auto *BB : {QTB, QFB}) {
4538 QStoreAddresses.
insert(SI->getPointerOperand());
4544 auto &CommonAddresses = PStoreAddresses;
4546 bool Changed =
false;
4547 for (
auto *
Address : CommonAddresses)
4550 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4568 !BI->
getParent()->getSinglePredecessor())
4570 if (!IfFalseBB->
phis().empty())
4580 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4591 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4592 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4603 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4604 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4683 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4685 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4689 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4692 if (CommonDestProb >= Likely)
4702 unsigned NumPhis = 0;
4724 if (OtherDest == BB) {
4731 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4732 OtherDest = InfLoopBlock;
4752 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4767 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4768 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4771 SuccTrueWeight, SuccFalseWeight);
4773 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4774 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4775 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4776 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4780 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4781 PredOther * SuccCommon,
4782 PredOther * SuccOther};
4811 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4812 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4813 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4814 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4817 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4818 PredOther * SuccCommon};
4841bool SimplifyCFGOpt::simplifyTerminatorOnSelect(
Instruction *OldTerm,
4852 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4859 if (Succ == KeepEdge1)
4860 KeepEdge1 =
nullptr;
4861 else if (Succ == KeepEdge2)
4862 KeepEdge2 =
nullptr;
4867 if (Succ != TrueBB && Succ != FalseBB)
4868 RemovedSuccessors.
insert(Succ);
4876 if (!KeepEdge1 && !KeepEdge2) {
4877 if (TrueBB == FalseBB) {
4885 if (TrueWeight != FalseWeight)
4888 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4910 for (
auto *RemovedSuccessor : RemovedSuccessors)
4911 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4912 DTU->applyUpdates(Updates);
4922bool SimplifyCFGOpt::simplifySwitchOnSelect(
SwitchInst *SI,
4927 if (!TrueVal || !FalseVal)
4932 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4933 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4936 uint32_t TrueWeight = 0, FalseWeight = 0;
4941 if (Weights.
size() == 1 +
SI->getNumCases()) {
4943 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4945 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4950 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4959bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4972 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4993bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5013 if (
SI->getCondition() != V)
5019 if (
SI->getDefaultDest() != BB) {
5021 assert(VVal &&
"Should have a unique destination value");
5029 return requestResimplify();
5035 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5045 return requestResimplify();
5052 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5077 auto W0 = SIW.getSuccessorWeight(0);
5081 SIW.setSuccessorWeight(0, *NewW);
5083 SIW.addCase(Cst, NewBB, NewW);
5085 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5094 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5095 DTU->applyUpdates(Updates);
5103bool SimplifyCFGOpt::simplifyBranchOnICmpChain(
BranchInst *BI,
5115 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5118 Value *CompVal = ConstantCompare.CompValue;
5119 unsigned UsedICmps = ConstantCompare.UsedICmps;
5120 Value *ExtraCase = ConstantCompare.Extra;
5121 bool TrueWhenEqual = ConstantCompare.IsEq;
5138 if (ExtraCase && Values.
size() < 2)
5153 <<
" cases into SWITCH. BB is:\n"
5163 nullptr,
"switch.early.test");
5187 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5193 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5194 <<
"\nEXTRABB = " << *BB);
5202 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5210 New->addCase(Val, EdgeBB);
5216 PHINode *PN = cast<PHINode>(BBI);
5218 for (
unsigned i = 0, e = Values.size() - 1; i != e; ++i)
5225 DTU->applyUpdates(Updates);
5227 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5233 return simplifyCommonResume(RI);
5234 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHIIt()) &&
5237 return simplifySingleResume(RI);
5245 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5250 switch (IntrinsicID) {
5251 case Intrinsic::dbg_declare:
5252 case Intrinsic::dbg_value:
5253 case Intrinsic::dbg_label:
5254 case Intrinsic::lifetime_end:
5264bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5274 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5277 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5279 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5280 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5284 if (IncomingBB->getUniqueSuccessor() != BB)
5287 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHIIt());
5289 if (IncomingValue != LandingPad)
5293 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5294 TrivialUnwindBlocks.
insert(IncomingBB);
5298 if (TrivialUnwindBlocks.
empty())
5302 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5306 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5320 TrivialBB->getTerminator()->eraseFromParent();
5323 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5330 return !TrivialUnwindBlocks.empty();
5334bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5338 "Resume must unwind the exception that caused control to here");
5342 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5378 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5394 int Idx = DestPN.getBasicBlockIndex(BB);
5408 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5409 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5411 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5415 DestPN.addIncoming(
Incoming, Pred);
5442 std::vector<DominatorTree::UpdateType> Updates;
5446 if (UnwindDest ==
nullptr) {
5458 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5459 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5486 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5487 if (!SuccessorCleanupPad)
5496 SuccessorCleanupPad->eraseFromParent();
5525 bool Changed =
false;
5554 BBI->dropDbgRecords();
5558 BBI->eraseFromParent();
5564 if (&BB->
front() != UI)
5567 std::vector<DominatorTree::UpdateType> Updates;
5573 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5577 [BB](
auto *
Successor) { return Successor == BB; })) {
5585 "The destinations are guaranteed to be different here.");
5596 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5602 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5603 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5605 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5606 if (i->getCaseSuccessor() != BB) {
5611 i = SU.removeCase(i);
5616 if (DTU &&
SI->getDefaultDest() != BB)
5617 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5618 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5619 if (
II->getUnwindDest() == BB) {
5621 DTU->applyUpdates(Updates);
5625 if (!CI->doesNotThrow())
5626 CI->setDoesNotThrow();
5629 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5630 if (CSI->getUnwindDest() == BB) {
5632 DTU->applyUpdates(Updates);
5641 E = CSI->handler_end();
5644 CSI->removeHandler(
I);
5651 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5652 if (CSI->getNumHandlers() == 0) {
5653 if (CSI->hasUnwindDest()) {
5657 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5658 Updates.push_back({DominatorTree::Insert,
5659 PredecessorOfPredecessor,
5660 CSI->getUnwindDest()});
5661 Updates.push_back({DominatorTree::Delete,
5662 PredecessorOfPredecessor, Predecessor});
5665 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5669 DTU->applyUpdates(Updates);
5678 CSI->eraseFromParent();
5681 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5683 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5684 "Expected to always have an unwind to BB.");
5686 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5694 DTU->applyUpdates(Updates);
5709 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5710 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5718 bool RemoveOrigDefaultBlock =
true) {
5720 auto *BB = Switch->getParent();
5721 auto *OrigDefaultBlock = Switch->getDefaultDest();
5722 if (RemoveOrigDefaultBlock)
5723 OrigDefaultBlock->removePredecessor(BB);
5727 auto *UI =
new UnreachableInst(Switch->getContext(), NewDefaultBlock);
5729 Switch->setDefaultDest(&*NewDefaultBlock);
5732 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5733 if (RemoveOrigDefaultBlock &&
5735 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5743bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(
SwitchInst *SI,
5745 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5747 bool HasDefault = !
SI->defaultDestUnreachable();
5749 auto *BB =
SI->getParent();
5752 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5757 for (
auto Case :
SI->cases()) {
5761 if (Dest == DestA) {
5767 if (Dest == DestB) {
5777 "Single-destination switch should have been folded.");
5779 assert(DestB !=
SI->getDefaultDest());
5780 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5788 ContiguousCases = &CasesA;
5789 ContiguousDest = DestA;
5792 ContiguousCases = &CasesB;
5793 ContiguousDest = DestB;
5802 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5805 if (!
Offset->isNullValue())
5820 if (Weights.
size() == 1 +
SI->getNumCases()) {
5823 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5824 if (
SI->getSuccessor(
I) == ContiguousDest)
5825 TrueWeight += Weights[
I];
5827 FalseWeight += Weights[
I];
5829 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5838 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5839 unsigned PreviousEdges = ContiguousCases->
size();
5840 if (ContiguousDest ==
SI->getDefaultDest())
5842 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5843 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5845 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5846 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5847 if (OtherDest ==
SI->getDefaultDest())
5849 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5850 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5858 auto *UnreachableDefault =
SI->getDefaultDest();
5861 SI->eraseFromParent();
5863 if (!HasDefault && DTU)
5864 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5880 unsigned MaxSignificantBitsInCond =
5887 for (
const auto &Case : SI->cases()) {
5888 auto *
Successor = Case.getCaseSuccessor();
5895 const APInt &CaseVal = Case.getCaseValue()->getValue();
5898 DeadCases.
push_back(Case.getCaseValue());
5910 bool HasDefault = !SI->defaultDestUnreachable();
5911 const unsigned NumUnknownBits =
5914 if (HasDefault && DeadCases.
empty() &&
5915 NumUnknownBits < 64 ) {
5916 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5917 if (SI->getNumCases() == AllNumCases) {
5924 if (SI->getNumCases() == AllNumCases - 1) {
5925 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5932 for (
const auto &Case : SI->cases())
5933 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5935 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5944 if (DeadCases.
empty())
5950 assert(CaseI != SI->case_default() &&
5951 "Case was not found. Probably mistake in DeadCases forming.");
5953 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5958 std::vector<DominatorTree::UpdateType> Updates;
5959 for (
auto *
Successor : UniqueSuccessors)
5960 if (NumPerSuccessorCases[
Successor] == 0)
5961 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5981 if (!Branch || !Branch->isUnconditional())
5987 int Idx =
PHI.getBasicBlockIndex(BB);
5988 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5991 if (InValue != CaseValue)
6007 ForwardingNodesMap ForwardingNodes;
6009 bool Changed =
false;
6010 for (
const auto &Case : SI->cases()) {
6012 BasicBlock *CaseDest = Case.getCaseSuccessor();
6031 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6032 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6033 count(Phi.blocks(), SwitchBlock) == 1) {
6034 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
6042 ForwardingNodes[Phi].push_back(PhiIdx);
6045 for (
auto &ForwardingNode : ForwardingNodes) {
6046 PHINode *Phi = ForwardingNode.first;
6052 for (
int Index : Indexes)
6053 Phi->setIncomingValue(Index, SI->getCondition());
6063 if (
C->isThreadDependent())
6065 if (
C->isDLLImportDependent())
6068 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
6069 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
6070 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
6076 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
6092 if (
Constant *
C = dyn_cast<Constant>(V))
6108 if (
A->isAllOnesValue())
6110 if (
A->isNullValue())
6116 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
6141 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
6143 if (
I.isTerminator()) {
6145 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6148 CaseDest =
I.getSuccessor(0);
6155 for (
auto &
Use :
I.uses()) {
6158 if (
I->getParent() == CaseDest)
6161 if (Phi->getIncomingBlock(
Use) == CaseDest)
6174 *CommonDest = CaseDest;
6176 if (CaseDest != *CommonDest)
6181 int Idx =
PHI.getBasicBlockIndex(Pred);
6194 Res.push_back(std::make_pair(&
PHI, ConstVal));
6197 return Res.size() > 0;
6203 SwitchCaseResultVectorTy &UniqueResults,
6205 for (
auto &
I : UniqueResults) {
6206 if (
I.first == Result) {
6207 I.second.push_back(CaseVal);
6208 return I.second.size();
6211 UniqueResults.push_back(
6222 SwitchCaseResultVectorTy &UniqueResults,
6226 uintptr_t MaxUniqueResults) {
6227 for (
const auto &
I : SI->cases()) {
6241 const size_t NumCasesForResult =
6249 if (UniqueResults.size() > MaxUniqueResults)
6260 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6265 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6267 return DefaultResult || SI->defaultDestUnreachable();
6284 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6285 ResultVector[1].second.size() == 1) {
6286 ConstantInt *FirstCase = ResultVector[0].second[0];
6287 ConstantInt *SecondCase = ResultVector[1].second[0];
6288 Value *SelectValue = ResultVector[1].first;
6289 if (DefaultResult) {
6290 Value *ValueCompare =
6291 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6292 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6293 DefaultResult,
"switch.select");
6295 Value *ValueCompare =
6296 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6297 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6298 SelectValue,
"switch.select");
6302 if (ResultVector.size() == 1 && DefaultResult) {
6304 unsigned CaseCount = CaseValues.
size();
6317 for (
auto *Case : CaseValues) {
6318 if (Case->getValue().slt(MinCaseVal->
getValue()))
6320 AndMask &= Case->getValue();
6330 if (FreeBits ==
Log2_32(CaseCount)) {
6334 return Builder.
CreateSelect(Cmp, ResultVector[0].first,
6341 for (
auto *Case : CaseValues)
6342 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6348 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6352 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6357 if (CaseValues.
size() == 2) {
6359 "switch.selectcmp.case1");
6361 "switch.selectcmp.case2");
6362 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6363 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6376 std::vector<DominatorTree::UpdateType> Updates;
6382 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6387 PHI->removeIncomingValueIf(
6388 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6389 PHI->addIncoming(SelectValue, SelectBB);
6392 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6398 if (DTU && RemovedSuccessors.
insert(Succ).second)
6399 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6401 SI->eraseFromParent();
6416 SwitchCaseResultVectorTy UniqueResults;
6422 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6424 Value *SelectValue =
6436class SwitchLookupTable {
6487 bool LinearMapValWrapped =
false;
6495SwitchLookupTable::SwitchLookupTable(
6499 assert(Values.size() &&
"Can't build lookup table without values!");
6500 assert(TableSize >= Values.size() &&
"Can't fit values in table!");
6503 SingleValue = Values.begin()->second;
6509 for (
const auto &[CaseVal, CaseRes] : Values) {
6513 TableContents[
Idx] = CaseRes;
6515 if (SingleValue && !isa<PoisonValue>(CaseRes) && CaseRes != SingleValue)
6516 SingleValue = isa<PoisonValue>(SingleValue) ? CaseRes :
nullptr;
6520 if (Values.size() < TableSize) {
6522 "Need a default value to fill the lookup table holes.");
6525 if (!TableContents[
I])
6526 TableContents[
I] = DefaultValue;
6530 bool DefaultValueIsPoison = isa<PoisonValue>(DefaultValue);
6532 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6533 SingleValue =
nullptr;
6539 Kind = SingleValueKind;
6546 bool LinearMappingPossible =
true;
6551 bool NonMonotonic =
false;
6552 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6555 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6557 if (!ConstVal && isa<PoisonValue>(TableContents[
I])) {
6563 ConstVal = dyn_cast<ConstantInt>(Values[0].second);
6569 LinearMappingPossible =
false;
6574 APInt Dist = Val - PrevVal;
6577 }
else if (Dist != DistToPrev) {
6578 LinearMappingPossible =
false;
6586 if (LinearMappingPossible) {
6587 LinearOffset = cast<ConstantInt>(TableContents[0]);
6588 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6589 APInt M = LinearMultiplier->getValue();
6590 bool MayWrap =
true;
6591 if (
isIntN(
M.getBitWidth(), TableSize - 1))
6592 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6593 LinearMapValWrapped = NonMonotonic || MayWrap;
6594 Kind = LinearMapKind;
6601 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6603 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6605 TableInt <<=
IT->getBitWidth();
6607 if (!isa<UndefValue>(TableContents[
I - 1])) {
6608 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6609 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6612 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6613 BitMapElementTy =
IT;
6624 GlobalVariable::PrivateLinkage, Initializer,
6625 "switch.table." + FuncName);
6626 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6636 case SingleValueKind:
6638 case LinearMapKind: {
6641 false,
"switch.idx.cast");
6642 if (!LinearMultiplier->isOne())
6643 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6645 !LinearMapValWrapped);
6647 if (!LinearOffset->isZero())
6650 !LinearMapValWrapped);
6666 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6667 "switch.shiftamt",
true,
true);
6670 Value *DownShifted =
6671 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6673 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6676 Type *IndexTy =
DL.getIndexType(
Array->getType());
6677 auto *ArrayTy = cast<ArrayType>(
Array->getValueType());
6679 if (
Index->getType() != IndexTy) {
6680 unsigned OldBitWidth =
Index->getType()->getIntegerBitWidth();
6682 if (
auto *Zext = dyn_cast<ZExtInst>(Index))
6684 isUIntN(OldBitWidth - 1, ArrayTy->getNumElements() - 1));
6687 Value *GEPIndices[] = {ConstantInt::get(IndexTy, 0),
Index};
6690 return Builder.
CreateLoad(ArrayTy->getElementType(),
GEP,
"switch.load");
6696bool SwitchLookupTable::wouldFitInRegister(
const DataLayout &
DL,
6698 Type *ElementType) {
6699 auto *
IT = dyn_cast<IntegerType>(ElementType);
6706 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6708 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6717 auto *
IT = dyn_cast<IntegerType>(Ty);
6729 DL.fitsInLegalInteger(
IT->getBitWidth());
6741 return NumCases * 100 >= CaseRange * MinDensity;
6762 if (SI->getNumCases() > TableSize)
6765 bool AllTablesFitInRegister =
true;
6766 bool HasIllegalType =
false;
6767 for (
const auto &
I : ResultTypes) {
6768 Type *Ty =
I.second;
6774 AllTablesFitInRegister =
6775 AllTablesFitInRegister &&
6776 SwitchLookupTable::wouldFitInRegister(
DL, TableSize, Ty);
6781 if (HasIllegalType && !AllTablesFitInRegister)
6786 if (AllTablesFitInRegister)
6803 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6806 return all_of(ResultTypes, [&](
const auto &KV) {
6807 return SwitchLookupTable::wouldFitInRegister(
6836 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6858 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6863 for (
auto ValuePair : Values) {
6866 if (!CaseConst || CaseConst == DefaultConst ||
6867 (CaseConst != TrueConst && CaseConst != FalseConst))
6881 if (DefaultConst == FalseConst) {
6884 ++NumTableCmpReuses;
6887 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6888 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6891 ++NumTableCmpReuses;
6901 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6920 if (SI->getNumCases() < 3)
6925 assert(!SI->cases().empty());
6942 MinCaseVal = CaseVal;
6944 MaxCaseVal = CaseVal;
6949 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6960 It->second.push_back(std::make_pair(CaseVal,
Value));
6966 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6974 bool HasDefaultResults =
6976 DefaultResultsList,
DL,
TTI);
6978 for (
const auto &
I : DefaultResultsList) {
6981 DefaultResults[
PHI] = Result;
6985 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6987 if (UseSwitchConditionAsTableIndex)
6996 bool DefaultIsReachable = !SI->defaultDestUnreachable();
6998 bool TableHasHoles = (NumResults < TableSize);
7003 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7011 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7014 if (SI->getNumCases() < 4)
7016 if (!
DL.fitsInLegalInteger(TableSize))
7023 std::vector<DominatorTree::UpdateType> Updates;
7029 assert(MaxTableSize >= TableSize &&
7030 "It is impossible for a switch to have more entries than the max "
7031 "representable value of its input integer type's size.");
7036 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7042 if (UseSwitchConditionAsTableIndex) {
7043 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7044 TableIndex = SI->getCondition();
7046 TableIndexOffset = MinCaseVal;
7049 bool MayWrap =
true;
7050 if (!DefaultIsReachable) {
7055 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
7056 "switch.tableidx",
false,
7065 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
7073 return SwitchLookupTable::wouldFitInRegister(
7074 DL, UpperBound, KV.second );
7078 TableSize = std::max(UpperBound, TableSize);
7081 DefaultIsReachable =
false;
7085 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7086 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7089 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7094 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7096 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
7098 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7108 MaskBB->
setName(
"switch.hole_check");
7115 APInt MaskInt(TableSizePowOf2, 0);
7116 APInt One(TableSizePowOf2, 1);
7118 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7119 for (
const auto &Result : ResultList) {
7122 MaskInt |= One <<
Idx;
7124 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7132 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7135 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
7137 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
7138 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
7144 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7147 SI->getDefaultDest()->removePredecessor(BB,
7150 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
7154 const ResultListTy &ResultList = ResultLists[
PHI];
7156 Type *ResultType = ResultList.begin()->second->getType();
7162 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
7165 Value *Result = Table.buildLookup(TableIndex, Builder,
DL);
7169 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7172 for (
auto *
User :
PHI->users()) {
7177 PHI->addIncoming(Result, LookupBB);
7182 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
7186 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
7189 if (Succ == SI->getDefaultDest())
7192 if (DTU && RemovedSuccessors.
insert(Succ).second)
7193 Updates.push_back({DominatorTree::Delete, BB, Succ});
7195 SI->eraseFromParent();
7202 ++NumLookupTablesHoles;
7217 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
7218 if (CondTy->getIntegerBitWidth() > 64 ||
7219 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7223 if (SI->getNumCases() < 4)
7231 for (
const auto &
C : SI->cases())
7232 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7240 int64_t
Base = Values[0];
7241 for (
auto &V : Values)
7254 unsigned Shift = 64;
7255 for (
auto &V : Values)
7259 for (
auto &V : Values)
7260 V = (int64_t)((
uint64_t)V >> Shift);
7276 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7279 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7281 Ty, Intrinsic::fshl,
7282 {
Sub,
Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7283 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7285 for (
auto Case : SI->cases()) {
7286 auto *Orig = Case.getCaseValue();
7287 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7288 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty,
Sub.lshr(Shift))));
7306 Value *Condition = SI->getCondition();
7308 auto *CondTy = cast<IntegerType>(Condition->
getType());
7310 if (CondTy->getIntegerBitWidth() > 64 ||
7311 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7323 if (SI->getNumCases() < 4)
7329 if (!SI->defaultDestUnreachable())
7334 for (
const auto &Case : SI->cases()) {
7335 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7352 for (
auto &Case : SI->cases()) {
7353 auto *OrigValue = Case.getCaseValue();
7354 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7355 OrigValue->getValue().countr_zero()));
7362 SI->setCondition(ConditionTrailingZeros);
7371 auto *Cmp = dyn_cast<CmpIntrinsic>(SI->getCondition());
7372 if (!Cmp || !Cmp->hasOneUse())
7383 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7386 if (SI->getNumCases() == 2) {
7393 Succ = SI->getDefaultDest();
7394 SuccWeight = Weights[0];
7396 for (
auto &Case : SI->cases()) {
7397 std::optional<int64_t> Val =
7401 if (!Missing.erase(*Val))
7406 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7409 assert(Missing.size() == 1 &&
"Should have one case left");
7410 Res = *Missing.begin();
7411 }
else if (SI->getNumCases() == 3 && SI->defaultDestUnreachable()) {
7413 Unreachable = SI->getDefaultDest();
7415 for (
auto &Case : SI->cases()) {
7416 BasicBlock *NewSucc = Case.getCaseSuccessor();
7417 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7420 OtherSuccWeight += Weight;
7423 SuccWeight = Weight;
7424 }
else if (Succ == NewSucc) {
7430 for (
auto &Case : SI->cases()) {
7431 std::optional<int64_t> Val =
7433 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7435 if (Case.getCaseSuccessor() == Succ) {
7448 Pred = ICmpInst::ICMP_UGT;
7451 Pred = ICmpInst::ICMP_EQ;
7454 Pred = ICmpInst::ICMP_ULT;
7457 if (Cmp->isSigned())
7460 MDNode *NewWeights =
nullptr;
7462 NewWeights =
MDBuilder(SI->getContext())
7469 SI->getMetadata(LLVMContext::MD_unpredictable));
7473 SI->eraseFromParent();
7474 Cmp->eraseFromParent();
7475 if (DTU && Unreachable)
7476 DTU->
applyUpdates({{DominatorTree::Delete, BB, Unreachable}});
7507 "Only supporting unconditional branches for now");
7509 "Expected unconditional branches to have one successor");
7510 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7531 if (
LHS == EKey ||
RHS == EKey ||
LHS == TKey ||
RHS == TKey)
7544 BranchInst *ABI = cast<BranchInst>(
A->getTerminator());
7545 BranchInst *BBI = cast<BranchInst>(
B->getTerminator());
7547 "Only supporting unconditional branches for now");
7554 auto &PredIVs = (*
LHS->PhiPredIVs)[&Phi];
7555 if (PredIVs[
A] != PredIVs[
B])
7564bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *SI,
7578 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7583 if (BB->
size() != 1)
7593 if (!Seen.
insert(BB).second) {
7594 auto It = BBToSuccessorIndexes.
find(BB);
7595 if (It != BBToSuccessorIndexes.
end())
7596 It->second.emplace_back(
I);
7611 BBToSuccessorIndexes[BB].emplace_back(
I);
7619 PhiPredIVs.
try_emplace(Phi,
Phi->getNumIncomingValues()).first->second;
7620 for (
auto &
IV :
Phi->incoming_values())
7621 IVs.insert({
Phi->getIncomingBlock(
IV),
IV.get()});
7637 bool MadeChange =
false;
7638 for (
auto &SSW : Cases) {
7646 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7647 for (
unsigned Idx : Successors)
7648 SI->setSuccessor(
Idx, (*It)->Dest);
7662 if (isValueEqualityComparison(SI)) {
7666 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7667 return requestResimplify();
7671 if (simplifySwitchOnSelect(SI,
Select))
7672 return requestResimplify();
7677 if (foldValueComparisonIntoPredecessors(SI, Builder))
7678 return requestResimplify();
7684 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7685 return requestResimplify();
7689 return requestResimplify();
7692 return requestResimplify();
7695 return requestResimplify();
7698 return requestResimplify();
7705 if (
Options.ConvertSwitchToLookupTable &&
7707 return requestResimplify();
7710 return requestResimplify();
7713 return requestResimplify();
7716 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
7717 return requestResimplify();
7719 if (simplifyDuplicateSwitchArms(SI, DTU))
7720 return requestResimplify();
7727 bool Changed =
false;
7736 RemovedSuccs.
insert(Dest);
7746 std::vector<DominatorTree::UpdateType> Updates;
7748 for (
auto *RemovedSucc : RemovedSuccs)
7768 if (simplifyIndirectBrOnSelect(IBI, SI))
7769 return requestResimplify();
7801 if (isa<PHINode>(*Succ->
begin()))
7805 if (BB == OtherPred)
7816 std::vector<DominatorTree::UpdateType> Updates;
7823 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7824 "unexpected successor");
7825 II->setUnwindDest(OtherPred);
7850 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7851 : simplifyCondBranch(
Branch, Builder);
7854bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7866 bool NeedCanonicalLoop =
7877 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7880 if (
I->isTerminator() &&
7881 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7897 if (
Options.SpeculateBlocks &&
7900 return requestResimplify();
7908 if (!PPred || (PredPred && PredPred != PPred))
7945 if (!SuccBI || !SuccBI->isConditional())
7949 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7950 !isa<PHINode>(Succ1->
front()) && !isa<PHINode>(Succ2->
front());
7953 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
7979 bool HasWeight =
false;
7984 BBTWeight = BBFWeight = 1;
7989 BB1TWeight = BB1FWeight = 1;
7994 BB2TWeight = BB2FWeight = 1;
7996 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
7997 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8008 "Tautological conditional branch should have been eliminated already.");
8011 if (!
Options.SimplifyCondBranch ||
8016 if (isValueEqualityComparison(BI)) {
8021 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8022 return requestResimplify();
8028 if (foldValueComparisonIntoPredecessors(BI, Builder))
8029 return requestResimplify();
8032 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8033 return requestResimplify();
8038 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8051 return requestResimplify();
8057 if (
Options.SpeculateBlocks &&
8060 return requestResimplify();
8069 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8070 return requestResimplify();
8072 if (BI &&
Options.HoistLoadsStoresWithCondFaulting &&
8075 auto CanSpeculateConditionalLoadsStores = [&]() {
8078 if (
I.isTerminator()) {
8079 if (
I.getNumSuccessors() > 1)
8083 SpeculatedConditionalLoadsStores.
size() ==
8087 SpeculatedConditionalLoadsStores.
push_back(&
I);
8090 return !SpeculatedConditionalLoadsStores.
empty();
8093 if (CanSpeculateConditionalLoadsStores()) {
8095 std::nullopt,
nullptr);
8096 return requestResimplify();
8106 return requestResimplify();
8115 return requestResimplify();
8121 if (foldCondBranchOnValueKnownInPredecessor(BI))
8122 return requestResimplify();
8127 if (PBI != BI && PBI->isConditional())
8129 return requestResimplify();
8134 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
8135 if (PBI != BI && PBI->isConditional())
8137 return requestResimplify();
8141 return requestResimplify();
8148 assert(V->getType() ==
I->getType() &&
"Mismatched types");
8156 if (
C->isNullValue() || isa<UndefValue>(
C)) {
8160 auto *Use = cast<Instruction>(U.getUser());
8162 switch (Use->getOpcode()) {
8165 case Instruction::GetElementPtr:
8166 case Instruction::Ret:
8167 case Instruction::BitCast:
8168 case Instruction::Load:
8169 case Instruction::Store:
8170 case Instruction::Call:
8171 case Instruction::CallBr:
8172 case Instruction::Invoke:
8173 case Instruction::UDiv:
8174 case Instruction::URem:
8178 case Instruction::SDiv:
8179 case Instruction::SRem:
8183 if (FindUse ==
I->use_end())
8185 auto &
Use = *FindUse;
8190 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8191 User->comesBefore(
I))
8205 if (
GEP->getPointerOperand() ==
I) {
8208 if (
GEP->getType()->isVectorTy())
8216 if (!
GEP->hasAllZeroIndices() &&
8217 (!
GEP->isInBounds() ||
8219 GEP->getPointerAddressSpace())))
8220 PtrValueMayBeModified =
true;
8226 bool HasNoUndefAttr =
8227 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8229 if (isa<UndefValue>(
C) && HasNoUndefAttr)
8232 if (
C->isNullValue() && HasNoUndefAttr &&
8233 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8234 return !PtrValueMayBeModified;
8240 if (!LI->isVolatile())
8242 LI->getPointerAddressSpace());
8246 if (!SI->isVolatile())
8248 SI->getPointerAddressSpace())) &&
8249 SI->getPointerOperand() ==
I;
8252 if (
auto *Assume = dyn_cast<AssumeInst>(
User)) {
8254 if (
I == Assume->getArgOperand(0))
8258 if (
auto *CB = dyn_cast<CallBase>(
User)) {
8262 if (CB->getCalledOperand() ==
I)
8265 if (CB->isArgOperand(&
Use)) {
8266 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8268 if (isa<ConstantPointerNull>(
C) &&
8269 CB->paramHasNonNullAttr(ArgIdx,
false))
8270 return !PtrValueMayBeModified;
8272 if (isa<UndefValue>(
C) && CB->isPassingUndefUB(ArgIdx))
8289 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8318 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
8326 for (
const auto &Case : SI->cases())
8327 if (Case.getCaseSuccessor() == BB) {
8329 Case.setSuccessor(Unreachable);
8331 if (SI->getDefaultDest() == BB) {
8333 SI->setDefaultDest(Unreachable);
8347bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
8348 bool Changed =
false;
8372 return requestResimplify();
8393 if (
Options.SpeculateBlocks &&
8397 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
8400 Options.SpeculateUnpredictables))
8407 case Instruction::Br:
8408 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
8410 case Instruction::Resume:
8411 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
8413 case Instruction::CleanupRet:
8414 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
8416 case Instruction::Switch:
8417 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
8419 case Instruction::Unreachable:
8420 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
8422 case Instruction::IndirectBr:
8423 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
8431 bool Changed =
false;
8439 Changed |= simplifyOnce(BB);
8440 }
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
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 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 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 bool switchToLookupTable(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 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 bool shouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallDenseMap< PHINode *, Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
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 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 bool shouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallDenseMap< PHINode *, Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
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.
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
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.