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)];
2158 isa<FPMathOperator>(PN) ? &PN :
nullptr,
2163 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2164 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2165 PN.setIncomingValue(i, SI);
2176 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2181 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2185 DTU->applyUpdates(Updates);
2191 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
2192 switch (
II->getIntrinsicID()) {
2195 case Intrinsic::lifetime_start:
2196 case Intrinsic::lifetime_end:
2208 if (
I->isIntDivRem())
2210 return !isa<IntrinsicInst>(
I);
2223 std::optional<unsigned> NumUses;
2224 for (
auto *
I : Insts) {
2226 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
2227 I->getType()->isTokenTy())
2232 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2239 if (
const auto *
C = dyn_cast<CallBase>(
I))
2240 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2244 NumUses =
I->getNumUses();
2245 else if (NumUses !=
I->getNumUses())
2251 for (
auto *
I : Insts) {
2258 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
2260 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
2273 for (
const Use &U : I0->
uses()) {
2274 auto It = PHIOperands.find(&U);
2275 if (It == PHIOperands.end())
2278 if (!
equal(Insts, It->second))
2286 if (isa<CallBase>(I0)) {
2288 return cast<CallBase>(
I)->isIndirectCall();
2290 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2291 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2292 if (HaveIndirectCalls) {
2293 if (!AllCallsAreIndirect)
2297 Value *Callee =
nullptr;
2299 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2301 Callee = CurrCallee;
2302 else if (Callee != CurrCallee)
2308 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2310 if (
Op->getType()->isTokenTy())
2318 if (!
all_of(Insts, SameAsI0)) {
2325 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2334 for (
auto *
I : Insts)
2335 Ops.push_back(
I->getOperand(OI));
2345 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2350 for (
auto *BB :
Blocks) {
2353 I =
I->getPrevNode();
2354 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2355 if (!isa<DbgInfoIntrinsic>(
I))
2380 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2383 PN->insertBefore(BBEnd->begin());
2384 for (
auto *
I : Insts)
2385 PN->addIncoming(
I->getOperand(O),
I->getParent());
2394 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2397 for (
auto *
I : Insts)
2409 if (
auto *CB = dyn_cast<CallBase>(I0)) {
2410 bool Success = CB->tryIntersectAttributes(cast<CallBase>(
I));
2411 assert(
Success &&
"We should not be trying to sink callbases "
2412 "with non-intersectable attributes");
2422 auto *PN = cast<PHINode>(U);
2423 PN->replaceAllUsesWith(I0);
2424 PN->eraseFromParent();
2428 for (
auto *
I : Insts) {
2433 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2434 I->replaceAllUsesWith(I0);
2435 I->eraseFromParent();
2485 bool HaveNonUnconditionalPredecessors =
false;
2487 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2488 if (PredBr && PredBr->isUnconditional())
2491 HaveNonUnconditionalPredecessors =
true;
2493 if (UnconditionalPreds.
size() < 2)
2506 for (
const Use &U : PN.incoming_values())
2507 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2508 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2510 Ops.push_back(*IncomingVals[Pred]);
2515 LockstepReverseIterator LRI(UnconditionalPreds);
2516 while (LRI.isValid() &&
2518 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2520 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2531 if (!followedByDeoptOrUnreachable) {
2533 auto IsMemOperand = [](
Use &U) {
2534 auto *
I = cast<Instruction>(U.getUser());
2535 if (isa<LoadInst>(
I))
2537 if (isa<StoreInst>(
I))
2545 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2546 unsigned NumPHIInsts = 0;
2547 for (
Use &U : (*LRI)[0]->operands()) {
2548 auto It = PHIOperands.
find(&U);
2549 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2550 return InstructionsToSink.contains(V);
2557 if (IsMemOperand(U) &&
2558 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2565 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2566 return NumPHIInsts <= 1;
2583 while (
Idx < ScanIdx) {
2584 if (!ProfitableToSinkInstruction(LRI)) {
2587 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2590 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2600 if (
Idx < ScanIdx) {
2603 InstructionsToSink = InstructionsProfitableToSink;
2609 !ProfitableToSinkInstruction(LRI) &&
2610 "We already know that the last instruction is unprofitable to sink");
2618 for (
auto *
I : *LRI)
2619 InstructionsProfitableToSink.
erase(
I);
2620 if (!ProfitableToSinkInstruction(LRI)) {
2623 InstructionsToSink = InstructionsProfitableToSink;
2635 bool Changed =
false;
2637 if (HaveNonUnconditionalPredecessors) {
2638 if (!followedByDeoptOrUnreachable) {
2646 bool Profitable =
false;
2647 while (
Idx < ScanIdx) {
2681 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2683 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2691 NumSinkCommonInstrs++;
2695 ++NumSinkCommonCode;
2701struct CompatibleSets {
2719 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2724 return Sets.emplace_back();
2728 getCompatibleSet(
II).emplace_back(
II);
2732 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2736 return II->cannotMerge() ||
II->isInlineAsm();
2738 if (
any_of(Invokes, IsIllegalToMerge))
2743 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2744 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2745 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2746 if (HaveIndirectCalls) {
2747 if (!AllCallsAreIndirect)
2753 Value *CurrCallee =
II->getCalledOperand();
2754 assert(CurrCallee &&
"There is always a called operand.");
2757 else if (Callee != CurrCallee)
2765 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2767 if (
any_of(Invokes, HasNormalDest)) {
2770 if (!
all_of(Invokes, HasNormalDest))
2777 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2779 NormalBB = CurrNormalBB;
2780 else if (NormalBB != CurrNormalBB)
2788 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2799 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2801 UnwindBB = CurrUnwindBB;
2803 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2810 Invokes.front()->getUnwindDest(),
2811 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2817 for (
auto *
II : Invokes.drop_front())
2822 auto IsIllegalToMergeArguments = [](
auto Ops) {
2823 Use &U0 = std::get<0>(Ops);
2824 Use &U1 = std::get<1>(Ops);
2831 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2832 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2833 IsIllegalToMergeArguments))
2845 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2851 bool HasNormalDest =
2852 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2856 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2860 II0->
getParent()->getIterator()->getNextNode();
2865 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2867 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2869 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2871 if (!HasNormalDest) {
2875 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2882 return MergedInvoke;
2890 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2896 SuccBBOfMergedInvoke});
2903 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2906 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2909 for (
Use &U : MergedInvoke->operands()) {
2911 if (MergedInvoke->isCallee(&U)) {
2912 if (!IsIndirectCall)
2914 }
else if (!MergedInvoke->isDataOperand(&U))
2919 return II->getOperand(
U.getOperandNo()) !=
U.get();
2926 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2938 Invokes.front()->getParent());
2946 if (!MergedDebugLoc)
2947 MergedDebugLoc =
II->getDebugLoc();
2955 OrigSuccBB->removePredecessor(
II->getParent());
2960 bool Success = MergedInvoke->tryIntersectAttributes(
II);
2961 assert(
Success &&
"Merged invokes with incompatible attributes");
2964 II->replaceAllUsesWith(MergedInvoke);
2965 II->eraseFromParent();
2968 MergedInvoke->setDebugLoc(MergedDebugLoc);
2969 ++NumInvokeSetsFormed;
2972 DTU->applyUpdates(Updates);
2999 bool Changed =
false;
3005 CompatibleSets Grouper;
3011 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
3015 if (Invokes.
size() < 2)
3027class EphemeralValueTracker {
3031 if (isa<AssumeInst>(
I))
3033 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3035 return EphValues.count(cast<Instruction>(U));
3041 if (isEphemeral(
I)) {
3080 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
3092 unsigned MaxNumInstToLookAt = 9;
3096 if (!MaxNumInstToLookAt)
3098 --MaxNumInstToLookAt;
3101 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
3104 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
3108 if (SI->getPointerOperand() == StorePtr &&
3109 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
3110 SI->getAlign() >= StoreToHoist->
getAlign())
3112 return SI->getValueOperand();
3116 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
3117 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3118 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3120 bool ExplicitlyDereferenceableOnly;
3124 (!ExplicitlyDereferenceableOnly ||
3126 LI->getDataLayout()))) {
3142 unsigned &SpeculatedInstructions,
3150 bool HaveRewritablePHIs =
false;
3168 HaveRewritablePHIs =
true;
3171 if (!OrigCE && !ThenCE)
3178 if (OrigCost + ThenCost > MaxCost)
3185 ++SpeculatedInstructions;
3186 if (SpeculatedInstructions > 1)
3190 return HaveRewritablePHIs;
3194 std::optional<bool> Invert,
3198 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3205 if (!Invert.has_value())
3208 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3212 return BIEndProb < Likely;
3252bool SimplifyCFGOpt::speculativelyExecuteBB(
BranchInst *BI,
3259 if (isa<FCmpInst>(BrCond))
3269 bool Invert =
false;
3288 unsigned SpeculatedInstructions = 0;
3290 Options.HoistLoadsStoresWithCondFaulting;
3292 Value *SpeculatedStoreValue =
nullptr;
3294 EphemeralValueTracker EphTracker;
3297 if (isa<DbgInfoIntrinsic>(
I)) {
3305 if (isa<PseudoProbeInst>(
I)) {
3315 if (EphTracker.track(&
I))
3320 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3322 SpeculatedConditionalLoadsStores.
size() <
3326 if (IsSafeCheapLoadStore)
3327 SpeculatedConditionalLoadsStores.
push_back(&
I);
3329 ++SpeculatedInstructions;
3331 if (SpeculatedInstructions > 1)
3335 if (!IsSafeCheapLoadStore &&
3338 (SpeculatedStoreValue =
3341 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3347 if (!SpeculatedStore && SpeculatedStoreValue)
3348 SpeculatedStore = cast<StoreInst>(&
I);
3353 for (
Use &
Op :
I.operands()) {
3358 ++SinkCandidateUseCounts[OpI];
3365 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3367 ++SpeculatedInstructions;
3368 if (SpeculatedInstructions > 1)
3375 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3378 SpeculatedInstructions,
Cost,
TTI);
3379 if (!Convert ||
Cost > Budget)
3383 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3386 if (SpeculatedStoreValue) {
3390 Value *FalseV = SpeculatedStoreValue;
3394 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3423 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3425 DbgAssign->replaceVariableLocationOp(OrigV, S);
3438 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3440 if (!isa<DbgAssignIntrinsic>(&
I))
3443 I.dropUBImplyingAttrsAndMetadata();
3446 if (EphTracker.contains(&
I)) {
3448 I.eraseFromParent();
3462 It.dropOneDbgRecord(&DR);
3464 std::prev(ThenBB->
end()));
3466 if (!SpeculatedConditionalLoadsStores.
empty())
3484 Value *TrueV = ThenV, *FalseV = OrigV;
3498 if (!isa<DbgAssignIntrinsic>(
I))
3499 I->eraseFromParent();
3509 EphemeralValueTracker EphTracker;
3515 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3516 if (CI->cannotDuplicate() || CI->isConvergent())
3522 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3529 for (
User *U :
I.users()) {
3531 if (UI->
getParent() != BB || isa<PHINode>(UI))
3545 auto *
I = dyn_cast<Instruction>(V);
3546 if (
I &&
I->getParent() == To)
3550 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3562static std::optional<bool>
3578 if (
auto *CB = dyn_cast<ConstantInt>(U))
3583 KnownValues[CB].
insert(Pred);
3587 if (KnownValues.
empty())
3596 for (
const auto &Pair : KnownValues) {
3614 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3617 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3625 EdgeBB->setName(RealDest->
getName() +
".critedge");
3626 EdgeBB->moveBefore(RealDest);
3636 TranslateMap[
Cond] = CB;
3642 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3649 N->insertInto(EdgeBB, InsertPt);
3652 N->setName(BBI->getName() +
".c");
3655 for (
Use &
Op :
N->operands()) {
3657 if (PI != TranslateMap.
end())
3663 if (!BBI->use_empty())
3664 TranslateMap[&*BBI] = V;
3665 if (!
N->mayHaveSideEffects()) {
3666 N->eraseFromParent();
3671 if (!BBI->use_empty())
3672 TranslateMap[&*BBI] =
N;
3678 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3679 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3680 SrcDbgCursor = std::next(BBI);
3682 N->cloneDebugInfoFrom(&*BBI);
3685 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3691 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3692 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3693 InsertPt->cloneDebugInfoFrom(BI);
3696 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3702 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3703 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3714 return std::nullopt;
3724 std::optional<bool> Result;
3725 bool EverChanged =
false;
3729 EverChanged |= Result == std::nullopt || *Result;
3730 }
while (Result == std::nullopt);
3739 bool SpeculateUnpredictables) {
3754 if (isa<ConstantInt>(IfCond))
3761 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3764 "Will have either one or two blocks to speculate.");
3771 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3772 if (!IsUnpredictable) {
3775 (TWeight + FWeight) != 0) {
3780 if (IfBlocks.
size() == 1) {
3782 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3783 if (BIBBProb >= Likely)
3786 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3794 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3795 if (IfCondPhiInst->getParent() == BB)
3803 unsigned NumPhis = 0;
3815 if (SpeculateUnpredictables && IsUnpredictable)
3818 bool Changed =
false;
3829 AggressiveInsts,
Cost, Budget,
TTI, AC) ||
3831 AggressiveInsts,
Cost, Budget,
TTI, AC))
3837 PN = dyn_cast<PHINode>(BB->
begin());
3843 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3854 auto IsBinOpOrAnd = [](
Value *V) {
3871 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3884 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3886 <<
" F: " << IfFalse->
getName() <<
"\n");
3904 isa<FPMathOperator>(PN) ? PN :
nullptr,
3908 PN->eraseFromParent();
3918 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3936 if (Opc == Instruction::And)
3938 if (Opc == Instruction::Or)
3951 bool PredHasWeights =
3953 bool SuccHasWeights =
3955 if (PredHasWeights || SuccHasWeights) {
3956 if (!PredHasWeights)
3957 PredTrueWeight = PredFalseWeight = 1;
3958 if (!SuccHasWeights)
3959 SuccTrueWeight = SuccFalseWeight = 1;
3969static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3973 "Both blocks must end with a conditional branches.");
3975 "PredBB must be a predecessor of BB.");
3983 (PTWeight + PFWeight) != 0) {
3991 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3992 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3996 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3999 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4000 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4006 return std::nullopt;
4019 bool InvertPredCond;
4020 std::tie(CommonSucc, Opc, InvertPredCond) =
4023 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4030 {LLVMContext::MD_annotation});
4033 if (InvertPredCond) {
4046 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4048 SuccTrueWeight, SuccFalseWeight)) {
4055 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4061 (SuccFalseWeight + SuccTrueWeight) +
4062 PredTrueWeight * SuccFalseWeight);
4068 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4069 PredFalseWeight * SuccTrueWeight);
4071 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4089 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
4090 {DominatorTree::Delete, PredBlock, BB}});
4117 ++NumFoldBranchToCommonDest;
4124 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4125 return U->getType()->isVectorTy();
4135 unsigned BonusInstThreshold) {
4149 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
4150 !isa<SelectInst>(
Cond)) ||
4151 Cond->getParent() != BB || !
Cond->hasOneUse())
4161 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
4172 bool InvertPredCond;
4174 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
4206 unsigned NumBonusInsts = 0;
4207 bool SawVectorOp =
false;
4208 const unsigned PredCount = Preds.
size();
4214 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
4225 NumBonusInsts += PredCount;
4233 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4234 auto *UI = cast<Instruction>(U.getUser());
4235 if (
auto *PN = dyn_cast<PHINode>(UI))
4237 return UI->
getParent() == BB &&
I.comesBefore(UI);
4241 if (!
all_of(
I.uses(), IsBCSSAUse))
4245 BonusInstThreshold *
4251 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4261 for (
auto *BB : {BB1, BB2}) {
4265 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4277 Value *AlternativeV =
nullptr) {
4295 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4296 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4297 PHI = cast<PHINode>(
I);
4303 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4304 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4312 if (!AlternativeV &&
4313 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4318 PHI->addIncoming(V, BB);
4328 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4337 if (!PStore || !QStore)
4358 if (
I.mayReadOrWriteMemory())
4360 for (
auto &
I : *QFB)
4361 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4364 for (
auto &
I : *QTB)
4365 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4369 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4385 if (
I.isTerminator())
4389 if (
auto *S = dyn_cast<StoreInst>(&
I))
4393 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4403 "When we run out of budget we will eagerly return from within the "
4404 "per-instruction loop.");
4408 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4410 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4411 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4519 bool InvertPCond =
false, InvertQCond =
false;
4525 if (QFB == PostBB) {
4544 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4547 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4555 for (
auto *BB : {PTB, PFB}) {
4560 PStoreAddresses.
insert(SI->getPointerOperand());
4562 for (
auto *BB : {QTB, QFB}) {
4567 QStoreAddresses.
insert(SI->getPointerOperand());
4573 auto &CommonAddresses = PStoreAddresses;
4575 bool Changed =
false;
4576 for (
auto *
Address : CommonAddresses)
4579 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4597 !BI->
getParent()->getSinglePredecessor())
4599 if (!IfFalseBB->
phis().empty())
4609 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4620 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4621 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4632 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4633 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4712 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4714 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4718 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4721 if (CommonDestProb >= Likely)
4731 unsigned NumPhis = 0;
4753 if (OtherDest == BB) {
4760 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4761 OtherDest = InfLoopBlock;
4781 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4796 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4797 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4800 SuccTrueWeight, SuccFalseWeight);
4802 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4803 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4804 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4805 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4809 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4810 PredOther * SuccCommon,
4811 PredOther * SuccOther};
4840 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4841 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4842 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4843 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4846 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4847 PredOther * SuccCommon};
4870bool SimplifyCFGOpt::simplifyTerminatorOnSelect(
Instruction *OldTerm,
4881 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4888 if (Succ == KeepEdge1)
4889 KeepEdge1 =
nullptr;
4890 else if (Succ == KeepEdge2)
4891 KeepEdge2 =
nullptr;
4896 if (Succ != TrueBB && Succ != FalseBB)
4897 RemovedSuccessors.
insert(Succ);
4905 if (!KeepEdge1 && !KeepEdge2) {
4906 if (TrueBB == FalseBB) {
4914 if (TrueWeight != FalseWeight)
4917 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4939 for (
auto *RemovedSuccessor : RemovedSuccessors)
4940 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4941 DTU->applyUpdates(Updates);
4951bool SimplifyCFGOpt::simplifySwitchOnSelect(
SwitchInst *SI,
4956 if (!TrueVal || !FalseVal)
4961 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4962 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4965 uint32_t TrueWeight = 0, FalseWeight = 0;
4970 if (Weights.
size() == 1 +
SI->getNumCases()) {
4972 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4974 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4979 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4988bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
5001 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
5022bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5042 if (
SI->getCondition() != V)
5048 if (
SI->getDefaultDest() != BB) {
5050 assert(VVal &&
"Should have a unique destination value");
5058 return requestResimplify();
5064 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5074 return requestResimplify();
5081 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5106 auto W0 = SIW.getSuccessorWeight(0);
5110 SIW.setSuccessorWeight(0, *NewW);
5112 SIW.addCase(Cst, NewBB, NewW);
5114 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5123 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5124 DTU->applyUpdates(Updates);
5132bool SimplifyCFGOpt::simplifyBranchOnICmpChain(
BranchInst *BI,
5144 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5147 Value *CompVal = ConstantCompare.CompValue;
5148 unsigned UsedICmps = ConstantCompare.UsedICmps;
5149 Value *ExtraCase = ConstantCompare.Extra;
5168 if (ExtraCase && Values.
size() < 2)
5183 <<
" cases into SWITCH. BB is:\n"
5193 nullptr,
"switch.early.test");
5217 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5223 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5224 <<
"\nEXTRABB = " << *BB);
5232 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5239 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
5240 New->addCase(Values[i], EdgeBB);
5246 PHINode *PN = cast<PHINode>(BBI);
5248 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5255 DTU->applyUpdates(Updates);
5257 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5263 return simplifyCommonResume(RI);
5264 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHI()) &&
5267 return simplifySingleResume(RI);
5275 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5280 switch (IntrinsicID) {
5281 case Intrinsic::dbg_declare:
5282 case Intrinsic::dbg_value:
5283 case Intrinsic::dbg_label:
5284 case Intrinsic::lifetime_end:
5294bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5304 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5307 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5309 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5310 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5314 if (IncomingBB->getUniqueSuccessor() != BB)
5317 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5319 if (IncomingValue != LandingPad)
5323 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5324 TrivialUnwindBlocks.
insert(IncomingBB);
5328 if (TrivialUnwindBlocks.
empty())
5332 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5336 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5350 TrivialBB->getTerminator()->eraseFromParent();
5353 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5360 return !TrivialUnwindBlocks.empty();
5364bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5368 "Resume must unwind the exception that caused control to here");
5372 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5408 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5425 int Idx = DestPN.getBasicBlockIndex(BB);
5439 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5440 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5442 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5446 DestPN.addIncoming(
Incoming, Pred);
5473 std::vector<DominatorTree::UpdateType> Updates;
5477 if (UnwindDest ==
nullptr) {
5489 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5490 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5517 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5518 if (!SuccessorCleanupPad)
5527 SuccessorCleanupPad->eraseFromParent();
5556 bool Changed =
false;
5585 BBI->dropDbgRecords();
5589 BBI->eraseFromParent();
5595 if (&BB->
front() != UI)
5598 std::vector<DominatorTree::UpdateType> Updates;
5604 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5608 [BB](
auto *
Successor) { return Successor == BB; })) {
5616 "The destinations are guaranteed to be different here.");
5627 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5633 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5634 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5636 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5637 if (i->getCaseSuccessor() != BB) {
5642 i = SU.removeCase(i);
5647 if (DTU &&
SI->getDefaultDest() != BB)
5648 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5649 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5650 if (
II->getUnwindDest() == BB) {
5652 DTU->applyUpdates(Updates);
5656 if (!CI->doesNotThrow())
5657 CI->setDoesNotThrow();
5660 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5661 if (CSI->getUnwindDest() == BB) {
5663 DTU->applyUpdates(Updates);
5672 E = CSI->handler_end();
5675 CSI->removeHandler(
I);
5682 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5683 if (CSI->getNumHandlers() == 0) {
5684 if (CSI->hasUnwindDest()) {
5688 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5689 Updates.push_back({DominatorTree::Insert,
5690 PredecessorOfPredecessor,
5691 CSI->getUnwindDest()});
5692 Updates.push_back({DominatorTree::Delete,
5693 PredecessorOfPredecessor, Predecessor});
5696 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5700 DTU->applyUpdates(Updates);
5709 CSI->eraseFromParent();
5712 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5714 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5715 "Expected to always have an unwind to BB.");
5717 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5725 DTU->applyUpdates(Updates);
5740 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5741 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5749 bool RemoveOrigDefaultBlock =
true) {
5751 auto *BB = Switch->getParent();
5752 auto *OrigDefaultBlock = Switch->getDefaultDest();
5753 if (RemoveOrigDefaultBlock)
5754 OrigDefaultBlock->removePredecessor(BB);
5759 Switch->setDefaultDest(&*NewDefaultBlock);
5762 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5763 if (RemoveOrigDefaultBlock &&
5765 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5773bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(
SwitchInst *SI,
5775 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5778 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5780 auto *BB =
SI->getParent();
5783 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5788 for (
auto Case :
SI->cases()) {
5792 if (Dest == DestA) {
5798 if (Dest == DestB) {
5808 "Single-destination switch should have been folded.");
5810 assert(DestB !=
SI->getDefaultDest());
5811 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5819 ContiguousCases = &CasesA;
5820 ContiguousDest = DestA;
5823 ContiguousCases = &CasesB;
5824 ContiguousDest = DestB;
5833 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5835 Value *Sub =
SI->getCondition();
5836 if (!
Offset->isNullValue())
5851 if (Weights.
size() == 1 +
SI->getNumCases()) {
5854 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5855 if (
SI->getSuccessor(
I) == ContiguousDest)
5856 TrueWeight += Weights[
I];
5858 FalseWeight += Weights[
I];
5860 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5869 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5870 unsigned PreviousEdges = ContiguousCases->
size();
5871 if (ContiguousDest ==
SI->getDefaultDest())
5873 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5874 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5876 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5877 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5878 if (OtherDest ==
SI->getDefaultDest())
5880 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5881 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5889 auto *UnreachableDefault =
SI->getDefaultDest();
5892 SI->eraseFromParent();
5894 if (!HasDefault && DTU)
5895 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5911 unsigned MaxSignificantBitsInCond =
5918 for (
const auto &Case : SI->cases()) {
5919 auto *
Successor = Case.getCaseSuccessor();
5925 const APInt &CaseVal = Case.getCaseValue()->getValue();
5928 DeadCases.
push_back(Case.getCaseValue());
5941 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5942 const unsigned NumUnknownBits =
5945 if (HasDefault && DeadCases.
empty() &&
5946 NumUnknownBits < 64 ) {
5947 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5948 if (SI->getNumCases() == AllNumCases) {
5955 if (SI->getNumCases() == AllNumCases - 1) {
5956 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5963 for (
const auto &Case : SI->cases())
5964 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5966 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5975 if (DeadCases.
empty())
5981 assert(CaseI != SI->case_default() &&
5982 "Case was not found. Probably mistake in DeadCases forming.");
5984 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5989 std::vector<DominatorTree::UpdateType> Updates;
5990 for (
auto *
Successor : UniqueSuccessors)
5991 if (NumPerSuccessorCases[
Successor] == 0)
5992 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
6012 if (!Branch || !Branch->isUnconditional())
6018 int Idx =
PHI.getBasicBlockIndex(BB);
6019 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
6022 if (InValue != CaseValue)
6038 ForwardingNodesMap ForwardingNodes;
6040 bool Changed =
false;
6041 for (
const auto &Case : SI->cases()) {
6043 BasicBlock *CaseDest = Case.getCaseSuccessor();
6062 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6063 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6064 count(Phi.blocks(), SwitchBlock) == 1) {
6065 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
6073 ForwardingNodes[Phi].push_back(PhiIdx);
6076 for (
auto &ForwardingNode : ForwardingNodes) {
6077 PHINode *Phi = ForwardingNode.first;
6083 for (
int Index : Indexes)
6084 Phi->setIncomingValue(Index, SI->getCondition());
6094 if (
C->isThreadDependent())
6096 if (
C->isDLLImportDependent())
6099 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
6100 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
6101 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
6107 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
6123 if (
Constant *
C = dyn_cast<Constant>(V))
6139 if (
A->isAllOnesValue())
6141 if (
A->isNullValue())
6147 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
6172 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
6174 if (
I.isTerminator()) {
6176 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6179 CaseDest =
I.getSuccessor(0);
6186 for (
auto &
Use :
I.uses()) {
6189 if (
I->getParent() == CaseDest)
6192 if (Phi->getIncomingBlock(
Use) == CaseDest)
6205 *CommonDest = CaseDest;
6207 if (CaseDest != *CommonDest)
6212 int Idx =
PHI.getBasicBlockIndex(Pred);
6225 Res.push_back(std::make_pair(&
PHI, ConstVal));
6228 return Res.size() > 0;
6234 SwitchCaseResultVectorTy &UniqueResults,
6236 for (
auto &
I : UniqueResults) {
6237 if (
I.first == Result) {
6238 I.second.push_back(CaseVal);
6239 return I.second.size();
6242 UniqueResults.push_back(
6253 SwitchCaseResultVectorTy &UniqueResults,
6257 uintptr_t MaxUniqueResults) {
6258 for (
const auto &
I : SI->cases()) {
6272 const size_t NumCasesForResult =
6280 if (UniqueResults.size() > MaxUniqueResults)
6291 BasicBlock *DefaultDest = SI->getDefaultDest();
6292 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6297 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6298 if ((!DefaultResult &&
6319 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6320 ResultVector[1].second.size() == 1) {
6321 ConstantInt *FirstCase = ResultVector[0].second[0];
6322 ConstantInt *SecondCase = ResultVector[1].second[0];
6323 Value *SelectValue = ResultVector[1].first;
6324 if (DefaultResult) {
6325 Value *ValueCompare =
6326 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6327 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6328 DefaultResult,
"switch.select");
6330 Value *ValueCompare =
6331 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6332 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6333 SelectValue,
"switch.select");
6337 if (ResultVector.size() == 1 && DefaultResult) {
6339 unsigned CaseCount = CaseValues.
size();
6347 for (
auto *Case : CaseValues)
6348 if (Case->getValue().slt(MinCaseVal->
getValue()))
6353 for (
auto *Case : CaseValues)
6354 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6360 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6364 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6369 if (CaseValues.
size() == 2) {
6371 "switch.selectcmp.case1");
6373 "switch.selectcmp.case2");
6374 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6375 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6388 std::vector<DominatorTree::UpdateType> Updates;
6394 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6399 PHI->removeIncomingValueIf(
6400 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6401 PHI->addIncoming(SelectValue, SelectBB);
6404 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6410 if (DTU && RemovedSuccessors.
insert(Succ).second)
6411 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6413 SI->eraseFromParent();
6428 SwitchCaseResultVectorTy UniqueResults;
6434 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6436 Value *SelectValue =
6448class SwitchLookupTable {
6499 bool LinearMapValWrapped =
false;
6507SwitchLookupTable::SwitchLookupTable(
6511 assert(Values.
size() &&
"Can't build lookup table without values!");
6512 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6515 SingleValue = Values.
begin()->second;
6521 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6527 TableContents[
Idx] = CaseRes;
6529 if (SingleValue && !isa<PoisonValue>(CaseRes) && CaseRes != SingleValue)
6530 SingleValue = isa<PoisonValue>(SingleValue) ? CaseRes :
nullptr;
6534 if (Values.
size() < TableSize) {
6536 "Need a default value to fill the lookup table holes.");
6539 if (!TableContents[
I])
6540 TableContents[
I] = DefaultValue;
6544 bool DefaultValueIsPoison = isa<PoisonValue>(DefaultValue);
6546 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6547 SingleValue =
nullptr;
6553 Kind = SingleValueKind;
6560 bool LinearMappingPossible =
true;
6565 bool NonMonotonic =
false;
6566 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6569 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6571 if (!ConstVal && isa<PoisonValue>(TableContents[
I])) {
6577 ConstVal = dyn_cast<ConstantInt>(Values[0].second);
6583 LinearMappingPossible =
false;
6588 APInt Dist = Val - PrevVal;
6591 }
else if (Dist != DistToPrev) {
6592 LinearMappingPossible =
false;
6600 if (LinearMappingPossible) {
6601 LinearOffset = cast<ConstantInt>(TableContents[0]);
6602 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6603 APInt M = LinearMultiplier->getValue();
6604 bool MayWrap =
true;
6605 if (
isIntN(
M.getBitWidth(), TableSize - 1))
6606 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6607 LinearMapValWrapped = NonMonotonic || MayWrap;
6608 Kind = LinearMapKind;
6615 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6617 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6619 TableInt <<=
IT->getBitWidth();
6621 if (!isa<UndefValue>(TableContents[
I - 1])) {
6622 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6623 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6626 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6627 BitMapElementTy =
IT;
6638 GlobalVariable::PrivateLinkage, Initializer,
6639 "switch.table." + FuncName);
6640 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6649 case SingleValueKind:
6651 case LinearMapKind: {
6654 false,
"switch.idx.cast");
6655 if (!LinearMultiplier->isOne())
6656 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6658 !LinearMapValWrapped);
6660 if (!LinearOffset->isZero())
6663 !LinearMapValWrapped);
6679 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6680 "switch.shiftamt",
true,
true);
6683 Value *DownShifted =
6684 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6686 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6692 Array->getInitializer()->getType()->getArrayNumElements();
6693 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6696 "switch.tableidx.zext");
6700 GEPIndices,
"switch.gep");
6702 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6709bool SwitchLookupTable::wouldFitInRegister(
const DataLayout &
DL,
6711 Type *ElementType) {
6712 auto *
IT = dyn_cast<IntegerType>(ElementType);
6719 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6721 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6730 auto *
IT = dyn_cast<IntegerType>(Ty);
6742 DL.fitsInLegalInteger(
IT->getBitWidth());
6754 return NumCases * 100 >= CaseRange * MinDensity;
6775 if (SI->getNumCases() > TableSize)
6778 bool AllTablesFitInRegister =
true;
6779 bool HasIllegalType =
false;
6780 for (
const auto &
I : ResultTypes) {
6781 Type *Ty =
I.second;
6787 AllTablesFitInRegister =
6788 AllTablesFitInRegister &&
6789 SwitchLookupTable::wouldFitInRegister(
DL, TableSize, Ty);
6794 if (HasIllegalType && !AllTablesFitInRegister)
6799 if (AllTablesFitInRegister)
6816 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6819 return all_of(ResultTypes, [&](
const auto &KV) {
6820 return SwitchLookupTable::wouldFitInRegister(
6849 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6871 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6876 for (
auto ValuePair : Values) {
6879 if (!CaseConst || CaseConst == DefaultConst ||
6880 (CaseConst != TrueConst && CaseConst != FalseConst))
6894 if (DefaultConst == FalseConst) {
6897 ++NumTableCmpReuses;
6900 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6901 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6904 ++NumTableCmpReuses;
6914 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6933 if (SI->getNumCases() < 3)
6938 assert(!SI->cases().empty());
6955 MinCaseVal = CaseVal;
6957 MaxCaseVal = CaseVal;
6962 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6972 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6978 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6986 bool HasDefaultResults =
6988 DefaultResultsList,
DL,
TTI);
6990 for (
const auto &
I : DefaultResultsList) {
6993 DefaultResults[
PHI] = Result;
6997 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6999 if (UseSwitchConditionAsTableIndex)
7008 bool DefaultIsReachable = !SI->defaultDestUndefined();
7010 bool TableHasHoles = (NumResults < TableSize);
7015 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7023 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7026 if (SI->getNumCases() < 4)
7028 if (!
DL.fitsInLegalInteger(TableSize))
7035 std::vector<DominatorTree::UpdateType> Updates;
7041 assert(MaxTableSize >= TableSize &&
7042 "It is impossible for a switch to have more entries than the max "
7043 "representable value of its input integer type's size.");
7048 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7054 if (UseSwitchConditionAsTableIndex) {
7055 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7056 TableIndex = SI->getCondition();
7058 TableIndexOffset = MinCaseVal;
7061 bool MayWrap =
true;
7062 if (!DefaultIsReachable) {
7067 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
7068 "switch.tableidx",
false,
7077 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
7085 return SwitchLookupTable::wouldFitInRegister(
7086 DL, UpperBound, KV.second );
7090 TableSize = std::max(UpperBound, TableSize);
7093 DefaultIsReachable =
false;
7097 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7098 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7101 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7106 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7108 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
7110 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7120 MaskBB->
setName(
"switch.hole_check");
7127 APInt MaskInt(TableSizePowOf2, 0);
7128 APInt One(TableSizePowOf2, 1);
7130 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7131 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
7134 MaskInt |= One <<
Idx;
7136 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7144 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7147 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
7149 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
7150 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
7156 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7159 SI->getDefaultDest()->removePredecessor(BB,
7162 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
7166 const ResultListTy &ResultList = ResultLists[
PHI];
7168 Type *ResultType = ResultList.begin()->second->getType();
7174 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
7177 Value *Result = Table.buildLookup(TableIndex, Builder);
7181 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7184 for (
auto *
User :
PHI->users()) {
7189 PHI->addIncoming(Result, LookupBB);
7194 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
7198 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
7201 if (Succ == SI->getDefaultDest())
7204 if (DTU && RemovedSuccessors.
insert(Succ).second)
7205 Updates.push_back({DominatorTree::Delete, BB, Succ});
7207 SI->eraseFromParent();
7214 ++NumLookupTablesHoles;
7229 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
7230 if (CondTy->getIntegerBitWidth() > 64 ||
7231 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7235 if (SI->getNumCases() < 4)
7243 for (
const auto &
C : SI->cases())
7244 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7252 int64_t
Base = Values[0];
7253 for (
auto &V : Values)
7266 unsigned Shift = 64;
7267 for (
auto &V : Values)
7271 for (
auto &V : Values)
7272 V = (int64_t)((
uint64_t)V >> Shift);
7288 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7291 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7293 Ty, Intrinsic::fshl,
7294 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7295 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7297 for (
auto Case : SI->cases()) {
7298 auto *Orig = Case.getCaseValue();
7299 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7300 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7316 Value *Condition = SI->getCondition();
7318 auto *CondTy = cast<IntegerType>(Condition->
getType());
7320 if (CondTy->getIntegerBitWidth() > 64 ||
7321 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7335 if (SI->getNumCases() < 4)
7341 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7346 for (
const auto &Case : SI->cases()) {
7347 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7364 for (
auto &Case : SI->cases()) {
7365 auto *OrigValue = Case.getCaseValue();
7366 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7367 OrigValue->getValue().countr_zero()));
7374 SI->setCondition(ConditionTrailingZeros);
7383 auto *Cmp = dyn_cast<CmpIntrinsic>(SI->getCondition());
7384 if (!Cmp || !Cmp->hasOneUse())
7395 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7398 if (SI->getNumCases() == 2) {
7405 Succ = SI->getDefaultDest();
7406 SuccWeight = Weights[0];
7408 for (
auto &Case : SI->cases()) {
7409 std::optional<int64_t> Val =
7413 if (!Missing.erase(*Val))
7418 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7421 assert(Missing.size() == 1 &&
"Should have one case left");
7422 Res = *Missing.begin();
7423 }
else if (SI->getNumCases() == 3 && SI->defaultDestUndefined()) {
7425 Unreachable = SI->getDefaultDest();
7427 for (
auto &Case : SI->cases()) {
7428 BasicBlock *NewSucc = Case.getCaseSuccessor();
7429 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7432 OtherSuccWeight += Weight;
7435 SuccWeight = Weight;
7436 }
else if (Succ == NewSucc) {
7442 for (
auto &Case : SI->cases()) {
7443 std::optional<int64_t> Val =
7445 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7447 if (Case.getCaseSuccessor() == Succ) {
7460 Pred = ICmpInst::ICMP_UGT;
7463 Pred = ICmpInst::ICMP_EQ;
7466 Pred = ICmpInst::ICMP_ULT;
7469 if (Cmp->isSigned())
7472 MDNode *NewWeights =
nullptr;
7474 NewWeights =
MDBuilder(SI->getContext())
7481 SI->getMetadata(LLVMContext::MD_unpredictable));
7485 SI->eraseFromParent();
7486 Cmp->eraseFromParent();
7487 if (DTU && Unreachable)
7488 DTU->
applyUpdates({{DominatorTree::Delete, BB, Unreachable}});
7519 "Only supporting unconditional branches for now");
7521 "Expected unconditional branches to have one successor");
7522 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7544 if (
LHS == EKey ||
RHS == EKey ||
LHS == TKey ||
RHS == TKey)
7557 BranchInst *ABI = cast<BranchInst>(
A->getTerminator());
7558 BranchInst *BBI = cast<BranchInst>(
B->getTerminator());
7560 "Only supporting unconditional branches for now");
7567 auto &PredIVs = (*
LHS->PhiPredIVs)[&Phi];
7568 if (PredIVs[
A] != PredIVs[
B])
7577bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *SI,
7591 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7596 if (BB->
size() != 1)
7612 if (Seen.
insert(BB).second) {
7621 BBToSuccessorIndexes[BB].emplace_back(
I);
7630 for (
auto &
IV :
Phi->incoming_values())
7647 bool MadeChange =
false;
7648 for (
auto &SSW : Cases) {
7656 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7657 for (
unsigned Idx : Successors)
7658 SI->setSuccessor(
Idx, (*It)->Dest);
7672 if (isValueEqualityComparison(SI)) {
7676 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7677 return requestResimplify();
7681 if (simplifySwitchOnSelect(SI,
Select))
7682 return requestResimplify();
7687 if (foldValueComparisonIntoPredecessors(SI, Builder))
7688 return requestResimplify();
7694 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7695 return requestResimplify();
7699 return requestResimplify();
7702 return requestResimplify();
7705 return requestResimplify();
7708 return requestResimplify();
7715 if (
Options.ConvertSwitchToLookupTable &&
7717 return requestResimplify();
7720 return requestResimplify();
7723 return requestResimplify();
7726 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
7727 return requestResimplify();
7729 if (simplifyDuplicateSwitchArms(SI, DTU))
7730 return requestResimplify();
7737 bool Changed =
false;
7746 RemovedSuccs.
insert(Dest);
7756 std::vector<DominatorTree::UpdateType> Updates;
7758 for (
auto *RemovedSucc : RemovedSuccs)
7778 if (simplifyIndirectBrOnSelect(IBI, SI))
7779 return requestResimplify();
7811 if (isa<PHINode>(*Succ->
begin()))
7815 if (BB == OtherPred)
7821 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7827 std::vector<DominatorTree::UpdateType> Updates;
7834 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7835 "unexpected successor");
7836 II->setUnwindDest(OtherPred);
7846 if (isa<DbgInfoIntrinsic>(Inst))
7867 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7868 : simplifyCondBranch(
Branch, Builder);
7871bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7883 bool NeedCanonicalLoop =
7894 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7896 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7898 if (
I->isTerminator() &&
7899 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7906 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7916 if (
Options.SpeculateBlocks &&
7919 return requestResimplify();
7927 if (!PPred || (PredPred && PredPred != PPred))
7964 if (!SuccBI || !SuccBI->isConditional())
7968 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7969 !isa<PHINode>(Succ1->
front()) && !isa<PHINode>(Succ2->
front());
7972 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
7998 bool HasWeight =
false;
8003 BBTWeight = BBFWeight = 1;
8008 BB1TWeight = BB1FWeight = 1;
8013 BB2TWeight = BB2FWeight = 1;
8015 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8016 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8027 "Tautological conditional branch should have been eliminated already.");
8030 if (!
Options.SimplifyCondBranch ||
8035 if (isValueEqualityComparison(BI)) {
8040 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8041 return requestResimplify();
8047 if (foldValueComparisonIntoPredecessors(BI, Builder))
8048 return requestResimplify();
8051 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8052 return requestResimplify();
8057 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8070 return requestResimplify();
8076 if (
Options.SpeculateBlocks &&
8079 return requestResimplify();
8088 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8089 return requestResimplify();
8092 Options.HoistLoadsStoresWithCondFaulting &&
8095 auto CanSpeculateConditionalLoadsStores = [&]() {
8098 if (
I.isTerminator()) {
8099 if (
I.getNumSuccessors() > 1)
8103 SpeculatedConditionalLoadsStores.
size() ==
8107 SpeculatedConditionalLoadsStores.
push_back(&
I);
8110 return !SpeculatedConditionalLoadsStores.
empty();
8113 if (CanSpeculateConditionalLoadsStores()) {
8116 return requestResimplify();
8126 return requestResimplify();
8135 return requestResimplify();
8142 return requestResimplify();
8147 if (PBI != BI && PBI->isConditional())
8149 return requestResimplify();
8154 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
8155 if (PBI != BI && PBI->isConditional())
8157 return requestResimplify();
8161 return requestResimplify();
8175 if (
C->isNullValue() || isa<UndefValue>(
C)) {
8179 auto *Use = cast<Instruction>(U);
8181 switch (Use->getOpcode()) {
8184 case Instruction::GetElementPtr:
8185 case Instruction::Ret:
8186 case Instruction::BitCast:
8187 case Instruction::Load:
8188 case Instruction::Store:
8189 case Instruction::Call:
8190 case Instruction::CallBr:
8191 case Instruction::Invoke:
8192 case Instruction::UDiv:
8193 case Instruction::URem:
8197 case Instruction::SDiv:
8198 case Instruction::SRem:
8202 if (FindUse ==
I->user_end())
8204 auto *
Use = cast<Instruction>(*FindUse);
8208 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
8222 if (
GEP->getPointerOperand() ==
I) {
8229 if (!
GEP->hasAllZeroIndices() &&
8230 (!
GEP->isInBounds() ||
8232 GEP->getPointerAddressSpace())))
8233 PtrValueMayBeModified =
true;
8239 bool HasNoUndefAttr =
8240 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8242 if (isa<UndefValue>(
C) && HasNoUndefAttr)
8245 if (
C->isNullValue() && HasNoUndefAttr &&
8246 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8247 return !PtrValueMayBeModified;
8253 if (!LI->isVolatile())
8255 LI->getPointerAddressSpace());
8259 if (!SI->isVolatile())
8261 SI->getPointerAddressSpace())) &&
8262 SI->getPointerOperand() ==
I;
8265 if (
auto *Assume = dyn_cast<AssumeInst>(
Use)) {
8267 if (
I == Assume->getArgOperand(0))
8271 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
8275 if (CB->getCalledOperand() ==
I)
8278 if (
C->isNullValue()) {
8281 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
8282 if (CB->isPassingUndefUB(ArgIdx) &&
8283 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
8285 return !PtrValueMayBeModified;
8288 }
else if (isa<UndefValue>(
C)) {
8292 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
8293 if (CB->isPassingUndefUB(ArgIdx)) {
8313 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8342 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
8350 for (
const auto &Case : SI->cases())
8351 if (Case.getCaseSuccessor() == BB) {
8353 Case.setSuccessor(Unreachable);
8355 if (SI->getDefaultDest() == BB) {
8357 SI->setDefaultDest(Unreachable);
8371bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
8372 bool Changed =
false;
8396 return requestResimplify();
8417 if (
Options.SpeculateBlocks &&
8421 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
8424 Options.SpeculateUnpredictables))
8431 case Instruction::Br:
8432 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
8434 case Instruction::Resume:
8435 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
8437 case Instruction::CleanupRet:
8438 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
8440 case Instruction::Switch:
8441 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
8443 case Instruction::Unreachable:
8444 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
8446 case Instruction::IndirectBr:
8447 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
8455 bool Changed =
false;
8463 Changed |= simplifyOnce(BB);
8464 }
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()
Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
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 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.
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
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.
@ 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.