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) &&
1133 if (isa<DbgInfoIntrinsic>(BonusInst))
1136 NewBonusInst->
takeName(&BonusInst);
1137 BonusInst.setName(NewBonusInst->
getName() +
".old");
1138 VMap[&BonusInst] = NewBonusInst;
1144 auto *UI = cast<Instruction>(U.getUser());
1145 auto *PN = dyn_cast<PHINode>(UI);
1147 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1148 "If the user is not a PHI node, then it should be in the same "
1149 "block as, and come after, the original bonus instruction.");
1153 if (PN->getIncomingBlock(U) == BB)
1157 assert(PN->getIncomingBlock(U) == PredBlock &&
1158 "Not in block-closed SSA form?");
1159 U.set(NewBonusInst);
1164bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1172 std::vector<ValueEqualityComparisonCase> BBCases;
1173 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1175 std::vector<ValueEqualityComparisonCase> PredCases;
1176 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1188 if (PredHasWeights) {
1191 if (Weights.
size() != 1 + PredCases.size())
1192 PredHasWeights = SuccHasWeights =
false;
1193 }
else if (SuccHasWeights)
1197 Weights.
assign(1 + PredCases.size(), 1);
1200 if (SuccHasWeights) {
1203 if (SuccWeights.
size() != 1 + BBCases.size())
1204 PredHasWeights = SuccHasWeights =
false;
1205 }
else if (PredHasWeights)
1206 SuccWeights.
assign(1 + BBCases.size(), 1);
1208 if (PredDefault == BB) {
1211 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1212 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1213 if (PredCases[i].Dest != BB)
1214 PTIHandled.insert(PredCases[i].
Value);
1217 std::swap(PredCases[i], PredCases.back());
1219 if (PredHasWeights || SuccHasWeights) {
1221 Weights[0] += Weights[i + 1];
1226 PredCases.pop_back();
1232 if (PredDefault != BBDefault) {
1234 if (DTU && PredDefault != BB)
1235 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1236 PredDefault = BBDefault;
1237 ++NewSuccessors[BBDefault];
1240 unsigned CasesFromPred = Weights.
size();
1242 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1243 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1244 PredCases.push_back(BBCases[i]);
1245 ++NewSuccessors[BBCases[i].Dest];
1246 if (SuccHasWeights || PredHasWeights) {
1250 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1251 ValidTotalSuccWeight += SuccWeights[i + 1];
1255 if (SuccHasWeights || PredHasWeights) {
1256 ValidTotalSuccWeight += SuccWeights[0];
1258 for (
unsigned i = 1; i < CasesFromPred; ++i)
1259 Weights[i] *= ValidTotalSuccWeight;
1261 Weights[0] *= SuccWeights[0];
1267 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1268 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1269 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1270 if (PredCases[i].Dest == BB) {
1273 if (PredHasWeights || SuccHasWeights) {
1274 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1279 std::swap(PredCases[i], PredCases.back());
1280 PredCases.pop_back();
1287 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1288 if (PTIHandled.count(BBCases[i].Value)) {
1290 if (PredHasWeights || SuccHasWeights)
1292 PredCases.push_back(BBCases[i]);
1293 ++NewSuccessors[BBCases[i].Dest];
1300 if (PredHasWeights || SuccHasWeights)
1302 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1303 ++NewSuccessors[BBDefault];
1315 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1317 for (
auto I :
seq(NewSuccessor.second)) {
1321 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1322 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1335 for (ValueEqualityComparisonCase &V : PredCases)
1338 if (PredHasWeights || SuccHasWeights) {
1355 if (!InfLoopBlock) {
1363 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1370 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1372 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1374 DTU->applyUpdates(Updates);
1377 ++NumFoldValueComparisonIntoPredecessors;
1385bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1388 Value *CV = isValueEqualityComparison(TI);
1389 assert(CV &&
"Not a comparison?");
1391 bool Changed =
false;
1394 while (!Preds.empty()) {
1403 Value *PCV = isValueEqualityComparison(PTI);
1409 for (
auto *Succ : FailBlocks) {
1415 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1429 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1430 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1431 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1450 if (
I->mayReadFromMemory())
1454 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1471 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1481 if (
auto *CB = dyn_cast<CallBase>(
I))
1482 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1489 if (
auto *J = dyn_cast<Instruction>(
Op))
1490 if (J->getParent() == BB)
1509 auto *C1 = dyn_cast<CallInst>(I1);
1510 auto *C2 = dyn_cast<CallInst>(I2);
1512 if (C1->isMustTailCall() != C2->isMustTailCall())
1520 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1521 if (CB1->cannotMerge() || CB1->isConvergent())
1523 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1524 if (CB2->cannotMerge() || CB2->isConvergent())
1539 if (!I1->hasDbgRecords())
1541 using CurrentAndEndIt =
1542 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1548 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1549 return Pair.first == Pair.second;
1555 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1561 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1563 if (!
Other->hasDbgRecords())
1566 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1573 while (
none_of(Itrs, atEnd)) {
1574 bool HoistDVRs = allIdentical(Itrs);
1575 for (CurrentAndEndIt &Pair : Itrs) {
1592bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1614 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1618 if (isa<PHINode>(*SuccItr))
1620 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1629 if (!INonDbg->isTerminator())
1639 unsigned NumSkipped = 0;
1642 if (SuccIterPairs.
size() > 2) {
1644 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1645 if (SuccIterPairs.
size() < 2)
1649 bool Changed =
false;
1652 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1653 auto &BB1ItrPair = *SuccIterPairBegin++;
1654 auto OtherSuccIterPairRange =
1661 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1663 return I1->isIdenticalToWhenDefined(I2);
1665 if (!AllDbgInstsAreIdentical) {
1666 while (isa<DbgInfoIntrinsic>(I1))
1667 I1 = &*++BB1ItrPair.first;
1668 for (
auto &SuccIter : OtherSuccIterRange) {
1670 while (isa<DbgInfoIntrinsic>(I2))
1675 bool AllInstsAreIdentical =
true;
1676 bool HasTerminator =
I1->isTerminator();
1677 for (
auto &SuccIter : OtherSuccIterRange) {
1680 if (AllInstsAreIdentical && !
I1->isIdenticalToWhenDefined(I2))
1681 AllInstsAreIdentical =
false;
1685 for (
auto &SuccIter : OtherSuccIterRange)
1690 if (HasTerminator) {
1694 if (NumSkipped || !AllInstsAreIdentical) {
1699 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1703 if (AllInstsAreIdentical) {
1704 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1705 AllInstsAreIdentical =
1707 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1709 unsigned SkipFlagsBB2 = Pair.second;
1719 if (AllInstsAreIdentical) {
1721 if (isa<DbgInfoIntrinsic>(I1)) {
1730 for (
auto &SuccIter : OtherSuccIterRange) {
1731 auto *I2 = &*SuccIter++;
1732 assert(isa<DbgInfoIntrinsic>(I2));
1744 for (
auto &SuccIter : OtherSuccIterRange) {
1758 NumHoistCommonCode += SuccIterPairs.
size();
1760 NumHoistCommonInstrs += SuccIterPairs.
size();
1769 for (
auto &SuccIterPair : SuccIterPairs) {
1778bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1782 auto *BI = dyn_cast<BranchInst>(TI);
1784 bool Changed =
false;
1789 auto *I2 = *OtherSuccTIs.
begin();
1805 if (isa<CallBrInst>(I1))
1810 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1812 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1832 if (!
NT->getType()->isVoidTy()) {
1833 I1->replaceAllUsesWith(NT);
1835 OtherSuccTI->replaceAllUsesWith(NT);
1839 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1845 for (
auto *OtherSuccTI : OtherSuccTIs)
1846 Locs.
push_back(OtherSuccTI->getDebugLoc());
1858 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1861 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1862 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1868 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1872 if (isa<FPMathOperator>(PN))
1881 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1882 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1883 PN.setIncomingValue(i, SI);
1894 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1899 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1903 DTU->applyUpdates(Updates);
1909 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1910 switch (II->getIntrinsicID()) {
1913 case Intrinsic::lifetime_start:
1914 case Intrinsic::lifetime_end:
1925 return !isa<IntrinsicInst>(
I);
1939 bool HasUse = !Insts.
front()->user_empty();
1940 for (
auto *
I : Insts) {
1942 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1943 I->getType()->isTokenTy())
1948 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1955 if (
const auto *
C = dyn_cast<CallBase>(
I))
1956 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1960 if (HasUse && !
I->hasOneUse())
1962 if (!HasUse && !
I->user_empty())
1967 for (
auto *
I : Insts) {
1968 if (!
I->isSameOperationAs(I0))
1974 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1976 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1985 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1988 auto *U = cast<Instruction>(*
I->user_begin());
1990 PNUse->getParent() == Succ &&
1991 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
1992 U->getParent() ==
I->getParent();
2007 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2011 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
2015 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2023 if (isa<CallBase>(I0)) {
2025 return cast<CallBase>(
I)->isIndirectCall();
2027 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2028 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2029 if (HaveIndirectCalls) {
2030 if (!AllCallsAreIndirect)
2034 Value *Callee =
nullptr;
2036 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2038 Callee = CurrCallee;
2039 else if (Callee != CurrCallee)
2045 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2047 if (
Op->getType()->isTokenTy())
2055 if (!
all_of(Insts, SameAsI0)) {
2060 for (
auto *
I : Insts)
2061 PHIOperands[
I].push_back(
I->getOperand(OI));
2071 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2076 for (
auto *BB :
Blocks) {
2079 I =
I->getPrevNode();
2080 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2081 if (!isa<DbgInfoIntrinsic>(
I))
2091 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
2093 auto *U = cast<Instruction>(*
I->user_begin());
2119 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2122 PN->insertBefore(BBEnd->begin());
2123 for (
auto *
I : Insts)
2124 PN->addIncoming(
I->getOperand(O),
I->getParent());
2133 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2136 for (
auto *
I : Insts)
2155 PN->replaceAllUsesWith(I0);
2156 PN->eraseFromParent();
2160 for (
auto *
I : Insts) {
2165 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2166 I->replaceAllUsesWith(I0);
2167 I->eraseFromParent();
2183 class LockstepReverseIterator {
2196 for (
auto *BB : Blocks) {
2198 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2216 for (
auto *&Inst : Insts) {
2217 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2230 for (
auto *&Inst : Insts) {
2231 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2294 bool HaveNonUnconditionalPredecessors =
false;
2296 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2297 if (PredBr && PredBr->isUnconditional())
2300 HaveNonUnconditionalPredecessors =
true;
2302 if (UnconditionalPreds.
size() < 2)
2314 LockstepReverseIterator LRI(UnconditionalPreds);
2315 while (LRI.isValid() &&
2317 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2319 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2330 if (!followedByDeoptOrUnreachable) {
2334 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2335 unsigned NumPHIdValues = 0;
2336 for (
auto *
I : *LRI)
2337 for (
auto *V : PHIOperands[
I]) {
2338 if (!InstructionsToSink.
contains(V))
2344 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2345 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.
size();
2346 if ((NumPHIdValues % UnconditionalPreds.
size()) != 0)
2349 return NumPHIInsts <= 1;
2366 while (
Idx < ScanIdx) {
2367 if (!ProfitableToSinkInstruction(LRI)) {
2370 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2373 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2383 if (
Idx < ScanIdx) {
2386 InstructionsToSink = InstructionsProfitableToSink;
2392 !ProfitableToSinkInstruction(LRI) &&
2393 "We already know that the last instruction is unprofitable to sink");
2401 for (
auto *
I : *LRI)
2402 InstructionsProfitableToSink.
erase(
I);
2403 if (!ProfitableToSinkInstruction(LRI)) {
2406 InstructionsToSink = InstructionsProfitableToSink;
2418 bool Changed =
false;
2420 if (HaveNonUnconditionalPredecessors) {
2421 if (!followedByDeoptOrUnreachable) {
2429 bool Profitable =
false;
2430 while (
Idx < ScanIdx) {
2464 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2466 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2476 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2480 NumSinkCommonInstrs++;
2484 ++NumSinkCommonCode;
2490struct CompatibleSets {
2508 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2517 getCompatibleSet(II).emplace_back(II);
2521 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2527 if (
any_of(Invokes, IsIllegalToMerge))
2533 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2534 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2535 if (HaveIndirectCalls) {
2536 if (!AllCallsAreIndirect)
2543 assert(CurrCallee &&
"There is always a called operand.");
2546 else if (Callee != CurrCallee)
2556 if (
any_of(Invokes, HasNormalDest)) {
2559 if (!
all_of(Invokes, HasNormalDest))
2566 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2568 NormalBB = CurrNormalBB;
2569 else if (NormalBB != CurrNormalBB)
2577 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2588 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2590 UnwindBB = CurrUnwindBB;
2592 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2599 Invokes.front()->getUnwindDest(),
2600 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2606 for (
auto *II : Invokes.drop_front())
2611 auto IsIllegalToMergeArguments = [](
auto Ops) {
2612 Use &U0 = std::get<0>(Ops);
2613 Use &U1 = std::get<1>(Ops);
2620 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2621 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2622 IsIllegalToMergeArguments))
2634 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2640 bool HasNormalDest =
2641 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2645 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2654 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2656 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2658 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2660 if (!HasNormalDest) {
2664 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2671 return MergedInvoke;
2685 SuccBBOfMergedInvoke});
2692 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2695 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2698 for (
Use &U : MergedInvoke->operands()) {
2700 if (MergedInvoke->isCallee(&U)) {
2701 if (!IsIndirectCall)
2703 }
else if (!MergedInvoke->isDataOperand(&U))
2715 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2727 Invokes.front()->getParent());
2735 if (!MergedDebugLoc)
2744 OrigSuccBB->removePredecessor(II->
getParent());
2750 MergedInvoke->setDebugLoc(MergedDebugLoc);
2751 ++NumInvokeSetsFormed;
2754 DTU->applyUpdates(Updates);
2781 bool Changed =
false;
2787 CompatibleSets Grouper;
2793 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2797 if (Invokes.
size() < 2)
2809class EphemeralValueTracker {
2813 if (isa<AssumeInst>(
I))
2815 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2817 return EphValues.count(cast<Instruction>(U));
2823 if (isEphemeral(
I)) {
2862 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2874 unsigned MaxNumInstToLookAt = 9;
2878 if (!MaxNumInstToLookAt)
2880 --MaxNumInstToLookAt;
2883 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2886 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2890 if (SI->getPointerOperand() == StorePtr &&
2891 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
2892 SI->getAlign() >= StoreToHoist->
getAlign())
2894 return SI->getValueOperand();
2898 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2899 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2900 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
2923 unsigned &SpeculatedInstructions,
2931 bool HaveRewritablePHIs =
false;
2949 HaveRewritablePHIs =
true;
2952 if (!OrigCE && !ThenCE)
2959 if (OrigCost + ThenCost > MaxCost)
2966 ++SpeculatedInstructions;
2967 if (SpeculatedInstructions > 1)
2971 return HaveRewritablePHIs;
3011bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
3018 if (isa<FCmpInst>(BrCond))
3028 bool Invert =
false;
3037 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
3040 (TWeight + FWeight) != 0) {
3041 uint64_t EndWeight = Invert ? TWeight : FWeight;
3045 if (BIEndProb >= Likely)
3059 unsigned SpeculatedInstructions = 0;
3060 Value *SpeculatedStoreValue =
nullptr;
3062 EphemeralValueTracker EphTracker;
3065 if (isa<DbgInfoIntrinsic>(
I)) {
3073 if (isa<PseudoProbeInst>(
I)) {
3083 if (EphTracker.track(&
I))
3088 ++SpeculatedInstructions;
3089 if (SpeculatedInstructions > 1)
3095 &
I, BB, ThenBB, EndBB))))
3097 if (!SpeculatedStoreValue &&
3103 if (SpeculatedStoreValue)
3104 SpeculatedStore = cast<StoreInst>(&
I);
3109 for (
Use &
Op :
I.operands()) {
3114 ++SinkCandidateUseCounts[OpI];
3121 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3123 ++SpeculatedInstructions;
3124 if (SpeculatedInstructions > 1)
3130 bool Convert = SpeculatedStore !=
nullptr;
3133 SpeculatedInstructions,
3135 if (!Convert ||
Cost > Budget)
3139 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3142 if (SpeculatedStoreValue) {
3146 Value *FalseV = SpeculatedStoreValue;
3150 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3179 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3181 DbgAssign->replaceVariableLocationOp(OrigV, S);
3194 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3196 if (!isa<DbgAssignIntrinsic>(&
I))
3199 I.dropUBImplyingAttrsAndMetadata();
3202 if (EphTracker.contains(&
I)) {
3204 I.eraseFromParent();
3218 It.dropOneDbgRecord(&DR);
3220 std::prev(ThenBB->
end()));
3237 Value *TrueV = ThenV, *FalseV = OrigV;
3251 if (!isa<DbgAssignIntrinsic>(
I))
3252 I->eraseFromParent();
3262 EphemeralValueTracker EphTracker;
3268 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3269 if (CI->cannotDuplicate() || CI->isConvergent())
3275 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3282 for (
User *U :
I.users()) {
3284 if (UI->
getParent() != BB || isa<PHINode>(UI))
3298 auto *
I = dyn_cast<Instruction>(V);
3299 if (
I &&
I->getParent() == To)
3303 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3315static std::optional<bool>
3331 if (
auto *CB = dyn_cast<ConstantInt>(U))
3336 KnownValues[CB].
insert(Pred);
3340 if (KnownValues.
empty())
3349 for (
const auto &Pair : KnownValues) {
3367 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3370 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3378 EdgeBB->setName(RealDest->
getName() +
".critedge");
3379 EdgeBB->moveBefore(RealDest);
3389 TranslateMap[
Cond] = CB;
3395 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3402 N->insertInto(EdgeBB, InsertPt);
3405 N->setName(BBI->getName() +
".c");
3408 for (
Use &
Op :
N->operands()) {
3410 if (PI != TranslateMap.
end())
3416 if (!BBI->use_empty())
3417 TranslateMap[&*BBI] = V;
3418 if (!
N->mayHaveSideEffects()) {
3419 N->eraseFromParent();
3424 if (!BBI->use_empty())
3425 TranslateMap[&*BBI] =
N;
3431 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3432 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3433 SrcDbgCursor = std::next(BBI);
3435 N->cloneDebugInfoFrom(&*BBI);
3438 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3444 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3445 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3446 InsertPt->cloneDebugInfoFrom(BI);
3449 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3455 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3456 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3467 return std::nullopt;
3477 std::optional<bool> Result;
3478 bool EverChanged =
false;
3482 EverChanged |= Result == std::nullopt || *Result;
3483 }
while (Result == std::nullopt);
3505 if (isa<ConstantInt>(IfCond))
3512 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3515 "Will have either one or two blocks to speculate.");
3522 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3525 (TWeight + FWeight) != 0) {
3530 if (IfBlocks.
size() == 1) {
3532 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3533 if (BIBBProb >= Likely)
3536 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3544 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3545 if (IfCondPhiInst->getParent() == BB)
3553 unsigned NumPhis = 0;
3566 bool Changed =
false;
3568 PHINode *PN = cast<PHINode>(II++);
3585 PN = dyn_cast<PHINode>(BB->
begin());
3591 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3602 auto IsBinOpOrAnd = [](
Value *V) {
3622 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3635 <<
" T: " << IfTrue->
getName()
3636 <<
" F: " << IfFalse->
getName() <<
"\n");
3650 if (isa<FPMathOperator>(PN))
3670 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3688 if (Opc == Instruction::And)
3690 if (Opc == Instruction::Or)
3703 bool PredHasWeights =
3705 bool SuccHasWeights =
3707 if (PredHasWeights || SuccHasWeights) {
3708 if (!PredHasWeights)
3709 PredTrueWeight = PredFalseWeight = 1;
3710 if (!SuccHasWeights)
3711 SuccTrueWeight = SuccFalseWeight = 1;
3721static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3725 "Both blocks must end with a conditional branches.");
3727 "PredBB must be a predecessor of BB.");
3735 (PTWeight + PFWeight) != 0) {
3743 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3744 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3748 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3751 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3752 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3758 return std::nullopt;
3771 bool InvertPredCond;
3772 std::tie(CommonSucc, Opc, InvertPredCond) =
3775 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3782 {LLVMContext::MD_annotation});
3785 if (InvertPredCond) {
3798 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3800 SuccTrueWeight, SuccFalseWeight)) {
3807 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3813 (SuccFalseWeight + SuccTrueWeight) +
3814 PredTrueWeight * SuccFalseWeight);
3820 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3821 PredFalseWeight * SuccTrueWeight);
3823 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3841 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3842 {DominatorTree::Delete, PredBlock, BB}});
3869 ++NumFoldBranchToCommonDest;
3876 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3877 return U->getType()->isVectorTy();
3887 unsigned BonusInstThreshold) {
3901 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3902 !isa<SelectInst>(
Cond)) ||
3903 Cond->getParent() != BB || !
Cond->hasOneUse())
3913 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3924 bool InvertPredCond;
3926 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3958 unsigned NumBonusInsts = 0;
3959 bool SawVectorOp =
false;
3960 const unsigned PredCount = Preds.
size();
3966 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3977 NumBonusInsts += PredCount;
3985 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3986 auto *UI = cast<Instruction>(U.getUser());
3987 if (
auto *PN = dyn_cast<PHINode>(UI))
3989 return UI->
getParent() == BB &&
I.comesBefore(UI);
3993 if (!
all_of(
I.uses(), IsBCSSAUse))
3997 BonusInstThreshold *
4003 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4013 for (
auto *BB : {BB1, BB2}) {
4017 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4029 Value *AlternativeV =
nullptr) {
4047 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4048 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4049 PHI = cast<PHINode>(
I);
4055 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4056 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4064 if (!AlternativeV &&
4065 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4070 PHI->addIncoming(V, BB);
4080 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4089 if (!PStore || !QStore)
4110 if (
I.mayReadOrWriteMemory())
4112 for (
auto &
I : *QFB)
4113 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4116 for (
auto &
I : *QTB)
4117 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4121 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4137 if (
I.isTerminator())
4141 if (
auto *S = dyn_cast<StoreInst>(&
I))
4145 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4155 "When we run out of budget we will eagerly return from within the "
4156 "per-instruction loop.");
4160 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4162 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4163 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4271 bool InvertPCond =
false, InvertQCond =
false;
4277 if (QFB == PostBB) {
4296 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4299 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4307 for (
auto *BB : {PTB, PFB}) {
4312 PStoreAddresses.
insert(SI->getPointerOperand());
4314 for (
auto *BB : {QTB, QFB}) {
4319 QStoreAddresses.
insert(SI->getPointerOperand());
4325 auto &CommonAddresses = PStoreAddresses;
4327 bool Changed =
false;
4328 for (
auto *Address : CommonAddresses)
4331 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4351 if (!IfFalseBB->
phis().empty())
4361 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4372 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4373 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4384 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4385 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4464 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4466 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4470 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4473 if (CommonDestProb >= Likely)
4483 unsigned NumPhis = 0;
4505 if (OtherDest == BB) {
4512 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4513 OtherDest = InfLoopBlock;
4533 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4548 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4549 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4552 SuccTrueWeight, SuccFalseWeight);
4554 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4555 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4556 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4557 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4561 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4562 PredOther * SuccCommon,
4563 PredOther * SuccOther};
4592 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4593 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4594 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4595 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4598 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4599 PredOther * SuccCommon};
4621bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4632 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4639 if (Succ == KeepEdge1)
4640 KeepEdge1 =
nullptr;
4641 else if (Succ == KeepEdge2)
4642 KeepEdge2 =
nullptr;
4647 if (Succ != TrueBB && Succ != FalseBB)
4648 RemovedSuccessors.
insert(Succ);
4656 if (!KeepEdge1 && !KeepEdge2) {
4657 if (TrueBB == FalseBB) {
4665 if (TrueWeight != FalseWeight)
4668 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4690 for (
auto *RemovedSuccessor : RemovedSuccessors)
4691 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4692 DTU->applyUpdates(Updates);
4702bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4707 if (!TrueVal || !FalseVal)
4712 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4713 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4716 uint32_t TrueWeight = 0, FalseWeight = 0;
4721 if (Weights.
size() == 1 +
SI->getNumCases()) {
4723 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4725 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4730 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4739bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4752 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4773bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4793 if (
SI->getCondition() != V)
4799 if (
SI->getDefaultDest() != BB) {
4801 assert(VVal &&
"Should have a unique destination value");
4809 return requestResimplify();
4815 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4825 return requestResimplify();
4832 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4857 auto W0 = SIW.getSuccessorWeight(0);
4861 SIW.setSuccessorWeight(0, *NewW);
4863 SIW.addCase(Cst, NewBB, NewW);
4865 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4874 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4875 DTU->applyUpdates(Updates);
4883bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4895 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4898 Value *CompVal = ConstantCompare.CompValue;
4899 unsigned UsedICmps = ConstantCompare.UsedICmps;
4900 Value *ExtraCase = ConstantCompare.Extra;
4919 if (ExtraCase && Values.
size() < 2)
4934 <<
" cases into SWITCH. BB is:\n"
4944 nullptr,
"switch.early.test");
4968 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4974 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4975 <<
"\nEXTRABB = " << *BB);
4983 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4990 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4991 New->addCase(Values[i], EdgeBB);
4997 PHINode *PN = cast<PHINode>(BBI);
4999 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5006 DTU->applyUpdates(Updates);
5008 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5014 return simplifyCommonResume(RI);
5018 return simplifySingleResume(RI);
5026 auto *II = dyn_cast<IntrinsicInst>(&
I);
5031 switch (IntrinsicID) {
5032 case Intrinsic::dbg_declare:
5033 case Intrinsic::dbg_value:
5034 case Intrinsic::dbg_label:
5035 case Intrinsic::lifetime_end:
5045bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5055 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5058 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5060 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5061 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5065 if (IncomingBB->getUniqueSuccessor() != BB)
5068 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5070 if (IncomingValue != LandingPad)
5074 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5075 TrivialUnwindBlocks.
insert(IncomingBB);
5079 if (TrivialUnwindBlocks.
empty())
5083 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5087 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5101 TrivialBB->getTerminator()->eraseFromParent();
5104 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5111 return !TrivialUnwindBlocks.empty();
5115bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5119 "Resume must unwind the exception that caused control to here");
5123 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5159 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5176 int Idx = DestPN.getBasicBlockIndex(BB);
5190 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5191 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5193 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5197 DestPN.addIncoming(
Incoming, Pred);
5224 std::vector<DominatorTree::UpdateType> Updates;
5228 if (UnwindDest ==
nullptr) {
5240 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5241 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5268 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5269 if (!SuccessorCleanupPad)
5278 SuccessorCleanupPad->eraseFromParent();
5307 bool Changed =
false;
5336 BBI->dropDbgRecords();
5340 BBI->eraseFromParent();
5346 if (&BB->
front() != UI)
5349 std::vector<DominatorTree::UpdateType> Updates;
5352 for (
unsigned i = 0, e = Preds.size(); i != e; ++i) {
5353 auto *Predecessor = Preds[i];
5356 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5360 [BB](
auto *
Successor) { return Successor == BB; })) {
5368 "The destinations are guaranteed to be different here.");
5379 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5385 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5386 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5388 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5389 if (i->getCaseSuccessor() != BB) {
5394 i = SU.removeCase(i);
5399 if (DTU &&
SI->getDefaultDest() != BB)
5400 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5401 }
else if (
auto *II = dyn_cast<InvokeInst>(TI)) {
5404 DTU->applyUpdates(Updates);
5408 if (!CI->doesNotThrow())
5409 CI->setDoesNotThrow();
5412 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5413 if (CSI->getUnwindDest() == BB) {
5415 DTU->applyUpdates(Updates);
5424 E = CSI->handler_end();
5427 CSI->removeHandler(
I);
5434 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5435 if (CSI->getNumHandlers() == 0) {
5436 if (CSI->hasUnwindDest()) {
5440 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5441 Updates.push_back({DominatorTree::Insert,
5442 PredecessorOfPredecessor,
5443 CSI->getUnwindDest()});
5444 Updates.push_back({DominatorTree::Delete,
5445 PredecessorOfPredecessor, Predecessor});
5448 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5452 DTU->applyUpdates(Updates);
5461 CSI->eraseFromParent();
5464 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5466 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5467 "Expected to always have an unwind to BB.");
5469 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5477 DTU->applyUpdates(Updates);
5492 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5493 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5502 auto *BB = Switch->getParent();
5503 auto *OrigDefaultBlock = Switch->getDefaultDest();
5504 OrigDefaultBlock->removePredecessor(BB);
5509 Switch->setDefaultDest(&*NewDefaultBlock);
5512 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5514 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5522bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(
SwitchInst *SI,
5524 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5527 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5529 auto *BB =
SI->getParent();
5532 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5537 for (
auto Case :
SI->cases()) {
5541 if (Dest == DestA) {
5547 if (Dest == DestB) {
5557 "Single-destination switch should have been folded.");
5559 assert(DestB !=
SI->getDefaultDest());
5560 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5568 ContiguousCases = &CasesA;
5569 ContiguousDest = DestA;
5572 ContiguousCases = &CasesB;
5573 ContiguousDest = DestB;
5582 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5584 Value *Sub =
SI->getCondition();
5585 if (!
Offset->isNullValue())
5600 if (Weights.
size() == 1 +
SI->getNumCases()) {
5603 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5604 if (
SI->getSuccessor(
I) == ContiguousDest)
5605 TrueWeight += Weights[
I];
5607 FalseWeight += Weights[
I];
5609 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5618 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5619 unsigned PreviousEdges = ContiguousCases->
size();
5620 if (ContiguousDest ==
SI->getDefaultDest())
5622 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5623 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5625 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5626 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5627 if (OtherDest ==
SI->getDefaultDest())
5629 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5630 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5638 auto *UnreachableDefault =
SI->getDefaultDest();
5641 SI->eraseFromParent();
5643 if (!HasDefault && DTU)
5644 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5660 unsigned MaxSignificantBitsInCond =
5667 for (
const auto &Case : SI->cases()) {
5668 auto *
Successor = Case.getCaseSuccessor();
5674 const APInt &CaseVal = Case.getCaseValue()->getValue();
5677 DeadCases.
push_back(Case.getCaseValue());
5690 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5691 const unsigned NumUnknownBits =
5694 if (HasDefault && DeadCases.
empty() &&
5695 NumUnknownBits < 64 &&
5696 SI->getNumCases() == (1ULL << NumUnknownBits)) {
5701 if (DeadCases.
empty())
5707 assert(CaseI != SI->case_default() &&
5708 "Case was not found. Probably mistake in DeadCases forming.");
5710 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5715 std::vector<DominatorTree::UpdateType> Updates;
5716 for (
auto *
Successor : UniqueSuccessors)
5717 if (NumPerSuccessorCases[
Successor] == 0)
5718 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5738 if (!Branch || !Branch->isUnconditional())
5744 int Idx =
PHI.getBasicBlockIndex(BB);
5745 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5748 if (InValue != CaseValue)
5764 ForwardingNodesMap ForwardingNodes;
5766 bool Changed =
false;
5767 for (
const auto &Case : SI->cases()) {
5769 BasicBlock *CaseDest = Case.getCaseSuccessor();
5788 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
5789 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
5790 count(Phi.blocks(), SwitchBlock) == 1) {
5791 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
5799 ForwardingNodes[Phi].push_back(PhiIdx);
5802 for (
auto &ForwardingNode : ForwardingNodes) {
5803 PHINode *Phi = ForwardingNode.first;
5805 if (Indexes.
size() < 2)
5808 for (
int Index : Indexes)
5809 Phi->setIncomingValue(
Index, SI->getCondition());
5819 if (
C->isThreadDependent())
5821 if (
C->isDLLImportDependent())
5824 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
5825 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
5826 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
5832 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
5848 if (
Constant *
C = dyn_cast<Constant>(V))
5864 if (
A->isAllOnesValue())
5866 if (
A->isNullValue())
5872 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
5897 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
5899 if (
I.isTerminator()) {
5901 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
5904 CaseDest =
I.getSuccessor(0);
5911 for (
auto &
Use :
I.uses()) {
5914 if (
I->getParent() == CaseDest)
5917 if (Phi->getIncomingBlock(
Use) == CaseDest)
5930 *CommonDest = CaseDest;
5932 if (CaseDest != *CommonDest)
5937 int Idx =
PHI.getBasicBlockIndex(Pred);
5950 Res.push_back(std::make_pair(&
PHI, ConstVal));
5953 return Res.size() > 0;
5959 SwitchCaseResultVectorTy &UniqueResults,
5961 for (
auto &
I : UniqueResults) {
5962 if (
I.first == Result) {
5963 I.second.push_back(CaseVal);
5964 return I.second.size();
5967 UniqueResults.push_back(
5978 SwitchCaseResultVectorTy &UniqueResults,
5982 uintptr_t MaxUniqueResults) {
5983 for (
const auto &
I : SI->cases()) {
5997 const size_t NumCasesForResult =
6005 if (UniqueResults.size() > MaxUniqueResults)
6016 BasicBlock *DefaultDest = SI->getDefaultDest();
6017 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6022 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6023 if ((!DefaultResult &&
6044 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6045 ResultVector[1].second.size() == 1) {
6046 ConstantInt *FirstCase = ResultVector[0].second[0];
6047 ConstantInt *SecondCase = ResultVector[1].second[0];
6048 Value *SelectValue = ResultVector[1].first;
6049 if (DefaultResult) {
6050 Value *ValueCompare =
6051 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6052 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6053 DefaultResult,
"switch.select");
6055 Value *ValueCompare =
6056 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6057 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6058 SelectValue,
"switch.select");
6062 if (ResultVector.size() == 1 && DefaultResult) {
6064 unsigned CaseCount = CaseValues.
size();
6072 for (
auto *Case : CaseValues)
6073 if (Case->getValue().slt(MinCaseVal->
getValue()))
6078 for (
auto *Case : CaseValues)
6079 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6085 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6089 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6094 if (CaseValues.
size() == 2) {
6096 "switch.selectcmp.case1");
6098 "switch.selectcmp.case2");
6099 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6100 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6113 std::vector<DominatorTree::UpdateType> Updates;
6119 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6124 PHI->removeIncomingValueIf(
6125 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6126 PHI->addIncoming(SelectValue, SelectBB);
6129 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6135 if (DTU && RemovedSuccessors.
insert(Succ).second)
6136 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6138 SI->eraseFromParent();
6153 SwitchCaseResultVectorTy UniqueResults;
6159 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6161 Value *SelectValue =
6173class SwitchLookupTable {
6224 bool LinearMapValWrapped =
false;
6232SwitchLookupTable::SwitchLookupTable(
6236 assert(Values.
size() &&
"Can't build lookup table without values!");
6237 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6240 SingleValue = Values.
begin()->second;
6246 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6252 TableContents[
Idx] = CaseRes;
6254 if (CaseRes != SingleValue)
6255 SingleValue =
nullptr;
6259 if (Values.
size() < TableSize) {
6261 "Need a default value to fill the lookup table holes.");
6264 if (!TableContents[
I])
6265 TableContents[
I] = DefaultValue;
6268 if (DefaultValue != SingleValue)
6269 SingleValue =
nullptr;
6275 Kind = SingleValueKind;
6282 bool LinearMappingPossible =
true;
6287 bool NonMonotonic =
false;
6288 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6291 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6295 LinearMappingPossible =
false;
6300 APInt Dist = Val - PrevVal;
6303 }
else if (Dist != DistToPrev) {
6304 LinearMappingPossible =
false;
6312 if (LinearMappingPossible) {
6313 LinearOffset = cast<ConstantInt>(TableContents[0]);
6314 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6315 bool MayWrap =
false;
6316 APInt M = LinearMultiplier->getValue();
6317 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6318 LinearMapValWrapped = NonMonotonic || MayWrap;
6319 Kind = LinearMapKind;
6326 if (WouldFitInRegister(
DL, TableSize,
ValueType)) {
6328 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6330 TableInt <<=
IT->getBitWidth();
6332 if (!isa<UndefValue>(TableContents[
I - 1])) {
6333 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6334 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6337 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6338 BitMapElementTy =
IT;
6349 GlobalVariable::PrivateLinkage, Initializer,
6350 "switch.table." + FuncName);
6351 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6360 case SingleValueKind:
6362 case LinearMapKind: {
6365 false,
"switch.idx.cast");
6366 if (!LinearMultiplier->isOne())
6367 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6369 !LinearMapValWrapped);
6371 if (!LinearOffset->isZero())
6374 !LinearMapValWrapped);
6390 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6391 "switch.shiftamt",
true,
true);
6394 Value *DownShifted =
6395 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6397 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6403 Array->getInitializer()->getType()->getArrayNumElements();
6404 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6407 "switch.tableidx.zext");
6411 GEPIndices,
"switch.gep");
6413 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6420bool SwitchLookupTable::WouldFitInRegister(
const DataLayout &
DL,
6422 Type *ElementType) {
6423 auto *
IT = dyn_cast<IntegerType>(ElementType);
6430 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6432 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6441 auto *
IT = dyn_cast<IntegerType>(Ty);
6453 DL.fitsInLegalInteger(
IT->getBitWidth());
6465 return NumCases * 100 >= CaseRange * MinDensity;
6486 if (SI->getNumCases() > TableSize)
6489 bool AllTablesFitInRegister =
true;
6490 bool HasIllegalType =
false;
6491 for (
const auto &
I : ResultTypes) {
6492 Type *Ty =
I.second;
6498 AllTablesFitInRegister =
6499 AllTablesFitInRegister &&
6500 SwitchLookupTable::WouldFitInRegister(
DL, TableSize, Ty);
6505 if (HasIllegalType && !AllTablesFitInRegister)
6510 if (AllTablesFitInRegister)
6527 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6530 return all_of(ResultTypes, [&](
const auto &KV) {
6531 return SwitchLookupTable::WouldFitInRegister(
6560 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6580 DefaultValue, CmpOp1,
true);
6581 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6586 for (
auto ValuePair : Values) {
6588 ValuePair.second, CmpOp1,
true);
6589 if (!CaseConst || CaseConst == DefaultConst ||
6590 (CaseConst != TrueConst && CaseConst != FalseConst))
6604 if (DefaultConst == FalseConst) {
6607 ++NumTableCmpReuses;
6610 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6611 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6614 ++NumTableCmpReuses;
6624 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6643 if (SI->getNumCases() < 3)
6648 assert(!SI->cases().empty());
6665 MinCaseVal = CaseVal;
6667 MaxCaseVal = CaseVal;
6672 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6682 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6688 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6696 bool HasDefaultResults =
6698 DefaultResultsList,
DL,
TTI);
6700 for (
const auto &
I : DefaultResultsList) {
6703 DefaultResults[
PHI] = Result;
6707 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6709 if (UseSwitchConditionAsTableIndex)
6715 bool TableHasHoles = (NumResults < TableSize);
6716 bool NeedMask = (TableHasHoles && !HasDefaultResults);
6719 if (SI->getNumCases() < 4)
6721 if (!
DL.fitsInLegalInteger(TableSize))
6728 std::vector<DominatorTree::UpdateType> Updates;
6734 assert(MaxTableSize >= TableSize &&
6735 "It is impossible for a switch to have more entries than the max "
6736 "representable value of its input integer type's size.");
6741 bool DefaultIsReachable =
6742 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
6753 if (UseSwitchConditionAsTableIndex) {
6754 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
6755 TableIndex = SI->getCondition();
6757 TableIndexOffset = MinCaseVal;
6760 bool MayWrap =
true;
6761 if (!DefaultIsReachable) {
6766 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
6767 "switch.tableidx",
false,
6776 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
6784 return SwitchLookupTable::WouldFitInRegister(
6785 DL, UpperBound, KV.second );
6789 TableSize = std::max(UpperBound, TableSize);
6792 DefaultIsReachable =
false;
6796 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
6797 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6800 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6805 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
6807 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
6809 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6819 MaskBB->
setName(
"switch.hole_check");
6826 APInt MaskInt(TableSizePowOf2, 0);
6827 APInt One(TableSizePowOf2, 1);
6829 const ResultListTy &ResultList = ResultLists[PHIs[0]];
6830 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
6833 MaskInt |= One <<
Idx;
6843 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
6846 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
6848 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
6849 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
6855 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6858 SI->getDefaultDest()->removePredecessor(BB,
6861 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
6865 const ResultListTy &ResultList = ResultLists[
PHI];
6868 Constant *DV = NeedMask ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
6870 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
6873 Value *Result = Table.BuildLookup(TableIndex, Builder);
6877 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
6880 for (
auto *
User :
PHI->users()) {
6885 PHI->addIncoming(Result, LookupBB);
6890 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
6894 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6897 if (Succ == SI->getDefaultDest())
6900 if (DTU && RemovedSuccessors.
insert(Succ).second)
6901 Updates.push_back({DominatorTree::Delete, BB, Succ});
6903 SI->eraseFromParent();
6910 ++NumLookupTablesHoles;
6925 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
6926 if (CondTy->getIntegerBitWidth() > 64 ||
6927 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6931 if (SI->getNumCases() < 4)
6939 for (
const auto &
C : SI->cases())
6940 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
6948 int64_t
Base = Values[0];
6949 for (
auto &V : Values)
6962 unsigned Shift = 64;
6963 for (
auto &V : Values)
6967 for (
auto &V : Values)
6968 V = (int64_t)((
uint64_t)V >> Shift);
6984 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
6987 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
6989 Ty, Intrinsic::fshl,
6990 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
6991 SI->replaceUsesOfWith(SI->getCondition(), Rot);
6993 for (
auto Case : SI->cases()) {
6994 auto *Orig = Case.getCaseValue();
6995 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base);
6996 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7012 Value *Condition = SI->getCondition();
7014 auto *CondTy = cast<IntegerType>(Condition->
getType());
7016 if (CondTy->getIntegerBitWidth() > 64 ||
7017 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7031 if (SI->getNumCases() < 4)
7037 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7042 for (
const auto &Case : SI->cases()) {
7043 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7060 for (
auto &Case : SI->cases()) {
7061 auto *OrigValue = Case.getCaseValue();
7062 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7063 OrigValue->getValue().countr_zero()));
7070 SI->setCondition(ConditionTrailingZeros);
7078 if (isValueEqualityComparison(SI)) {
7082 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7083 return requestResimplify();
7087 if (SimplifySwitchOnSelect(SI,
Select))
7088 return requestResimplify();
7093 if (FoldValueComparisonIntoPredecessors(SI, Builder))
7094 return requestResimplify();
7100 if (
Options.ConvertSwitchRangeToICmp && TurnSwitchRangeIntoICmp(SI, Builder))
7101 return requestResimplify();
7105 return requestResimplify();
7108 return requestResimplify();
7111 return requestResimplify();
7118 if (
Options.ConvertSwitchToLookupTable &&
7120 return requestResimplify();
7123 return requestResimplify();
7126 return requestResimplify();
7129 hoistCommonCodeFromSuccessors(
SI->getParent(), !
Options.HoistCommonInsts))
7130 return requestResimplify();
7137 bool Changed =
false;
7146 RemovedSuccs.
insert(Dest);
7156 std::vector<DominatorTree::UpdateType> Updates;
7157 Updates.reserve(RemovedSuccs.
size());
7158 for (
auto *RemovedSucc : RemovedSuccs)
7159 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7160 DTU->applyUpdates(Updates);
7178 if (SimplifyIndirectBrOnSelect(IBI, SI))
7179 return requestResimplify();
7211 if (isa<PHINode>(*Succ->
begin()))
7215 if (BB == OtherPred)
7221 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7227 std::vector<DominatorTree::UpdateType> Updates;
7235 "unexpected successor");
7238 Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
7239 Updates.push_back({DominatorTree::Delete, Pred, BB});
7246 if (isa<DbgInfoIntrinsic>(Inst))
7253 Updates.push_back({DominatorTree::Delete, BB, Succ});
7267 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7268 : simplifyCondBranch(
Branch, Builder);
7271bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7283 bool NeedCanonicalLoop =
7294 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7296 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7298 if (
I->isTerminator() &&
7299 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7306 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7316 if (
Options.SpeculateBlocks &&
7319 return requestResimplify();
7327 if (!PPred || (PredPred && PredPred != PPred))
7338 "Tautological conditional branch should have been eliminated already.");
7341 if (!
Options.SimplifyCondBranch ||
7346 if (isValueEqualityComparison(BI)) {
7351 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
7352 return requestResimplify();
7358 if (FoldValueComparisonIntoPredecessors(BI, Builder))
7359 return requestResimplify();
7362 if (&*
I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
7363 return requestResimplify();
7368 if (SimplifyBranchOnICmpChain(BI, Builder,
DL))
7381 return requestResimplify();
7387 if (
Options.SpeculateBlocks &&
7390 return requestResimplify();
7400 return requestResimplify();
7408 return requestResimplify();
7417 return requestResimplify();
7424 return requestResimplify();
7429 if (PBI != BI && PBI->isConditional())
7431 return requestResimplify();
7436 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
7437 if (PBI != BI && PBI->isConditional())
7439 return requestResimplify();
7453 if (
C->isNullValue() || isa<UndefValue>(
C)) {
7455 auto *
Use = cast<Instruction>(*
I->user_begin());
7459 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
7473 if (
GEP->getPointerOperand() ==
I) {
7480 if (!
GEP->hasAllZeroIndices() &&
7481 (!
GEP->isInBounds() ||
7483 GEP->getPointerAddressSpace())))
7484 PtrValueMayBeModified =
true;
7490 bool HasNoUndefAttr =
7491 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
7493 if (isa<UndefValue>(
C) && HasNoUndefAttr)
7496 if (
C->isNullValue() && HasNoUndefAttr &&
7497 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
7498 return !PtrValueMayBeModified;
7508 if (!LI->isVolatile())
7510 LI->getPointerAddressSpace());
7514 if (!SI->isVolatile())
7516 SI->getPointerAddressSpace())) &&
7517 SI->getPointerOperand() ==
I;
7519 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
7523 if (CB->getCalledOperand() ==
I)
7526 if (
C->isNullValue()) {
7529 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7530 if (CB->isPassingUndefUB(ArgIdx) &&
7531 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
7533 return !PtrValueMayBeModified;
7536 }
else if (isa<UndefValue>(
C)) {
7540 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7541 if (CB->isPassingUndefUB(ArgIdx)) {
7558 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
7585 DTU->
applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
7587 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
7595 for (
const auto &Case : SI->cases())
7596 if (Case.getCaseSuccessor() == BB) {
7598 Case.setSuccessor(Unreachable);
7600 if (SI->getDefaultDest() == BB) {
7602 SI->setDefaultDest(Unreachable);
7607 { { DominatorTree::Insert, Predecessor, Unreachable },
7608 { DominatorTree::Delete, Predecessor, BB } });
7616bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
7617 bool Changed =
false;
7641 return requestResimplify();
7662 if (
Options.SpeculateBlocks &&
7666 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
7675 case Instruction::Br:
7676 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
7678 case Instruction::Resume:
7679 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
7681 case Instruction::CleanupRet:
7682 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
7684 case Instruction::Switch:
7685 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
7687 case Instruction::Unreachable:
7688 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
7690 case Instruction::IndirectBr:
7691 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
7699 bool Changed =
false;
7707 Changed |= simplifyOnce(BB);
7708 }
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")
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 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 void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static 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,...
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
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.
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 HasNSW=false)
This is the shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
bool isEmptySet() const
Return true if this set contains no members.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DILocation * getMergedLocations(ArrayRef< DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
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 * 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 * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * 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< DbgVariableRecord * > getDVRAssignmentMarkers(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.
pred_iterator pred_end(BasicBlock *BB)
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void 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.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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.
void RemapDbgVariableRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgVariableRecord V using the value map VM.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
pred_iterator pred_begin(BasicBlock *BB)
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.
void RemapDbgVariableRecord(Module *M, DbgVariableRecord *V, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgVariableRecord V using the value map VM.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
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.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ And
Bitwise or logical AND of integers.
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 DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
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.