92using namespace PatternMatch;
94#define DEBUG_TYPE "simplifycfg"
97 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
100 "Temporary development switch used to gradually uplift SimplifyCFG "
101 "into preserving DomTree,"));
110 "Control the amount of phi node folding to perform (default = 2)"));
114 cl::desc(
"Control the maximal total instruction cost that we are willing "
115 "to speculatively execute to fold a 2-entry PHI node into a "
116 "select (default = 4)"));
120 cl::desc(
"Hoist common instructions up to the parent block"));
123 "simplifycfg-hoist-loads-stores-with-cond-faulting",
cl::Hidden,
125 cl::desc(
"Hoist loads/stores if the target supports "
126 "conditional faulting"));
130 cl::desc(
"Control the maximal conditional load/store that we are willing "
131 "to speculatively execute to eliminate conditional branch "
137 cl::desc(
"Allow reordering across at most this many "
138 "instructions when hoisting"));
142 cl::desc(
"Sink common instructions down to the end block"));
146 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
150 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
151 "precede - hoist multiple conditional stores into a single "
152 "predicated store"));
156 cl::desc(
"When merging conditional stores, do so even if the resultant "
157 "basic blocks are unlikely to be if-converted as a result"));
161 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
166 cl::desc(
"Limit maximum recursion depth when calculating costs of "
167 "speculatively executed instructions"));
172 cl::desc(
"Max size of a block which is still considered "
173 "small enough to thread through"));
179 cl::desc(
"Maximum cost of combining conditions when "
180 "folding branches"));
183 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
185 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
186 "to fold branch to common destination when vector operations are "
191 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
195 cl::desc(
"Limit cases to analyze when converting a switch to select"));
197STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
199 "Number of switch instructions turned into linear mapping");
201 "Number of switch instructions turned into lookup tables");
203 NumLookupTablesHoles,
204 "Number of switch instructions turned into lookup tables (holes checked)");
205STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
207 "Number of value comparisons folded into predecessor basic blocks");
209 "Number of branches folded into predecessor basic block");
212 "Number of common instruction 'blocks' hoisted up to the begin block");
214 "Number of common instructions hoisted up to the begin block");
216 "Number of common instruction 'blocks' sunk down to the end block");
218 "Number of common instructions sunk down to the end block");
219STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
221 "Number of invokes with empty resume blocks simplified into calls");
222STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
223STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
230using SwitchCaseResultVectorTy =
239struct ValueEqualityComparisonCase {
246 bool operator<(ValueEqualityComparisonCase RHS)
const {
254class SimplifyCFGOpt {
264 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
265 bool simplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
268 bool performValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
271 bool foldValueComparisonIntoPredecessors(
Instruction *TI,
286 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
289 bool hoistCommonCodeFromSuccessors(
Instruction *TI,
bool AllInstsEqOnly);
290 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
307 :
TTI(
TTI), DTU(DTU),
DL(
DL), LoopHeaders(LoopHeaders), Options(Opts) {
309 "SimplifyCFG is not yet capable of maintaining validity of a "
310 "PostDomTree, so don't ask for it.");
317 bool requestResimplify() {
336 "Only for a pair of incoming blocks at the time!");
342 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
343 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
346 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
347 EquivalenceSet->contains(IV1))
370 if (!SI1Succs.
count(Succ))
376 FailBlocks->insert(Succ);
392 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
394 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
395 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
457 if (AggressiveInsts.
count(
I))
481 for (
Use &
Op :
I->operands())
495 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
496 DL.isNonIntegralPointerType(V->getType()))
501 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
504 if (isa<ConstantPointerNull>(V))
505 return ConstantInt::get(PtrTy, 0);
509 if (CE->getOpcode() == Instruction::IntToPtr)
510 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
515 return cast<ConstantInt>(
533struct ConstantComparesGatherer {
537 Value *CompValue =
nullptr;
540 Value *Extra =
nullptr;
546 unsigned UsedICmps = 0;
553 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
554 ConstantComparesGatherer &
555 operator=(
const ConstantComparesGatherer &) =
delete;
560 bool setValueOnce(
Value *NewVal) {
561 if (CompValue && CompValue != NewVal)
564 return (CompValue !=
nullptr);
578 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
589 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
633 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
635 if (!setValueOnce(RHSVal))
640 ConstantInt::get(
C->getContext(),
641 C->getValue() | Mask));
656 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
658 if (!setValueOnce(RHSVal))
662 Vals.
push_back(ConstantInt::get(
C->getContext(),
663 C->getValue() & ~Mask));
684 Value *CandidateVal =
I->getOperand(0);
687 CandidateVal = RHSVal;
702 if (!setValueOnce(CandidateVal))
707 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
718 void gather(
Value *V) {
729 while (!DFT.
empty()) {
737 if (Visited.
insert(Op1).second)
739 if (Visited.
insert(Op0).second)
746 if (matchInstruction(
I, isEQ))
770 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
771 Cond = dyn_cast<Instruction>(SI->getCondition());
772 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
773 if (BI->isConditional())
774 Cond = dyn_cast<Instruction>(BI->getCondition());
776 Cond = dyn_cast<Instruction>(IBI->getAddress());
788 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
791 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
792 CV =
SI->getCondition();
793 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
794 if (BI->isConditional() && BI->getCondition()->hasOneUse())
795 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
803 Value *
Ptr = PTII->getPointerOperand();
804 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
813BasicBlock *SimplifyCFGOpt::getValueEqualityComparisonCases(
814 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
815 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
816 Cases.reserve(
SI->getNumCases());
817 for (
auto Case :
SI->cases())
818 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
819 Case.getCaseSuccessor()));
820 return SI->getDefaultDest();
826 Cases.push_back(ValueEqualityComparisonCase(
835 std::vector<ValueEqualityComparisonCase> &Cases) {
841 std::vector<ValueEqualityComparisonCase> &C2) {
842 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
845 if (V1->size() > V2->size())
850 if (V1->size() == 1) {
853 for (
const ValueEqualityComparisonCase &VECC : *V2)
854 if (TheVal == VECC.
Value)
861 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
862 while (i1 != e1 && i2 != e2) {
883 SI->setMetadata(LLVMContext::MD_prof,
N);
889 uint32_t FalseWeight,
bool IsExpected) {
890 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
894 if (TrueWeight || FalseWeight)
897 I->setMetadata(LLVMContext::MD_prof,
N);
905bool SimplifyCFGOpt::simplifyEqualityComparisonWithOnlyPredecessor(
911 Value *ThisVal = isValueEqualityComparison(TI);
912 assert(ThisVal &&
"This isn't a value comparison!!");
913 if (ThisVal != PredVal)
920 std::vector<ValueEqualityComparisonCase> PredCases;
922 getValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
926 std::vector<ValueEqualityComparisonCase> ThisCases;
927 BasicBlock *ThisDef = getValueEqualityComparisonCases(TI, ThisCases);
939 if (isa<BranchInst>(TI)) {
942 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
948 ThisCases[0].Dest->removePredecessor(PredDef);
951 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
958 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
966 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
970 <<
"Through successor TI: " << *TI);
978 if (DeadCases.
count(i->getCaseValue())) {
987 std::vector<DominatorTree::UpdateType> Updates;
988 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
990 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
991 DTU->applyUpdates(Updates);
1002 for (
const auto &[
Value, Dest] : PredCases)
1008 assert(TIV &&
"No edge from pred to succ?");
1013 for (
const auto &[
Value, Dest] : ThisCases)
1021 TheRealDest = ThisDef;
1028 if (Succ != CheckEdge) {
1029 if (Succ != TheRealDest)
1030 RemovedSuccs.
insert(Succ);
1033 CheckEdge =
nullptr;
1040 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1047 for (
auto *RemovedSucc : RemovedSuccs)
1048 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1049 DTU->applyUpdates(Updates);
1059struct ConstantIntOrdering {
1061 return LHS->getValue().ult(
RHS->getValue());
1073 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1082 assert(MD &&
"Invalid branch-weight metadata");
1088 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1099 if (Max > UINT_MAX) {
1114 if (BonusInst.isTerminator())
1119 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1143 if (isa<DbgInfoIntrinsic>(BonusInst))
1146 NewBonusInst->
takeName(&BonusInst);
1147 BonusInst.setName(NewBonusInst->
getName() +
".old");
1148 VMap[&BonusInst] = NewBonusInst;
1154 auto *UI = cast<Instruction>(U.getUser());
1155 auto *PN = dyn_cast<PHINode>(UI);
1157 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1158 "If the user is not a PHI node, then it should be in the same "
1159 "block as, and come after, the original bonus instruction.");
1163 if (PN->getIncomingBlock(U) == BB)
1167 assert(PN->getIncomingBlock(U) == PredBlock &&
1168 "Not in block-closed SSA form?");
1169 U.set(NewBonusInst);
1174bool SimplifyCFGOpt::performValueComparisonIntoPredecessorFolding(
1182 std::vector<ValueEqualityComparisonCase> BBCases;
1183 BasicBlock *BBDefault = getValueEqualityComparisonCases(TI, BBCases);
1185 std::vector<ValueEqualityComparisonCase> PredCases;
1186 BasicBlock *PredDefault = getValueEqualityComparisonCases(PTI, PredCases);
1198 if (PredHasWeights) {
1201 if (Weights.
size() != 1 + PredCases.size())
1202 PredHasWeights = SuccHasWeights =
false;
1203 }
else if (SuccHasWeights)
1207 Weights.
assign(1 + PredCases.size(), 1);
1210 if (SuccHasWeights) {
1213 if (SuccWeights.
size() != 1 + BBCases.size())
1214 PredHasWeights = SuccHasWeights =
false;
1215 }
else if (PredHasWeights)
1216 SuccWeights.
assign(1 + BBCases.size(), 1);
1218 if (PredDefault == BB) {
1221 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1222 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1223 if (PredCases[i].Dest != BB)
1224 PTIHandled.insert(PredCases[i].
Value);
1227 std::swap(PredCases[i], PredCases.back());
1229 if (PredHasWeights || SuccHasWeights) {
1231 Weights[0] += Weights[i + 1];
1236 PredCases.pop_back();
1242 if (PredDefault != BBDefault) {
1244 if (DTU && PredDefault != BB)
1245 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1246 PredDefault = BBDefault;
1247 ++NewSuccessors[BBDefault];
1250 unsigned CasesFromPred = Weights.
size();
1252 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1253 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1254 PredCases.push_back(BBCases[i]);
1255 ++NewSuccessors[BBCases[i].Dest];
1256 if (SuccHasWeights || PredHasWeights) {
1260 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1261 ValidTotalSuccWeight += SuccWeights[i + 1];
1265 if (SuccHasWeights || PredHasWeights) {
1266 ValidTotalSuccWeight += SuccWeights[0];
1268 for (
unsigned i = 1; i < CasesFromPred; ++i)
1269 Weights[i] *= ValidTotalSuccWeight;
1271 Weights[0] *= SuccWeights[0];
1277 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1278 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1279 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1280 if (PredCases[i].Dest == BB) {
1283 if (PredHasWeights || SuccHasWeights) {
1284 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1289 std::swap(PredCases[i], PredCases.back());
1290 PredCases.pop_back();
1297 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1298 if (PTIHandled.count(BBCases[i].Value)) {
1300 if (PredHasWeights || SuccHasWeights)
1302 PredCases.push_back(BBCases[i]);
1303 ++NewSuccessors[BBCases[i].Dest];
1310 if (PredHasWeights || SuccHasWeights)
1312 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1313 ++NewSuccessors[BBDefault];
1325 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1327 for (
auto I :
seq(NewSuccessor.second)) {
1331 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1332 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1345 for (ValueEqualityComparisonCase &V : PredCases)
1348 if (PredHasWeights || SuccHasWeights) {
1365 if (!InfLoopBlock) {
1373 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1380 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1382 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1384 DTU->applyUpdates(Updates);
1387 ++NumFoldValueComparisonIntoPredecessors;
1395bool SimplifyCFGOpt::foldValueComparisonIntoPredecessors(
Instruction *TI,
1398 Value *CV = isValueEqualityComparison(TI);
1399 assert(CV &&
"Not a comparison?");
1401 bool Changed =
false;
1404 while (!Preds.empty()) {
1413 Value *PCV = isValueEqualityComparison(PTI);
1419 for (
auto *Succ : FailBlocks) {
1425 performValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1439 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1440 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1441 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1460 if (
I->mayReadFromMemory())
1464 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1481 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1491 if (
auto *CB = dyn_cast<CallBase>(
I))
1492 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1499 if (
auto *J = dyn_cast<Instruction>(
Op))
1500 if (J->getParent() == BB)
1519 auto *C1 = dyn_cast<CallInst>(I1);
1520 auto *C2 = dyn_cast<CallInst>(I2);
1522 if (C1->isMustTailCall() != C2->isMustTailCall())
1530 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1531 if (CB1->cannotMerge() || CB1->isConvergent())
1533 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1534 if (CB2->cannotMerge() || CB2->isConvergent())
1549 if (!I1->hasDbgRecords())
1551 using CurrentAndEndIt =
1552 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1558 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1559 return Pair.first == Pair.second;
1565 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1571 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1573 if (!
Other->hasDbgRecords())
1576 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1583 while (
none_of(Itrs, atEnd)) {
1584 bool HoistDVRs = allIdentical(Itrs);
1585 for (CurrentAndEndIt &Pair : Itrs) {
1599 if (I1->isIdenticalToWhenDefined(I2,
true))
1602 if (
auto *Cmp1 = dyn_cast<CmpInst>(I1))
1603 if (
auto *Cmp2 = dyn_cast<CmpInst>(I2))
1604 return Cmp1->getPredicate() == Cmp2->getSwappedPredicate() &&
1605 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
1606 Cmp1->getOperand(1) == Cmp2->getOperand(0);
1608 if (I1->isCommutative() && I1->isSameOperationAs(I2)) {
1609 return I1->getOperand(0) == I2->
getOperand(1) &&
1674 std::optional<bool> Invert) {
1675 auto &Context = BI->
getParent()->getContext();
1681 Invert.has_value() ? SpeculatedConditionalLoadsStores.
back() : BI);
1682 Value *Mask =
nullptr;
1683 Value *MaskFalse =
nullptr;
1684 Value *MaskTrue =
nullptr;
1685 if (Invert.has_value()) {
1694 auto PeekThroughBitcasts = [](
Value *V) {
1695 while (
auto *BitCast = dyn_cast<BitCastInst>(V))
1696 V = BitCast->getOperand(0);
1699 for (
auto *
I : SpeculatedConditionalLoadsStores) {
1701 if (!Invert.has_value())
1702 Mask =
I->getParent() == BI->getSuccessor(0) ? MaskTrue : MaskFalse;
1707 auto *Op0 =
I->getOperand(0);
1708 CallInst *MaskedLoadStore =
nullptr;
1709 if (
auto *LI = dyn_cast<LoadInst>(
I)) {
1711 auto *Ty =
I->getType();
1713 Value *PassThru =
nullptr;
1714 if (Invert.has_value())
1715 for (
User *U :
I->users())
1716 if ((PN = dyn_cast<PHINode>(U))) {
1727 I->replaceAllUsesWith(NewLoadStore);
1733 StoredVal,
I->getOperand(1), cast<StoreInst>(
I)->getAlign(), Mask);
1743 if (
const MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1745 I->dropUBImplyingAttrsAndUnknownMetadata({LLVMContext::MD_annotation});
1749 I->eraseMetadataIf([](
unsigned MDKind,
MDNode *
Node) {
1750 return Node->getMetadataID() == Metadata::DIAssignIDKind;
1753 I->eraseFromParent();
1760 if (
auto *L = dyn_cast<LoadInst>(
I)) {
1763 }
else if (
auto *S = dyn_cast<StoreInst>(
I)) {
1786class LockstepReverseIterator {
1799 for (
auto *BB : Blocks) {
1801 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1817 for (
auto *&Inst : Insts) {
1818 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1831 for (
auto *&Inst : Insts) {
1832 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1852bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
Instruction *TI,
1853 bool AllInstsEqOnly) {
1873 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1877 if (isa<PHINode>(*SuccItr))
1879 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1882 if (AllInstsEqOnly) {
1891 return !
Term->isSameOperationAs(Term0) ||
1893 Succs[0]->size() != Succ->
size();
1898 LockstepReverseIterator LRI(Succs);
1899 while (LRI.isValid()) {
1916 unsigned NumSkipped = 0;
1919 if (SuccIterPairs.
size() > 2) {
1921 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1922 if (SuccIterPairs.
size() < 2)
1926 bool Changed =
false;
1929 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1930 auto &BB1ItrPair = *SuccIterPairBegin++;
1931 auto OtherSuccIterPairRange =
1938 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1940 return I1->isIdenticalToWhenDefined(I2);
1942 if (!AllDbgInstsAreIdentical) {
1943 while (isa<DbgInfoIntrinsic>(I1))
1944 I1 = &*++BB1ItrPair.first;
1945 for (
auto &SuccIter : OtherSuccIterRange) {
1947 while (isa<DbgInfoIntrinsic>(I2))
1952 bool AllInstsAreIdentical =
true;
1953 bool HasTerminator =
I1->isTerminator();
1954 for (
auto &SuccIter : OtherSuccIterRange) {
1959 AllInstsAreIdentical =
false;
1963 for (
auto &SuccIter : OtherSuccIterRange)
1968 if (HasTerminator) {
1972 if (NumSkipped || !AllInstsAreIdentical) {
1977 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1981 if (AllInstsAreIdentical) {
1982 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1983 AllInstsAreIdentical =
1985 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1987 unsigned SkipFlagsBB2 = Pair.second;
1997 if (AllInstsAreIdentical) {
1999 if (isa<DbgInfoIntrinsic>(I1)) {
2008 for (
auto &SuccIter : OtherSuccIterRange) {
2009 auto *I2 = &*SuccIter++;
2010 assert(isa<DbgInfoIntrinsic>(I2));
2022 for (
auto &SuccIter : OtherSuccIterRange) {
2028 if (
auto *CB = dyn_cast<CallBase>(I1)) {
2029 bool Success = CB->tryIntersectAttributes(cast<CallBase>(I2));
2030 assert(
Success &&
"We should not be trying to hoist callbases "
2031 "with non-intersectable attributes");
2044 NumHoistCommonCode += SuccIterPairs.
size();
2046 NumHoistCommonInstrs += SuccIterPairs.
size();
2055 for (
auto &SuccIterPair : SuccIterPairs) {
2064bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
2068 auto *BI = dyn_cast<BranchInst>(TI);
2070 bool Changed =
false;
2075 auto *I2 = *OtherSuccTIs.
begin();
2091 if (isa<CallBrInst>(I1))
2096 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2098 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
2118 if (!
NT->getType()->isVoidTy()) {
2119 I1->replaceAllUsesWith(NT);
2121 OtherSuccTI->replaceAllUsesWith(NT);
2125 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
2131 for (
auto *OtherSuccTI : OtherSuccTIs)
2132 Locs.
push_back(OtherSuccTI->getDebugLoc());
2144 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
2147 Value *BB1V = PN.getIncomingValueForBlock(BB1);
2148 Value *BB2V = PN.getIncomingValueForBlock(BB2);
2154 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
2159 isa<FPMathOperator>(PN) ? &PN :
nullptr,
2164 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2165 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
2166 PN.setIncomingValue(i, SI);
2177 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
2182 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
2186 DTU->applyUpdates(Updates);
2195 if (
I->isIntDivRem())
2197 return !isa<IntrinsicInst>(
I);
2210 std::optional<unsigned> NumUses;
2211 for (
auto *
I : Insts) {
2213 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
2214 I->getType()->isTokenTy())
2219 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2226 if (
const auto *
C = dyn_cast<CallBase>(
I))
2227 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2231 NumUses =
I->getNumUses();
2232 else if (NumUses !=
I->getNumUses())
2238 for (
auto *
I : Insts) {
2245 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
2247 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
2260 for (
const Use &U : I0->
uses()) {
2261 auto It = PHIOperands.find(&U);
2262 if (It == PHIOperands.end())
2265 if (!
equal(Insts, It->second))
2273 if (isa<CallBase>(I0)) {
2275 return cast<CallBase>(
I)->isIndirectCall();
2277 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2278 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2279 if (HaveIndirectCalls) {
2280 if (!AllCallsAreIndirect)
2284 Value *Callee =
nullptr;
2286 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2288 Callee = CurrCallee;
2289 else if (Callee != CurrCallee)
2295 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2297 if (
Op->getType()->isTokenTy())
2305 if (!
all_of(Insts, SameAsI0)) {
2310 if (isa<LifetimeIntrinsic>(I0) && OI == 1 &&
2312 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2321 for (
auto *
I : Insts)
2322 Ops.push_back(
I->getOperand(OI));
2332 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2337 for (
auto *BB :
Blocks) {
2340 I =
I->getPrevNode();
2341 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2342 if (!isa<DbgInfoIntrinsic>(
I))
2367 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2370 PN->insertBefore(BBEnd->begin());
2371 for (
auto *
I : Insts)
2372 PN->addIncoming(
I->getOperand(O),
I->getParent());
2381 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2384 for (
auto *
I : Insts)
2396 if (
auto *CB = dyn_cast<CallBase>(I0)) {
2397 bool Success = CB->tryIntersectAttributes(cast<CallBase>(
I));
2398 assert(
Success &&
"We should not be trying to sink callbases "
2399 "with non-intersectable attributes");
2409 auto *PN = cast<PHINode>(U);
2410 PN->replaceAllUsesWith(I0);
2411 PN->eraseFromParent();
2415 for (
auto *
I : Insts) {
2420 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2421 I->replaceAllUsesWith(I0);
2422 I->eraseFromParent();
2472 bool HaveNonUnconditionalPredecessors =
false;
2474 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2475 if (PredBr && PredBr->isUnconditional())
2478 HaveNonUnconditionalPredecessors =
true;
2480 if (UnconditionalPreds.
size() < 2)
2493 for (
const Use &U : PN.incoming_values())
2494 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2495 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2497 Ops.push_back(*IncomingVals[Pred]);
2502 LockstepReverseIterator LRI(UnconditionalPreds);
2503 while (LRI.isValid() &&
2505 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2507 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2518 if (!followedByDeoptOrUnreachable) {
2520 auto IsMemOperand = [](
Use &U) {
2521 auto *
I = cast<Instruction>(U.getUser());
2522 if (isa<LoadInst>(
I))
2524 if (isa<StoreInst>(
I))
2532 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2533 unsigned NumPHIInsts = 0;
2534 for (
Use &U : (*LRI)[0]->operands()) {
2535 auto It = PHIOperands.
find(&U);
2536 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2537 return InstructionsToSink.contains(V);
2544 if (IsMemOperand(U) &&
2545 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2552 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2553 return NumPHIInsts <= 1;
2570 while (
Idx < ScanIdx) {
2571 if (!ProfitableToSinkInstruction(LRI)) {
2574 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2577 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2587 if (
Idx < ScanIdx) {
2590 InstructionsToSink = InstructionsProfitableToSink;
2596 !ProfitableToSinkInstruction(LRI) &&
2597 "We already know that the last instruction is unprofitable to sink");
2605 for (
auto *
I : *LRI)
2606 InstructionsProfitableToSink.
erase(
I);
2607 if (!ProfitableToSinkInstruction(LRI)) {
2610 InstructionsToSink = InstructionsProfitableToSink;
2622 bool Changed =
false;
2624 if (HaveNonUnconditionalPredecessors) {
2625 if (!followedByDeoptOrUnreachable) {
2633 bool Profitable =
false;
2634 while (
Idx < ScanIdx) {
2668 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2670 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2678 NumSinkCommonInstrs++;
2682 ++NumSinkCommonCode;
2688struct CompatibleSets {
2706 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2711 return Sets.emplace_back();
2715 getCompatibleSet(
II).emplace_back(
II);
2719 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2723 return II->cannotMerge() ||
II->isInlineAsm();
2725 if (
any_of(Invokes, IsIllegalToMerge))
2730 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2731 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2732 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2733 if (HaveIndirectCalls) {
2734 if (!AllCallsAreIndirect)
2740 Value *CurrCallee =
II->getCalledOperand();
2741 assert(CurrCallee &&
"There is always a called operand.");
2744 else if (Callee != CurrCallee)
2752 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2754 if (
any_of(Invokes, HasNormalDest)) {
2757 if (!
all_of(Invokes, HasNormalDest))
2764 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2766 NormalBB = CurrNormalBB;
2767 else if (NormalBB != CurrNormalBB)
2775 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2786 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2788 UnwindBB = CurrUnwindBB;
2790 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2797 Invokes.front()->getUnwindDest(),
2798 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2804 for (
auto *
II : Invokes.drop_front())
2809 auto IsIllegalToMergeArguments = [](
auto Ops) {
2810 Use &U0 = std::get<0>(Ops);
2811 Use &U1 = std::get<1>(Ops);
2818 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2819 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2820 IsIllegalToMergeArguments))
2832 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2838 bool HasNormalDest =
2839 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2843 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2847 II0->
getParent()->getIterator()->getNextNode();
2852 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2854 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2856 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2858 if (!HasNormalDest) {
2862 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2869 return MergedInvoke;
2877 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2883 SuccBBOfMergedInvoke});
2890 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2893 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2896 for (
Use &U : MergedInvoke->operands()) {
2898 if (MergedInvoke->isCallee(&U)) {
2899 if (!IsIndirectCall)
2901 }
else if (!MergedInvoke->isDataOperand(&U))
2906 return II->getOperand(
U.getOperandNo()) !=
U.get();
2913 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2925 Invokes.front()->getParent());
2933 if (!MergedDebugLoc)
2934 MergedDebugLoc =
II->getDebugLoc();
2942 OrigSuccBB->removePredecessor(
II->getParent());
2947 bool Success = MergedInvoke->tryIntersectAttributes(
II);
2948 assert(
Success &&
"Merged invokes with incompatible attributes");
2951 II->replaceAllUsesWith(MergedInvoke);
2952 II->eraseFromParent();
2955 MergedInvoke->setDebugLoc(MergedDebugLoc);
2956 ++NumInvokeSetsFormed;
2959 DTU->applyUpdates(Updates);
2986 bool Changed =
false;
2992 CompatibleSets Grouper;
2998 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
3002 if (Invokes.
size() < 2)
3014class EphemeralValueTracker {
3018 if (isa<AssumeInst>(
I))
3020 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3022 return EphValues.count(cast<Instruction>(U));
3028 if (isEphemeral(
I)) {
3067 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
3079 unsigned MaxNumInstToLookAt = 9;
3083 if (!MaxNumInstToLookAt)
3085 --MaxNumInstToLookAt;
3088 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
3091 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
3095 if (SI->getPointerOperand() == StorePtr &&
3096 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
3097 SI->getAlign() >= StoreToHoist->
getAlign())
3099 return SI->getValueOperand();
3103 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
3104 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3105 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3107 bool ExplicitlyDereferenceableOnly;
3111 (!ExplicitlyDereferenceableOnly ||
3113 LI->getDataLayout()))) {
3129 unsigned &SpeculatedInstructions,
3137 bool HaveRewritablePHIs =
false;
3155 HaveRewritablePHIs =
true;
3158 if (!OrigCE && !ThenCE)
3165 if (OrigCost + ThenCost > MaxCost)
3172 ++SpeculatedInstructions;
3173 if (SpeculatedInstructions > 1)
3177 return HaveRewritablePHIs;
3181 std::optional<bool> Invert,
3185 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3192 if (!Invert.has_value())
3195 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3199 return BIEndProb < Likely;
3239bool SimplifyCFGOpt::speculativelyExecuteBB(
BranchInst *BI,
3246 if (isa<FCmpInst>(BrCond))
3256 bool Invert =
false;
3275 unsigned SpeculatedInstructions = 0;
3277 Options.HoistLoadsStoresWithCondFaulting;
3279 Value *SpeculatedStoreValue =
nullptr;
3281 EphemeralValueTracker EphTracker;
3284 if (isa<DbgInfoIntrinsic>(
I)) {
3292 if (isa<PseudoProbeInst>(
I)) {
3302 if (EphTracker.track(&
I))
3307 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3309 SpeculatedConditionalLoadsStores.
size() <
3313 if (IsSafeCheapLoadStore)
3314 SpeculatedConditionalLoadsStores.
push_back(&
I);
3316 ++SpeculatedInstructions;
3318 if (SpeculatedInstructions > 1)
3322 if (!IsSafeCheapLoadStore &&
3325 (SpeculatedStoreValue =
3328 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3334 if (!SpeculatedStore && SpeculatedStoreValue)
3335 SpeculatedStore = cast<StoreInst>(&
I);
3340 for (
Use &
Op :
I.operands()) {
3345 ++SinkCandidateUseCounts[OpI];
3352 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3354 ++SpeculatedInstructions;
3355 if (SpeculatedInstructions > 1)
3362 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3365 SpeculatedInstructions,
Cost,
TTI);
3366 if (!Convert ||
Cost > Budget)
3370 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3373 if (SpeculatedStoreValue) {
3377 Value *FalseV = SpeculatedStoreValue;
3381 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3410 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3412 DbgAssign->replaceVariableLocationOp(OrigV, S);
3425 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3427 if (!isa<DbgAssignIntrinsic>(&
I))
3430 I.dropUBImplyingAttrsAndMetadata();
3433 if (EphTracker.contains(&
I)) {
3435 I.eraseFromParent();
3449 It.dropOneDbgRecord(&DR);
3451 std::prev(ThenBB->
end()));
3453 if (!SpeculatedConditionalLoadsStores.
empty())
3471 Value *TrueV = ThenV, *FalseV = OrigV;
3485 if (!isa<DbgAssignIntrinsic>(
I))
3486 I->eraseFromParent();
3496 EphemeralValueTracker EphTracker;
3502 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3503 if (CI->cannotDuplicate() || CI->isConvergent())
3509 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3516 for (
User *U :
I.users()) {
3518 if (UI->
getParent() != BB || isa<PHINode>(UI))
3532 auto *
I = dyn_cast<Instruction>(V);
3533 if (
I &&
I->getParent() == To)
3537 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3549static std::optional<bool>
3565 if (
auto *CB = dyn_cast<ConstantInt>(U))
3570 KnownValues[CB].
insert(Pred);
3574 if (KnownValues.
empty())
3583 for (
const auto &Pair : KnownValues) {
3601 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3604 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3612 EdgeBB->setName(RealDest->
getName() +
".critedge");
3613 EdgeBB->moveBefore(RealDest);
3623 TranslateMap[
Cond] = CB;
3629 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3636 N->insertInto(EdgeBB, InsertPt);
3639 N->setName(BBI->getName() +
".c");
3642 for (
Use &
Op :
N->operands()) {
3644 if (PI != TranslateMap.
end())
3650 if (!BBI->use_empty())
3651 TranslateMap[&*BBI] = V;
3652 if (!
N->mayHaveSideEffects()) {
3653 N->eraseFromParent();
3658 if (!BBI->use_empty())
3659 TranslateMap[&*BBI] =
N;
3665 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3666 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3667 SrcDbgCursor = std::next(BBI);
3669 N->cloneDebugInfoFrom(&*BBI);
3672 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3678 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3679 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3680 InsertPt->cloneDebugInfoFrom(BI);
3683 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3689 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3690 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3701 return std::nullopt;
3711 std::optional<bool> Result;
3712 bool EverChanged =
false;
3716 EverChanged |= Result == std::nullopt || *Result;
3717 }
while (Result == std::nullopt);
3726 bool SpeculateUnpredictables) {
3741 if (isa<ConstantInt>(IfCond))
3748 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3751 "Will have either one or two blocks to speculate.");
3758 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3759 if (!IsUnpredictable) {
3762 (TWeight + FWeight) != 0) {
3767 if (IfBlocks.
size() == 1) {
3769 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3770 if (BIBBProb >= Likely)
3773 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3781 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3782 if (IfCondPhiInst->getParent() == BB)
3790 unsigned NumPhis = 0;
3802 if (SpeculateUnpredictables && IsUnpredictable)
3805 bool Changed =
false;
3816 AggressiveInsts,
Cost, Budget,
TTI, AC) ||
3818 AggressiveInsts,
Cost, Budget,
TTI, AC))
3824 PN = dyn_cast<PHINode>(BB->
begin());
3830 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3841 auto IsBinOpOrAnd = [](
Value *V) {
3858 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3871 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3873 <<
" F: " << IfFalse->
getName() <<
"\n");
3891 isa<FPMathOperator>(PN) ? PN :
nullptr,
3895 PN->eraseFromParent();
3905 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3923 if (Opc == Instruction::And)
3925 if (Opc == Instruction::Or)
3938 bool PredHasWeights =
3940 bool SuccHasWeights =
3942 if (PredHasWeights || SuccHasWeights) {
3943 if (!PredHasWeights)
3944 PredTrueWeight = PredFalseWeight = 1;
3945 if (!SuccHasWeights)
3946 SuccTrueWeight = SuccFalseWeight = 1;
3956static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3960 "Both blocks must end with a conditional branches.");
3962 "PredBB must be a predecessor of BB.");
3970 (PTWeight + PFWeight) != 0) {
3978 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3979 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3983 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3986 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3987 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3993 return std::nullopt;
4006 bool InvertPredCond;
4007 std::tie(CommonSucc, Opc, InvertPredCond) =
4010 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4017 {LLVMContext::MD_annotation});
4020 if (InvertPredCond) {
4033 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4035 SuccTrueWeight, SuccFalseWeight)) {
4042 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4048 (SuccFalseWeight + SuccTrueWeight) +
4049 PredTrueWeight * SuccFalseWeight);
4055 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4056 PredFalseWeight * SuccTrueWeight);
4058 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4076 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
4077 {DominatorTree::Delete, PredBlock, BB}});
4104 ++NumFoldBranchToCommonDest;
4111 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4112 return U->getType()->isVectorTy();
4122 unsigned BonusInstThreshold) {
4136 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
4137 !isa<SelectInst>(
Cond)) ||
4138 Cond->getParent() != BB || !
Cond->hasOneUse())
4148 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
4159 bool InvertPredCond;
4161 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
4193 unsigned NumBonusInsts = 0;
4194 bool SawVectorOp =
false;
4195 const unsigned PredCount = Preds.
size();
4201 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
4212 NumBonusInsts += PredCount;
4220 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4221 auto *UI = cast<Instruction>(U.getUser());
4222 if (
auto *PN = dyn_cast<PHINode>(UI))
4224 return UI->
getParent() == BB &&
I.comesBefore(UI);
4228 if (!
all_of(
I.uses(), IsBCSSAUse))
4232 BonusInstThreshold *
4238 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4248 for (
auto *BB : {BB1, BB2}) {
4252 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4264 Value *AlternativeV =
nullptr) {
4282 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4283 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4284 PHI = cast<PHINode>(
I);
4290 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4291 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4299 if (!AlternativeV &&
4300 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4305 PHI->addIncoming(V, BB);
4315 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4324 if (!PStore || !QStore)
4345 if (
I.mayReadOrWriteMemory())
4347 for (
auto &
I : *QFB)
4348 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4351 for (
auto &
I : *QTB)
4352 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4356 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4372 if (
I.isTerminator())
4376 if (
auto *S = dyn_cast<StoreInst>(&
I))
4380 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4390 "When we run out of budget we will eagerly return from within the "
4391 "per-instruction loop.");
4395 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4397 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4398 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4506 bool InvertPCond =
false, InvertQCond =
false;
4512 if (QFB == PostBB) {
4531 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4534 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4542 for (
auto *BB : {PTB, PFB}) {
4547 PStoreAddresses.
insert(SI->getPointerOperand());
4549 for (
auto *BB : {QTB, QFB}) {
4554 QStoreAddresses.
insert(SI->getPointerOperand());
4560 auto &CommonAddresses = PStoreAddresses;
4562 bool Changed =
false;
4563 for (
auto *
Address : CommonAddresses)
4566 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4584 !BI->
getParent()->getSinglePredecessor())
4586 if (!IfFalseBB->
phis().empty())
4596 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4607 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4608 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4619 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4620 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4699 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4701 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4705 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4708 if (CommonDestProb >= Likely)
4718 unsigned NumPhis = 0;
4740 if (OtherDest == BB) {
4747 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4748 OtherDest = InfLoopBlock;
4768 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4783 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4784 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4787 SuccTrueWeight, SuccFalseWeight);
4789 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4790 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4791 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4792 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4796 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4797 PredOther * SuccCommon,
4798 PredOther * SuccOther};
4827 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4828 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4829 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4830 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4833 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4834 PredOther * SuccCommon};
4857bool SimplifyCFGOpt::simplifyTerminatorOnSelect(
Instruction *OldTerm,
4868 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4875 if (Succ == KeepEdge1)
4876 KeepEdge1 =
nullptr;
4877 else if (Succ == KeepEdge2)
4878 KeepEdge2 =
nullptr;
4883 if (Succ != TrueBB && Succ != FalseBB)
4884 RemovedSuccessors.
insert(Succ);
4892 if (!KeepEdge1 && !KeepEdge2) {
4893 if (TrueBB == FalseBB) {
4901 if (TrueWeight != FalseWeight)
4904 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4926 for (
auto *RemovedSuccessor : RemovedSuccessors)
4927 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4928 DTU->applyUpdates(Updates);
4938bool SimplifyCFGOpt::simplifySwitchOnSelect(
SwitchInst *SI,
4943 if (!TrueVal || !FalseVal)
4948 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4949 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4952 uint32_t TrueWeight = 0, FalseWeight = 0;
4957 if (Weights.
size() == 1 +
SI->getNumCases()) {
4959 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4961 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4966 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4975bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4988 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
5009bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5029 if (
SI->getCondition() != V)
5035 if (
SI->getDefaultDest() != BB) {
5037 assert(VVal &&
"Should have a unique destination value");
5045 return requestResimplify();
5051 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5061 return requestResimplify();
5068 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5093 auto W0 = SIW.getSuccessorWeight(0);
5097 SIW.setSuccessorWeight(0, *NewW);
5099 SIW.addCase(Cst, NewBB, NewW);
5101 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5110 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5111 DTU->applyUpdates(Updates);
5119bool SimplifyCFGOpt::simplifyBranchOnICmpChain(
BranchInst *BI,
5131 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5134 Value *CompVal = ConstantCompare.CompValue;
5135 unsigned UsedICmps = ConstantCompare.UsedICmps;
5136 Value *ExtraCase = ConstantCompare.Extra;
5155 if (ExtraCase && Values.
size() < 2)
5170 <<
" cases into SWITCH. BB is:\n"
5180 nullptr,
"switch.early.test");
5204 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5210 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5211 <<
"\nEXTRABB = " << *BB);
5219 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5226 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
5227 New->addCase(Values[i], EdgeBB);
5233 PHINode *PN = cast<PHINode>(BBI);
5235 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5242 DTU->applyUpdates(Updates);
5244 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5250 return simplifyCommonResume(RI);
5251 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHIIt()) &&
5254 return simplifySingleResume(RI);
5262 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5267 switch (IntrinsicID) {
5268 case Intrinsic::dbg_declare:
5269 case Intrinsic::dbg_value:
5270 case Intrinsic::dbg_label:
5271 case Intrinsic::lifetime_end:
5281bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5291 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5294 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5296 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5297 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5301 if (IncomingBB->getUniqueSuccessor() != BB)
5304 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHIIt());
5306 if (IncomingValue != LandingPad)
5310 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5311 TrivialUnwindBlocks.
insert(IncomingBB);
5315 if (TrivialUnwindBlocks.
empty())
5319 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5323 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5337 TrivialBB->getTerminator()->eraseFromParent();
5340 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5347 return !TrivialUnwindBlocks.empty();
5351bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5355 "Resume must unwind the exception that caused control to here");
5359 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5395 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5411 int Idx = DestPN.getBasicBlockIndex(BB);
5425 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5426 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5428 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5432 DestPN.addIncoming(
Incoming, Pred);
5459 std::vector<DominatorTree::UpdateType> Updates;
5463 if (UnwindDest ==
nullptr) {
5475 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5476 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5503 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5504 if (!SuccessorCleanupPad)
5513 SuccessorCleanupPad->eraseFromParent();
5542 bool Changed =
false;
5571 BBI->dropDbgRecords();
5575 BBI->eraseFromParent();
5581 if (&BB->
front() != UI)
5584 std::vector<DominatorTree::UpdateType> Updates;
5590 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5594 [BB](
auto *
Successor) { return Successor == BB; })) {
5602 "The destinations are guaranteed to be different here.");
5613 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5619 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5620 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5622 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5623 if (i->getCaseSuccessor() != BB) {
5628 i = SU.removeCase(i);
5633 if (DTU &&
SI->getDefaultDest() != BB)
5634 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5635 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5636 if (
II->getUnwindDest() == BB) {
5638 DTU->applyUpdates(Updates);
5642 if (!CI->doesNotThrow())
5643 CI->setDoesNotThrow();
5646 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5647 if (CSI->getUnwindDest() == BB) {
5649 DTU->applyUpdates(Updates);
5658 E = CSI->handler_end();
5661 CSI->removeHandler(
I);
5668 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5669 if (CSI->getNumHandlers() == 0) {
5670 if (CSI->hasUnwindDest()) {
5674 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5675 Updates.push_back({DominatorTree::Insert,
5676 PredecessorOfPredecessor,
5677 CSI->getUnwindDest()});
5678 Updates.push_back({DominatorTree::Delete,
5679 PredecessorOfPredecessor, Predecessor});
5682 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5686 DTU->applyUpdates(Updates);
5695 CSI->eraseFromParent();
5698 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5700 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5701 "Expected to always have an unwind to BB.");
5703 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5711 DTU->applyUpdates(Updates);
5726 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5727 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5735 bool RemoveOrigDefaultBlock =
true) {
5737 auto *BB = Switch->getParent();
5738 auto *OrigDefaultBlock = Switch->getDefaultDest();
5739 if (RemoveOrigDefaultBlock)
5740 OrigDefaultBlock->removePredecessor(BB);
5745 Switch->setDefaultDest(&*NewDefaultBlock);
5748 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5749 if (RemoveOrigDefaultBlock &&
5751 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5759bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(
SwitchInst *SI,
5761 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5764 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5766 auto *BB =
SI->getParent();
5769 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5774 for (
auto Case :
SI->cases()) {
5778 if (Dest == DestA) {
5784 if (Dest == DestB) {
5794 "Single-destination switch should have been folded.");
5796 assert(DestB !=
SI->getDefaultDest());
5797 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5805 ContiguousCases = &CasesA;
5806 ContiguousDest = DestA;
5809 ContiguousCases = &CasesB;
5810 ContiguousDest = DestB;
5819 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5821 Value *Sub =
SI->getCondition();
5822 if (!
Offset->isNullValue())
5837 if (Weights.
size() == 1 +
SI->getNumCases()) {
5840 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5841 if (
SI->getSuccessor(
I) == ContiguousDest)
5842 TrueWeight += Weights[
I];
5844 FalseWeight += Weights[
I];
5846 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5855 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5856 unsigned PreviousEdges = ContiguousCases->
size();
5857 if (ContiguousDest ==
SI->getDefaultDest())
5859 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5860 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5862 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5863 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5864 if (OtherDest ==
SI->getDefaultDest())
5866 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5867 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5875 auto *UnreachableDefault =
SI->getDefaultDest();
5878 SI->eraseFromParent();
5880 if (!HasDefault && DTU)
5881 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5897 unsigned MaxSignificantBitsInCond =
5904 for (
const auto &Case : SI->cases()) {
5905 auto *
Successor = Case.getCaseSuccessor();
5911 const APInt &CaseVal = Case.getCaseValue()->getValue();
5914 DeadCases.
push_back(Case.getCaseValue());
5927 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5928 const unsigned NumUnknownBits =
5931 if (HasDefault && DeadCases.
empty() &&
5932 NumUnknownBits < 64 ) {
5933 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5934 if (SI->getNumCases() == AllNumCases) {
5941 if (SI->getNumCases() == AllNumCases - 1) {
5942 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5949 for (
const auto &Case : SI->cases())
5950 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5952 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5961 if (DeadCases.
empty())
5967 assert(CaseI != SI->case_default() &&
5968 "Case was not found. Probably mistake in DeadCases forming.");
5970 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5975 std::vector<DominatorTree::UpdateType> Updates;
5976 for (
auto *
Successor : UniqueSuccessors)
5977 if (NumPerSuccessorCases[
Successor] == 0)
5978 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5998 if (!Branch || !Branch->isUnconditional())
6004 int Idx =
PHI.getBasicBlockIndex(BB);
6005 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
6008 if (InValue != CaseValue)
6024 ForwardingNodesMap ForwardingNodes;
6026 bool Changed =
false;
6027 for (
const auto &Case : SI->cases()) {
6029 BasicBlock *CaseDest = Case.getCaseSuccessor();
6048 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6049 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6050 count(Phi.blocks(), SwitchBlock) == 1) {
6051 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
6059 ForwardingNodes[Phi].push_back(PhiIdx);
6062 for (
auto &ForwardingNode : ForwardingNodes) {
6063 PHINode *Phi = ForwardingNode.first;
6069 for (
int Index : Indexes)
6070 Phi->setIncomingValue(Index, SI->getCondition());
6080 if (
C->isThreadDependent())
6082 if (
C->isDLLImportDependent())
6085 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
6086 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
6087 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
6093 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
6109 if (
Constant *
C = dyn_cast<Constant>(V))
6125 if (
A->isAllOnesValue())
6127 if (
A->isNullValue())
6133 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
6158 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
6160 if (
I.isTerminator()) {
6162 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6165 CaseDest =
I.getSuccessor(0);
6172 for (
auto &
Use :
I.uses()) {
6175 if (
I->getParent() == CaseDest)
6178 if (Phi->getIncomingBlock(
Use) == CaseDest)
6191 *CommonDest = CaseDest;
6193 if (CaseDest != *CommonDest)
6198 int Idx =
PHI.getBasicBlockIndex(Pred);
6211 Res.push_back(std::make_pair(&
PHI, ConstVal));
6214 return Res.size() > 0;
6220 SwitchCaseResultVectorTy &UniqueResults,
6222 for (
auto &
I : UniqueResults) {
6223 if (
I.first == Result) {
6224 I.second.push_back(CaseVal);
6225 return I.second.size();
6228 UniqueResults.push_back(
6239 SwitchCaseResultVectorTy &UniqueResults,
6243 uintptr_t MaxUniqueResults) {
6244 for (
const auto &
I : SI->cases()) {
6258 const size_t NumCasesForResult =
6266 if (UniqueResults.size() > MaxUniqueResults)
6277 BasicBlock *DefaultDest = SI->getDefaultDest();
6278 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6283 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6284 if ((!DefaultResult &&
6305 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6306 ResultVector[1].second.size() == 1) {
6307 ConstantInt *FirstCase = ResultVector[0].second[0];
6308 ConstantInt *SecondCase = ResultVector[1].second[0];
6309 Value *SelectValue = ResultVector[1].first;
6310 if (DefaultResult) {
6311 Value *ValueCompare =
6312 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6313 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6314 DefaultResult,
"switch.select");
6316 Value *ValueCompare =
6317 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6318 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6319 SelectValue,
"switch.select");
6323 if (ResultVector.size() == 1 && DefaultResult) {
6325 unsigned CaseCount = CaseValues.
size();
6333 for (
auto *Case : CaseValues)
6334 if (Case->getValue().slt(MinCaseVal->
getValue()))
6339 for (
auto *Case : CaseValues)
6340 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6346 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6350 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6355 if (CaseValues.
size() == 2) {
6357 "switch.selectcmp.case1");
6359 "switch.selectcmp.case2");
6360 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6361 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6374 std::vector<DominatorTree::UpdateType> Updates;
6380 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6385 PHI->removeIncomingValueIf(
6386 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6387 PHI->addIncoming(SelectValue, SelectBB);
6390 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6396 if (DTU && RemovedSuccessors.
insert(Succ).second)
6397 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6399 SI->eraseFromParent();
6414 SwitchCaseResultVectorTy UniqueResults;
6420 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6422 Value *SelectValue =
6434class SwitchLookupTable {
6485 bool LinearMapValWrapped =
false;
6493SwitchLookupTable::SwitchLookupTable(
6497 assert(Values.
size() &&
"Can't build lookup table without values!");
6498 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6501 SingleValue = Values.
begin()->second;
6507 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6513 TableContents[
Idx] = CaseRes;
6515 if (SingleValue && !isa<PoisonValue>(CaseRes) && CaseRes != SingleValue)
6516 SingleValue = isa<PoisonValue>(SingleValue) ? CaseRes :
nullptr;
6520 if (Values.
size() < TableSize) {
6522 "Need a default value to fill the lookup table holes.");
6525 if (!TableContents[
I])
6526 TableContents[
I] = DefaultValue;
6530 bool DefaultValueIsPoison = isa<PoisonValue>(DefaultValue);
6532 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6533 SingleValue =
nullptr;
6539 Kind = SingleValueKind;
6546 bool LinearMappingPossible =
true;
6551 bool NonMonotonic =
false;
6552 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6555 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6557 if (!ConstVal && isa<PoisonValue>(TableContents[
I])) {
6563 ConstVal = dyn_cast<ConstantInt>(Values[0].second);
6569 LinearMappingPossible =
false;
6574 APInt Dist = Val - PrevVal;
6577 }
else if (Dist != DistToPrev) {
6578 LinearMappingPossible =
false;
6586 if (LinearMappingPossible) {
6587 LinearOffset = cast<ConstantInt>(TableContents[0]);
6588 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6589 APInt M = LinearMultiplier->getValue();
6590 bool MayWrap =
true;
6591 if (
isIntN(
M.getBitWidth(), TableSize - 1))
6592 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6593 LinearMapValWrapped = NonMonotonic || MayWrap;
6594 Kind = LinearMapKind;
6601 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6603 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6605 TableInt <<=
IT->getBitWidth();
6607 if (!isa<UndefValue>(TableContents[
I - 1])) {
6608 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6609 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6612 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6613 BitMapElementTy =
IT;
6624 GlobalVariable::PrivateLinkage, Initializer,
6625 "switch.table." + FuncName);
6626 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6635 case SingleValueKind:
6637 case LinearMapKind: {
6640 false,
"switch.idx.cast");
6641 if (!LinearMultiplier->isOne())
6642 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6644 !LinearMapValWrapped);
6646 if (!LinearOffset->isZero())
6649 !LinearMapValWrapped);
6665 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6666 "switch.shiftamt",
true,
true);
6669 Value *DownShifted =
6670 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6672 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6678 Array->getInitializer()->getType()->getArrayNumElements();
6679 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6682 "switch.tableidx.zext");
6686 GEPIndices,
"switch.gep");
6688 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6695bool SwitchLookupTable::wouldFitInRegister(
const DataLayout &
DL,
6697 Type *ElementType) {
6698 auto *
IT = dyn_cast<IntegerType>(ElementType);
6705 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6707 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6716 auto *
IT = dyn_cast<IntegerType>(Ty);
6728 DL.fitsInLegalInteger(
IT->getBitWidth());
6740 return NumCases * 100 >= CaseRange * MinDensity;
6761 if (SI->getNumCases() > TableSize)
6764 bool AllTablesFitInRegister =
true;
6765 bool HasIllegalType =
false;
6766 for (
const auto &
I : ResultTypes) {
6767 Type *Ty =
I.second;
6773 AllTablesFitInRegister =
6774 AllTablesFitInRegister &&
6775 SwitchLookupTable::wouldFitInRegister(
DL, TableSize, Ty);
6780 if (HasIllegalType && !AllTablesFitInRegister)
6785 if (AllTablesFitInRegister)
6802 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6805 return all_of(ResultTypes, [&](
const auto &KV) {
6806 return SwitchLookupTable::wouldFitInRegister(
6835 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6857 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6862 for (
auto ValuePair : Values) {
6865 if (!CaseConst || CaseConst == DefaultConst ||
6866 (CaseConst != TrueConst && CaseConst != FalseConst))
6880 if (DefaultConst == FalseConst) {
6883 ++NumTableCmpReuses;
6886 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6887 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6890 ++NumTableCmpReuses;
6900 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6919 if (SI->getNumCases() < 3)
6924 assert(!SI->cases().empty());
6941 MinCaseVal = CaseVal;
6943 MaxCaseVal = CaseVal;
6948 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6958 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6964 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6972 bool HasDefaultResults =
6974 DefaultResultsList,
DL,
TTI);
6976 for (
const auto &
I : DefaultResultsList) {
6979 DefaultResults[
PHI] = Result;
6983 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6985 if (UseSwitchConditionAsTableIndex)
6994 bool DefaultIsReachable = !SI->defaultDestUndefined();
6996 bool TableHasHoles = (NumResults < TableSize);
7001 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7009 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7012 if (SI->getNumCases() < 4)
7014 if (!
DL.fitsInLegalInteger(TableSize))
7021 std::vector<DominatorTree::UpdateType> Updates;
7027 assert(MaxTableSize >= TableSize &&
7028 "It is impossible for a switch to have more entries than the max "
7029 "representable value of its input integer type's size.");
7034 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7040 if (UseSwitchConditionAsTableIndex) {
7041 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7042 TableIndex = SI->getCondition();
7044 TableIndexOffset = MinCaseVal;
7047 bool MayWrap =
true;
7048 if (!DefaultIsReachable) {
7053 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
7054 "switch.tableidx",
false,
7063 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
7071 return SwitchLookupTable::wouldFitInRegister(
7072 DL, UpperBound, KV.second );
7076 TableSize = std::max(UpperBound, TableSize);
7079 DefaultIsReachable =
false;
7083 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7084 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7087 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7092 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7094 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
7096 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7106 MaskBB->
setName(
"switch.hole_check");
7113 APInt MaskInt(TableSizePowOf2, 0);
7114 APInt One(TableSizePowOf2, 1);
7116 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7117 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
7120 MaskInt |= One <<
Idx;
7122 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7130 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7133 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
7135 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
7136 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
7142 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7145 SI->getDefaultDest()->removePredecessor(BB,
7148 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
7152 const ResultListTy &ResultList = ResultLists[
PHI];
7154 Type *ResultType = ResultList.begin()->second->getType();
7160 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
7163 Value *Result = Table.buildLookup(TableIndex, Builder);
7167 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7170 for (
auto *
User :
PHI->users()) {
7175 PHI->addIncoming(Result, LookupBB);
7180 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
7184 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
7187 if (Succ == SI->getDefaultDest())
7190 if (DTU && RemovedSuccessors.
insert(Succ).second)
7191 Updates.push_back({DominatorTree::Delete, BB, Succ});
7193 SI->eraseFromParent();
7200 ++NumLookupTablesHoles;
7215 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
7216 if (CondTy->getIntegerBitWidth() > 64 ||
7217 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7221 if (SI->getNumCases() < 4)
7229 for (
const auto &
C : SI->cases())
7230 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7238 int64_t
Base = Values[0];
7239 for (
auto &V : Values)
7252 unsigned Shift = 64;
7253 for (
auto &V : Values)
7257 for (
auto &V : Values)
7258 V = (int64_t)((
uint64_t)V >> Shift);
7274 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7277 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7279 Ty, Intrinsic::fshl,
7280 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7281 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7283 for (
auto Case : SI->cases()) {
7284 auto *Orig = Case.getCaseValue();
7285 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7286 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7302 Value *Condition = SI->getCondition();
7304 auto *CondTy = cast<IntegerType>(Condition->
getType());
7306 if (CondTy->getIntegerBitWidth() > 64 ||
7307 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7321 if (SI->getNumCases() < 4)
7327 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7332 for (
const auto &Case : SI->cases()) {
7333 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7350 for (
auto &Case : SI->cases()) {
7351 auto *OrigValue = Case.getCaseValue();
7352 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7353 OrigValue->getValue().countr_zero()));
7360 SI->setCondition(ConditionTrailingZeros);
7369 auto *Cmp = dyn_cast<CmpIntrinsic>(SI->getCondition());
7370 if (!Cmp || !Cmp->hasOneUse())
7381 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7384 if (SI->getNumCases() == 2) {
7391 Succ = SI->getDefaultDest();
7392 SuccWeight = Weights[0];
7394 for (
auto &Case : SI->cases()) {
7395 std::optional<int64_t> Val =
7399 if (!Missing.erase(*Val))
7404 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7407 assert(Missing.size() == 1 &&
"Should have one case left");
7408 Res = *Missing.begin();
7409 }
else if (SI->getNumCases() == 3 && SI->defaultDestUndefined()) {
7411 Unreachable = SI->getDefaultDest();
7413 for (
auto &Case : SI->cases()) {
7414 BasicBlock *NewSucc = Case.getCaseSuccessor();
7415 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7418 OtherSuccWeight += Weight;
7421 SuccWeight = Weight;
7422 }
else if (Succ == NewSucc) {
7428 for (
auto &Case : SI->cases()) {
7429 std::optional<int64_t> Val =
7431 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7433 if (Case.getCaseSuccessor() == Succ) {
7446 Pred = ICmpInst::ICMP_UGT;
7449 Pred = ICmpInst::ICMP_EQ;
7452 Pred = ICmpInst::ICMP_ULT;
7455 if (Cmp->isSigned())
7458 MDNode *NewWeights =
nullptr;
7460 NewWeights =
MDBuilder(SI->getContext())
7467 SI->getMetadata(LLVMContext::MD_unpredictable));
7471 SI->eraseFromParent();
7472 Cmp->eraseFromParent();
7473 if (DTU && Unreachable)
7474 DTU->
applyUpdates({{DominatorTree::Delete, BB, Unreachable}});
7505 "Only supporting unconditional branches for now");
7507 "Expected unconditional branches to have one successor");
7508 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7530 if (
LHS == EKey ||
RHS == EKey ||
LHS == TKey ||
RHS == TKey)
7543 BranchInst *ABI = cast<BranchInst>(
A->getTerminator());
7544 BranchInst *BBI = cast<BranchInst>(
B->getTerminator());
7546 "Only supporting unconditional branches for now");
7553 auto &PredIVs = (*
LHS->PhiPredIVs)[&Phi];
7554 if (PredIVs[
A] != PredIVs[
B])
7563bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *SI,
7577 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7582 if (BB->
size() != 1)
7598 if (Seen.
insert(BB).second) {
7607 BBToSuccessorIndexes[BB].emplace_back(
I);
7616 for (
auto &
IV :
Phi->incoming_values())
7633 bool MadeChange =
false;
7634 for (
auto &SSW : Cases) {
7642 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7643 for (
unsigned Idx : Successors)
7644 SI->setSuccessor(
Idx, (*It)->Dest);
7658 if (isValueEqualityComparison(SI)) {
7662 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7663 return requestResimplify();
7667 if (simplifySwitchOnSelect(SI,
Select))
7668 return requestResimplify();
7673 if (foldValueComparisonIntoPredecessors(SI, Builder))
7674 return requestResimplify();
7680 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7681 return requestResimplify();
7685 return requestResimplify();
7688 return requestResimplify();
7691 return requestResimplify();
7694 return requestResimplify();
7701 if (
Options.ConvertSwitchToLookupTable &&
7703 return requestResimplify();
7706 return requestResimplify();
7709 return requestResimplify();
7712 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
7713 return requestResimplify();
7715 if (simplifyDuplicateSwitchArms(SI, DTU))
7716 return requestResimplify();
7723 bool Changed =
false;
7732 RemovedSuccs.
insert(Dest);
7742 std::vector<DominatorTree::UpdateType> Updates;
7744 for (
auto *RemovedSucc : RemovedSuccs)
7764 if (simplifyIndirectBrOnSelect(IBI, SI))
7765 return requestResimplify();
7797 if (isa<PHINode>(*Succ->
begin()))
7801 if (BB == OtherPred)
7807 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7813 std::vector<DominatorTree::UpdateType> Updates;
7820 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7821 "unexpected successor");
7822 II->setUnwindDest(OtherPred);
7832 if (isa<DbgInfoIntrinsic>(Inst))
7853 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7854 : simplifyCondBranch(
Branch, Builder);
7857bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7869 bool NeedCanonicalLoop =
7880 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7882 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7884 if (
I->isTerminator() &&
7885 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7892 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7902 if (
Options.SpeculateBlocks &&
7905 return requestResimplify();
7913 if (!PPred || (PredPred && PredPred != PPred))
7950 if (!SuccBI || !SuccBI->isConditional())
7954 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7955 !isa<PHINode>(Succ1->
front()) && !isa<PHINode>(Succ2->
front());
7958 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
7984 bool HasWeight =
false;
7989 BBTWeight = BBFWeight = 1;
7994 BB1TWeight = BB1FWeight = 1;
7999 BB2TWeight = BB2FWeight = 1;
8001 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8002 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8013 "Tautological conditional branch should have been eliminated already.");
8016 if (!
Options.SimplifyCondBranch ||
8021 if (isValueEqualityComparison(BI)) {
8026 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8027 return requestResimplify();
8033 if (foldValueComparisonIntoPredecessors(BI, Builder))
8034 return requestResimplify();
8037 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8038 return requestResimplify();
8043 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8056 return requestResimplify();
8062 if (
Options.SpeculateBlocks &&
8065 return requestResimplify();
8074 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8075 return requestResimplify();
8078 Options.HoistLoadsStoresWithCondFaulting &&
8081 auto CanSpeculateConditionalLoadsStores = [&]() {
8084 if (
I.isTerminator()) {
8085 if (
I.getNumSuccessors() > 1)
8089 SpeculatedConditionalLoadsStores.
size() ==
8093 SpeculatedConditionalLoadsStores.
push_back(&
I);
8096 return !SpeculatedConditionalLoadsStores.
empty();
8099 if (CanSpeculateConditionalLoadsStores()) {
8102 return requestResimplify();
8112 return requestResimplify();
8121 return requestResimplify();
8128 return requestResimplify();
8133 if (PBI != BI && PBI->isConditional())
8135 return requestResimplify();
8140 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
8141 if (PBI != BI && PBI->isConditional())
8143 return requestResimplify();
8147 return requestResimplify();
8161 if (
C->isNullValue() || isa<UndefValue>(
C)) {
8165 auto *Use = cast<Instruction>(U.getUser());
8167 switch (Use->getOpcode()) {
8170 case Instruction::GetElementPtr:
8171 case Instruction::Ret:
8172 case Instruction::BitCast:
8173 case Instruction::Load:
8174 case Instruction::Store:
8175 case Instruction::Call:
8176 case Instruction::CallBr:
8177 case Instruction::Invoke:
8178 case Instruction::UDiv:
8179 case Instruction::URem:
8183 case Instruction::SDiv:
8184 case Instruction::SRem:
8188 if (FindUse ==
I->use_end())
8190 auto &
Use = *FindUse;
8195 if (
User->getParent() !=
I->getParent() ||
User ==
I ||
8196 User->comesBefore(
I))
8210 if (
GEP->getPointerOperand() ==
I) {
8217 if (!
GEP->hasAllZeroIndices() &&
8218 (!
GEP->isInBounds() ||
8220 GEP->getPointerAddressSpace())))
8221 PtrValueMayBeModified =
true;
8227 bool HasNoUndefAttr =
8228 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8230 if (isa<UndefValue>(
C) && HasNoUndefAttr)
8233 if (
C->isNullValue() && HasNoUndefAttr &&
8234 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8235 return !PtrValueMayBeModified;
8241 if (!LI->isVolatile())
8243 LI->getPointerAddressSpace());
8247 if (!SI->isVolatile())
8249 SI->getPointerAddressSpace())) &&
8250 SI->getPointerOperand() ==
I;
8253 if (
auto *Assume = dyn_cast<AssumeInst>(
User)) {
8255 if (
I == Assume->getArgOperand(0))
8259 if (
auto *CB = dyn_cast<CallBase>(
User)) {
8263 if (CB->getCalledOperand() ==
I)
8266 if (CB->isArgOperand(&
Use)) {
8267 unsigned ArgIdx = CB->getArgOperandNo(&
Use);
8269 if (
C->isNullValue() && CB->isPassingUndefUB(ArgIdx) &&
8270 CB->paramHasAttr(ArgIdx, Attribute::NonNull))
8271 return !PtrValueMayBeModified;
8273 if (isa<UndefValue>(
C) && CB->isPassingUndefUB(ArgIdx))
8290 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8319 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
8327 for (
const auto &Case : SI->cases())
8328 if (Case.getCaseSuccessor() == BB) {
8330 Case.setSuccessor(Unreachable);
8332 if (SI->getDefaultDest() == BB) {
8334 SI->setDefaultDest(Unreachable);
8348bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
8349 bool Changed =
false;
8373 return requestResimplify();
8394 if (
Options.SpeculateBlocks &&
8398 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
8401 Options.SpeculateUnpredictables))
8408 case Instruction::Br:
8409 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
8411 case Instruction::Resume:
8412 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
8414 case Instruction::CleanupRet:
8415 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
8417 case Instruction::Switch:
8418 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
8420 case Instruction::Unreachable:
8421 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
8423 case Instruction::IndirectBr:
8424 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
8432 bool Changed =
false;
8440 Changed |= simplifyOnce(BB);
8441 }
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< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static 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)
static cl::opt< unsigned > HoistLoadsStoresWithCondFaultingThreshold("hoist-loads-stores-with-cond-faulting-threshold", cl::Hidden, cl::init(6), cl::desc("Control the maximal conditional load/store that we are willing " "to speculatively execute to eliminate conditional branch " "(default = 6)"))
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,...
InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
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.
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.
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....
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataSetTy *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
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.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataSetTy *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
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.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataSetTy *IdentityMD=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
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.
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 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.