90using namespace PatternMatch;
92#define DEBUG_TYPE "simplifycfg"
95 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
97 cl::desc(
"Temorary development switch used to gradually uplift SimplifyCFG "
98 "into preserving DomTree,"));
107 "Control the amount of phi node folding to perform (default = 2)"));
111 cl::desc(
"Control the maximal total instruction cost that we are willing "
112 "to speculatively execute to fold a 2-entry PHI node into a "
113 "select (default = 4)"));
117 cl::desc(
"Hoist common instructions up to the parent block"));
122 cl::desc(
"Allow reordering across at most this many "
123 "instructions when hoisting"));
127 cl::desc(
"Sink common instructions down to the end block"));
131 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
135 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
136 "precede - hoist multiple conditional stores into a single "
137 "predicated store"));
141 cl::desc(
"When merging conditional stores, do so even if the resultant "
142 "basic blocks are unlikely to be if-converted as a result"));
146 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
151 cl::desc(
"Limit maximum recursion depth when calculating costs of "
152 "speculatively executed instructions"));
157 cl::desc(
"Max size of a block which is still considered "
158 "small enough to thread through"));
164 cl::desc(
"Maximum cost of combining conditions when "
165 "folding branches"));
168 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
170 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
171 "to fold branch to common destination when vector operations are "
176 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
180 cl::desc(
"Limit cases to analyze when converting a switch to select"));
182STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
184 "Number of switch instructions turned into linear mapping");
186 "Number of switch instructions turned into lookup tables");
188 NumLookupTablesHoles,
189 "Number of switch instructions turned into lookup tables (holes checked)");
190STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
192 "Number of value comparisons folded into predecessor basic blocks");
194 "Number of branches folded into predecessor basic block");
197 "Number of common instruction 'blocks' hoisted up to the begin block");
199 "Number of common instructions hoisted up to the begin block");
201 "Number of common instruction 'blocks' sunk down to the end block");
203 "Number of common instructions sunk down to the end block");
204STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
206 "Number of invokes with empty resume blocks simplified into calls");
207STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
208STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
215using SwitchCaseResultVectorTy =
224struct ValueEqualityComparisonCase {
231 bool operator<(ValueEqualityComparisonCase RHS)
const {
239class SimplifyCFGOpt {
249 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
250 bool SimplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
253 bool PerformValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
256 bool FoldValueComparisonIntoPredecessors(
Instruction *TI,
270 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
273 bool hoistCommonCodeFromSuccessors(
BasicBlock *BB,
bool EqTermsOnly);
274 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
293 "SimplifyCFG is not yet capable of maintaining validity of a "
294 "PostDomTree, so don't ask for it.");
301 bool requestResimplify() {
320 "Only for a pair of incoming blocks at the time!");
326 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
327 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
330 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
331 EquivalenceSet->contains(IV1))
354 if (!SI1Succs.
count(Succ))
360 FailBlocks->insert(Succ);
376 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
378 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
379 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
388 assert((!isa<Instruction>(
I) ||
390 "Instruction is not safe to speculatively execute!");
416 unsigned Depth = 0) {
445 if (AggressiveInsts.
count(
I))
469 for (
Use &
Op :
I->operands())
483 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
484 DL.isNonIntegralPointerType(V->getType()))
489 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
492 if (isa<ConstantPointerNull>(V))
493 return ConstantInt::get(PtrTy, 0);
497 if (CE->getOpcode() == Instruction::IntToPtr)
498 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
503 return cast<ConstantInt>(
521struct ConstantComparesGatherer {
525 Value *CompValue =
nullptr;
528 Value *Extra =
nullptr;
534 unsigned UsedICmps = 0;
541 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
542 ConstantComparesGatherer &
543 operator=(
const ConstantComparesGatherer &) =
delete;
548 bool setValueOnce(
Value *NewVal) {
549 if (CompValue && CompValue != NewVal)
552 return (CompValue !=
nullptr);
566 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
577 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
621 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
623 if (!setValueOnce(RHSVal))
628 ConstantInt::get(
C->getContext(),
629 C->getValue() | Mask));
644 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
646 if (!setValueOnce(RHSVal))
650 Vals.
push_back(ConstantInt::get(
C->getContext(),
651 C->getValue() & ~Mask));
672 Value *CandidateVal =
I->getOperand(0);
675 CandidateVal = RHSVal;
690 if (!setValueOnce(CandidateVal))
695 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
706 void gather(
Value *V) {
717 while (!DFT.
empty()) {
725 if (Visited.
insert(Op1).second)
727 if (Visited.
insert(Op0).second)
734 if (matchInstruction(
I, isEQ))
758 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
759 Cond = dyn_cast<Instruction>(SI->getCondition());
760 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
761 if (BI->isConditional())
762 Cond = dyn_cast<Instruction>(BI->getCondition());
764 Cond = dyn_cast<Instruction>(IBI->getAddress());
776 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
779 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
780 CV =
SI->getCondition();
781 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
782 if (BI->isConditional() && BI->getCondition()->hasOneUse())
783 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
791 Value *
Ptr = PTII->getPointerOperand();
792 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
801BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
802 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
803 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
804 Cases.reserve(
SI->getNumCases());
805 for (
auto Case :
SI->cases())
806 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
807 Case.getCaseSuccessor()));
808 return SI->getDefaultDest();
814 Cases.push_back(ValueEqualityComparisonCase(
823 std::vector<ValueEqualityComparisonCase> &Cases) {
829 std::vector<ValueEqualityComparisonCase> &C2) {
830 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
833 if (V1->size() > V2->size())
838 if (V1->size() == 1) {
841 for (
const ValueEqualityComparisonCase &VECC : *V2)
842 if (TheVal == VECC.
Value)
849 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
850 while (i1 != e1 && i2 != e2) {
869 SI->setMetadata(LLVMContext::MD_prof,
N);
876 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
880 if (TrueWeight || FalseWeight)
883 I->setMetadata(LLVMContext::MD_prof,
N);
891bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
897 Value *ThisVal = isValueEqualityComparison(TI);
898 assert(ThisVal &&
"This isn't a value comparison!!");
899 if (ThisVal != PredVal)
906 std::vector<ValueEqualityComparisonCase> PredCases;
908 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
912 std::vector<ValueEqualityComparisonCase> ThisCases;
913 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
925 if (isa<BranchInst>(TI)) {
928 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
934 ThisCases[0].Dest->removePredecessor(PredDef);
937 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
944 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
952 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
956 <<
"Through successor TI: " << *TI);
964 if (DeadCases.
count(i->getCaseValue())) {
973 std::vector<DominatorTree::UpdateType> Updates;
974 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
976 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
977 DTU->applyUpdates(Updates);
988 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
989 if (PredCases[i].Dest == TIBB) {
992 TIV = PredCases[i].
Value;
994 assert(TIV &&
"No edge from pred to succ?");
999 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1000 if (ThisCases[i].
Value == TIV) {
1001 TheRealDest = ThisCases[i].Dest;
1007 TheRealDest = ThisDef;
1014 if (Succ != CheckEdge) {
1015 if (Succ != TheRealDest)
1016 RemovedSuccs.
insert(Succ);
1019 CheckEdge =
nullptr;
1026 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1033 for (
auto *RemovedSucc : RemovedSuccs)
1034 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1035 DTU->applyUpdates(Updates);
1045struct ConstantIntOrdering {
1047 return LHS->getValue().ult(
RHS->getValue());
1059 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1077 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1088 if (Max > UINT_MAX) {
1103 if (BonusInst.isTerminator())
1108 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1132 if (isa<DbgInfoIntrinsic>(BonusInst))
1135 NewBonusInst->
takeName(&BonusInst);
1136 BonusInst.setName(NewBonusInst->
getName() +
".old");
1137 VMap[&BonusInst] = NewBonusInst;
1143 auto *UI = cast<Instruction>(U.getUser());
1144 auto *PN = dyn_cast<PHINode>(UI);
1146 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1147 "If the user is not a PHI node, then it should be in the same "
1148 "block as, and come after, the original bonus instruction.");
1152 if (PN->getIncomingBlock(U) == BB)
1156 assert(PN->getIncomingBlock(U) == PredBlock &&
1157 "Not in block-closed SSA form?");
1158 U.set(NewBonusInst);
1163bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1171 std::vector<ValueEqualityComparisonCase> BBCases;
1172 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1174 std::vector<ValueEqualityComparisonCase> PredCases;
1175 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1187 if (PredHasWeights) {
1190 if (Weights.
size() != 1 + PredCases.size())
1191 PredHasWeights = SuccHasWeights =
false;
1192 }
else if (SuccHasWeights)
1196 Weights.
assign(1 + PredCases.size(), 1);
1199 if (SuccHasWeights) {
1202 if (SuccWeights.
size() != 1 + BBCases.size())
1203 PredHasWeights = SuccHasWeights =
false;
1204 }
else if (PredHasWeights)
1205 SuccWeights.
assign(1 + BBCases.size(), 1);
1207 if (PredDefault == BB) {
1210 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1211 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1212 if (PredCases[i].Dest != BB)
1213 PTIHandled.insert(PredCases[i].
Value);
1216 std::swap(PredCases[i], PredCases.back());
1218 if (PredHasWeights || SuccHasWeights) {
1220 Weights[0] += Weights[i + 1];
1225 PredCases.pop_back();
1231 if (PredDefault != BBDefault) {
1233 if (DTU && PredDefault != BB)
1234 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1235 PredDefault = BBDefault;
1236 ++NewSuccessors[BBDefault];
1239 unsigned CasesFromPred = Weights.
size();
1241 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1242 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1243 PredCases.push_back(BBCases[i]);
1244 ++NewSuccessors[BBCases[i].Dest];
1245 if (SuccHasWeights || PredHasWeights) {
1249 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1250 ValidTotalSuccWeight += SuccWeights[i + 1];
1254 if (SuccHasWeights || PredHasWeights) {
1255 ValidTotalSuccWeight += SuccWeights[0];
1257 for (
unsigned i = 1; i < CasesFromPred; ++i)
1258 Weights[i] *= ValidTotalSuccWeight;
1260 Weights[0] *= SuccWeights[0];
1266 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1267 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1268 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1269 if (PredCases[i].Dest == BB) {
1272 if (PredHasWeights || SuccHasWeights) {
1273 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1278 std::swap(PredCases[i], PredCases.back());
1279 PredCases.pop_back();
1286 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1287 if (PTIHandled.count(BBCases[i].Value)) {
1289 if (PredHasWeights || SuccHasWeights)
1291 PredCases.push_back(BBCases[i]);
1292 ++NewSuccessors[BBCases[i].Dest];
1299 if (PredHasWeights || SuccHasWeights)
1301 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1302 ++NewSuccessors[BBDefault];
1314 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1316 for (
auto I :
seq(NewSuccessor.second)) {
1320 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1321 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1334 for (ValueEqualityComparisonCase &V : PredCases)
1337 if (PredHasWeights || SuccHasWeights) {
1354 if (!InfLoopBlock) {
1362 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1369 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1371 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1373 DTU->applyUpdates(Updates);
1376 ++NumFoldValueComparisonIntoPredecessors;
1384bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1387 Value *CV = isValueEqualityComparison(TI);
1388 assert(CV &&
"Not a comparison?");
1390 bool Changed =
false;
1393 while (!Preds.empty()) {
1402 Value *PCV = isValueEqualityComparison(PTI);
1408 for (
auto *Succ : FailBlocks) {
1414 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1428 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1429 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1430 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1449 if (
I->mayReadFromMemory())
1453 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1470 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1480 if (
auto *CB = dyn_cast<CallBase>(
I))
1481 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1488 if (
auto *J = dyn_cast<Instruction>(
Op))
1489 if (J->getParent() == BB)
1508 auto *C1 = dyn_cast<CallInst>(I1);
1509 auto *C2 = dyn_cast<CallInst>(I2);
1511 if (C1->isMustTailCall() != C2->isMustTailCall())
1519 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1520 if (CB1->cannotMerge() || CB1->isConvergent())
1522 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1523 if (CB2->cannotMerge() || CB2->isConvergent())
1538 if (!I1->hasDbgRecords())
1540 using CurrentAndEndIt =
1541 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1547 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1548 return Pair.first == Pair.second;
1554 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1560 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1562 if (!
Other->hasDbgRecords())
1565 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1572 while (
none_of(Itrs, atEnd)) {
1573 bool HoistDPVs = allIdentical(Itrs);
1574 for (CurrentAndEndIt &Pair : Itrs) {
1591bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1613 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1617 if (isa<PHINode>(*SuccItr))
1619 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1628 if (!INonDbg->isTerminator())
1638 unsigned NumSkipped = 0;
1641 if (SuccIterPairs.
size() > 2) {
1643 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1644 if (SuccIterPairs.
size() < 2)
1648 bool Changed =
false;
1651 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1652 auto &BB1ItrPair = *SuccIterPairBegin++;
1653 auto OtherSuccIterPairRange =
1660 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1662 return I1->isIdenticalToWhenDefined(I2);
1664 if (!AllDbgInstsAreIdentical) {
1665 while (isa<DbgInfoIntrinsic>(I1))
1666 I1 = &*++BB1ItrPair.first;
1667 for (
auto &SuccIter : OtherSuccIterRange) {
1669 while (isa<DbgInfoIntrinsic>(I2))
1674 bool AllInstsAreIdentical =
true;
1675 bool HasTerminator =
I1->isTerminator();
1676 for (
auto &SuccIter : OtherSuccIterRange) {
1679 if (AllInstsAreIdentical && !
I1->isIdenticalToWhenDefined(I2))
1680 AllInstsAreIdentical =
false;
1684 for (
auto &SuccIter : OtherSuccIterRange)
1689 if (HasTerminator) {
1693 if (NumSkipped || !AllInstsAreIdentical) {
1698 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1702 if (AllInstsAreIdentical) {
1703 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1704 AllInstsAreIdentical =
1706 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1708 unsigned SkipFlagsBB2 = Pair.second;
1718 if (AllInstsAreIdentical) {
1720 if (isa<DbgInfoIntrinsic>(I1)) {
1729 for (
auto &SuccIter : OtherSuccIterRange) {
1730 auto *I2 = &*SuccIter++;
1731 assert(isa<DbgInfoIntrinsic>(I2));
1743 for (
auto &SuccIter : OtherSuccIterRange) {
1757 NumHoistCommonCode += SuccIterPairs.
size();
1759 NumHoistCommonInstrs += SuccIterPairs.
size();
1768 for (
auto &SuccIterPair : SuccIterPairs) {
1777bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1781 auto *BI = dyn_cast<BranchInst>(TI);
1783 bool Changed =
false;
1788 auto *I2 = *OtherSuccTIs.
begin();
1804 if (isa<CallBrInst>(I1))
1809 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1811 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1831 if (!
NT->getType()->isVoidTy()) {
1832 I1->replaceAllUsesWith(NT);
1834 OtherSuccTI->replaceAllUsesWith(NT);
1838 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1844 for (
auto *OtherSuccTI : OtherSuccTIs)
1845 Locs.
push_back(OtherSuccTI->getDebugLoc());
1857 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1860 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1861 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1867 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1871 if (isa<FPMathOperator>(PN))
1880 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1881 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1882 PN.setIncomingValue(i, SI);
1893 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1898 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1902 DTU->applyUpdates(Updates);
1908 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1909 switch (II->getIntrinsicID()) {
1912 case Intrinsic::lifetime_start:
1913 case Intrinsic::lifetime_end:
1924 return !isa<IntrinsicInst>(
I);
1938 bool HasUse = !Insts.
front()->user_empty();
1939 for (
auto *
I : Insts) {
1941 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1942 I->getType()->isTokenTy())
1947 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1954 if (
const auto *
C = dyn_cast<CallBase>(
I))
1955 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1959 if (HasUse && !
I->hasOneUse())
1961 if (!HasUse && !
I->user_empty())
1966 for (
auto *
I : Insts) {
1967 if (!
I->isSameOperationAs(I0))
1973 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1975 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1984 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1987 auto *U = cast<Instruction>(*
I->user_begin());
1989 PNUse->getParent() == Succ &&
1990 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
1991 U->getParent() ==
I->getParent();
2006 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2010 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
2014 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2022 if (isa<CallBase>(I0)) {
2024 return cast<CallBase>(
I)->isIndirectCall();
2026 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2027 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2028 if (HaveIndirectCalls) {
2029 if (!AllCallsAreIndirect)
2033 Value *Callee =
nullptr;
2035 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2037 Callee = CurrCallee;
2038 else if (Callee != CurrCallee)
2044 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2046 if (
Op->getType()->isTokenTy())
2054 if (!
all_of(Insts, SameAsI0)) {
2059 for (
auto *
I : Insts)
2060 PHIOperands[
I].push_back(
I->getOperand(OI));
2070 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2075 for (
auto *BB :
Blocks) {
2078 I =
I->getPrevNode();
2079 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2080 if (!isa<DbgInfoIntrinsic>(
I))
2090 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
2092 auto *U = cast<Instruction>(*
I->user_begin());
2118 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2121 PN->insertBefore(BBEnd->begin());
2122 for (
auto *
I : Insts)
2123 PN->addIncoming(
I->getOperand(O),
I->getParent());
2132 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2135 for (
auto *
I : Insts)
2154 PN->replaceAllUsesWith(I0);
2155 PN->eraseFromParent();
2159 for (
auto *
I : Insts) {
2164 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2165 I->replaceAllUsesWith(I0);
2166 I->eraseFromParent();
2182 class LockstepReverseIterator {
2195 for (
auto *BB : Blocks) {
2197 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2215 for (
auto *&Inst : Insts) {
2216 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2229 for (
auto *&Inst : Insts) {
2230 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2293 bool HaveNonUnconditionalPredecessors =
false;
2295 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2296 if (PredBr && PredBr->isUnconditional())
2299 HaveNonUnconditionalPredecessors =
true;
2301 if (UnconditionalPreds.
size() < 2)
2313 LockstepReverseIterator LRI(UnconditionalPreds);
2314 while (LRI.isValid() &&
2316 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2318 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2329 if (!followedByDeoptOrUnreachable) {
2333 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2334 unsigned NumPHIdValues = 0;
2335 for (
auto *
I : *LRI)
2336 for (
auto *V : PHIOperands[
I]) {
2337 if (!InstructionsToSink.
contains(V))
2343 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2344 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.
size();
2345 if ((NumPHIdValues % UnconditionalPreds.
size()) != 0)
2348 return NumPHIInsts <= 1;
2365 while (
Idx < ScanIdx) {
2366 if (!ProfitableToSinkInstruction(LRI)) {
2369 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2372 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2382 if (
Idx < ScanIdx) {
2385 InstructionsToSink = InstructionsProfitableToSink;
2391 !ProfitableToSinkInstruction(LRI) &&
2392 "We already know that the last instruction is unprofitable to sink");
2400 for (
auto *
I : *LRI)
2401 InstructionsProfitableToSink.
erase(
I);
2402 if (!ProfitableToSinkInstruction(LRI)) {
2405 InstructionsToSink = InstructionsProfitableToSink;
2417 bool Changed =
false;
2419 if (HaveNonUnconditionalPredecessors) {
2420 if (!followedByDeoptOrUnreachable) {
2428 bool Profitable =
false;
2429 while (
Idx < ScanIdx) {
2463 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2465 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2475 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2479 NumSinkCommonInstrs++;
2483 ++NumSinkCommonCode;
2489struct CompatibleSets {
2507 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2516 getCompatibleSet(II).emplace_back(II);
2520 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2526 if (
any_of(Invokes, IsIllegalToMerge))
2532 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2533 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2534 if (HaveIndirectCalls) {
2535 if (!AllCallsAreIndirect)
2542 assert(CurrCallee &&
"There is always a called operand.");
2545 else if (Callee != CurrCallee)
2555 if (
any_of(Invokes, HasNormalDest)) {
2558 if (!
all_of(Invokes, HasNormalDest))
2565 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2567 NormalBB = CurrNormalBB;
2568 else if (NormalBB != CurrNormalBB)
2576 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2587 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2589 UnwindBB = CurrUnwindBB;
2591 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2598 Invokes.front()->getUnwindDest(),
2599 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2605 for (
auto *II : Invokes.drop_front())
2610 auto IsIllegalToMergeArguments = [](
auto Ops) {
2611 Use &U0 = std::get<0>(Ops);
2612 Use &U1 = std::get<1>(Ops);
2619 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2620 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2621 IsIllegalToMergeArguments))
2633 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2639 bool HasNormalDest =
2640 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2644 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2653 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2655 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2657 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2659 if (!HasNormalDest) {
2663 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2670 return MergedInvoke;
2684 SuccBBOfMergedInvoke});
2691 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2694 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2697 for (
Use &U : MergedInvoke->operands()) {
2699 if (MergedInvoke->isCallee(&U)) {
2700 if (!IsIndirectCall)
2702 }
else if (!MergedInvoke->isDataOperand(&U))
2714 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2726 Invokes.front()->getParent());
2734 if (!MergedDebugLoc)
2743 OrigSuccBB->removePredecessor(II->
getParent());
2749 MergedInvoke->setDebugLoc(MergedDebugLoc);
2750 ++NumInvokeSetsFormed;
2753 DTU->applyUpdates(Updates);
2780 bool Changed =
false;
2786 CompatibleSets Grouper;
2792 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2796 if (Invokes.
size() < 2)
2808class EphemeralValueTracker {
2812 if (isa<AssumeInst>(
I))
2814 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2816 return EphValues.count(cast<Instruction>(U));
2822 if (isEphemeral(
I)) {
2861 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2873 unsigned MaxNumInstToLookAt = 9;
2877 if (!MaxNumInstToLookAt)
2879 --MaxNumInstToLookAt;
2882 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2885 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2889 if (SI->getPointerOperand() == StorePtr &&
2890 SI->getValueOperand()->getType() == StoreTy && SI->isSimple())
2892 return SI->getValueOperand();
2896 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2897 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2921 unsigned &SpeculatedInstructions,
2929 bool HaveRewritablePHIs =
false;
2947 HaveRewritablePHIs =
true;
2950 if (!OrigCE && !ThenCE)
2957 if (OrigCost + ThenCost > MaxCost)
2964 ++SpeculatedInstructions;
2965 if (SpeculatedInstructions > 1)
2969 return HaveRewritablePHIs;
3009bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
3016 if (isa<FCmpInst>(BrCond))
3026 bool Invert =
false;
3035 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
3038 (TWeight + FWeight) != 0) {
3039 uint64_t EndWeight = Invert ? TWeight : FWeight;
3043 if (BIEndProb >= Likely)
3057 unsigned SpeculatedInstructions = 0;
3058 Value *SpeculatedStoreValue =
nullptr;
3060 EphemeralValueTracker EphTracker;
3063 if (isa<DbgInfoIntrinsic>(
I)) {
3071 if (isa<PseudoProbeInst>(
I)) {
3081 if (EphTracker.track(&
I))
3086 ++SpeculatedInstructions;
3087 if (SpeculatedInstructions > 1)
3093 &
I, BB, ThenBB, EndBB))))
3095 if (!SpeculatedStoreValue &&
3101 if (SpeculatedStoreValue)
3102 SpeculatedStore = cast<StoreInst>(&
I);
3107 for (
Use &
Op :
I.operands()) {
3112 ++SinkCandidateUseCounts[OpI];
3119 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3121 ++SpeculatedInstructions;
3122 if (SpeculatedInstructions > 1)
3128 bool Convert = SpeculatedStore !=
nullptr;
3131 SpeculatedInstructions,
3133 if (!Convert ||
Cost > Budget)
3137 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3140 if (SpeculatedStoreValue) {
3144 Value *FalseV = SpeculatedStoreValue;
3148 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3177 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3179 DbgAssign->replaceVariableLocationOp(OrigV, S);
3192 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3194 if (!isa<DbgAssignIntrinsic>(&
I))
3197 I.dropUBImplyingAttrsAndMetadata();
3200 if (EphTracker.contains(&
I)) {
3202 I.eraseFromParent();
3214 It.dropOneDbgRecord(&DR);
3216 std::prev(ThenBB->
end()));
3233 Value *TrueV = ThenV, *FalseV = OrigV;
3247 if (!isa<DbgAssignIntrinsic>(
I))
3248 I->eraseFromParent();
3258 EphemeralValueTracker EphTracker;
3264 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3265 if (CI->cannotDuplicate() || CI->isConvergent())
3271 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3278 for (
User *U :
I.users()) {
3280 if (UI->
getParent() != BB || isa<PHINode>(UI))
3294 auto *
I = dyn_cast<Instruction>(V);
3295 if (
I &&
I->getParent() == To)
3299 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3311static std::optional<bool>
3327 if (
auto *CB = dyn_cast<ConstantInt>(U))
3332 KnownValues[CB].
insert(Pred);
3336 if (KnownValues.
empty())
3345 for (
const auto &Pair : KnownValues) {
3363 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3366 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3374 EdgeBB->setName(RealDest->
getName() +
".critedge");
3375 EdgeBB->moveBefore(RealDest);
3385 TranslateMap[
Cond] = CB;
3391 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3398 N->insertInto(EdgeBB, InsertPt);
3401 N->setName(BBI->getName() +
".c");
3404 for (
Use &
Op :
N->operands()) {
3406 if (PI != TranslateMap.
end())
3412 if (!BBI->use_empty())
3413 TranslateMap[&*BBI] = V;
3414 if (!
N->mayHaveSideEffects()) {
3415 N->eraseFromParent();
3420 if (!BBI->use_empty())
3421 TranslateMap[&*BBI] =
N;
3427 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3428 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3429 SrcDbgCursor = std::next(BBI);
3431 N->cloneDebugInfoFrom(&*BBI);
3434 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3440 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3441 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3442 InsertPt->cloneDebugInfoFrom(BI);
3445 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3451 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3452 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3463 return std::nullopt;
3473 std::optional<bool> Result;
3474 bool EverChanged =
false;
3478 EverChanged |= Result == std::nullopt || *Result;
3479 }
while (Result == std::nullopt);
3501 if (isa<ConstantInt>(IfCond))
3508 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3511 "Will have either one or two blocks to speculate.");
3518 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3521 (TWeight + FWeight) != 0) {
3526 if (IfBlocks.
size() == 1) {
3528 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3529 if (BIBBProb >= Likely)
3532 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3540 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3541 if (IfCondPhiInst->getParent() == BB)
3549 unsigned NumPhis = 0;
3562 bool Changed =
false;
3564 PHINode *PN = cast<PHINode>(II++);
3581 PN = dyn_cast<PHINode>(BB->
begin());
3587 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3598 auto IsBinOpOrAnd = [](
Value *V) {
3618 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3631 <<
" T: " << IfTrue->
getName()
3632 <<
" F: " << IfFalse->
getName() <<
"\n");
3646 if (isa<FPMathOperator>(PN))
3666 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3684 if (Opc == Instruction::And)
3686 if (Opc == Instruction::Or)
3699 bool PredHasWeights =
3701 bool SuccHasWeights =
3703 if (PredHasWeights || SuccHasWeights) {
3704 if (!PredHasWeights)
3705 PredTrueWeight = PredFalseWeight = 1;
3706 if (!SuccHasWeights)
3707 SuccTrueWeight = SuccFalseWeight = 1;
3717static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3721 "Both blocks must end with a conditional branches.");
3723 "PredBB must be a predecessor of BB.");
3731 (PTWeight + PFWeight) != 0) {
3739 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3740 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3744 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3747 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3748 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3754 return std::nullopt;
3767 bool InvertPredCond;
3768 std::tie(CommonSucc, Opc, InvertPredCond) =
3771 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3778 {LLVMContext::MD_annotation});
3781 if (InvertPredCond) {
3794 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3796 SuccTrueWeight, SuccFalseWeight)) {
3803 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3809 (SuccFalseWeight + SuccTrueWeight) +
3810 PredTrueWeight * SuccFalseWeight);
3816 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3817 PredFalseWeight * SuccTrueWeight);
3819 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3837 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3838 {DominatorTree::Delete, PredBlock, BB}});
3865 ++NumFoldBranchToCommonDest;
3872 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3873 return U->getType()->isVectorTy();
3883 unsigned BonusInstThreshold) {
3897 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3898 !isa<SelectInst>(
Cond)) ||
3899 Cond->getParent() != BB || !
Cond->hasOneUse())
3909 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3920 bool InvertPredCond;
3922 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3954 unsigned NumBonusInsts = 0;
3955 bool SawVectorOp =
false;
3956 const unsigned PredCount = Preds.
size();
3962 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3973 NumBonusInsts += PredCount;
3981 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3982 auto *UI = cast<Instruction>(U.getUser());
3983 if (
auto *PN = dyn_cast<PHINode>(UI))
3985 return UI->
getParent() == BB &&
I.comesBefore(UI);
3989 if (!
all_of(
I.uses(), IsBCSSAUse))
3993 BonusInstThreshold *
3999 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4009 for (
auto *BB : {BB1, BB2}) {
4013 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4025 Value *AlternativeV =
nullptr) {
4043 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4044 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4045 PHI = cast<PHINode>(
I);
4051 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4052 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4060 if (!AlternativeV &&
4061 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4066 PHI->addIncoming(V, BB);
4076 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4085 if (!PStore || !QStore)
4106 if (
I.mayReadOrWriteMemory())
4108 for (
auto &
I : *QFB)
4109 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4112 for (
auto &
I : *QTB)
4113 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4117 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4133 if (
I.isTerminator())
4137 if (
auto *S = dyn_cast<StoreInst>(&
I))
4141 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4151 "When we run out of budget we will eagerly return from within the "
4152 "per-instruction loop.");
4156 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4158 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4159 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4267 bool InvertPCond =
false, InvertQCond =
false;
4273 if (QFB == PostBB) {
4292 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4295 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4303 for (
auto *BB : {PTB, PFB}) {
4308 PStoreAddresses.
insert(SI->getPointerOperand());
4310 for (
auto *BB : {QTB, QFB}) {
4315 QStoreAddresses.
insert(SI->getPointerOperand());
4321 auto &CommonAddresses = PStoreAddresses;
4323 bool Changed =
false;
4324 for (
auto *Address : CommonAddresses)
4327 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4347 if (!IfFalseBB->
phis().empty())
4357 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4368 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4369 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4380 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4381 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4460 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4462 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4466 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4469 if (CommonDestProb >= Likely)
4479 unsigned NumPhis = 0;
4501 if (OtherDest == BB) {
4508 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4509 OtherDest = InfLoopBlock;
4529 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4544 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4545 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4548 SuccTrueWeight, SuccFalseWeight);
4550 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4551 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4552 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4553 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4557 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4558 PredOther * SuccCommon,
4559 PredOther * SuccOther};
4588 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4589 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4590 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4591 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4594 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4595 PredOther * SuccCommon};
4617bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4628 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4635 if (Succ == KeepEdge1)
4636 KeepEdge1 =
nullptr;
4637 else if (Succ == KeepEdge2)
4638 KeepEdge2 =
nullptr;
4643 if (Succ != TrueBB && Succ != FalseBB)
4644 RemovedSuccessors.
insert(Succ);
4652 if (!KeepEdge1 && !KeepEdge2) {
4653 if (TrueBB == FalseBB) {
4661 if (TrueWeight != FalseWeight)
4664 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4686 for (
auto *RemovedSuccessor : RemovedSuccessors)
4687 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4688 DTU->applyUpdates(Updates);
4698bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4703 if (!TrueVal || !FalseVal)
4708 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4709 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4712 uint32_t TrueWeight = 0, FalseWeight = 0;
4717 if (Weights.
size() == 1 +
SI->getNumCases()) {
4719 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4721 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4726 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4735bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4748 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4769bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4789 if (
SI->getCondition() != V)
4795 if (
SI->getDefaultDest() != BB) {
4797 assert(VVal &&
"Should have a unique destination value");
4805 return requestResimplify();
4811 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4821 return requestResimplify();
4828 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4853 auto W0 = SIW.getSuccessorWeight(0);
4857 SIW.setSuccessorWeight(0, *NewW);
4859 SIW.addCase(Cst, NewBB, NewW);
4861 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4870 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4871 DTU->applyUpdates(Updates);
4879bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4891 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4894 Value *CompVal = ConstantCompare.CompValue;
4895 unsigned UsedICmps = ConstantCompare.UsedICmps;
4896 Value *ExtraCase = ConstantCompare.Extra;
4915 if (ExtraCase && Values.
size() < 2)
4930 <<
" cases into SWITCH. BB is:\n"
4940 nullptr,
"switch.early.test");
4964 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4970 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4971 <<
"\nEXTRABB = " << *BB);
4979 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4986 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4987 New->addCase(Values[i], EdgeBB);
4993 PHINode *PN = cast<PHINode>(BBI);
4995 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5002 DTU->applyUpdates(Updates);
5004 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5010 return simplifyCommonResume(RI);
5014 return simplifySingleResume(RI);
5022 auto *II = dyn_cast<IntrinsicInst>(&
I);
5027 switch (IntrinsicID) {
5028 case Intrinsic::dbg_declare:
5029 case Intrinsic::dbg_value:
5030 case Intrinsic::dbg_label:
5031 case Intrinsic::lifetime_end:
5041bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5051 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5054 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5056 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5057 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5061 if (IncomingBB->getUniqueSuccessor() != BB)
5064 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5066 if (IncomingValue != LandingPad)
5070 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5071 TrivialUnwindBlocks.
insert(IncomingBB);
5075 if (TrivialUnwindBlocks.
empty())
5079 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5083 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5097 TrivialBB->getTerminator()->eraseFromParent();
5100 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5107 return !TrivialUnwindBlocks.empty();
5111bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5115 "Resume must unwind the exception that caused control to here");
5119 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5155 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5172 int Idx = DestPN.getBasicBlockIndex(BB);
5186 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5187 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5189 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5193 DestPN.addIncoming(
Incoming, Pred);
5220 std::vector<DominatorTree::UpdateType> Updates;
5224 if (UnwindDest ==
nullptr) {
5236 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5237 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5264 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5265 if (!SuccessorCleanupPad)
5274 SuccessorCleanupPad->eraseFromParent();
5303 bool Changed =
false;
5332 BBI->dropDbgRecords();
5336 BBI->eraseFromParent();
5342 if (&BB->
front() != UI)
5345 std::vector<DominatorTree::UpdateType> Updates;
5348 for (
unsigned i = 0, e = Preds.size(); i != e; ++i) {
5349 auto *Predecessor = Preds[i];
5352 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5356 [BB](
auto *
Successor) { return Successor == BB; })) {
5364 "The destinations are guaranteed to be different here.");
5375 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5381 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5382 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5384 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5385 if (i->getCaseSuccessor() != BB) {
5390 i = SU.removeCase(i);
5395 if (DTU &&
SI->getDefaultDest() != BB)
5396 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5397 }
else if (
auto *II = dyn_cast<InvokeInst>(TI)) {
5400 DTU->applyUpdates(Updates);
5404 if (!CI->doesNotThrow())
5405 CI->setDoesNotThrow();
5408 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5409 if (CSI->getUnwindDest() == BB) {
5411 DTU->applyUpdates(Updates);
5420 E = CSI->handler_end();
5423 CSI->removeHandler(
I);
5430 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5431 if (CSI->getNumHandlers() == 0) {
5432 if (CSI->hasUnwindDest()) {
5436 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5437 Updates.push_back({DominatorTree::Insert,
5438 PredecessorOfPredecessor,
5439 CSI->getUnwindDest()});
5440 Updates.push_back({DominatorTree::Delete,
5441 PredecessorOfPredecessor, Predecessor});
5444 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5448 DTU->applyUpdates(Updates);
5457 CSI->eraseFromParent();
5460 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5462 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5463 "Expected to always have an unwind to BB.");
5465 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5473 DTU->applyUpdates(Updates);
5488 for (
size_t I = 1,
E = Cases.
size();
I !=
E; ++
I) {
5489 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5498 auto *BB = Switch->getParent();
5499 auto *OrigDefaultBlock = Switch->getDefaultDest();
5500 OrigDefaultBlock->removePredecessor(BB);
5505 Switch->setDefaultDest(&*NewDefaultBlock);
5508 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5510 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5518bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(
SwitchInst *SI,
5520 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5523 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5525 auto *BB =
SI->getParent();
5528 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5533 for (
auto Case :
SI->cases()) {
5537 if (Dest == DestA) {
5543 if (Dest == DestB) {
5553 "Single-destination switch should have been folded.");
5555 assert(DestB !=
SI->getDefaultDest());
5556 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5564 ContiguousCases = &CasesA;
5565 ContiguousDest = DestA;
5568 ContiguousCases = &CasesB;
5569 ContiguousDest = DestB;
5578 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5580 Value *Sub =
SI->getCondition();
5581 if (!
Offset->isNullValue())
5596 if (Weights.
size() == 1 +
SI->getNumCases()) {
5599 for (
size_t I = 0,
E = Weights.
size();
I !=
E; ++
I) {
5600 if (
SI->getSuccessor(
I) == ContiguousDest)
5601 TrueWeight += Weights[
I];
5603 FalseWeight += Weights[
I];
5605 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5614 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5615 unsigned PreviousEdges = ContiguousCases->
size();
5616 if (ContiguousDest ==
SI->getDefaultDest())
5618 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5619 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5621 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5622 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5623 if (OtherDest ==
SI->getDefaultDest())
5625 for (
unsigned I = 0,
E = PreviousEdges - 1;
I !=
E; ++
I)
5626 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5634 auto *UnreachableDefault =
SI->getDefaultDest();
5637 SI->eraseFromParent();
5639 if (!HasDefault && DTU)
5640 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5656 unsigned MaxSignificantBitsInCond =
5663 for (
const auto &Case : SI->cases()) {
5664 auto *
Successor = Case.getCaseSuccessor();
5670 const APInt &CaseVal = Case.getCaseValue()->getValue();
5673 DeadCases.
push_back(Case.getCaseValue());
5686 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5687 const unsigned NumUnknownBits =
5690 if (HasDefault && DeadCases.
empty() &&
5691 NumUnknownBits < 64 &&
5692 SI->getNumCases() == (1ULL << NumUnknownBits)) {
5697 if (DeadCases.
empty())
5703 assert(CaseI != SI->case_default() &&
5704 "Case was not found. Probably mistake in DeadCases forming.");
5706 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5711 std::vector<DominatorTree::UpdateType> Updates;
5712 for (
auto *
Successor : UniqueSuccessors)
5713 if (NumPerSuccessorCases[
Successor] == 0)
5714 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5734 if (!Branch || !Branch->isUnconditional())
5740 int Idx =
PHI.getBasicBlockIndex(BB);
5741 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5744 if (InValue != CaseValue)
5760 ForwardingNodesMap ForwardingNodes;
5762 bool Changed =
false;
5763 for (
const auto &Case : SI->cases()) {
5765 BasicBlock *CaseDest = Case.getCaseSuccessor();
5784 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
5785 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
5786 count(Phi.blocks(), SwitchBlock) == 1) {
5787 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
5795 ForwardingNodes[Phi].push_back(PhiIdx);
5798 for (
auto &ForwardingNode : ForwardingNodes) {
5799 PHINode *Phi = ForwardingNode.first;
5801 if (Indexes.
size() < 2)
5804 for (
int Index : Indexes)
5805 Phi->setIncomingValue(
Index, SI->getCondition());
5815 if (
C->isThreadDependent())
5817 if (
C->isDLLImportDependent())
5820 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
5821 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
5822 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
5828 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
5844 if (
Constant *
C = dyn_cast<Constant>(V))
5860 if (
A->isAllOnesValue())
5862 if (
A->isNullValue())
5868 for (
unsigned N = 0,
E =
I->getNumOperands();
N !=
E; ++
N) {
5893 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
5895 if (
I.isTerminator()) {
5897 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
5900 CaseDest =
I.getSuccessor(0);
5907 for (
auto &
Use :
I.uses()) {
5910 if (
I->getParent() == CaseDest)
5913 if (Phi->getIncomingBlock(
Use) == CaseDest)
5926 *CommonDest = CaseDest;
5928 if (CaseDest != *CommonDest)
5933 int Idx =
PHI.getBasicBlockIndex(Pred);
5946 Res.push_back(std::make_pair(&
PHI, ConstVal));
5949 return Res.size() > 0;
5955 SwitchCaseResultVectorTy &UniqueResults,
5957 for (
auto &
I : UniqueResults) {
5958 if (
I.first == Result) {
5959 I.second.push_back(CaseVal);
5960 return I.second.size();
5963 UniqueResults.push_back(
5974 SwitchCaseResultVectorTy &UniqueResults,
5978 uintptr_t MaxUniqueResults) {
5979 for (
const auto &
I : SI->cases()) {
5993 const size_t NumCasesForResult =
6001 if (UniqueResults.size() > MaxUniqueResults)
6012 BasicBlock *DefaultDest = SI->getDefaultDest();
6013 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6018 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6019 if ((!DefaultResult &&
6040 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6041 ResultVector[1].second.size() == 1) {
6042 ConstantInt *FirstCase = ResultVector[0].second[0];
6043 ConstantInt *SecondCase = ResultVector[1].second[0];
6044 Value *SelectValue = ResultVector[1].first;
6045 if (DefaultResult) {
6046 Value *ValueCompare =
6047 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6048 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6049 DefaultResult,
"switch.select");
6051 Value *ValueCompare =
6052 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6053 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6054 SelectValue,
"switch.select");
6058 if (ResultVector.size() == 1 && DefaultResult) {
6060 unsigned CaseCount = CaseValues.
size();
6068 for (
auto *Case : CaseValues)
6069 if (Case->getValue().slt(MinCaseVal->
getValue()))
6074 for (
auto *Case : CaseValues)
6075 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6081 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6085 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6090 if (CaseValues.
size() == 2) {
6092 "switch.selectcmp.case1");
6094 "switch.selectcmp.case2");
6095 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6096 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6109 std::vector<DominatorTree::UpdateType> Updates;
6115 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6120 PHI->removeIncomingValueIf(
6121 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6122 PHI->addIncoming(SelectValue, SelectBB);
6125 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6131 if (DTU && RemovedSuccessors.
insert(Succ).second)
6132 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6134 SI->eraseFromParent();
6149 SwitchCaseResultVectorTy UniqueResults;
6155 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6157 Value *SelectValue =
6169class SwitchLookupTable {
6220 bool LinearMapValWrapped =
false;
6228SwitchLookupTable::SwitchLookupTable(
6232 assert(Values.
size() &&
"Can't build lookup table without values!");
6233 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6236 SingleValue = Values.
begin()->second;
6242 for (
size_t I = 0,
E = Values.
size();
I !=
E; ++
I) {
6248 TableContents[
Idx] = CaseRes;
6250 if (CaseRes != SingleValue)
6251 SingleValue =
nullptr;
6255 if (Values.
size() < TableSize) {
6257 "Need a default value to fill the lookup table holes.");
6260 if (!TableContents[
I])
6261 TableContents[
I] = DefaultValue;
6264 if (DefaultValue != SingleValue)
6265 SingleValue =
nullptr;
6271 Kind = SingleValueKind;
6278 bool LinearMappingPossible =
true;
6283 bool NonMonotonic =
false;
6284 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6287 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6291 LinearMappingPossible =
false;
6296 APInt Dist = Val - PrevVal;
6299 }
else if (Dist != DistToPrev) {
6300 LinearMappingPossible =
false;
6308 if (LinearMappingPossible) {
6309 LinearOffset = cast<ConstantInt>(TableContents[0]);
6310 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6311 bool MayWrap =
false;
6312 APInt M = LinearMultiplier->getValue();
6313 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6314 LinearMapValWrapped = NonMonotonic || MayWrap;
6315 Kind = LinearMapKind;
6322 if (WouldFitInRegister(
DL, TableSize,
ValueType)) {
6324 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6326 TableInt <<=
IT->getBitWidth();
6328 if (!isa<UndefValue>(TableContents[
I - 1])) {
6329 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6330 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6333 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6334 BitMapElementTy =
IT;
6345 GlobalVariable::PrivateLinkage, Initializer,
6346 "switch.table." + FuncName);
6347 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6356 case SingleValueKind:
6358 case LinearMapKind: {
6361 false,
"switch.idx.cast");
6362 if (!LinearMultiplier->isOne())
6363 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6365 !LinearMapValWrapped);
6367 if (!LinearOffset->isZero())
6370 !LinearMapValWrapped);
6386 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6387 "switch.shiftamt",
true,
true);
6390 Value *DownShifted =
6391 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6393 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6399 Array->getInitializer()->getType()->getArrayNumElements();
6400 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6403 "switch.tableidx.zext");
6407 GEPIndices,
"switch.gep");
6409 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6416bool SwitchLookupTable::WouldFitInRegister(
const DataLayout &
DL,
6418 Type *ElementType) {
6419 auto *
IT = dyn_cast<IntegerType>(ElementType);
6426 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6428 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6437 auto *
IT = dyn_cast<IntegerType>(Ty);
6449 DL.fitsInLegalInteger(
IT->getBitWidth());
6461 return NumCases * 100 >= CaseRange * MinDensity;
6482 if (SI->getNumCases() > TableSize)
6485 bool AllTablesFitInRegister =
true;
6486 bool HasIllegalType =
false;
6487 for (
const auto &
I : ResultTypes) {
6488 Type *Ty =
I.second;
6494 AllTablesFitInRegister =
6495 AllTablesFitInRegister &&
6496 SwitchLookupTable::WouldFitInRegister(
DL, TableSize, Ty);
6501 if (HasIllegalType && !AllTablesFitInRegister)
6506 if (AllTablesFitInRegister)
6523 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6526 return all_of(ResultTypes, [&](
const auto &KV) {
6527 return SwitchLookupTable::WouldFitInRegister(
6556 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6576 DefaultValue, CmpOp1,
true);
6577 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6582 for (
auto ValuePair : Values) {
6584 ValuePair.second, CmpOp1,
true);
6585 if (!CaseConst || CaseConst == DefaultConst ||
6586 (CaseConst != TrueConst && CaseConst != FalseConst))
6600 if (DefaultConst == FalseConst) {
6603 ++NumTableCmpReuses;
6606 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6607 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6610 ++NumTableCmpReuses;
6620 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6639 if (SI->getNumCases() < 3)
6644 assert(!SI->cases().empty());
6661 MinCaseVal = CaseVal;
6663 MaxCaseVal = CaseVal;
6668 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6678 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6684 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6692 bool HasDefaultResults =
6694 DefaultResultsList,
DL,
TTI);
6696 for (
const auto &
I : DefaultResultsList) {
6699 DefaultResults[
PHI] = Result;
6703 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6705 if (UseSwitchConditionAsTableIndex)
6711 bool TableHasHoles = (NumResults < TableSize);
6712 bool NeedMask = (TableHasHoles && !HasDefaultResults);
6715 if (SI->getNumCases() < 4)
6717 if (!
DL.fitsInLegalInteger(TableSize))
6724 std::vector<DominatorTree::UpdateType> Updates;
6730 assert(MaxTableSize >= TableSize &&
6731 "It is impossible for a switch to have more entries than the max "
6732 "representable value of its input integer type's size.");
6737 bool DefaultIsReachable =
6738 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
6749 if (UseSwitchConditionAsTableIndex) {
6750 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
6751 TableIndex = SI->getCondition();
6753 TableIndexOffset = MinCaseVal;
6756 bool MayWrap =
true;
6757 if (!DefaultIsReachable) {
6762 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
6763 "switch.tableidx",
false,
6772 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
6780 return SwitchLookupTable::WouldFitInRegister(
6781 DL, UpperBound, KV.second );
6785 TableSize = UpperBound;
6786 DefaultIsReachable =
false;
6790 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
6791 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6794 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6799 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
6801 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
6803 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6813 MaskBB->
setName(
"switch.hole_check");
6820 APInt MaskInt(TableSizePowOf2, 0);
6821 APInt One(TableSizePowOf2, 1);
6823 const ResultListTy &ResultList = ResultLists[PHIs[0]];
6824 for (
size_t I = 0,
E = ResultList.size();
I !=
E; ++
I) {
6827 MaskInt |= One <<
Idx;
6837 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
6840 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
6842 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
6843 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
6849 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6852 SI->getDefaultDest()->removePredecessor(BB,
6855 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
6859 const ResultListTy &ResultList = ResultLists[
PHI];
6862 Constant *DV = NeedMask ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
6864 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
6867 Value *Result = Table.BuildLookup(TableIndex, Builder);
6871 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
6874 for (
auto *
User :
PHI->users()) {
6879 PHI->addIncoming(Result, LookupBB);
6884 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
6888 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6891 if (Succ == SI->getDefaultDest())
6894 if (DTU && RemovedSuccessors.
insert(Succ).second)
6895 Updates.push_back({DominatorTree::Delete, BB, Succ});
6897 SI->eraseFromParent();
6904 ++NumLookupTablesHoles;
6919 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
6920 if (CondTy->getIntegerBitWidth() > 64 ||
6921 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6925 if (SI->getNumCases() < 4)
6933 for (
const auto &
C : SI->cases())
6934 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
6942 int64_t
Base = Values[0];
6943 for (
auto &V : Values)
6956 unsigned Shift = 64;
6957 for (
auto &V : Values)
6961 for (
auto &V : Values)
6962 V = (int64_t)((
uint64_t)V >> Shift);
6978 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
6981 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
6983 Ty, Intrinsic::fshl,
6984 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
6985 SI->replaceUsesOfWith(SI->getCondition(), Rot);
6987 for (
auto Case : SI->cases()) {
6988 auto *Orig = Case.getCaseValue();
6989 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base);
6990 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7006 Value *Condition = SI->getCondition();
7008 auto *CondTy = cast<IntegerType>(Condition->
getType());
7010 if (CondTy->getIntegerBitWidth() > 64 ||
7011 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7025 if (SI->getNumCases() < 4)
7031 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7036 for (
const auto &Case : SI->cases()) {
7037 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7054 for (
auto &Case : SI->cases()) {
7055 auto *OrigValue = Case.getCaseValue();
7056 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7057 OrigValue->getValue().countr_zero()));
7064 SI->setCondition(ConditionTrailingZeros);
7072 if (isValueEqualityComparison(SI)) {
7076 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7077 return requestResimplify();
7081 if (SimplifySwitchOnSelect(SI,
Select))
7082 return requestResimplify();
7087 if (FoldValueComparisonIntoPredecessors(SI, Builder))
7088 return requestResimplify();
7094 if (
Options.ConvertSwitchRangeToICmp && TurnSwitchRangeIntoICmp(SI, Builder))
7095 return requestResimplify();
7099 return requestResimplify();
7102 return requestResimplify();
7105 return requestResimplify();
7112 if (
Options.ConvertSwitchToLookupTable &&
7114 return requestResimplify();
7117 return requestResimplify();
7120 return requestResimplify();
7123 hoistCommonCodeFromSuccessors(
SI->getParent(), !
Options.HoistCommonInsts))
7124 return requestResimplify();
7131 bool Changed =
false;
7140 RemovedSuccs.
insert(Dest);
7150 std::vector<DominatorTree::UpdateType> Updates;
7151 Updates.reserve(RemovedSuccs.
size());
7152 for (
auto *RemovedSucc : RemovedSuccs)
7153 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7154 DTU->applyUpdates(Updates);
7172 if (SimplifyIndirectBrOnSelect(IBI, SI))
7173 return requestResimplify();
7205 if (isa<PHINode>(*Succ->
begin()))
7209 if (BB == OtherPred)
7215 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7221 std::vector<DominatorTree::UpdateType> Updates;
7229 "unexpected successor");
7232 Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
7233 Updates.push_back({DominatorTree::Delete, Pred, BB});
7240 if (isa<DbgInfoIntrinsic>(Inst))
7247 Updates.push_back({DominatorTree::Delete, BB, Succ});
7261 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7262 : simplifyCondBranch(
Branch, Builder);
7265bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7277 bool NeedCanonicalLoop =
7288 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7290 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7292 if (
I->isTerminator() &&
7293 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7300 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7310 if (
Options.SpeculateBlocks &&
7313 return requestResimplify();
7321 if (!PPred || (PredPred && PredPred != PPred))
7332 "Tautological conditional branch should have been eliminated already.");
7335 if (!
Options.SimplifyCondBranch ||
7340 if (isValueEqualityComparison(BI)) {
7345 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
7346 return requestResimplify();
7352 if (FoldValueComparisonIntoPredecessors(BI, Builder))
7353 return requestResimplify();
7356 if (&*
I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
7357 return requestResimplify();
7362 if (SimplifyBranchOnICmpChain(BI, Builder,
DL))
7375 return requestResimplify();
7381 if (
Options.SpeculateBlocks &&
7384 return requestResimplify();
7394 return requestResimplify();
7402 return requestResimplify();
7411 return requestResimplify();
7418 return requestResimplify();
7423 if (PBI != BI && PBI->isConditional())
7425 return requestResimplify();
7430 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
7431 if (PBI != BI && PBI->isConditional())
7433 return requestResimplify();
7447 if (
C->isNullValue() || isa<UndefValue>(
C)) {
7449 auto *
Use = cast<Instruction>(*
I->user_begin());
7453 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
7467 if (
GEP->getPointerOperand() ==
I) {
7474 if (!
GEP->hasAllZeroIndices() &&
7475 (!
GEP->isInBounds() ||
7477 GEP->getPointerAddressSpace())))
7478 PtrValueMayBeModified =
true;
7484 bool HasNoUndefAttr =
7485 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
7487 if (isa<UndefValue>(
C) && HasNoUndefAttr)
7490 if (
C->isNullValue() && HasNoUndefAttr &&
7491 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
7492 return !PtrValueMayBeModified;
7502 if (!LI->isVolatile())
7504 LI->getPointerAddressSpace());
7508 if (!SI->isVolatile())
7510 SI->getPointerAddressSpace())) &&
7511 SI->getPointerOperand() ==
I;
7513 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
7517 if (CB->getCalledOperand() ==
I)
7520 if (
C->isNullValue()) {
7523 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7524 if (CB->isPassingUndefUB(ArgIdx) &&
7525 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
7527 return !PtrValueMayBeModified;
7530 }
else if (isa<UndefValue>(
C)) {
7534 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7535 if (CB->isPassingUndefUB(ArgIdx)) {
7552 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
7579 DTU->
applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
7581 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
7589 for (
const auto &Case : SI->cases())
7590 if (Case.getCaseSuccessor() == BB) {
7592 Case.setSuccessor(Unreachable);
7594 if (SI->getDefaultDest() == BB) {
7596 SI->setDefaultDest(Unreachable);
7601 { { DominatorTree::Insert, Predecessor, Unreachable },
7602 { DominatorTree::Delete, Predecessor, BB } });
7610bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
7611 bool Changed =
false;
7635 return requestResimplify();
7656 if (
Options.SpeculateBlocks &&
7660 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
7669 case Instruction::Br:
7670 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
7672 case Instruction::Resume:
7673 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
7675 case Instruction::CleanupRet:
7676 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
7678 case Instruction::Switch:
7679 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
7681 case Instruction::Unreachable:
7682 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
7684 case Instruction::IndirectBr:
7685 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
7693 bool Changed =
false;
7701 Changed |= simplifyOnce(BB);
7702 }
while (Resimplify);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
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< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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...
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 exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
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())
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 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 bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static Constant * ConstantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static Constant * LookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
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 SafeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
static void CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
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 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 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 ConstantInt * GetConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
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 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 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 bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
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 bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
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 PHINode * FindPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
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 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 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 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 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 SinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static void setBranchWeights(SwitchInst *SI, ArrayRef< uint32_t > Weights)
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 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 mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
@ 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 FoldCondBranchOnValueKnownInPredecessor(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
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 bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool ForwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
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 int ConstantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
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 void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static void FitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
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 void EraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static unsigned skippedInstrFlags(Instruction *I)
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
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 canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< Instruction *, SmallVector< Value *, 4 > > &PHIOperands)
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 size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static void MergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool ShouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallDenseMap< PHINode *, Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
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 void hoistLockstepIdenticalDPValues(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DPValues from I1 and OtherInstrs that are identical in lock-step to TI.
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 bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const DataLayout &DL)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool CasesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
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 > 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 MergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
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 cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
uint64_t getZExtValue() const
Get zero extended value.
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.
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 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.
void insertDbgRecordBefore(DbgRecord *DPV, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
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.
This class represents a no-op cast from one type to another.
The address of a basic block.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
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
bool isInlineAsm() const
Check if this call is an inline asm statement.
bool cannotMerge() const
Determine if the call cannot be tail merged.
bool isIndirectCall() const
Return true if the callsite is an indirect call.
Value * getCalledOperand() const
Intrinsic::ID getIntrinsicID() const
Returns the intrinsic ID of the intrinsic called or Intrinsic::not_intrinsic if the called function i...
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 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 * getICmp(unsigned short pred, Constant *LHS, Constant *RHS, bool OnlyIfReduced=false)
get* - Return some common constants without having to specify the full Instruction::OPCODE identifier...
static Constant * getNeg(Constant *C, bool HasNUW=false, 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...
Record of a variable value-assignment, aka a non instruction representation of the dbg....
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
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.
bool hasPostDomTree() const
Returns true if it holds a PostDominatorTree.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
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.
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.
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 * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
UnreachableInst * CreateUnreachable()
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
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)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles=std::nullopt)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
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 * 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 * 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:
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const LLVM_READONLY
This function determines if the specified instruction executes the same operation as the current one.
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.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
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 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.
BasicBlock * getUnwindDest() const
void setNormalDest(BasicBlock *B)
void setUnwindDest(BasicBlock *B)
BasicBlock * getNormalDest() const
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.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
const MDOperand & getOperand(unsigned I) const
unsigned getNumOperands() const
Return number of MDNode operands.
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.
LLVMContext & getContext() const
Get the global data context.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
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()
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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 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)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
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.
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()
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...
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.
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.
user_iterator user_begin()
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.
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.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
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)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
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.
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< DPValue * > getDPVAssignmentMarkers(const Instruction *Inst)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
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)
Interval::succ_iterator succ_end(Interval *I)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
void RemapDPValue(Module *M, DPValue *V, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DPValue V using the value map VM.
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 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.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
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...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
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 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.
Interval::pred_iterator pred_end(Interval *I)
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.
BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It)
Advance It while it points to a debug instruction and return the result.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
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 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.
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
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.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
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.
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.
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...
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.
void RemapDPValueRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DPValue V using the value map VM.
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)
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.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
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={})
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.
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.
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.
unsigned succ_size(const MachineBasicBlock *BB)
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.
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 DPValue 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.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
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.