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);
2192 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
2193 switch (
II->getIntrinsicID()) {
2196 case Intrinsic::lifetime_start:
2197 case Intrinsic::lifetime_end:
2209 if (
I->isIntDivRem())
2211 return !isa<IntrinsicInst>(
I);
2224 std::optional<unsigned> NumUses;
2225 for (
auto *
I : Insts) {
2227 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
2228 I->getType()->isTokenTy())
2233 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
2240 if (
const auto *
C = dyn_cast<CallBase>(
I))
2241 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
2245 NumUses =
I->getNumUses();
2246 else if (NumUses !=
I->getNumUses())
2252 for (
auto *
I : Insts) {
2259 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
2261 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
2274 for (
const Use &U : I0->
uses()) {
2275 auto It = PHIOperands.find(&U);
2276 if (It == PHIOperands.end())
2279 if (!
equal(Insts, It->second))
2287 if (isa<CallBase>(I0)) {
2289 return cast<CallBase>(
I)->isIndirectCall();
2291 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2292 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2293 if (HaveIndirectCalls) {
2294 if (!AllCallsAreIndirect)
2298 Value *Callee =
nullptr;
2300 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2302 Callee = CurrCallee;
2303 else if (Callee != CurrCallee)
2309 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2311 if (
Op->getType()->isTokenTy())
2319 if (!
all_of(Insts, SameAsI0)) {
2326 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2335 for (
auto *
I : Insts)
2336 Ops.push_back(
I->getOperand(OI));
2346 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2351 for (
auto *BB :
Blocks) {
2354 I =
I->getPrevNode();
2355 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2356 if (!isa<DbgInfoIntrinsic>(
I))
2381 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2384 PN->insertBefore(BBEnd->begin());
2385 for (
auto *
I : Insts)
2386 PN->addIncoming(
I->getOperand(O),
I->getParent());
2395 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2398 for (
auto *
I : Insts)
2410 if (
auto *CB = dyn_cast<CallBase>(I0)) {
2411 bool Success = CB->tryIntersectAttributes(cast<CallBase>(
I));
2412 assert(
Success &&
"We should not be trying to sink callbases "
2413 "with non-intersectable attributes");
2423 auto *PN = cast<PHINode>(U);
2424 PN->replaceAllUsesWith(I0);
2425 PN->eraseFromParent();
2429 for (
auto *
I : Insts) {
2434 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2435 I->replaceAllUsesWith(I0);
2436 I->eraseFromParent();
2486 bool HaveNonUnconditionalPredecessors =
false;
2488 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2489 if (PredBr && PredBr->isUnconditional())
2492 HaveNonUnconditionalPredecessors =
true;
2494 if (UnconditionalPreds.
size() < 2)
2507 for (
const Use &U : PN.incoming_values())
2508 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2509 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2511 Ops.push_back(*IncomingVals[Pred]);
2516 LockstepReverseIterator LRI(UnconditionalPreds);
2517 while (LRI.isValid() &&
2519 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2521 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2532 if (!followedByDeoptOrUnreachable) {
2534 auto IsMemOperand = [](
Use &U) {
2535 auto *
I = cast<Instruction>(U.getUser());
2536 if (isa<LoadInst>(
I))
2538 if (isa<StoreInst>(
I))
2546 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2547 unsigned NumPHIInsts = 0;
2548 for (
Use &U : (*LRI)[0]->operands()) {
2549 auto It = PHIOperands.
find(&U);
2550 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2551 return InstructionsToSink.contains(V);
2558 if (IsMemOperand(U) &&
2559 any_of(It->second, [](
Value *V) { return isa<GEPOperator>(V); }))
2566 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2567 return NumPHIInsts <= 1;
2584 while (
Idx < ScanIdx) {
2585 if (!ProfitableToSinkInstruction(LRI)) {
2588 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2591 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2601 if (
Idx < ScanIdx) {
2604 InstructionsToSink = InstructionsProfitableToSink;
2610 !ProfitableToSinkInstruction(LRI) &&
2611 "We already know that the last instruction is unprofitable to sink");
2619 for (
auto *
I : *LRI)
2620 InstructionsProfitableToSink.
erase(
I);
2621 if (!ProfitableToSinkInstruction(LRI)) {
2624 InstructionsToSink = InstructionsProfitableToSink;
2636 bool Changed =
false;
2638 if (HaveNonUnconditionalPredecessors) {
2639 if (!followedByDeoptOrUnreachable) {
2647 bool Profitable =
false;
2648 while (
Idx < ScanIdx) {
2682 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2684 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2692 NumSinkCommonInstrs++;
2696 ++NumSinkCommonCode;
2702struct CompatibleSets {
2720 if (CompatibleSets::shouldBelongToSameSet({
Set.front(),
II}))
2725 return Sets.emplace_back();
2729 getCompatibleSet(
II).emplace_back(
II);
2733 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2737 return II->cannotMerge() ||
II->isInlineAsm();
2739 if (
any_of(Invokes, IsIllegalToMerge))
2744 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2745 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2746 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2747 if (HaveIndirectCalls) {
2748 if (!AllCallsAreIndirect)
2754 Value *CurrCallee =
II->getCalledOperand();
2755 assert(CurrCallee &&
"There is always a called operand.");
2758 else if (Callee != CurrCallee)
2766 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2768 if (
any_of(Invokes, HasNormalDest)) {
2771 if (!
all_of(Invokes, HasNormalDest))
2778 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2780 NormalBB = CurrNormalBB;
2781 else if (NormalBB != CurrNormalBB)
2789 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2800 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2802 UnwindBB = CurrUnwindBB;
2804 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2811 Invokes.front()->getUnwindDest(),
2812 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2818 for (
auto *
II : Invokes.drop_front())
2823 auto IsIllegalToMergeArguments = [](
auto Ops) {
2824 Use &U0 = std::get<0>(Ops);
2825 Use &U1 = std::get<1>(Ops);
2832 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2833 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2834 IsIllegalToMergeArguments))
2846 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2852 bool HasNormalDest =
2853 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2857 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2861 II0->
getParent()->getIterator()->getNextNode();
2866 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2868 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2870 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2872 if (!HasNormalDest) {
2876 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2883 return MergedInvoke;
2891 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2897 SuccBBOfMergedInvoke});
2904 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2907 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2910 for (
Use &U : MergedInvoke->operands()) {
2912 if (MergedInvoke->isCallee(&U)) {
2913 if (!IsIndirectCall)
2915 }
else if (!MergedInvoke->isDataOperand(&U))
2920 return II->getOperand(
U.getOperandNo()) !=
U.get();
2927 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2939 Invokes.front()->getParent());
2947 if (!MergedDebugLoc)
2948 MergedDebugLoc =
II->getDebugLoc();
2956 OrigSuccBB->removePredecessor(
II->getParent());
2961 bool Success = MergedInvoke->tryIntersectAttributes(
II);
2962 assert(
Success &&
"Merged invokes with incompatible attributes");
2965 II->replaceAllUsesWith(MergedInvoke);
2966 II->eraseFromParent();
2969 MergedInvoke->setDebugLoc(MergedDebugLoc);
2970 ++NumInvokeSetsFormed;
2973 DTU->applyUpdates(Updates);
3000 bool Changed =
false;
3006 CompatibleSets Grouper;
3012 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
3016 if (Invokes.
size() < 2)
3028class EphemeralValueTracker {
3032 if (isa<AssumeInst>(
I))
3034 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
3036 return EphValues.count(cast<Instruction>(U));
3042 if (isEphemeral(
I)) {
3081 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
3093 unsigned MaxNumInstToLookAt = 9;
3097 if (!MaxNumInstToLookAt)
3099 --MaxNumInstToLookAt;
3102 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
3105 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
3109 if (SI->getPointerOperand() == StorePtr &&
3110 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
3111 SI->getAlign() >= StoreToHoist->
getAlign())
3113 return SI->getValueOperand();
3117 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
3118 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
3119 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
3121 bool ExplicitlyDereferenceableOnly;
3125 (!ExplicitlyDereferenceableOnly ||
3127 LI->getDataLayout()))) {
3143 unsigned &SpeculatedInstructions,
3151 bool HaveRewritablePHIs =
false;
3169 HaveRewritablePHIs =
true;
3172 if (!OrigCE && !ThenCE)
3179 if (OrigCost + ThenCost > MaxCost)
3186 ++SpeculatedInstructions;
3187 if (SpeculatedInstructions > 1)
3191 return HaveRewritablePHIs;
3195 std::optional<bool> Invert,
3199 if (BI->
getMetadata(LLVMContext::MD_unpredictable))
3206 if (!Invert.has_value())
3209 uint64_t EndWeight = *Invert ? TWeight : FWeight;
3213 return BIEndProb < Likely;
3253bool SimplifyCFGOpt::speculativelyExecuteBB(
BranchInst *BI,
3260 if (isa<FCmpInst>(BrCond))
3270 bool Invert =
false;
3289 unsigned SpeculatedInstructions = 0;
3291 Options.HoistLoadsStoresWithCondFaulting;
3293 Value *SpeculatedStoreValue =
nullptr;
3295 EphemeralValueTracker EphTracker;
3298 if (isa<DbgInfoIntrinsic>(
I)) {
3306 if (isa<PseudoProbeInst>(
I)) {
3316 if (EphTracker.track(&
I))
3321 bool IsSafeCheapLoadStore = HoistLoadsStores &&
3323 SpeculatedConditionalLoadsStores.
size() <
3327 if (IsSafeCheapLoadStore)
3328 SpeculatedConditionalLoadsStores.
push_back(&
I);
3330 ++SpeculatedInstructions;
3332 if (SpeculatedInstructions > 1)
3336 if (!IsSafeCheapLoadStore &&
3339 (SpeculatedStoreValue =
3342 if (!IsSafeCheapLoadStore && !SpeculatedStoreValue &&
3348 if (!SpeculatedStore && SpeculatedStoreValue)
3349 SpeculatedStore = cast<StoreInst>(&
I);
3354 for (
Use &
Op :
I.operands()) {
3359 ++SinkCandidateUseCounts[OpI];
3366 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3368 ++SpeculatedInstructions;
3369 if (SpeculatedInstructions > 1)
3376 SpeculatedStore !=
nullptr || !SpeculatedConditionalLoadsStores.
empty();
3379 SpeculatedInstructions,
Cost,
TTI);
3380 if (!Convert ||
Cost > Budget)
3384 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3387 if (SpeculatedStoreValue) {
3391 Value *FalseV = SpeculatedStoreValue;
3395 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3424 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3426 DbgAssign->replaceVariableLocationOp(OrigV, S);
3439 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3441 if (!isa<DbgAssignIntrinsic>(&
I))
3444 I.dropUBImplyingAttrsAndMetadata();
3447 if (EphTracker.contains(&
I)) {
3449 I.eraseFromParent();
3463 It.dropOneDbgRecord(&DR);
3465 std::prev(ThenBB->
end()));
3467 if (!SpeculatedConditionalLoadsStores.
empty())
3485 Value *TrueV = ThenV, *FalseV = OrigV;
3499 if (!isa<DbgAssignIntrinsic>(
I))
3500 I->eraseFromParent();
3510 EphemeralValueTracker EphTracker;
3516 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3517 if (CI->cannotDuplicate() || CI->isConvergent())
3523 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3530 for (
User *U :
I.users()) {
3532 if (UI->
getParent() != BB || isa<PHINode>(UI))
3546 auto *
I = dyn_cast<Instruction>(V);
3547 if (
I &&
I->getParent() == To)
3551 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3563static std::optional<bool>
3579 if (
auto *CB = dyn_cast<ConstantInt>(U))
3584 KnownValues[CB].
insert(Pred);
3588 if (KnownValues.
empty())
3597 for (
const auto &Pair : KnownValues) {
3615 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3618 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3626 EdgeBB->setName(RealDest->
getName() +
".critedge");
3627 EdgeBB->moveBefore(RealDest);
3637 TranslateMap[
Cond] = CB;
3643 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3650 N->insertInto(EdgeBB, InsertPt);
3653 N->setName(BBI->getName() +
".c");
3656 for (
Use &
Op :
N->operands()) {
3658 if (PI != TranslateMap.
end())
3664 if (!BBI->use_empty())
3665 TranslateMap[&*BBI] = V;
3666 if (!
N->mayHaveSideEffects()) {
3667 N->eraseFromParent();
3672 if (!BBI->use_empty())
3673 TranslateMap[&*BBI] =
N;
3679 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3680 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3681 SrcDbgCursor = std::next(BBI);
3683 N->cloneDebugInfoFrom(&*BBI);
3686 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3692 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3693 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3694 InsertPt->cloneDebugInfoFrom(BI);
3697 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3703 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3704 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3715 return std::nullopt;
3725 std::optional<bool> Result;
3726 bool EverChanged =
false;
3730 EverChanged |= Result == std::nullopt || *Result;
3731 }
while (Result == std::nullopt);
3740 bool SpeculateUnpredictables) {
3755 if (isa<ConstantInt>(IfCond))
3762 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3765 "Will have either one or two blocks to speculate.");
3772 bool IsUnpredictable = DomBI->
getMetadata(LLVMContext::MD_unpredictable);
3773 if (!IsUnpredictable) {
3776 (TWeight + FWeight) != 0) {
3781 if (IfBlocks.
size() == 1) {
3783 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3784 if (BIBBProb >= Likely)
3787 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3795 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3796 if (IfCondPhiInst->getParent() == BB)
3804 unsigned NumPhis = 0;
3816 if (SpeculateUnpredictables && IsUnpredictable)
3819 bool Changed =
false;
3830 AggressiveInsts,
Cost, Budget,
TTI, AC) ||
3832 AggressiveInsts,
Cost, Budget,
TTI, AC))
3838 PN = dyn_cast<PHINode>(BB->
begin());
3844 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3855 auto IsBinOpOrAnd = [](
Value *V) {
3872 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3885 if (IsUnpredictable)
dbgs() <<
" (unpredictable)";
3887 <<
" F: " << IfFalse->
getName() <<
"\n");
3905 isa<FPMathOperator>(PN) ? PN :
nullptr,
3909 PN->eraseFromParent();
3919 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3937 if (Opc == Instruction::And)
3939 if (Opc == Instruction::Or)
3952 bool PredHasWeights =
3954 bool SuccHasWeights =
3956 if (PredHasWeights || SuccHasWeights) {
3957 if (!PredHasWeights)
3958 PredTrueWeight = PredFalseWeight = 1;
3959 if (!SuccHasWeights)
3960 SuccTrueWeight = SuccFalseWeight = 1;
3970static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3974 "Both blocks must end with a conditional branches.");
3976 "PredBB must be a predecessor of BB.");
3984 (PTWeight + PFWeight) != 0) {
3992 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3993 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3997 return {{BI->
getSuccessor(1), Instruction::And,
false}};
4000 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
4001 return {{BI->
getSuccessor(1), Instruction::And,
true}};
4007 return std::nullopt;
4020 bool InvertPredCond;
4021 std::tie(CommonSucc, Opc, InvertPredCond) =
4024 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
4031 {LLVMContext::MD_annotation});
4034 if (InvertPredCond) {
4047 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4049 SuccTrueWeight, SuccFalseWeight)) {
4056 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
4062 (SuccFalseWeight + SuccTrueWeight) +
4063 PredTrueWeight * SuccFalseWeight);
4069 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
4070 PredFalseWeight * SuccTrueWeight);
4072 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
4090 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
4091 {DominatorTree::Delete, PredBlock, BB}});
4118 ++NumFoldBranchToCommonDest;
4125 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
4126 return U->getType()->isVectorTy();
4136 unsigned BonusInstThreshold) {
4150 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
4151 !isa<SelectInst>(
Cond)) ||
4152 Cond->getParent() != BB || !
Cond->hasOneUse())
4162 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
4173 bool InvertPredCond;
4175 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
4207 unsigned NumBonusInsts = 0;
4208 bool SawVectorOp =
false;
4209 const unsigned PredCount = Preds.
size();
4215 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
4226 NumBonusInsts += PredCount;
4234 auto IsBCSSAUse = [BB, &
I](
Use &U) {
4235 auto *UI = cast<Instruction>(U.getUser());
4236 if (
auto *PN = dyn_cast<PHINode>(UI))
4238 return UI->
getParent() == BB &&
I.comesBefore(UI);
4242 if (!
all_of(
I.uses(), IsBCSSAUse))
4246 BonusInstThreshold *
4252 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4262 for (
auto *BB : {BB1, BB2}) {
4266 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4278 Value *AlternativeV =
nullptr) {
4296 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4297 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4298 PHI = cast<PHINode>(
I);
4304 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4305 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4313 if (!AlternativeV &&
4314 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4319 PHI->addIncoming(V, BB);
4329 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4338 if (!PStore || !QStore)
4359 if (
I.mayReadOrWriteMemory())
4361 for (
auto &
I : *QFB)
4362 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4365 for (
auto &
I : *QTB)
4366 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4370 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4386 if (
I.isTerminator())
4390 if (
auto *S = dyn_cast<StoreInst>(&
I))
4394 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4404 "When we run out of budget we will eagerly return from within the "
4405 "per-instruction loop.");
4409 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4411 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4412 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4520 bool InvertPCond =
false, InvertQCond =
false;
4526 if (QFB == PostBB) {
4545 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4548 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4556 for (
auto *BB : {PTB, PFB}) {
4561 PStoreAddresses.
insert(SI->getPointerOperand());
4563 for (
auto *BB : {QTB, QFB}) {
4568 QStoreAddresses.
insert(SI->getPointerOperand());
4574 auto &CommonAddresses = PStoreAddresses;
4576 bool Changed =
false;
4577 for (
auto *
Address : CommonAddresses)
4580 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4598 !BI->
getParent()->getSinglePredecessor())
4600 if (!IfFalseBB->
phis().empty())
4610 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4621 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4622 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4633 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4634 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4713 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4715 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4719 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4722 if (CommonDestProb >= Likely)
4732 unsigned NumPhis = 0;
4754 if (OtherDest == BB) {
4761 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4762 OtherDest = InfLoopBlock;
4782 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4797 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4798 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4801 SuccTrueWeight, SuccFalseWeight);
4803 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4804 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4805 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4806 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4810 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4811 PredOther * SuccCommon,
4812 PredOther * SuccOther};
4841 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4842 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4843 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4844 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4847 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4848 PredOther * SuccCommon};
4871bool SimplifyCFGOpt::simplifyTerminatorOnSelect(
Instruction *OldTerm,
4882 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4889 if (Succ == KeepEdge1)
4890 KeepEdge1 =
nullptr;
4891 else if (Succ == KeepEdge2)
4892 KeepEdge2 =
nullptr;
4897 if (Succ != TrueBB && Succ != FalseBB)
4898 RemovedSuccessors.
insert(Succ);
4906 if (!KeepEdge1 && !KeepEdge2) {
4907 if (TrueBB == FalseBB) {
4915 if (TrueWeight != FalseWeight)
4918 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4940 for (
auto *RemovedSuccessor : RemovedSuccessors)
4941 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4942 DTU->applyUpdates(Updates);
4952bool SimplifyCFGOpt::simplifySwitchOnSelect(
SwitchInst *SI,
4957 if (!TrueVal || !FalseVal)
4962 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4963 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4966 uint32_t TrueWeight = 0, FalseWeight = 0;
4971 if (Weights.
size() == 1 +
SI->getNumCases()) {
4973 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4975 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4980 return simplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4989bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
5002 return simplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
5023bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
5043 if (
SI->getCondition() != V)
5049 if (
SI->getDefaultDest() != BB) {
5051 assert(VVal &&
"Should have a unique destination value");
5059 return requestResimplify();
5065 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
5075 return requestResimplify();
5082 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
5107 auto W0 = SIW.getSuccessorWeight(0);
5111 SIW.setSuccessorWeight(0, *NewW);
5113 SIW.addCase(Cst, NewBB, NewW);
5115 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
5124 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
5125 DTU->applyUpdates(Updates);
5133bool SimplifyCFGOpt::simplifyBranchOnICmpChain(
BranchInst *BI,
5145 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
5148 Value *CompVal = ConstantCompare.CompValue;
5149 unsigned UsedICmps = ConstantCompare.UsedICmps;
5150 Value *ExtraCase = ConstantCompare.Extra;
5169 if (ExtraCase && Values.
size() < 2)
5184 <<
" cases into SWITCH. BB is:\n"
5194 nullptr,
"switch.early.test");
5218 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
5224 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
5225 <<
"\nEXTRABB = " << *BB);
5233 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
5240 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
5241 New->addCase(Values[i], EdgeBB);
5247 PHINode *PN = cast<PHINode>(BBI);
5249 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5256 DTU->applyUpdates(Updates);
5258 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5264 return simplifyCommonResume(RI);
5265 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHI()) &&
5268 return simplifySingleResume(RI);
5276 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5281 switch (IntrinsicID) {
5282 case Intrinsic::dbg_declare:
5283 case Intrinsic::dbg_value:
5284 case Intrinsic::dbg_label:
5285 case Intrinsic::lifetime_end:
5295bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5305 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5308 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5310 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5311 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5315 if (IncomingBB->getUniqueSuccessor() != BB)
5318 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5320 if (IncomingValue != LandingPad)
5324 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5325 TrivialUnwindBlocks.
insert(IncomingBB);
5329 if (TrivialUnwindBlocks.
empty())
5333 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5337 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5351 TrivialBB->getTerminator()->eraseFromParent();
5354 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5361 return !TrivialUnwindBlocks.empty();
5365bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5369 "Resume must unwind the exception that caused control to here");
5373 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5409 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5426 int Idx = DestPN.getBasicBlockIndex(BB);
5440 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5441 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5443 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5447 DestPN.addIncoming(
Incoming, Pred);
5474 std::vector<DominatorTree::UpdateType> Updates;
5478 if (UnwindDest ==
nullptr) {
5490 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5491 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5518 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5519 if (!SuccessorCleanupPad)
5528 SuccessorCleanupPad->eraseFromParent();
5557 bool Changed =
false;
5586 BBI->dropDbgRecords();
5590 BBI->eraseFromParent();
5596 if (&BB->
front() != UI)
5599 std::vector<DominatorTree::UpdateType> Updates;
5605 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5609 [BB](
auto *
Successor) { return Successor == BB; })) {
5617 "The destinations are guaranteed to be different here.");
5628 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5634 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5635 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5637 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5638 if (i->getCaseSuccessor() != BB) {
5643 i = SU.removeCase(i);
5648 if (DTU &&
SI->getDefaultDest() != BB)
5649 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5650 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5651 if (
II->getUnwindDest() == BB) {
5653 DTU->applyUpdates(Updates);
5657 if (!CI->doesNotThrow())
5658 CI->setDoesNotThrow();
5661 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5662 if (CSI->getUnwindDest() == BB) {
5664 DTU->applyUpdates(Updates);
5673 E = CSI->handler_end();
5676 CSI->removeHandler(
I);
5683 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5684 if (CSI->getNumHandlers() == 0) {
5685 if (CSI->hasUnwindDest()) {
5689 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5690 Updates.push_back({DominatorTree::Insert,
5691 PredecessorOfPredecessor,
5692 CSI->getUnwindDest()});
5693 Updates.push_back({DominatorTree::Delete,
5694 PredecessorOfPredecessor, Predecessor});
5697 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5701 DTU->applyUpdates(Updates);
5710 CSI->eraseFromParent();
5713 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5715 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5716 "Expected to always have an unwind to BB.");
5718 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5726 DTU->applyUpdates(Updates);
5741 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5742 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5750 bool RemoveOrigDefaultBlock =
true) {
5752 auto *BB = Switch->getParent();
5753 auto *OrigDefaultBlock = Switch->getDefaultDest();
5754 if (RemoveOrigDefaultBlock)
5755 OrigDefaultBlock->removePredecessor(BB);
5760 Switch->setDefaultDest(&*NewDefaultBlock);
5763 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5764 if (RemoveOrigDefaultBlock &&
5766 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5774bool SimplifyCFGOpt::turnSwitchRangeIntoICmp(
SwitchInst *SI,
5776 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5779 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5781 auto *BB =
SI->getParent();
5784 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5789 for (
auto Case :
SI->cases()) {
5793 if (Dest == DestA) {
5799 if (Dest == DestB) {
5809 "Single-destination switch should have been folded.");
5811 assert(DestB !=
SI->getDefaultDest());
5812 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5820 ContiguousCases = &CasesA;
5821 ContiguousDest = DestA;
5824 ContiguousCases = &CasesB;
5825 ContiguousDest = DestB;
5834 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5836 Value *Sub =
SI->getCondition();
5837 if (!
Offset->isNullValue())
5852 if (Weights.
size() == 1 +
SI->getNumCases()) {
5855 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5856 if (
SI->getSuccessor(
I) == ContiguousDest)
5857 TrueWeight += Weights[
I];
5859 FalseWeight += Weights[
I];
5861 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5870 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5871 unsigned PreviousEdges = ContiguousCases->
size();
5872 if (ContiguousDest ==
SI->getDefaultDest())
5874 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5875 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5877 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5878 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5879 if (OtherDest ==
SI->getDefaultDest())
5881 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5882 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5890 auto *UnreachableDefault =
SI->getDefaultDest();
5893 SI->eraseFromParent();
5895 if (!HasDefault && DTU)
5896 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5912 unsigned MaxSignificantBitsInCond =
5919 for (
const auto &Case : SI->cases()) {
5920 auto *
Successor = Case.getCaseSuccessor();
5926 const APInt &CaseVal = Case.getCaseValue()->getValue();
5929 DeadCases.
push_back(Case.getCaseValue());
5942 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5943 const unsigned NumUnknownBits =
5946 if (HasDefault && DeadCases.
empty() &&
5947 NumUnknownBits < 64 ) {
5948 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5949 if (SI->getNumCases() == AllNumCases) {
5956 if (SI->getNumCases() == AllNumCases - 1) {
5957 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5964 for (
const auto &Case : SI->cases())
5965 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5967 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5976 if (DeadCases.
empty())
5982 assert(CaseI != SI->case_default() &&
5983 "Case was not found. Probably mistake in DeadCases forming.");
5985 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5990 std::vector<DominatorTree::UpdateType> Updates;
5991 for (
auto *
Successor : UniqueSuccessors)
5992 if (NumPerSuccessorCases[
Successor] == 0)
5993 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
6013 if (!Branch || !Branch->isUnconditional())
6019 int Idx =
PHI.getBasicBlockIndex(BB);
6020 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
6023 if (InValue != CaseValue)
6039 ForwardingNodesMap ForwardingNodes;
6041 bool Changed =
false;
6042 for (
const auto &Case : SI->cases()) {
6044 BasicBlock *CaseDest = Case.getCaseSuccessor();
6063 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
6064 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
6065 count(Phi.blocks(), SwitchBlock) == 1) {
6066 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
6074 ForwardingNodes[Phi].push_back(PhiIdx);
6077 for (
auto &ForwardingNode : ForwardingNodes) {
6078 PHINode *Phi = ForwardingNode.first;
6084 for (
int Index : Indexes)
6085 Phi->setIncomingValue(Index, SI->getCondition());
6095 if (
C->isThreadDependent())
6097 if (
C->isDLLImportDependent())
6100 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
6101 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
6102 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
6108 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
6124 if (
Constant *
C = dyn_cast<Constant>(V))
6140 if (
A->isAllOnesValue())
6142 if (
A->isNullValue())
6148 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
6173 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
6175 if (
I.isTerminator()) {
6177 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
6180 CaseDest =
I.getSuccessor(0);
6187 for (
auto &
Use :
I.uses()) {
6190 if (
I->getParent() == CaseDest)
6193 if (Phi->getIncomingBlock(
Use) == CaseDest)
6206 *CommonDest = CaseDest;
6208 if (CaseDest != *CommonDest)
6213 int Idx =
PHI.getBasicBlockIndex(Pred);
6226 Res.push_back(std::make_pair(&
PHI, ConstVal));
6229 return Res.size() > 0;
6235 SwitchCaseResultVectorTy &UniqueResults,
6237 for (
auto &
I : UniqueResults) {
6238 if (
I.first == Result) {
6239 I.second.push_back(CaseVal);
6240 return I.second.size();
6243 UniqueResults.push_back(
6254 SwitchCaseResultVectorTy &UniqueResults,
6258 uintptr_t MaxUniqueResults) {
6259 for (
const auto &
I : SI->cases()) {
6273 const size_t NumCasesForResult =
6281 if (UniqueResults.size() > MaxUniqueResults)
6292 BasicBlock *DefaultDest = SI->getDefaultDest();
6293 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6298 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6299 if ((!DefaultResult &&
6320 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6321 ResultVector[1].second.size() == 1) {
6322 ConstantInt *FirstCase = ResultVector[0].second[0];
6323 ConstantInt *SecondCase = ResultVector[1].second[0];
6324 Value *SelectValue = ResultVector[1].first;
6325 if (DefaultResult) {
6326 Value *ValueCompare =
6327 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6328 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6329 DefaultResult,
"switch.select");
6331 Value *ValueCompare =
6332 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6333 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6334 SelectValue,
"switch.select");
6338 if (ResultVector.size() == 1 && DefaultResult) {
6340 unsigned CaseCount = CaseValues.
size();
6348 for (
auto *Case : CaseValues)
6349 if (Case->getValue().slt(MinCaseVal->
getValue()))
6354 for (
auto *Case : CaseValues)
6355 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6361 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6365 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6370 if (CaseValues.
size() == 2) {
6372 "switch.selectcmp.case1");
6374 "switch.selectcmp.case2");
6375 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6376 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6389 std::vector<DominatorTree::UpdateType> Updates;
6395 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6400 PHI->removeIncomingValueIf(
6401 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6402 PHI->addIncoming(SelectValue, SelectBB);
6405 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6411 if (DTU && RemovedSuccessors.
insert(Succ).second)
6412 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6414 SI->eraseFromParent();
6429 SwitchCaseResultVectorTy UniqueResults;
6435 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6437 Value *SelectValue =
6449class SwitchLookupTable {
6500 bool LinearMapValWrapped =
false;
6508SwitchLookupTable::SwitchLookupTable(
6512 assert(Values.
size() &&
"Can't build lookup table without values!");
6513 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6516 SingleValue = Values.
begin()->second;
6522 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6528 TableContents[
Idx] = CaseRes;
6530 if (SingleValue && !isa<PoisonValue>(CaseRes) && CaseRes != SingleValue)
6531 SingleValue = isa<PoisonValue>(SingleValue) ? CaseRes :
nullptr;
6535 if (Values.
size() < TableSize) {
6537 "Need a default value to fill the lookup table holes.");
6540 if (!TableContents[
I])
6541 TableContents[
I] = DefaultValue;
6545 bool DefaultValueIsPoison = isa<PoisonValue>(DefaultValue);
6547 if (DefaultValue != SingleValue && !DefaultValueIsPoison)
6548 SingleValue =
nullptr;
6554 Kind = SingleValueKind;
6561 bool LinearMappingPossible =
true;
6566 bool NonMonotonic =
false;
6567 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6570 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6572 if (!ConstVal && isa<PoisonValue>(TableContents[
I])) {
6578 ConstVal = dyn_cast<ConstantInt>(Values[0].second);
6584 LinearMappingPossible =
false;
6589 APInt Dist = Val - PrevVal;
6592 }
else if (Dist != DistToPrev) {
6593 LinearMappingPossible =
false;
6601 if (LinearMappingPossible) {
6602 LinearOffset = cast<ConstantInt>(TableContents[0]);
6603 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6604 APInt M = LinearMultiplier->getValue();
6605 bool MayWrap =
true;
6606 if (
isIntN(
M.getBitWidth(), TableSize - 1))
6607 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6608 LinearMapValWrapped = NonMonotonic || MayWrap;
6609 Kind = LinearMapKind;
6616 if (wouldFitInRegister(
DL, TableSize,
ValueType)) {
6618 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6620 TableInt <<=
IT->getBitWidth();
6622 if (!isa<UndefValue>(TableContents[
I - 1])) {
6623 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6624 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6627 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6628 BitMapElementTy =
IT;
6639 GlobalVariable::PrivateLinkage, Initializer,
6640 "switch.table." + FuncName);
6641 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6650 case SingleValueKind:
6652 case LinearMapKind: {
6655 false,
"switch.idx.cast");
6656 if (!LinearMultiplier->isOne())
6657 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6659 !LinearMapValWrapped);
6661 if (!LinearOffset->isZero())
6664 !LinearMapValWrapped);
6680 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6681 "switch.shiftamt",
true,
true);
6684 Value *DownShifted =
6685 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6687 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6693 Array->getInitializer()->getType()->getArrayNumElements();
6694 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6697 "switch.tableidx.zext");
6701 GEPIndices,
"switch.gep");
6703 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6710bool SwitchLookupTable::wouldFitInRegister(
const DataLayout &
DL,
6712 Type *ElementType) {
6713 auto *
IT = dyn_cast<IntegerType>(ElementType);
6720 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6722 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6731 auto *
IT = dyn_cast<IntegerType>(Ty);
6743 DL.fitsInLegalInteger(
IT->getBitWidth());
6755 return NumCases * 100 >= CaseRange * MinDensity;
6776 if (SI->getNumCases() > TableSize)
6779 bool AllTablesFitInRegister =
true;
6780 bool HasIllegalType =
false;
6781 for (
const auto &
I : ResultTypes) {
6782 Type *Ty =
I.second;
6788 AllTablesFitInRegister =
6789 AllTablesFitInRegister &&
6790 SwitchLookupTable::wouldFitInRegister(
DL, TableSize, Ty);
6795 if (HasIllegalType && !AllTablesFitInRegister)
6800 if (AllTablesFitInRegister)
6817 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6820 return all_of(ResultTypes, [&](
const auto &KV) {
6821 return SwitchLookupTable::wouldFitInRegister(
6850 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6872 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6877 for (
auto ValuePair : Values) {
6880 if (!CaseConst || CaseConst == DefaultConst ||
6881 (CaseConst != TrueConst && CaseConst != FalseConst))
6895 if (DefaultConst == FalseConst) {
6898 ++NumTableCmpReuses;
6901 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6902 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6905 ++NumTableCmpReuses;
6915 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6934 if (SI->getNumCases() < 3)
6939 assert(!SI->cases().empty());
6956 MinCaseVal = CaseVal;
6958 MaxCaseVal = CaseVal;
6963 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6973 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6979 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6987 bool HasDefaultResults =
6989 DefaultResultsList,
DL,
TTI);
6991 for (
const auto &
I : DefaultResultsList) {
6994 DefaultResults[
PHI] = Result;
6998 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
7000 if (UseSwitchConditionAsTableIndex)
7009 bool DefaultIsReachable = !SI->defaultDestUndefined();
7011 bool TableHasHoles = (NumResults < TableSize);
7016 bool AllHolesArePoison = TableHasHoles && !HasDefaultResults;
7024 bool NeedMask = AllHolesArePoison && DefaultIsReachable;
7027 if (SI->getNumCases() < 4)
7029 if (!
DL.fitsInLegalInteger(TableSize))
7036 std::vector<DominatorTree::UpdateType> Updates;
7042 assert(MaxTableSize >= TableSize &&
7043 "It is impossible for a switch to have more entries than the max "
7044 "representable value of its input integer type's size.");
7049 Mod.getContext(),
"switch.lookup", CommonDest->
getParent(), CommonDest);
7055 if (UseSwitchConditionAsTableIndex) {
7056 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
7057 TableIndex = SI->getCondition();
7059 TableIndexOffset = MinCaseVal;
7062 bool MayWrap =
true;
7063 if (!DefaultIsReachable) {
7068 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
7069 "switch.tableidx",
false,
7078 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
7086 return SwitchLookupTable::wouldFitInRegister(
7087 DL, UpperBound, KV.second );
7091 TableSize = std::max(UpperBound, TableSize);
7094 DefaultIsReachable =
false;
7098 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
7099 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7102 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7107 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
7109 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
7111 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
7121 MaskBB->
setName(
"switch.hole_check");
7128 APInt MaskInt(TableSizePowOf2, 0);
7129 APInt One(TableSizePowOf2, 1);
7131 const ResultListTy &ResultList = ResultLists[PHIs[0]];
7132 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
7135 MaskInt |= One <<
Idx;
7137 ConstantInt *TableMask = ConstantInt::get(
Mod.getContext(), MaskInt);
7145 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
7148 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
7150 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
7151 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
7157 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
7160 SI->getDefaultDest()->removePredecessor(BB,
7163 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
7167 const ResultListTy &ResultList = ResultLists[
PHI];
7169 Type *ResultType = ResultList.begin()->second->getType();
7175 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
7178 Value *Result = Table.buildLookup(TableIndex, Builder);
7182 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
7185 for (
auto *
User :
PHI->users()) {
7190 PHI->addIncoming(Result, LookupBB);
7195 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
7199 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
7202 if (Succ == SI->getDefaultDest())
7205 if (DTU && RemovedSuccessors.
insert(Succ).second)
7206 Updates.push_back({DominatorTree::Delete, BB, Succ});
7208 SI->eraseFromParent();
7215 ++NumLookupTablesHoles;
7230 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
7231 if (CondTy->getIntegerBitWidth() > 64 ||
7232 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7236 if (SI->getNumCases() < 4)
7244 for (
const auto &
C : SI->cases())
7245 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
7253 int64_t
Base = Values[0];
7254 for (
auto &V : Values)
7267 unsigned Shift = 64;
7268 for (
auto &V : Values)
7272 for (
auto &V : Values)
7273 V = (int64_t)((
uint64_t)V >> Shift);
7289 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7292 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7294 Ty, Intrinsic::fshl,
7295 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7296 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7298 for (
auto Case : SI->cases()) {
7299 auto *Orig = Case.getCaseValue();
7300 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base,
true);
7301 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7317 Value *Condition = SI->getCondition();
7319 auto *CondTy = cast<IntegerType>(Condition->
getType());
7321 if (CondTy->getIntegerBitWidth() > 64 ||
7322 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7336 if (SI->getNumCases() < 4)
7342 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7347 for (
const auto &Case : SI->cases()) {
7348 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7365 for (
auto &Case : SI->cases()) {
7366 auto *OrigValue = Case.getCaseValue();
7367 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7368 OrigValue->getValue().countr_zero()));
7375 SI->setCondition(ConditionTrailingZeros);
7384 auto *Cmp = dyn_cast<CmpIntrinsic>(SI->getCondition());
7385 if (!Cmp || !Cmp->hasOneUse())
7396 uint32_t SuccWeight = 0, OtherSuccWeight = 0;
7399 if (SI->getNumCases() == 2) {
7406 Succ = SI->getDefaultDest();
7407 SuccWeight = Weights[0];
7409 for (
auto &Case : SI->cases()) {
7410 std::optional<int64_t> Val =
7414 if (!Missing.erase(*Val))
7419 OtherSuccWeight += Weights[Case.getSuccessorIndex()];
7422 assert(Missing.size() == 1 &&
"Should have one case left");
7423 Res = *Missing.begin();
7424 }
else if (SI->getNumCases() == 3 && SI->defaultDestUndefined()) {
7426 Unreachable = SI->getDefaultDest();
7428 for (
auto &Case : SI->cases()) {
7429 BasicBlock *NewSucc = Case.getCaseSuccessor();
7430 uint32_t Weight = Weights[Case.getSuccessorIndex()];
7433 OtherSuccWeight += Weight;
7436 SuccWeight = Weight;
7437 }
else if (Succ == NewSucc) {
7443 for (
auto &Case : SI->cases()) {
7444 std::optional<int64_t> Val =
7446 if (!Val || (Val != 1 && Val != 0 && Val != -1))
7448 if (Case.getCaseSuccessor() == Succ) {
7461 Pred = ICmpInst::ICMP_UGT;
7464 Pred = ICmpInst::ICMP_EQ;
7467 Pred = ICmpInst::ICMP_ULT;
7470 if (Cmp->isSigned())
7473 MDNode *NewWeights =
nullptr;
7475 NewWeights =
MDBuilder(SI->getContext())
7482 SI->getMetadata(LLVMContext::MD_unpredictable));
7486 SI->eraseFromParent();
7487 Cmp->eraseFromParent();
7488 if (DTU && Unreachable)
7489 DTU->
applyUpdates({{DominatorTree::Delete, BB, Unreachable}});
7520 "Only supporting unconditional branches for now");
7522 "Expected unconditional branches to have one successor");
7523 assert(Succ->
size() == 1 &&
"Expected just a single branch in the BB");
7545 if (
LHS == EKey ||
RHS == EKey ||
LHS == TKey ||
RHS == TKey)
7558 BranchInst *ABI = cast<BranchInst>(
A->getTerminator());
7559 BranchInst *BBI = cast<BranchInst>(
B->getTerminator());
7561 "Only supporting unconditional branches for now");
7568 auto &PredIVs = (*
LHS->PhiPredIVs)[&Phi];
7569 if (PredIVs[
A] != PredIVs[
B])
7578bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(
SwitchInst *SI,
7592 for (
unsigned I = 0;
I <
SI->getNumSuccessors(); ++
I) {
7597 if (BB->
size() != 1)
7613 if (Seen.
insert(BB).second) {
7622 BBToSuccessorIndexes[BB].emplace_back(
I);
7631 for (
auto &
IV :
Phi->incoming_values())
7648 bool MadeChange =
false;
7649 for (
auto &SSW : Cases) {
7657 const auto &Successors = BBToSuccessorIndexes.
at(SSW.Dest);
7658 for (
unsigned Idx : Successors)
7659 SI->setSuccessor(
Idx, (*It)->Dest);
7673 if (isValueEqualityComparison(SI)) {
7677 if (simplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7678 return requestResimplify();
7682 if (simplifySwitchOnSelect(SI,
Select))
7683 return requestResimplify();
7688 if (foldValueComparisonIntoPredecessors(SI, Builder))
7689 return requestResimplify();
7695 if (
Options.ConvertSwitchRangeToICmp && turnSwitchRangeIntoICmp(SI, Builder))
7696 return requestResimplify();
7700 return requestResimplify();
7703 return requestResimplify();
7706 return requestResimplify();
7709 return requestResimplify();
7716 if (
Options.ConvertSwitchToLookupTable &&
7718 return requestResimplify();
7721 return requestResimplify();
7724 return requestResimplify();
7727 hoistCommonCodeFromSuccessors(SI, !
Options.HoistCommonInsts))
7728 return requestResimplify();
7730 if (simplifyDuplicateSwitchArms(SI, DTU))
7731 return requestResimplify();
7738 bool Changed =
false;
7747 RemovedSuccs.
insert(Dest);
7757 std::vector<DominatorTree::UpdateType> Updates;
7759 for (
auto *RemovedSucc : RemovedSuccs)
7779 if (simplifyIndirectBrOnSelect(IBI, SI))
7780 return requestResimplify();
7812 if (isa<PHINode>(*Succ->
begin()))
7816 if (BB == OtherPred)
7822 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7828 std::vector<DominatorTree::UpdateType> Updates;
7835 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7836 "unexpected successor");
7837 II->setUnwindDest(OtherPred);
7847 if (isa<DbgInfoIntrinsic>(Inst))
7868 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7869 : simplifyCondBranch(
Branch, Builder);
7872bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7884 bool NeedCanonicalLoop =
7895 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7897 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7899 if (
I->isTerminator() &&
7900 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7907 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7917 if (
Options.SpeculateBlocks &&
7920 return requestResimplify();
7928 if (!PPred || (PredPred && PredPred != PPred))
7965 if (!SuccBI || !SuccBI->isConditional())
7969 return Succ1 != Succ && Succ2 != Succ && Succ1 != BB && Succ2 != BB &&
7970 !isa<PHINode>(Succ1->
front()) && !isa<PHINode>(Succ2->
front());
7973 if (!IsSimpleSuccessor(BB1, BB1BI) || !IsSimpleSuccessor(BB2, BB2BI))
7999 bool HasWeight =
false;
8004 BBTWeight = BBFWeight = 1;
8009 BB1TWeight = BB1FWeight = 1;
8014 BB2TWeight = BB2FWeight = 1;
8016 uint64_t Weights[2] = {BBTWeight * BB1FWeight + BBFWeight * BB2TWeight,
8017 BBTWeight * BB1TWeight + BBFWeight * BB2FWeight};
8028 "Tautological conditional branch should have been eliminated already.");
8031 if (!
Options.SimplifyCondBranch ||
8036 if (isValueEqualityComparison(BI)) {
8041 if (simplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
8042 return requestResimplify();
8048 if (foldValueComparisonIntoPredecessors(BI, Builder))
8049 return requestResimplify();
8052 if (&*
I == BI && foldValueComparisonIntoPredecessors(BI, Builder))
8053 return requestResimplify();
8058 if (simplifyBranchOnICmpChain(BI, Builder,
DL))
8071 return requestResimplify();
8077 if (
Options.SpeculateBlocks &&
8080 return requestResimplify();
8089 hoistCommonCodeFromSuccessors(BI, !
Options.HoistCommonInsts))
8090 return requestResimplify();
8093 Options.HoistLoadsStoresWithCondFaulting &&
8096 auto CanSpeculateConditionalLoadsStores = [&]() {
8099 if (
I.isTerminator()) {
8100 if (
I.getNumSuccessors() > 1)
8104 SpeculatedConditionalLoadsStores.
size() ==
8108 SpeculatedConditionalLoadsStores.
push_back(&
I);
8111 return !SpeculatedConditionalLoadsStores.
empty();
8114 if (CanSpeculateConditionalLoadsStores()) {
8117 return requestResimplify();
8127 return requestResimplify();
8136 return requestResimplify();
8143 return requestResimplify();
8148 if (PBI != BI && PBI->isConditional())
8150 return requestResimplify();
8155 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
8156 if (PBI != BI && PBI->isConditional())
8158 return requestResimplify();
8162 return requestResimplify();
8176 if (
C->isNullValue() || isa<UndefValue>(
C)) {
8180 auto *Use = cast<Instruction>(U);
8182 switch (Use->getOpcode()) {
8185 case Instruction::GetElementPtr:
8186 case Instruction::Ret:
8187 case Instruction::BitCast:
8188 case Instruction::Load:
8189 case Instruction::Store:
8190 case Instruction::Call:
8191 case Instruction::CallBr:
8192 case Instruction::Invoke:
8193 case Instruction::UDiv:
8194 case Instruction::URem:
8198 case Instruction::SDiv:
8199 case Instruction::SRem:
8203 if (FindUse ==
I->user_end())
8205 auto *
Use = cast<Instruction>(*FindUse);
8209 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
8223 if (
GEP->getPointerOperand() ==
I) {
8230 if (!
GEP->hasAllZeroIndices() &&
8231 (!
GEP->isInBounds() ||
8233 GEP->getPointerAddressSpace())))
8234 PtrValueMayBeModified =
true;
8240 bool HasNoUndefAttr =
8241 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
8243 if (isa<UndefValue>(
C) && HasNoUndefAttr)
8246 if (
C->isNullValue() && HasNoUndefAttr &&
8247 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
8248 return !PtrValueMayBeModified;
8254 if (!LI->isVolatile())
8256 LI->getPointerAddressSpace());
8260 if (!SI->isVolatile())
8262 SI->getPointerAddressSpace())) &&
8263 SI->getPointerOperand() ==
I;
8266 if (
auto *Assume = dyn_cast<AssumeInst>(
Use)) {
8268 if (
I == Assume->getArgOperand(0))
8272 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
8276 if (CB->getCalledOperand() ==
I)
8279 if (
C->isNullValue()) {
8282 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
8283 if (CB->isPassingUndefUB(ArgIdx) &&
8284 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
8286 return !PtrValueMayBeModified;
8289 }
else if (isa<UndefValue>(
C)) {
8293 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
8294 if (CB->isPassingUndefUB(ArgIdx)) {
8314 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
8343 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
8351 for (
const auto &Case : SI->cases())
8352 if (Case.getCaseSuccessor() == BB) {
8354 Case.setSuccessor(Unreachable);
8356 if (SI->getDefaultDest() == BB) {
8358 SI->setDefaultDest(Unreachable);
8372bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
8373 bool Changed =
false;
8397 return requestResimplify();
8418 if (
Options.SpeculateBlocks &&
8422 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
8425 Options.SpeculateUnpredictables))
8432 case Instruction::Br:
8433 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
8435 case Instruction::Resume:
8436 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
8438 case Instruction::CleanupRet:
8439 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
8441 case Instruction::Switch:
8442 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
8444 case Instruction::Unreachable:
8445 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
8447 case Instruction::IndirectBr:
8448 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
8456 bool Changed =
false;
8464 Changed |= simplifyOnce(BB);
8465 }
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 isLifeTimeMarker(const Instruction *I)
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static bool dominatesMergePoint(Value *V, BasicBlock *BB, Instruction *InsertPt, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, AssumptionCache *AC, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
static bool isSafeCheapLoadStore(const Instruction *I, const TargetTransformInfo &TTI)
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
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,...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
The address of a basic block.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void addRangeRetAttr(const ConstantRange &CR)
adds the range attribute to the list of attributes.
This class represents a function call, abstracting a target machine's calling convention.
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getPredicate() const
Return the predicate for this instruction.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
bool isEmptySet() const
Return true if this set contains no members.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DILocation * getMergedLocations(ArrayRef< DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Implements a dense probed hash-table based set.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
bool hasPostDomTree() const
Returns true if it holds a PostDomTreeT.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
UnreachableInst * CreateUnreachable()
Value * CreateSelectFMF(Value *C, Value *True, Value *False, FMFSource FMFSource, const Twine &Name="", Instruction *MDFrom=nullptr)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
CallInst * CreateMaskedLoad(Type *Ty, Value *Ptr, Align Alignment, Value *Mask, Value *PassThru=nullptr, const Twine &Name="")
Create a call to Masked Load intrinsic.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
CallInst * CreateMaskedStore(Value *Val, Value *Ptr, Align Alignment, Value *Mask)
Create a call to Masked Store intrinsic.
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
@ CompareUsingIntersectedAttrs
Check for equivalence with intersected callbase attrs.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
static unsigned getPointerOperandIndex()
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents a cast from a pointer to an integer.
Resume the propagation of an exception.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
static unsigned getPointerOperandIndex()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
unsigned getOperandNo() const
Return the operand # of this use in its User.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
static constexpr uint64_t MaximumAlignment
Value(Type *Ty, unsigned scid)
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ArchKind & operator--(ArchKind &Kind)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
ThreeOps_match< decltype(m_Value()), LHS, RHS, Instruction::Select, true > m_c_Select(const LHS &L, const RHS &R)
Match Select(C, LHS, RHS) or Select(C, RHS, LHS)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
auto pred_end(const MachineBasicBlock *BB)
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
APInt operator*(APInt a, uint64_t RHS)
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Align getLoadStoreAlignment(const Value *I)
A helper function that returns the alignment of load or store instruction.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
auto unique(Range &&R, Predicate P)
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
auto succ_size(const MachineBasicBlock *BB)
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ And
Bitwise or logical AND of integers.
bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
constexpr unsigned BitWidth
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
auto pred_begin(const MachineBasicBlock *BB)
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
bool foldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Checking whether two cases of SI are equal depends on the contents of the BasicBlock and the incoming...
DenseMap< PHINode *, SmallDenseMap< BasicBlock *, Value *, 8 > > * PhiPredIVs
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
static const SwitchSuccWrapper * getEmptyKey()
static const SwitchSuccWrapper * getTombstoneKey()
static unsigned getHashValue(const SwitchSuccWrapper *SSW)
static bool isEqual(const SwitchSuccWrapper *LHS, const SwitchSuccWrapper *RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
A MapVector that performs no allocations if smaller than a certain size.