92using namespace PatternMatch;
94#define DEBUG_TYPE "simplifycfg"
97 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
99 cl::desc(
"Temorary development switch used to gradually uplift SimplifyCFG "
100 "into preserving DomTree,"));
109 "Control the amount of phi node folding to perform (default = 2)"));
113 cl::desc(
"Control the maximal total instruction cost that we are willing "
114 "to speculatively execute to fold a 2-entry PHI node into a "
115 "select (default = 4)"));
119 cl::desc(
"Hoist common instructions up to the parent block"));
122 "simplifycfg-hoist-loads-stores-with-cond-faulting",
cl::Hidden,
124 cl::desc(
"Hoist loads/stores if the target supports "
125 "conditional faulting"));
129 cl::desc(
"Control the maximal conditonal load/store that we are willing "
130 "to speculatively execute to eliminate conditional branch "
136 cl::desc(
"Allow reordering across at most this many "
137 "instructions when hoisting"));
141 cl::desc(
"Sink common instructions down to the end block"));
145 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
149 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
150 "precede - hoist multiple conditional stores into a single "
151 "predicated store"));
155 cl::desc(
"When merging conditional stores, do so even if the resultant "
156 "basic blocks are unlikely to be if-converted as a result"));
160 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
165 cl::desc(
"Limit maximum recursion depth when calculating costs of "
166 "speculatively executed instructions"));
171 cl::desc(
"Max size of a block which is still considered "
172 "small enough to thread through"));
178 cl::desc(
"Maximum cost of combining conditions when "
179 "folding branches"));
182 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
184 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
185 "to fold branch to common destination when vector operations are "
190 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
194 cl::desc(
"Limit cases to analyze when converting a switch to select"));
196STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
198 "Number of switch instructions turned into linear mapping");
200 "Number of switch instructions turned into lookup tables");
202 NumLookupTablesHoles,
203 "Number of switch instructions turned into lookup tables (holes checked)");
204STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
206 "Number of value comparisons folded into predecessor basic blocks");
208 "Number of branches folded into predecessor basic block");
211 "Number of common instruction 'blocks' hoisted up to the begin block");
213 "Number of common instructions hoisted up to the begin block");
215 "Number of common instruction 'blocks' sunk down to the end block");
217 "Number of common instructions sunk down to the end block");
218STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
220 "Number of invokes with empty resume blocks simplified into calls");
221STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
222STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
229using SwitchCaseResultVectorTy =
238struct ValueEqualityComparisonCase {
245 bool operator<(ValueEqualityComparisonCase RHS)
const {
253class SimplifyCFGOpt {
263 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
264 bool simplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
267 bool performValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
270 bool foldValueComparisonIntoPredecessors(
Instruction *TI,
285 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
288 bool hoistCommonCodeFromSuccessors(
Instruction *TI,
bool AllInstsEqOnly);
289 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
306 :
TTI(
TTI), DTU(DTU),
DL(
DL), LoopHeaders(LoopHeaders), Options(Opts) {
308 "SimplifyCFG is not yet capable of maintaining validity of a "
309 "PostDomTree, so don't ask for it.");
316 bool requestResimplify() {
335 "Only for a pair of incoming blocks at the time!");
341 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
342 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
345 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
346 EquivalenceSet->contains(IV1))
369 if (!SI1Succs.
count(Succ))
375 FailBlocks->insert(Succ);
391 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
393 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
394 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
456 if (AggressiveInsts.
count(
I))
480 for (
Use &
Op :
I->operands())
494 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
495 DL.isNonIntegralPointerType(V->getType()))
500 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
503 if (isa<ConstantPointerNull>(V))
504 return ConstantInt::get(PtrTy, 0);
508 if (CE->getOpcode() == Instruction::IntToPtr)
509 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
514 return cast<ConstantInt>(
532struct ConstantComparesGatherer {
536 Value *CompValue =
nullptr;
539 Value *Extra =
nullptr;
545 unsigned UsedICmps = 0;
552 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
553 ConstantComparesGatherer &
554 operator=(
const ConstantComparesGatherer &) =
delete;
559 bool setValueOnce(
Value *NewVal) {
560 if (CompValue && CompValue != NewVal)
563 return (CompValue !=
nullptr);
577 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
588 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
632 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
634 if (!setValueOnce(RHSVal))
639 ConstantInt::get(
C->getContext(),
640 C->getValue() | Mask));
655 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
657 if (!setValueOnce(RHSVal))
661 Vals.
push_back(ConstantInt::get(
C->getContext(),
662 C->getValue() & ~Mask));
683 Value *CandidateVal =
I->getOperand(0);
686 CandidateVal = RHSVal;
701 if (!setValueOnce(CandidateVal))
706 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
717 void gather(
Value *V) {
728 while (!DFT.
empty()) {
736 if (Visited.
insert(Op1).second)
738 if (Visited.
insert(Op0).second)
745 if (matchInstruction(
I, isEQ))
769 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
770 Cond = dyn_cast<Instruction>(SI->getCondition());
771 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
772 if (BI->isConditional())
773 Cond = dyn_cast<Instruction>(BI->getCondition());
775 Cond = dyn_cast<Instruction>(IBI->getAddress());
787 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
790 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
791 CV =
SI->getCondition();
792 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
793 if (BI->isConditional() && BI->getCondition()->hasOneUse())
794 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
802 Value *
Ptr = PTII->getPointerOperand();
803 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
812BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
813 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
814 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
815 Cases.reserve(
SI->getNumCases());
816 for (
auto Case :
SI->cases())
817 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
818 Case.getCaseSuccessor()));
819 return SI->getDefaultDest();
825 Cases.push_back(ValueEqualityComparisonCase(
834 std::vector<ValueEqualityComparisonCase> &Cases) {
840 std::vector<ValueEqualityComparisonCase> &C2) {
841 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
844 if (V1->size() > V2->size())
849 if (V1->size() == 1) {
852 for (
const ValueEqualityComparisonCase &VECC : *V2)
853 if (TheVal == VECC.
Value)
860 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
861 while (i1 != e1 && i2 != e2) {
882 SI->setMetadata(LLVMContext::MD_prof,
N);
888 uint32_t FalseWeight,
bool IsExpected) {
889 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
893 if (TrueWeight || FalseWeight)
896 I->setMetadata(LLVMContext::MD_prof,
N);
904bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
910 Value *ThisVal = isValueEqualityComparison(TI);
911 assert(ThisVal &&
"This isn't a value comparison!!");
912 if (ThisVal != PredVal)
919 std::vector<ValueEqualityComparisonCase> PredCases;
921 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
925 std::vector<ValueEqualityComparisonCase> ThisCases;
926 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
938 if (isa<BranchInst>(TI)) {
941 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
947 ThisCases[0].Dest->removePredecessor(PredDef);
950 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
957 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
965 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
969 <<
"Through successor TI: " << *TI);
977 if (DeadCases.
count(i->getCaseValue())) {
986 std::vector<DominatorTree::UpdateType> Updates;
987 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
989 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
990 DTU->applyUpdates(Updates);
1001 for (
const auto &[
Value, Dest] : PredCases)
1007 assert(TIV &&
"No edge from pred to succ?");
1012 for (
const auto &[
Value, Dest] : ThisCases)
1020 TheRealDest = ThisDef;
1027 if (Succ != CheckEdge) {
1028 if (Succ != TheRealDest)
1029 RemovedSuccs.
insert(Succ);
1032 CheckEdge =
nullptr;
1039 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1046 for (
auto *RemovedSucc : RemovedSuccs)
1047 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1048 DTU->applyUpdates(Updates);
1058struct ConstantIntOrdering {
1060 return LHS->getValue().ult(
RHS->getValue());
1072 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1081 assert(MD &&
"Invalid branch-weight metadata");
1087 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1098 if (Max > UINT_MAX) {
1113 if (BonusInst.isTerminator())
1118 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1142 if (isa<DbgInfoIntrinsic>(BonusInst))
1145 NewBonusInst->
takeName(&BonusInst);
1146 BonusInst.setName(NewBonusInst->
getName() +
".old");
1147 VMap[&BonusInst] = NewBonusInst;
1153 auto *UI = cast<Instruction>(U.getUser());
1154 auto *PN = dyn_cast<PHINode>(UI);
1156 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1157 "If the user is not a PHI node, then it should be in the same "
1158 "block as, and come after, the original bonus instruction.");
1162 if (PN->getIncomingBlock(U) == BB)
1166 assert(PN->getIncomingBlock(U) == PredBlock &&
1167 "Not in block-closed SSA form?");
1168 U.set(NewBonusInst);
1173bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1181 std::vector<ValueEqualityComparisonCase> BBCases;
1182 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1184 std::vector<ValueEqualityComparisonCase> PredCases;
1185 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1197 if (PredHasWeights) {
1200 if (Weights.
size() != 1 + PredCases.size())
1201 PredHasWeights = SuccHasWeights =
false;
1202 }
else if (SuccHasWeights)
1206 Weights.
assign(1 + PredCases.size(), 1);
1209 if (SuccHasWeights) {
1212 if (SuccWeights.
size() != 1 + BBCases.size())
1213 PredHasWeights = SuccHasWeights =
false;
1214 }
else if (PredHasWeights)
1215 SuccWeights.
assign(1 + BBCases.size(), 1);
1217 if (PredDefault == BB) {
1220 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1221 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1222 if (PredCases[i].Dest != BB)
1223 PTIHandled.insert(PredCases[i].
Value);
1226 std::swap(PredCases[i], PredCases.back());
1228 if (PredHasWeights || SuccHasWeights) {
1230 Weights[0] += Weights[i + 1];
1235 PredCases.pop_back();
1241 if (PredDefault != BBDefault) {
1243 if (DTU && PredDefault != BB)
1244 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1245 PredDefault = BBDefault;
1246 ++NewSuccessors[BBDefault];
1249 unsigned CasesFromPred = Weights.
size();
1251 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1252 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1253 PredCases.push_back(BBCases[i]);
1254 ++NewSuccessors[BBCases[i].Dest];
1255 if (SuccHasWeights || PredHasWeights) {
1259 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1260 ValidTotalSuccWeight += SuccWeights[i + 1];
1264 if (SuccHasWeights || PredHasWeights) {
1265 ValidTotalSuccWeight += SuccWeights[0];
1267 for (
unsigned i = 1; i < CasesFromPred; ++i)
1268 Weights[i] *= ValidTotalSuccWeight;
1270 Weights[0] *= SuccWeights[0];
1276 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1277 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1278 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1279 if (PredCases[i].Dest == BB) {
1282 if (PredHasWeights || SuccHasWeights) {
1283 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1288 std::swap(PredCases[i], PredCases.back());
1289 PredCases.pop_back();
1296 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1297 if (PTIHandled.count(BBCases[i].Value)) {
1299 if (PredHasWeights || SuccHasWeights)
1301 PredCases.push_back(BBCases[i]);
1302 ++NewSuccessors[BBCases[i].Dest];
1309 if (PredHasWeights || SuccHasWeights)
1311 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1312 ++NewSuccessors[BBDefault];
1324 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1326 for (
auto I :
seq(NewSuccessor.second)) {
1330 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1331 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1344 for (ValueEqualityComparisonCase &V : PredCases)
1347 if (PredHasWeights || SuccHasWeights) {
1364 if (!InfLoopBlock) {
1372 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1379 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1381 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1383 DTU->applyUpdates(Updates);
1386 ++NumFoldValueComparisonIntoPredecessors;
1394bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(
Instruction *TI,
1397 Value *CV = isValueEqualityComparison(TI);
1398 assert(CV &&
"Not a comparison?");
1400 bool Changed =
false;
1403 while (!Preds.empty()) {
1412 Value *PCV = isValueEqualityComparison(PTI);
1418 for (
auto *Succ : FailBlocks) {
1424 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1438 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1439 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1440 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1459 if (
I->mayReadFromMemory())
1463 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1480 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1490 if (
auto *CB = dyn_cast<CallBase>(
I))
1491 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1498 if (
auto *J = dyn_cast<Instruction>(
Op))
1499 if (J->getParent() == BB)
1518 auto *C1 = dyn_cast<CallInst>(I1);
1519 auto *C2 = dyn_cast<CallInst>(I2);
1521 if (C1->isMustTailCall() != C2->isMustTailCall())
1529 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1530 if (CB1->cannotMerge() || CB1->isConvergent())
1532 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1533 if (CB2->cannotMerge() || CB2->isConvergent())
1548 if (!I1->hasDbgRecords())
1550 using CurrentAndEndIt =
1551 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1557 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1558 return Pair.first == Pair.second;
1564 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1570 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1572 if (!
Other->hasDbgRecords())
1575 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1582 while (
none_of(Itrs, atEnd)) {
1583 bool HoistDVRs = allIdentical(Itrs);
1584 for (CurrentAndEndIt &Pair : Itrs) {
1598 if (I1->isIdenticalToWhenDefined(I2,
true))
1601 if (
auto *Cmp1 = dyn_cast<CmpInst>(I1))
1602 if (
auto *Cmp2 = dyn_cast<CmpInst>(I2))
1603 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1604 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1605 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1607 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1608 return I1->getOperand(0) == I2->
getOperand(1) &&
1673 std::optional<bool> Invert) {
1674 auto &Context = BI->
getParent()->getContext();
1680 Invert.has_value() ? SpeculatedConditionalLoadsStores.
back() : BI);
1681 Value *Mask =
nullptr;
1682 Value *MaskFalse =
nullptr;
1683 Value *MaskTrue =
nullptr;
1684 if (Invert.has_value()) {
1693 auto PeekThroughBitcasts = [](
Value *V) {
1694 while (
auto *BitCast = dyn_cast<BitCastInst>(V))
1695 V = BitCast->getOperand(0);
1698 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1700 if (!Invert.has_value())
1701 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1706 auto *Op0 =
I->getOperand(0);
1707 CallInst *MaskedLoadStore =
nullptr;
1708 if (
auto *LI = dyn_cast<LoadInst>(
I)) {
1710 auto *Ty =
I->getType();
1712 Value *PassThru =
nullptr;
1713 if (Invert.has_value())
1714 for (
User *U :
I->users())
1715 if ((PN = dyn_cast<PHINode>(U))) {
1726 I->replaceAllUsesWith(NewLoadStore);
1732 StoredVal,
I->getOperand(1), cast<StoreInst>(
I)->getAlign(), Mask);
1742 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1744 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1748 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1749 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1752 I->eraseFromParent();
1759 if (
auto *L = dyn_cast<LoadInst>(
I)) {
1762 }
else if (
auto *S = dyn_cast<StoreInst>(
I)) {
1785class LockstepReverseIterator {
1798 for (
auto *BB : Blocks) {
1800 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1816 for (
auto *&Inst : Insts) {
1817 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1830 for (
auto *&Inst : Insts) {
1831 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1851bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
Instruction *TI,
1852 bool AllInstsEqOnly) {
1872 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1876 if (isa<PHINode>(*SuccItr))
1878 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1881 if (AllInstsEqOnly) {
1890 return !
Term->isSameOperationAs(Term0) ||
1892 Succs[0]->size() != Succ->
size();
1897 LockstepReverseIterator LRI(Succs);
1898 while (LRI.isValid()) {
1915 unsigned NumSkipped = 0;
1918 if (SuccIterPairs.
size() > 2) {
1920 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1921 if (SuccIterPairs.
size() < 2)
1925 bool Changed =
false;
1928 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1929 auto &BB1ItrPair = *SuccIterPairBegin++;
1930 auto OtherSuccIterPairRange =
1937 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1939 return I1->isIdenticalToWhenDefined(I2);
1941 if (!AllDbgInstsAreIdentical) {
1942 while (isa<DbgInfoIntrinsic>(I1))
1943 I1 = &*++BB1ItrPair.first;
1944 for (
auto &SuccIter : OtherSuccIterRange) {
1946 while (isa<DbgInfoIntrinsic>(I2))
1951 bool AllInstsAreIdentical =
true;
1952 bool HasTerminator =
I1->isTerminator();
1953 for (
auto &SuccIter : OtherSuccIterRange) {
1958 AllInstsAreIdentical =
false;
1962 for (
auto &SuccIter : OtherSuccIterRange)
1967 if (HasTerminator) {
1971 if (NumSkipped || !AllInstsAreIdentical) {
1976 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1980 if (AllInstsAreIdentical) {
1981 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1982 AllInstsAreIdentical =
1984 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1986 unsigned SkipFlagsBB2 = Pair.second;
1996 if (AllInstsAreIdentical) {
1998 if (isa<DbgInfoIntrinsic>(I1)) {
2007 for (
auto &SuccIter : OtherSuccIterRange) {
2008 auto *I2 = &*SuccIter++;
2009 assert(isa<DbgInfoIntrinsic>(I2));
2021 for (
auto &SuccIter : OtherSuccIterRange) {
2027 if (
auto *CB = dyn_cast<CallBase>(I1)) {
2028 bool Success = CB->tryIntersectAttributes(cast<CallBase>(I2));
2029 assert(
Success &&
"We should not be trying to hoist callbases "
2030 "with non-intersectable attributes");
2043 NumHoistCommonCode += SuccIterPairs.
size();
2045 NumHoistCommonInstrs += SuccIterPairs.
size();
2054 for (
auto &SuccIterPair : SuccIterPairs) {
2063bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2067 auto *BI = dyn_cast<BranchInst>(TI);
2069 bool Changed =
false;
2074 auto *I2 = *OtherSuccTIs.
begin();
2090 if (isa<CallBrInst>(I1))
2095 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2097 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2117 if (!
NT->getType()->isVoidTy()) {
2118 I1->replaceAllUsesWith(NT);
2120 OtherSuccTI->replaceAllUsesWith(NT);
2124 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2130 for (
auto *OtherSuccTI : OtherSuccTIs)
2131 Locs.
push_back(OtherSuccTI->getDebugLoc());
2143 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
2146 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2147 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2153 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2157 if (isa<FPMathOperator>(PN))
2166 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2167 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2168 PN.setIncomingValue(i, SI);
2179 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2184 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2188 DTU->applyUpdates(Updates);
2194 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
2195 switch (
II->getIntrinsicID()) {
2198 case Intrinsic::lifetime_start:
2199 case Intrinsic::lifetime_end:
2211 if (
I->isIntDivRem())
2213 return !isa<IntrinsicInst>(
I);
2226 std::optional<unsigned> NumUses;
2227 for (
auto *
I : Insts) {
2229 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
2230 I->getType()->isTokenTy())
2235 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2242 if (
const auto *
C = dyn_cast<CallBase>(
I))
2243 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2247 NumUses =
I->getNumUses();
2248 else if (NumUses !=
I->getNumUses())
2254 for (
auto *
I : Insts) {
2261 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
2263 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
2276 for (
const Use &U : I0->
uses()) {
2277 auto It = PHIOperands.find(&U);
2278 if (It == PHIOperands.end())
2281 if (!
equal(Insts, It->second))
2289 if (isa<CallBase>(I0)) {
2291 return cast<CallBase>(
I)->isIndirectCall();
2293 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2294 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2295 if (HaveIndirectCalls) {
2296 if (!AllCallsAreIndirect)
2300 Value *Callee =
nullptr;
2302 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2304 Callee = CurrCallee;
2305 else if (Callee != CurrCallee)
2311 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2313 if (
Op->getType()->isTokenTy())
2321 if (!
all_of(Insts, SameAsI0)) {
2328 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2337 for (
auto *
I : Insts)
2338 Ops.push_back(
I->getOperand(OI));
2348 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2353 for (
auto *BB :
Blocks) {
2356 I =
I->getPrevNode();
2357 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2358 if (!isa<DbgInfoIntrinsic>(
I))
2383 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2386 PN->insertBefore(BBEnd->begin());
2387 for (
auto *
I : Insts)
2388 PN->addIncoming(
I->getOperand(O),
I->getParent());
2397 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2400 for (
auto *
I : Insts)
2412 if (
auto *CB = dyn_cast<CallBase>(I0)) {
2413 bool Success = CB->tryIntersectAttributes(cast<CallBase>(
I));
2414 assert(
Success &&
"We should not be trying to sink callbases "
2415 "with non-intersectable attributes");
2425 auto *PN = cast<PHINode>(U);
2426 PN->replaceAllUsesWith(I0);
2427 PN->eraseFromParent();
2431 for (
auto *
I : Insts) {
2436 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2437 I->replaceAllUsesWith(I0);
2438 I->eraseFromParent();
2488 bool HaveNonUnconditionalPredecessors =
false;
2490 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2491 if (PredBr && PredBr->isUnconditional())
2494 HaveNonUnconditionalPredecessors =
true;
2496 if (UnconditionalPreds.
size() < 2)
2509 for (
const Use &U : PN.incoming_values())
2510 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2511 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2513 Ops.push_back(*IncomingVals[Pred]);
2518 LockstepReverseIterator LRI(UnconditionalPreds);
2519 while (LRI.isValid() &&
2521 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2523 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2534 if (!followedByDeoptOrUnreachable) {
2536 auto IsMemOperand = [](
Use &U) {
2537 auto *
I = cast<Instruction>(U.getUser());
2538 if (isa<LoadInst>(
I))
2540 if (isa<StoreInst>(
I))
2548 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2549 unsigned NumPHIInsts = 0;
2550 for (
Use &U : (*LRI)[0]->operands()) {
2551 auto It = PHIOperands.
find(&U);
2552 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2553 return InstructionsToSink.contains(V);
2560 if (IsMemOperand(U) &&
2561 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2568 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2569 return NumPHIInsts <= 1;
2586 while (
Idx < ScanIdx) {
2587 if (!ProfitableToSinkInstruction(LRI)) {
2590 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2593 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2603 if (
Idx < ScanIdx) {
2606 InstructionsToSink = InstructionsProfitableToSink;
2612 !ProfitableToSinkInstruction(LRI) &&
2613 "We already know that the last instruction is unprofitable to sink");
2621 for (
auto *
I : *LRI)
2622 InstructionsProfitableToSink.
erase(
I);
2623 if (!ProfitableToSinkInstruction(LRI)) {
2626 InstructionsToSink = InstructionsProfitableToSink;
2638 bool Changed =
false;
2640 if (HaveNonUnconditionalPredecessors) {
2641 if (!followedByDeoptOrUnreachable) {
2649 bool Profitable =
false;
2650 while (
Idx < ScanIdx) {
2684 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2686 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2694 NumSinkCommonInstrs++;
2698 ++NumSinkCommonCode;
2704struct CompatibleSets {
2722 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2727 return Sets.emplace_back();
2731 getCompatibleSet(
II).emplace_back(
II);
2735 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2739 return II->cannotMerge() ||
II->isInlineAsm();
2741 if (
any_of(Invokes, IsIllegalToMerge))
2746 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2747 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2748 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2749 if (HaveIndirectCalls) {
2750 if (!AllCallsAreIndirect)
2756 Value *CurrCallee =
II->getCalledOperand();
2757 assert(CurrCallee &&
"There is always a called operand.");
2760 else if (Callee != CurrCallee)
2768 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2770 if (
any_of(Invokes, HasNormalDest)) {
2773 if (!
all_of(Invokes, HasNormalDest))
2780 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2782 NormalBB = CurrNormalBB;
2783 else if (NormalBB != CurrNormalBB)
2791 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2802 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2804 UnwindBB = CurrUnwindBB;
2806 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2813 Invokes.front()->getUnwindDest(),
2814 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2820 for (
auto *
II : Invokes.drop_front())
2825 auto IsIllegalToMergeArguments = [](
auto Ops) {
2826 Use &U0 = std::get<0>(Ops);
2827 Use &U1 = std::get<1>(Ops);
2834 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2835 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2836 IsIllegalToMergeArguments))
2848 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2854 bool HasNormalDest =
2855 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2859 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2863 II0->
getParent()->getIterator()->getNextNode();
2868 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2870 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2872 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2874 if (!HasNormalDest) {
2878 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2885 return MergedInvoke;
2893 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2899 SuccBBOfMergedInvoke});
2906 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2909 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2912 for (
Use &U : MergedInvoke->operands()) {
2914 if (MergedInvoke->isCallee(&U)) {
2915 if (!IsIndirectCall)
2917 }
else if (!MergedInvoke->isDataOperand(&U))
2922 return II->getOperand(
U.getOperandNo()) !=
U.get();
2929 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2941 Invokes.front()->getParent());
2949 if (!MergedDebugLoc)
2950 MergedDebugLoc =
II->getDebugLoc();
2958 OrigSuccBB->removePredecessor(
II->getParent());
2963 bool Success = MergedInvoke->tryIntersectAttributes(
II);
2964 assert(
Success &&
"Merged invokes with incompatible attributes");
2967 II->replaceAllUsesWith(MergedInvoke);
2968 II->eraseFromParent();
2971 MergedInvoke->setDebugLoc(MergedDebugLoc);
2972 ++NumInvokeSetsFormed;
2975 DTU->applyUpdates(Updates);
3002 bool Changed =
false;
3008 CompatibleSets Grouper;
3014 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
3018 if (Invokes.
size() < 2)
3030class EphemeralValueTracker {
3034 if (isa<AssumeInst>(
I))
3036 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3038 return EphValues.count(cast<Instruction>(U));
3044 if (isEphemeral(
I)) {
3083 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
3095 unsigned MaxNumInstToLookAt = 9;
3099 if (!MaxNumInstToLookAt)
3101 --MaxNumInstToLookAt;
3104 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
3107 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
3111 if (SI->getPointerOperand() == StorePtr &&
3112 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
3113 SI->getAlign() >= StoreToHoist->
getAlign())
3115 return SI->getValueOperand();
3119 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
3120 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3121 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3123 bool ExplicitlyDereferenceableOnly;
3127 (!ExplicitlyDereferenceableOnly ||
3129 LI->getDataLayout()))) {
3145 unsigned &SpeculatedInstructions,
3153 bool HaveRewritablePHIs =
false;
3171 HaveRewritablePHIs =
true;
3174 if (!OrigCE && !ThenCE)
3181 if (OrigCost + ThenCost > MaxCost)
3188 ++SpeculatedInstructions;
3189 if (SpeculatedInstructions > 1)
3193 return HaveRewritablePHIs;
3197 std::optional<bool> Invert,
3201 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3208 if (!Invert.has_value())
3211 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3215 return BIEndProb < Likely;
3255bool SimplifyCFGOpt::speculativelyExecuteBB(
BranchInst *BI,
3262 if (isa<FCmpInst>(BrCond))
3272 bool Invert =
false;
3291 unsigned SpeculatedInstructions = 0;
3293 Options.HoistLoadsStoresWithCondFaulting;
3295 Value *SpeculatedStoreValue =
nullptr;
3297 EphemeralValueTracker EphTracker;
3300 if (isa<DbgInfoIntrinsic>(
I)) {
3308 if (isa<PseudoProbeInst>(
I)) {
3318 if (EphTracker.track(&
I))
3323 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3325 SpeculatedConditionalLoadsStores.
size() <
3329 if (IsSafeCheapLoadStore)
3330 SpeculatedConditionalLoadsStores.
push_back(&
I);
3332 ++SpeculatedInstructions;
3334 if (SpeculatedInstructions > 1)
3338 if (!IsSafeCheapLoadStore &&
3341 (SpeculatedStoreValue =
3344 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3350 if (!SpeculatedStore && SpeculatedStoreValue)
3351 SpeculatedStore = cast<StoreInst>(&
I);
3356 for (
Use &
Op :
I.operands()) {
3361 ++SinkCandidateUseCounts[OpI];
3368 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3370 ++SpeculatedInstructions;
3371 if (SpeculatedInstructions > 1)
3378 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3381 SpeculatedInstructions,
Cost,
TTI);
3382 if (!Convert ||
Cost > Budget)
3386 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3389 if (SpeculatedStoreValue) {
3393 Value *FalseV = SpeculatedStoreValue;
3397 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3426 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3428 DbgAssign->replaceVariableLocationOp(OrigV, S);
3441 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3443 if (!isa<DbgAssignIntrinsic>(&
I))
3446 I.dropUBImplyingAttrsAndMetadata();
3449 if (EphTracker.contains(&
I)) {
3451 I.eraseFromParent();
3465 It.dropOneDbgRecord(&DR);
3467 std::prev(ThenBB->
end()));
3469 if (!SpeculatedConditionalLoadsStores.
empty())
3487 Value *TrueV = ThenV, *FalseV = OrigV;
3501 if (!isa<DbgAssignIntrinsic>(
I))
3502 I->eraseFromParent();
3512 EphemeralValueTracker EphTracker;
3518 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3519 if (CI->cannotDuplicate() || CI->isConvergent())
3525 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3532 for (
User *U :
I.users()) {
3534 if (UI->
getParent() != BB || isa<PHINode>(UI))
3548 auto *
I = dyn_cast<Instruction>(V);
3549 if (
I &&
I->getParent() == To)
3553 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3565static std::optional<bool>
3581 if (
auto *CB = dyn_cast<ConstantInt>(U))
3586 KnownValues[CB].
insert(Pred);
3590 if (KnownValues.
empty())
3599 for (
const auto &Pair : KnownValues) {
3617 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3620 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3628 EdgeBB->setName(RealDest->
getName() +
".critedge");
3629 EdgeBB->moveBefore(RealDest);
3639 TranslateMap[
Cond] = CB;
3645 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3652 N->insertInto(EdgeBB, InsertPt);
3655 N->setName(BBI->getName() +
".c");
3658 for (
Use &
Op :
N->operands()) {
3660 if (PI != TranslateMap.
end())
3666 if (!BBI->use_empty())
3667 TranslateMap[&*BBI] = V;
3668 if (!
N->mayHaveSideEffects()) {
3669 N->eraseFromParent();
3674 if (!BBI->use_empty())
3675 TranslateMap[&*BBI] =
N;
3681 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3682 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3683 SrcDbgCursor = std::next(BBI);
3685 N->cloneDebugInfoFrom(&*BBI);
3688 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3694 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3695 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3696 InsertPt->cloneDebugInfoFrom(BI);
3699 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3705 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3706 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3717 return std::nullopt;
3727 std::optional<bool> Result;
3728 bool EverChanged =
false;
3732 EverChanged |= Result == std::nullopt || *Result;
3733 }
while (Result == std::nullopt);
3742 bool SpeculateUnpredictables) {
3757 if (isa<ConstantInt>(IfCond))
3764 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3767 "Will have either one or two blocks to speculate.");
3774 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3775 if (!IsUnpredictable) {
3778 (TWeight + FWeight) != 0) {
3783 if (IfBlocks.
size() == 1) {
3785 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3786 if (BIBBProb >= Likely)
3789 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3797 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3798 if (IfCondPhiInst->getParent() == BB)
3806 unsigned NumPhis = 0;
3818 if (SpeculateUnpredictables && IsUnpredictable)
3821 bool Changed =
false;
3832 AggressiveInsts,
Cost, Budget,
TTI, AC) ||
3834 AggressiveInsts,
Cost, Budget,
TTI, AC))
3840 PN = dyn_cast<PHINode>(BB->
begin());
3846 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3857 auto IsBinOpOrAnd = [](
Value *V) {
3874 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3887 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3889 <<
" F: " << IfFalse->
getName() <<
"\n");
3903 if (isa<FPMathOperator>(PN))
3923 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3941 if (Opc == Instruction::And)
3943 if (Opc == Instruction::Or)
3956 bool PredHasWeights =
3958 bool SuccHasWeights =
3960 if (PredHasWeights || SuccHasWeights) {
3961 if (!PredHasWeights)
3962 PredTrueWeight = PredFalseWeight = 1;
3963 if (!SuccHasWeights)
3964 SuccTrueWeight = SuccFalseWeight = 1;
3974static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3978 "Both blocks must end with a conditional branches.");
3980 "PredBB must be a predecessor of BB.");
3988 (PTWeight + PFWeight) != 0) {
3996 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3997 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
4001 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4004 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4005 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4011 return std::nullopt;
4024 bool InvertPredCond;
4025 std::tie(CommonSucc, Opc, InvertPredCond) =
4028 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4035 {LLVMContext::MD_annotation});
4038 if (InvertPredCond) {
4051 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4053 SuccTrueWeight, SuccFalseWeight)) {
4060 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4066 (SuccFalseWeight + SuccTrueWeight) +
4067 PredTrueWeight * SuccFalseWeight);
4073 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4074 PredFalseWeight * SuccTrueWeight);
4076 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4094 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
4095 {DominatorTree::Delete, PredBlock, BB}});
4122 ++NumFoldBranchToCommonDest;
4129 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4130 return U->getType()->isVectorTy();
4140 unsigned BonusInstThreshold) {
4154 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
4155 !isa<SelectInst>(
Cond)) ||
4156 Cond->getParent() != BB || !
Cond->hasOneUse())
4166 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
4177 bool InvertPredCond;
4179 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
4211 unsigned NumBonusInsts = 0;
4212 bool SawVectorOp =
false;
4213 const unsigned PredCount = Preds.
size();
4219 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
4230 NumBonusInsts += PredCount;
4238 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4239 auto *UI = cast<Instruction>(U.getUser());
4240 if (
auto *PN = dyn_cast<PHINode>(UI))
4242 return UI->
getParent() == BB &&
I.comesBefore(UI);
4246 if (!
all_of(
I.uses(), IsBCSSAUse))
4250 BonusInstThreshold *
4256 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4266 for (
auto *BB : {BB1, BB2}) {
4270 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4282 Value *AlternativeV =
nullptr) {
4300 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4301 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4302 PHI = cast<PHINode>(
I);
4308 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4309 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4317 if (!AlternativeV &&
4318 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4323 PHI->addIncoming(V, BB);
4333 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4342 if (!PStore || !QStore)
4363 if (
I.mayReadOrWriteMemory())
4365 for (
auto &
I : *QFB)
4366 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4369 for (
auto &
I : *QTB)
4370 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4374 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4390 if (
I.isTerminator())
4394 if (
auto *S = dyn_cast<StoreInst>(&
I))
4398 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4408 "When we run out of budget we will eagerly return from within the "
4409 "per-instruction loop.");
4413 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4415 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4416 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4524 bool InvertPCond =
false, InvertQCond =
false;
4530 if (QFB == PostBB) {
4549 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4552 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4560 for (
auto *BB : {PTB, PFB}) {
4565 PStoreAddresses.
insert(SI->getPointerOperand());
4567 for (
auto *BB : {QTB, QFB}) {
4572 QStoreAddresses.
insert(SI->getPointerOperand());
4578 auto &CommonAddresses = PStoreAddresses;
4580 bool Changed =
false;
4581 for (
auto *
Address : CommonAddresses)
4584 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4602 !BI->
getParent()->getSinglePredecessor())
4604 if (!IfFalseBB->
phis().empty())
4614 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4625 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4626 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4637 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4638 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4717 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4719 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4723 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4726 if (CommonDestProb >= Likely)
4736 unsigned NumPhis = 0;
4758 if (OtherDest == BB) {
4765 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4766 OtherDest = InfLoopBlock;
4786 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4801 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4802 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4805 SuccTrueWeight, SuccFalseWeight);
4807 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4808 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4809 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4810 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4814 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4815 PredOther * SuccCommon,
4816 PredOther * SuccOther};
4845 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4846 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4847 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4848 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4851 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4852 PredOther * SuccCommon};
4875bool SimplifyCFGOpt::simplifyTerminatorOnSelect(
Instruction *OldTerm,
4886 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4893 if (Succ == KeepEdge1)
4894 KeepEdge1 =
nullptr;
4895 else if (Succ == KeepEdge2)
4896 KeepEdge2 =
nullptr;
4901 if (Succ != TrueBB && Succ != FalseBB)
4902 RemovedSuccessors.
insert(Succ);
4910 if (!KeepEdge1 && !KeepEdge2) {
4911 if (TrueBB == FalseBB) {
4919 if (TrueWeight != FalseWeight)
4922 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4944 for (
auto *RemovedSuccessor : RemovedSuccessors)
4945 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4946 DTU->applyUpdates(Updates);
4956bool SimplifyCFGOpt::simplifySwitchOnSelect(
SwitchInst *SI,
4961 if (!TrueVal || !FalseVal)
4966 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4967 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4970 uint32_t TrueWeight = 0, FalseWeight = 0;
4975 if (Weights.
size() == 1 +
SI->getNumCases()) {
4977 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4979 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4984 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4993bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
5006 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
5027bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5047 if (
SI->getCondition() != V)
5053 if (
SI->getDefaultDest() != BB) {
5055 assert(VVal &&
"Should have a unique destination value");
5063 return requestResimplify();
5069 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5079 return requestResimplify();
5086 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5111 auto W0 = SIW.getSuccessorWeight(0);
5115 SIW.setSuccessorWeight(0, *NewW);
5117 SIW.addCase(Cst, NewBB, NewW);
5119 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5128 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5129 DTU->applyUpdates(Updates);
5137bool SimplifyCFGOpt::simplifyBranchOnICmpChain(
BranchInst *BI,
5149 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5152 Value *CompVal = ConstantCompare.CompValue;
5153 unsigned UsedICmps = ConstantCompare.UsedICmps;
5154 Value *ExtraCase = ConstantCompare.Extra;
5173 if (ExtraCase && Values.
size() < 2)
5188 <<
" cases into SWITCH. BB is:\n"
5198 nullptr,
"switch.early.test");
5222 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5228 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5229 <<
"\nEXTRABB = " << *BB);
5237 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5244 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
5245 New->addCase(Values[i], EdgeBB);
5251 PHINode *PN = cast<PHINode>(BBI);
5253 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5260 DTU->applyUpdates(Updates);
5262 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5268 return simplifyCommonResume(RI);
5269 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHI()) &&
5272 return simplifySingleResume(RI);
5280 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5285 switch (IntrinsicID) {
5286 case Intrinsic::dbg_declare:
5287 case Intrinsic::dbg_value:
5288 case Intrinsic::dbg_label:
5289 case Intrinsic::lifetime_end:
5299bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5309 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5312 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5314 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5315 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5319 if (IncomingBB->getUniqueSuccessor() != BB)
5322 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5324 if (IncomingValue != LandingPad)
5328 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5329 TrivialUnwindBlocks.
insert(IncomingBB);
5333 if (TrivialUnwindBlocks.
empty())
5337 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5341 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5355 TrivialBB->getTerminator()->eraseFromParent();
5358 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5365 return !TrivialUnwindBlocks.empty();
5369bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5373 "Resume must unwind the exception that caused control to here");
5377 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5413 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5430 int Idx = DestPN.getBasicBlockIndex(BB);
5444 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5445 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5447 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5451 DestPN.addIncoming(
Incoming, Pred);
5478 std::vector<DominatorTree::UpdateType> Updates;
5482 if (UnwindDest ==
nullptr) {
5494 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5495 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5522 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5523 if (!SuccessorCleanupPad)
5532 SuccessorCleanupPad->eraseFromParent();
5561 bool Changed =
false;
5590 BBI->dropDbgRecords();
5594 BBI->eraseFromParent();
5600 if (&BB->
front() != UI)
5603 std::vector<DominatorTree::UpdateType> Updates;
5609 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5613 [BB](
auto *
Successor) { return Successor == BB; })) {
5621 "The destinations are guaranteed to be different here.");
5632 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5638 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5639 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5641 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5642 if (i->getCaseSuccessor() != BB) {
5647 i = SU.removeCase(i);
5652 if (DTU &&
SI->getDefaultDest() != BB)
5653 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5654 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5655 if (
II->getUnwindDest() == BB) {
5657 DTU->applyUpdates(Updates);
5661 if (!CI->doesNotThrow())
5662 CI->setDoesNotThrow();
5665 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5666 if (CSI->getUnwindDest() == BB) {
5668 DTU->applyUpdates(Updates);
5677 E = CSI->handler_end();
5680 CSI->removeHandler(
I);
5687 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5688 if (CSI->getNumHandlers() == 0) {
5689 if (CSI->hasUnwindDest()) {
5693 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5694 Updates.push_back({DominatorTree::Insert,
5695 PredecessorOfPredecessor,
5696 CSI->getUnwindDest()});
5697 Updates.push_back({DominatorTree::Delete,
5698 PredecessorOfPredecessor, Predecessor});
5701 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5705 DTU->applyUpdates(Updates);
5714 CSI->eraseFromParent();
5717 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5719 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5720 "Expected to always have an unwind to BB.");
5722 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5730 DTU->applyUpdates(Updates);
5745 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5746 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5754 bool RemoveOrigDefaultBlock =
true) {
5756 auto *BB = Switch->getParent();
5757 auto *OrigDefaultBlock = Switch->getDefaultDest();
5758 if (RemoveOrigDefaultBlock)
5759 OrigDefaultBlock->removePredecessor(BB);
5764 Switch->setDefaultDest(&*NewDefaultBlock);
5767 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5768 if (RemoveOrigDefaultBlock &&
5770 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5778bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(
SwitchInst *SI,
5780 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5783 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5785 auto *BB =
SI->getParent();
5788 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5793 for (
auto Case :
SI->cases()) {
5797 if (Dest == DestA) {
5803 if (Dest == DestB) {
5813 "Single-destination switch should have been folded.");
5815 assert(DestB !=
SI->getDefaultDest());
5816 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5824 ContiguousCases = &CasesA;
5825 ContiguousDest = DestA;
5828 ContiguousCases = &CasesB;
5829 ContiguousDest = DestB;
5838 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5840 Value *Sub =
SI->getCondition();
5841 if (!
Offset->isNullValue())
5856 if (Weights.
size() == 1 +
SI->getNumCases()) {
5859 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5860 if (
SI->getSuccessor(
I) == ContiguousDest)
5861 TrueWeight += Weights[
I];
5863 FalseWeight += Weights[
I];
5865 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5874 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5875 unsigned PreviousEdges = ContiguousCases->
size();
5876 if (ContiguousDest ==
SI->getDefaultDest())
5878 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5879 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5881 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5882 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5883 if (OtherDest ==
SI->getDefaultDest())
5885 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5886 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5894 auto *UnreachableDefault =
SI->getDefaultDest();
5897 SI->eraseFromParent();
5899 if (!HasDefault && DTU)
5900 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5916 unsigned MaxSignificantBitsInCond =
5923 for (
const auto &Case : SI->cases()) {
5924 auto *
Successor = Case.getCaseSuccessor();
5930 const APInt &CaseVal = Case.getCaseValue()->getValue();
5933 DeadCases.
push_back(Case.getCaseValue());
5946 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5947 const unsigned NumUnknownBits =
5950 if (HasDefault && DeadCases.
empty() &&
5951 NumUnknownBits < 64 ) {
5952 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5953 if (SI->getNumCases() == AllNumCases) {
5960 if (SI->getNumCases() == AllNumCases - 1) {
5961 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5968 for (
const auto &Case : SI->cases())
5969 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5971 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5980 if (DeadCases.
empty())
5986 assert(CaseI != SI->case_default() &&
5987 "Case was not found. Probably mistake in DeadCases forming.");
5989 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5994 std::vector<DominatorTree::UpdateType> Updates;
5995 for (
auto *
Successor : UniqueSuccessors)
5996 if (NumPerSuccessorCases[
Successor] == 0)
5997 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
6017 if (!Branch || !Branch->isUnconditional())
6023 int Idx =
PHI.getBasicBlockIndex(BB);
6024 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
6027 if (InValue != CaseValue)
6043 ForwardingNodesMap ForwardingNodes;
6045 bool Changed =
false;
6046 for (
const auto &Case : SI->cases()) {
6048 BasicBlock *CaseDest = Case.getCaseSuccessor();
6067 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6068 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6069 count(Phi.blocks(), SwitchBlock) == 1) {
6070 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
6078 ForwardingNodes[Phi].push_back(PhiIdx);
6081 for (
auto &ForwardingNode : ForwardingNodes) {
6082 PHINode *Phi = ForwardingNode.first;
6088 for (
int Index : Indexes)
6089 Phi->setIncomingValue(Index, SI->getCondition());
6099 if (
C->isThreadDependent())
6101 if (
C->isDLLImportDependent())
6104 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
6105 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
6106 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
6112 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
6128 if (
Constant *
C = dyn_cast<Constant>(V))
6144 if (
A->isAllOnesValue())
6146 if (
A->isNullValue())
6152 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
6177 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
6179 if (
I.isTerminator()) {
6181 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6184 CaseDest =
I.getSuccessor(0);
6191 for (
auto &
Use :
I.uses()) {
6194 if (
I->getParent() == CaseDest)
6197 if (Phi->getIncomingBlock(
Use) == CaseDest)
6210 *CommonDest = CaseDest;
6212 if (CaseDest != *CommonDest)
6217 int Idx =
PHI.getBasicBlockIndex(Pred);
6230 Res.push_back(std::make_pair(&
PHI, ConstVal));
6233 return Res.size() > 0;
6239 SwitchCaseResultVectorTy &UniqueResults,
6241 for (
auto &
I : UniqueResults) {
6242 if (
I.first == Result) {
6243 I.second.push_back(CaseVal);
6244 return I.second.size();
6247 UniqueResults.push_back(
6258 SwitchCaseResultVectorTy &UniqueResults,
6262 uintptr_t MaxUniqueResults) {
6263 for (
const auto &
I : SI->cases()) {
6277 const size_t NumCasesForResult =
6285 if (UniqueResults.size() > MaxUniqueResults)
6296 BasicBlock *DefaultDest = SI->getDefaultDest();
6297 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6302 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6303 if ((!DefaultResult &&
6324 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6325 ResultVector[1].second.size() == 1) {
6326 ConstantInt *FirstCase = ResultVector[0].second[0];
6327 ConstantInt *SecondCase = ResultVector[1].second[0];
6328 Value *SelectValue = ResultVector[1].first;
6329 if (DefaultResult) {
6330 Value *ValueCompare =
6331 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6332 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6333 DefaultResult,
"switch.select");
6335 Value *ValueCompare =
6336 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6337 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6338 SelectValue,
"switch.select");
6342 if (ResultVector.size() == 1 && DefaultResult) {
6344 unsigned CaseCount = CaseValues.
size();
6352 for (
auto *Case : CaseValues)
6353 if (Case->getValue().slt(MinCaseVal->
getValue()))
6358 for (
auto *Case : CaseValues)
6359 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6365 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6369 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6374 if (CaseValues.
size() == 2) {
6376 "switch.selectcmp.case1");
6378 "switch.selectcmp.case2");
6379 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6380 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6393 std::vector<DominatorTree::UpdateType> Updates;
6399 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6404 PHI->removeIncomingValueIf(
6405 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6406 PHI->addIncoming(SelectValue, SelectBB);
6409 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6415 if (DTU && RemovedSuccessors.
insert(Succ).second)
6416 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6418 SI->eraseFromParent();
6433 SwitchCaseResultVectorTy UniqueResults;
6439 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6441 Value *SelectValue =
6453class SwitchLookupTable {
6504 bool LinearMapValWrapped =
false;
6512SwitchLookupTable::SwitchLookupTable(
6516 assert(Values.
size() &&
"Can't build lookup table without values!");
6517 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6520 SingleValue = Values.
begin()->second;
6526 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6532 TableContents[
Idx] = CaseRes;
6534 if (CaseRes != SingleValue)
6535 SingleValue =
nullptr;
6539 if (Values.
size() < TableSize) {
6541 "Need a default value to fill the lookup table holes.");
6544 if (!TableContents[
I])
6545 TableContents[
I] = DefaultValue;
6548 if (DefaultValue != SingleValue)
6549 SingleValue =
nullptr;
6555 Kind = SingleValueKind;
6562 bool LinearMappingPossible =
true;
6567 bool NonMonotonic =
false;
6568 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6571 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6575 LinearMappingPossible =
false;
6580 APInt Dist = Val - PrevVal;
6583 }
else if (Dist != DistToPrev) {
6584 LinearMappingPossible =
false;
6592 if (LinearMappingPossible) {
6593 LinearOffset = cast<ConstantInt>(TableContents[0]);
6594 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6595 APInt M = LinearMultiplier->getValue();
6596 bool MayWrap =
true;
6597 if (
isIntN(
M.getBitWidth(), TableSize - 1))
6598 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6599 LinearMapValWrapped = NonMonotonic || MayWrap;
6600 Kind = LinearMapKind;
6607 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6609 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6611 TableInt <<=
IT->getBitWidth();
6613 if (!isa<UndefValue>(TableContents[
I - 1])) {
6614 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6615 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6618 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6619 BitMapElementTy =
IT;
6630 GlobalVariable::PrivateLinkage, Initializer,
6631 "switch.table." + FuncName);
6632 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6641 case SingleValueKind:
6643 case LinearMapKind: {
6646 false,
"switch.idx.cast");
6647 if (!LinearMultiplier->isOne())
6648 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6650 !LinearMapValWrapped);
6652 if (!LinearOffset->isZero())
6655 !LinearMapValWrapped);
6671 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6672 "switch.shiftamt",
true,
true);
6675 Value *DownShifted =
6676 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6678 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6684 Array->getInitializer()->getType()->getArrayNumElements();
6685 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6688 "switch.tableidx.zext");
6692 GEPIndices,
"switch.gep");
6694 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6701bool SwitchLookupTable::wouldFitInRegister(
const DataLayout &
DL,
6703 Type *ElementType) {
6704 auto *
IT = dyn_cast<IntegerType>(ElementType);
6711 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6713 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6722 auto *
IT = dyn_cast<IntegerType>(Ty);
6734 DL.fitsInLegalInteger(
IT->getBitWidth());
6746 return NumCases * 100 >= CaseRange * MinDensity;
6767 if (SI->getNumCases() > TableSize)
6770 bool AllTablesFitInRegister =
true;
6771 bool HasIllegalType =
false;
6772 for (
const auto &
I : ResultTypes) {
6773 Type *Ty =
I.second;
6779 AllTablesFitInRegister =
6780 AllTablesFitInRegister &&
6781 SwitchLookupTable::wouldFitInRegister(
DL, TableSize, Ty);
6786 if (HasIllegalType && !AllTablesFitInRegister)
6791 if (AllTablesFitInRegister)
6808 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6811 return all_of(ResultTypes, [&](
const auto &KV) {
6812 return SwitchLookupTable::wouldFitInRegister(
6841 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6863 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6868 for (
auto ValuePair : Values) {
6871 if (!CaseConst || CaseConst == DefaultConst ||
6872 (CaseConst != TrueConst && CaseConst != FalseConst))
6886 if (DefaultConst == FalseConst) {
6889 ++NumTableCmpReuses;
6892 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6893 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6896 ++NumTableCmpReuses;
6906 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6925 if (SI->getNumCases() < 3)
6930 assert(!SI->cases().empty());
6947 MinCaseVal = CaseVal;
6949 MaxCaseVal = CaseVal;
6954 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6964 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6970 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6978 bool HasDefaultResults =
6980 DefaultResultsList,
DL,
TTI);
6982 for (
const auto &
I : DefaultResultsList) {
6985 DefaultResults[
PHI] = Result;
6989 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6991 if (UseSwitchConditionAsTableIndex)
7000 bool DefaultIsReachable = !SI->defaultDestUndefined();
7002 bool TableHasHoles = (NumResults < TableSize);
7007 bool AllHolesAreUndefined = TableHasHoles && !HasDefaultResults;
7015 bool NeedMask = AllHolesAreUndefined && DefaultIsReachable;
7018 if (SI->getNumCases() < 4)
7020 if (!
DL.fitsInLegalInteger(TableSize))
7027 std::vector<DominatorTree::UpdateType> Updates;
7033 assert(MaxTableSize >= TableSize &&
7034 "It is impossible for a switch to have more entries than the max "
7035 "representable value of its input integer type's size.");
7040 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7046 if (UseSwitchConditionAsTableIndex) {
7047 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7048 TableIndex = SI->getCondition();
7050 TableIndexOffset = MinCaseVal;
7053 bool MayWrap =
true;
7054 if (!DefaultIsReachable) {
7059 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
7060 "switch.tableidx",
false,
7069 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
7077 return SwitchLookupTable::wouldFitInRegister(
7078 DL, UpperBound, KV.second );
7082 TableSize = std::max(UpperBound, TableSize);
7085 DefaultIsReachable =
false;
7089 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7090 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7093 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7098 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7100 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
7102 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7112 MaskBB->
setName(
"switch.hole_check");
7119 APInt MaskInt(TableSizePowOf2, 0);
7120 APInt One(TableSizePowOf2, 1);
7122 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7123 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
7126 MaskInt |= One <<
Idx;
7128 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7136 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7139 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
7141 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
7142 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
7148 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7151 SI->getDefaultDest()->removePredecessor(BB,
7154 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
7158 const ResultListTy &ResultList = ResultLists[
PHI];
7162 AllHolesAreUndefined ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
7164 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
7167 Value *Result = Table.buildLookup(TableIndex, Builder);
7171 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7174 for (
auto *
User :
PHI->users()) {
7179 PHI->addIncoming(Result, LookupBB);
7184 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
7188 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
7191 if (Succ == SI->getDefaultDest())
7194 if (DTU && RemovedSuccessors.
insert(Succ).second)
7195 Updates.push_back({DominatorTree::Delete, BB, Succ});
7197 SI->eraseFromParent();
7204 ++NumLookupTablesHoles;
7219 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
7220 if (CondTy->getIntegerBitWidth() > 64 ||
7221 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7225 if (SI->getNumCases() < 4)
7233 for (
const auto &
C : SI->cases())
7234 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7242 int64_t
Base = Values[0];
7243 for (
auto &V : Values)
7256 unsigned Shift = 64;
7257 for (
auto &V : Values)
7261 for (
auto &V : Values)
7262 V = (int64_t)((
uint64_t)V >> Shift);
7278 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7281 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7283 Ty, Intrinsic::fshl,
7284 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7285 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7287 for (
auto Case : SI->cases()) {
7288 auto *Orig = Case.getCaseValue();
7289 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7290 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()))
7325 if (SI->getNumCases() < 4)
7331 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7336 for (
const auto &Case : SI->cases()) {
7337 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7354 for (
auto &Case : SI->cases()) {
7355 auto *OrigValue = Case.getCaseValue();
7356 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7357 OrigValue->getValue().countr_zero()));
7364 SI->setCondition(ConditionTrailingZeros);
7373 auto *Cmp = dyn_cast<CmpIntrinsic>(SI->getCondition());
7374 if (!Cmp || !Cmp->hasOneUse())
7385 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7388 if (SI->getNumCases() == 2) {
7395 Succ = SI->getDefaultDest();
7396 SuccWeight = Weights[0];
7398 for (
auto &Case : SI->cases()) {
7399 std::optional<int64_t> Val =
7403 if (!Missing.erase(*Val))
7408 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7411 assert(Missing.size() == 1 &&
"Should have one case left");
7412 Res = *Missing.begin();
7413 }
else if (SI->getNumCases() == 3 && SI->defaultDestUndefined()) {
7415 Unreachable = SI->getDefaultDest();
7417 for (
auto &Case : SI->cases()) {
7418 BasicBlock *NewSucc = Case.getCaseSuccessor();
7419 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7422 OtherSuccWeight += Weight;
7425 SuccWeight = Weight;
7426 }
else if (Succ == NewSucc) {
7432 for (
auto &Case : SI->cases()) {
7433 std::optional<int64_t> Val =
7435 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7437 if (Case.getCaseSuccessor() == Succ) {
7450 Pred = ICmpInst::ICMP_UGT;
7453 Pred = ICmpInst::ICMP_EQ;
7456 Pred = ICmpInst::ICMP_ULT;
7459 if (Cmp->isSigned())
7462 MDNode *NewWeights =
nullptr;
7464 NewWeights =
MDBuilder(SI->getContext())
7471 SI->getMetadata(LLVMContext::MD_unpredictable));
7475 SI->eraseFromParent();
7476 Cmp->eraseFromParent();
7477 if (DTU && Unreachable)
7478 DTU->
applyUpdates({{DominatorTree::Delete, BB, Unreachable}});
7509 "Only supporting unconditional branches for now");
7511 "Expected unconditional branches to have one successor");
7512 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7534 if (
LHS == EKey ||
RHS == EKey ||
LHS == TKey ||
RHS == TKey)
7547 BranchInst *ABI = cast<BranchInst>(
A->getTerminator());
7548 BranchInst *BBI = cast<BranchInst>(
B->getTerminator());
7550 "Only supporting unconditional branches for now");
7557 auto &PredIVs = (*
LHS->PhiPredIVs)[&Phi];
7558 if (PredIVs[
A] != PredIVs[
B])
7567bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *SI,
7581 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7586 if (BB->
size() != 1)
7602 if (Seen.
insert(BB).second) {
7611 BBToSuccessorIndexes[BB].emplace_back(
I);
7620 for (
auto &
IV :
Phi->incoming_values())
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)
7811 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7817 std::vector<DominatorTree::UpdateType> Updates;
7824 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7825 "unexpected successor");
7826 II->setUnwindDest(OtherPred);
7836 if (isa<DbgInfoIntrinsic>(Inst))
7857 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7858 : simplifyCondBranch(
Branch, Builder);
7861bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7873 bool NeedCanonicalLoop =
7884 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7886 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7888 if (
I->isTerminator() &&
7889 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7896 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7906 if (
Options.SpeculateBlocks &&
7909 return requestResimplify();
7917 if (!PPred || (PredPred && PredPred != PPred))
7954 if (!SuccBI || !SuccBI->isConditional())
7958 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7959 !isa<PHINode>(Succ1->
front()) && !isa<PHINode>(Succ2->
front());
7962 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
7988 bool HasWeight =
false;
7993 BBTWeight = BBFWeight = 1;
7998 BB1TWeight = BB1FWeight = 1;
8003 BB2TWeight = BB2FWeight = 1;
8005 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8006 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8017 "Tautological conditional branch should have been eliminated already.");
8020 if (!
Options.SimplifyCondBranch ||
8025 if (isValueEqualityComparison(BI)) {
8030 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8031 return requestResimplify();
8037 if (foldValueComparisonIntoPredecessors(BI, Builder))
8038 return requestResimplify();
8041 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8042 return requestResimplify();
8047 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8060 return requestResimplify();
8066 if (
Options.SpeculateBlocks &&
8069 return requestResimplify();
8078 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8079 return requestResimplify();
8082 Options.HoistLoadsStoresWithCondFaulting &&
8085 auto CanSpeculateConditionalLoadsStores = [&]() {
8088 if (
I.isTerminator()) {
8089 if (
I.getNumSuccessors() > 1)
8093 SpeculatedConditionalLoadsStores.
size() ==
8097 SpeculatedConditionalLoadsStores.
push_back(&
I);
8100 return !SpeculatedConditionalLoadsStores.
empty();
8103 if (CanSpeculateConditionalLoadsStores()) {
8106 return requestResimplify();
8116 return requestResimplify();
8125 return requestResimplify();
8132 return requestResimplify();
8137 if (PBI != BI && PBI->isConditional())
8139 return requestResimplify();
8144 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
8145 if (PBI != BI && PBI->isConditional())
8147 return requestResimplify();
8151 return requestResimplify();
8165 if (
C->isNullValue() || isa<UndefValue>(
C)) {
8169 auto *Use = cast<Instruction>(U);
8171 switch (Use->getOpcode()) {
8174 case Instruction::GetElementPtr:
8175 case Instruction::Ret:
8176 case Instruction::BitCast:
8177 case Instruction::Load:
8178 case Instruction::Store:
8179 case Instruction::Call:
8180 case Instruction::CallBr:
8181 case Instruction::Invoke:
8182 case Instruction::UDiv:
8183 case Instruction::URem:
8187 case Instruction::SDiv:
8188 case Instruction::SRem:
8192 if (FindUse ==
I->user_end())
8194 auto *
Use = cast<Instruction>(*FindUse);
8198 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
8212 if (
GEP->getPointerOperand() ==
I) {
8219 if (!
GEP->hasAllZeroIndices() &&
8220 (!
GEP->isInBounds() ||
8222 GEP->getPointerAddressSpace())))
8223 PtrValueMayBeModified =
true;
8229 bool HasNoUndefAttr =
8230 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8232 if (isa<UndefValue>(
C) && HasNoUndefAttr)
8235 if (
C->isNullValue() && HasNoUndefAttr &&
8236 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8237 return !PtrValueMayBeModified;
8243 if (!LI->isVolatile())
8245 LI->getPointerAddressSpace());
8249 if (!SI->isVolatile())
8251 SI->getPointerAddressSpace())) &&
8252 SI->getPointerOperand() ==
I;
8255 if (
auto *Assume = dyn_cast<AssumeInst>(
Use)) {
8257 if (
I == Assume->getArgOperand(0))
8261 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
8265 if (CB->getCalledOperand() ==
I)
8268 if (
C->isNullValue()) {
8271 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
8272 if (CB->isPassingUndefUB(ArgIdx) &&
8273 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
8275 return !PtrValueMayBeModified;
8278 }
else if (isa<UndefValue>(
C)) {
8282 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
8283 if (CB->isPassingUndefUB(ArgIdx)) {
8303 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8332 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
8340 for (
const auto &Case : SI->cases())
8341 if (Case.getCaseSuccessor() == BB) {
8343 Case.setSuccessor(Unreachable);
8345 if (SI->getDefaultDest() == BB) {
8347 SI->setDefaultDest(Unreachable);
8361bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
8362 bool Changed =
false;
8386 return requestResimplify();
8407 if (
Options.SpeculateBlocks &&
8411 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
8414 Options.SpeculateUnpredictables))
8421 case Instruction::Br:
8422 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
8424 case Instruction::Resume:
8425 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
8427 case Instruction::CleanupRet:
8428 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
8430 case Instruction::Switch:
8431 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
8433 case Instruction::Unreachable:
8434 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
8436 case Instruction::IndirectBr:
8437 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
8445 bool Changed =
false;
8453 Changed |= simplifyOnce(BB);
8454 }
while (Resimplify);
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< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
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...
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 isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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 cl::opt< bool > HoistLoadsStoresWithCondFaulting("simplifycfg-hoist-loads-stores-with-cond-faulting", cl::Hidden, cl::init(true), cl::desc("Hoist loads/stores if the target supports " "conditional faulting"))
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 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 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 foldCondBranchOnValueKnownInPredecessor(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
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 Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
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 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 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 hoistConditionalLoadsStores(BranchInst *BI, SmallVectorImpl< Instruction * > &SpeculatedConditionalLoadsStores, std::optional< bool > Invert)
If the target supports conditional faulting, we look for the following pattern:
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 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< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditonal load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
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 isLifeTimeMarker(const Instruction *I)
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 bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
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 dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
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.
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 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.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
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.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
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.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
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,...
const Instruction * getFirstNonPHI() const
Returns a pointer 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.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
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.
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
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...
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.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
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 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.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getPredicate() const
Return the predicate for this instruction.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static 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 ConstantInt * getTrue(LLVMContext &Context)
static 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.
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.
bool isEmptySet() const
Return true if this set contains no members.
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.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static 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...
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 Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DILocation * getMergedLocations(ArrayRef< DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
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.
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
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 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()
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
CallInst * CreateMaskedLoad(Type *Ty, Value *Ptr, Align Alignment, Value *Mask, Value *PassThru=nullptr, const Twine &Name="")
Create a call to Masked Load intrinsic.
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 setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
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.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
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 * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
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 * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
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 * 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.
void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
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.
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.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
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...
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.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
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.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
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 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.
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...
void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
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.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
unsigned getOperandNo() const
Return the operand # of this use in its User.
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
Value(Type *Ty, unsigned scid)
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.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
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.
ArchKind & operator--(ArchKind &Kind)
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< 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.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
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)
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< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
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.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
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.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each 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.
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)
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 @...
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...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
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<>...
APInt operator*(APInt a, uint64_t RHS)
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
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)
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
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.
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.
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
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...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
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.
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)
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
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...
Constant * ConstantFoldInstOperands(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.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
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.
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)
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.
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...
@ And
Bitwise or logical AND of integers.
bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
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 computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
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...
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
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.
constexpr unsigned BitWidth
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.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
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...
auto predecessors(const MachineBasicBlock *BB)
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.
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)
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 ...
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.
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.
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...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
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 ...
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
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
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.
A MapVector that performs no allocations if smaller than a certain size.