91using namespace PatternMatch;
93#define DEBUG_TYPE "simplifycfg"
96 "simplifycfg-require-and-preserve-domtree",
cl::Hidden,
98 cl::desc(
"Temorary development switch used to gradually uplift SimplifyCFG "
99 "into preserving DomTree,"));
108 "Control the amount of phi node folding to perform (default = 2)"));
112 cl::desc(
"Control the maximal total instruction cost that we are willing "
113 "to speculatively execute to fold a 2-entry PHI node into a "
114 "select (default = 4)"));
118 cl::desc(
"Hoist common instructions up to the parent block"));
123 cl::desc(
"Allow reordering across at most this many "
124 "instructions when hoisting"));
128 cl::desc(
"Sink common instructions down to the end block"));
132 cl::desc(
"Hoist conditional stores if an unconditional store precedes"));
136 cl::desc(
"Hoist conditional stores even if an unconditional store does not "
137 "precede - hoist multiple conditional stores into a single "
138 "predicated store"));
142 cl::desc(
"When merging conditional stores, do so even if the resultant "
143 "basic blocks are unlikely to be if-converted as a result"));
147 cl::desc(
"Allow exactly one expensive instruction to be speculatively "
152 cl::desc(
"Limit maximum recursion depth when calculating costs of "
153 "speculatively executed instructions"));
158 cl::desc(
"Max size of a block which is still considered "
159 "small enough to thread through"));
165 cl::desc(
"Maximum cost of combining conditions when "
166 "folding branches"));
169 "simplifycfg-branch-fold-common-dest-vector-multiplier",
cl::Hidden,
171 cl::desc(
"Multiplier to apply to threshold when determining whether or not "
172 "to fold branch to common destination when vector operations are "
177 cl::desc(
"Allow SimplifyCFG to merge invokes together when appropriate"));
181 cl::desc(
"Limit cases to analyze when converting a switch to select"));
183STATISTIC(NumBitMaps,
"Number of switch instructions turned into bitmaps");
185 "Number of switch instructions turned into linear mapping");
187 "Number of switch instructions turned into lookup tables");
189 NumLookupTablesHoles,
190 "Number of switch instructions turned into lookup tables (holes checked)");
191STATISTIC(NumTableCmpReuses,
"Number of reused switch table lookup compares");
193 "Number of value comparisons folded into predecessor basic blocks");
195 "Number of branches folded into predecessor basic block");
198 "Number of common instruction 'blocks' hoisted up to the begin block");
200 "Number of common instructions hoisted up to the begin block");
202 "Number of common instruction 'blocks' sunk down to the end block");
204 "Number of common instructions sunk down to the end block");
205STATISTIC(NumSpeculations,
"Number of speculative executed instructions");
207 "Number of invokes with empty resume blocks simplified into calls");
208STATISTIC(NumInvokesMerged,
"Number of invokes that were merged together");
209STATISTIC(NumInvokeSetsFormed,
"Number of invoke sets that were formed");
216using SwitchCaseResultVectorTy =
225struct ValueEqualityComparisonCase {
232 bool operator<(ValueEqualityComparisonCase RHS)
const {
240class SimplifyCFGOpt {
250 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases);
251 bool SimplifyEqualityComparisonWithOnlyPredecessor(
Instruction *TI,
254 bool PerformValueComparisonIntoPredecessorFolding(
Instruction *TI,
Value *&CV,
257 bool FoldValueComparisonIntoPredecessors(
Instruction *TI,
271 bool tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI,
274 bool hoistCommonCodeFromSuccessors(
BasicBlock *BB,
bool EqTermsOnly);
275 bool hoistSuccIdenticalTerminatorToSwitchOrIf(
294 "SimplifyCFG is not yet capable of maintaining validity of a "
295 "PostDomTree, so don't ask for it.");
302 bool requestResimplify() {
321 "Only for a pair of incoming blocks at the time!");
327 Value *IV0 = PN.getIncomingValueForBlock(IncomingBlocks[0]);
328 Value *IV1 = PN.getIncomingValueForBlock(IncomingBlocks[1]);
331 if (EquivalenceSet && EquivalenceSet->contains(IV0) &&
332 EquivalenceSet->contains(IV1))
355 if (!SI1Succs.
count(Succ))
361 FailBlocks->insert(Succ);
377 PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
379 if (
auto *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Succ))
380 MPhi->addIncoming(MPhi->getIncomingValueForBlock(ExistPred), NewPred);
389 assert((!isa<Instruction>(
I) ||
391 "Instruction is not safe to speculatively execute!");
417 unsigned Depth = 0) {
446 if (AggressiveInsts.
count(
I))
470 for (
Use &
Op :
I->operands())
484 if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy() ||
485 DL.isNonIntegralPointerType(V->getType()))
490 IntegerType *PtrTy = cast<IntegerType>(
DL.getIntPtrType(V->getType()));
493 if (isa<ConstantPointerNull>(V))
494 return ConstantInt::get(PtrTy, 0);
498 if (CE->getOpcode() == Instruction::IntToPtr)
499 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
504 return cast<ConstantInt>(
522struct ConstantComparesGatherer {
526 Value *CompValue =
nullptr;
529 Value *Extra =
nullptr;
535 unsigned UsedICmps = 0;
542 ConstantComparesGatherer(
const ConstantComparesGatherer &) =
delete;
543 ConstantComparesGatherer &
544 operator=(
const ConstantComparesGatherer &) =
delete;
549 bool setValueOnce(
Value *NewVal) {
550 if (CompValue && CompValue != NewVal)
553 return (CompValue !=
nullptr);
567 if (!((ICI = dyn_cast<ICmpInst>(
I)) &&
578 if (ICI->
getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
622 if (
Mask.isPowerOf2() && (
C->getValue() & ~Mask) ==
C->getValue()) {
624 if (!setValueOnce(RHSVal))
629 ConstantInt::get(
C->getContext(),
630 C->getValue() | Mask));
645 if (
Mask.isPowerOf2() && (
C->getValue() | Mask) ==
C->getValue()) {
647 if (!setValueOnce(RHSVal))
651 Vals.
push_back(ConstantInt::get(
C->getContext(),
652 C->getValue() & ~Mask));
673 Value *CandidateVal =
I->getOperand(0);
676 CandidateVal = RHSVal;
691 if (!setValueOnce(CandidateVal))
696 Vals.
push_back(ConstantInt::get(
I->getContext(), Tmp));
707 void gather(
Value *V) {
718 while (!DFT.
empty()) {
726 if (Visited.
insert(Op1).second)
728 if (Visited.
insert(Op0).second)
735 if (matchInstruction(
I, isEQ))
759 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
760 Cond = dyn_cast<Instruction>(SI->getCondition());
761 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
762 if (BI->isConditional())
763 Cond = dyn_cast<Instruction>(BI->getCondition());
765 Cond = dyn_cast<Instruction>(IBI->getAddress());
777 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
780 if (!
SI->getParent()->hasNPredecessorsOrMore(128 /
SI->getNumSuccessors()))
781 CV =
SI->getCondition();
782 }
else if (
BranchInst *BI = dyn_cast<BranchInst>(TI))
783 if (BI->isConditional() && BI->getCondition()->hasOneUse())
784 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
792 Value *
Ptr = PTII->getPointerOperand();
793 if (PTII->getType() ==
DL.getIntPtrType(
Ptr->getType()))
802BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
803 Instruction *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
804 if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
805 Cases.reserve(
SI->getNumCases());
806 for (
auto Case :
SI->cases())
807 Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
808 Case.getCaseSuccessor()));
809 return SI->getDefaultDest();
815 Cases.push_back(ValueEqualityComparisonCase(
824 std::vector<ValueEqualityComparisonCase> &Cases) {
830 std::vector<ValueEqualityComparisonCase> &C2) {
831 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
834 if (V1->size() > V2->size())
839 if (V1->size() == 1) {
842 for (
const ValueEqualityComparisonCase &VECC : *V2)
843 if (TheVal == VECC.
Value)
850 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
851 while (i1 != e1 && i2 != e2) {
872 SI->setMetadata(LLVMContext::MD_prof,
N);
878 uint32_t FalseWeight,
bool IsExpected) {
879 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
883 if (TrueWeight || FalseWeight)
886 I->setMetadata(LLVMContext::MD_prof,
N);
894bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
900 Value *ThisVal = isValueEqualityComparison(TI);
901 assert(ThisVal &&
"This isn't a value comparison!!");
902 if (ThisVal != PredVal)
909 std::vector<ValueEqualityComparisonCase> PredCases;
911 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
915 std::vector<ValueEqualityComparisonCase> ThisCases;
916 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
928 if (isa<BranchInst>(TI)) {
931 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
937 ThisCases[0].Dest->removePredecessor(PredDef);
940 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
947 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
955 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
959 <<
"Through successor TI: " << *TI);
967 if (DeadCases.
count(i->getCaseValue())) {
976 std::vector<DominatorTree::UpdateType> Updates;
977 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
979 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
980 DTU->applyUpdates(Updates);
991 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
992 if (PredCases[i].Dest == TIBB) {
995 TIV = PredCases[i].
Value;
997 assert(TIV &&
"No edge from pred to succ?");
1002 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1003 if (ThisCases[i].
Value == TIV) {
1004 TheRealDest = ThisCases[i].Dest;
1010 TheRealDest = ThisDef;
1017 if (Succ != CheckEdge) {
1018 if (Succ != TheRealDest)
1019 RemovedSuccs.
insert(Succ);
1022 CheckEdge =
nullptr;
1029 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1036 for (
auto *RemovedSucc : RemovedSuccs)
1037 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1038 DTU->applyUpdates(Updates);
1048struct ConstantIntOrdering {
1050 return LHS->getValue().ult(
RHS->getValue());
1062 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1071 assert(MD &&
"Invalid branch-weight metadata");
1077 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1088 if (Max > UINT_MAX) {
1103 if (BonusInst.isTerminator())
1108 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1132 if (isa<DbgInfoIntrinsic>(BonusInst))
1135 NewBonusInst->
takeName(&BonusInst);
1136 BonusInst.setName(NewBonusInst->
getName() +
".old");
1137 VMap[&BonusInst] = NewBonusInst;
1143 auto *UI = cast<Instruction>(U.getUser());
1144 auto *PN = dyn_cast<PHINode>(UI);
1146 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1147 "If the user is not a PHI node, then it should be in the same "
1148 "block as, and come after, the original bonus instruction.");
1152 if (PN->getIncomingBlock(U) == BB)
1156 assert(PN->getIncomingBlock(U) == PredBlock &&
1157 "Not in block-closed SSA form?");
1158 U.set(NewBonusInst);
1163bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1171 std::vector<ValueEqualityComparisonCase> BBCases;
1172 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1174 std::vector<ValueEqualityComparisonCase> PredCases;
1175 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1187 if (PredHasWeights) {
1190 if (Weights.
size() != 1 + PredCases.size())
1191 PredHasWeights = SuccHasWeights =
false;
1192 }
else if (SuccHasWeights)
1196 Weights.
assign(1 + PredCases.size(), 1);
1199 if (SuccHasWeights) {
1202 if (SuccWeights.
size() != 1 + BBCases.size())
1203 PredHasWeights = SuccHasWeights =
false;
1204 }
else if (PredHasWeights)
1205 SuccWeights.
assign(1 + BBCases.size(), 1);
1207 if (PredDefault == BB) {
1210 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1211 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1212 if (PredCases[i].Dest != BB)
1213 PTIHandled.insert(PredCases[i].
Value);
1216 std::swap(PredCases[i], PredCases.back());
1218 if (PredHasWeights || SuccHasWeights) {
1220 Weights[0] += Weights[i + 1];
1225 PredCases.pop_back();
1231 if (PredDefault != BBDefault) {
1233 if (DTU && PredDefault != BB)
1234 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1235 PredDefault = BBDefault;
1236 ++NewSuccessors[BBDefault];
1239 unsigned CasesFromPred = Weights.
size();
1241 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1242 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1243 PredCases.push_back(BBCases[i]);
1244 ++NewSuccessors[BBCases[i].Dest];
1245 if (SuccHasWeights || PredHasWeights) {
1249 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1250 ValidTotalSuccWeight += SuccWeights[i + 1];
1254 if (SuccHasWeights || PredHasWeights) {
1255 ValidTotalSuccWeight += SuccWeights[0];
1257 for (
unsigned i = 1; i < CasesFromPred; ++i)
1258 Weights[i] *= ValidTotalSuccWeight;
1260 Weights[0] *= SuccWeights[0];
1266 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1267 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1268 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1269 if (PredCases[i].Dest == BB) {
1272 if (PredHasWeights || SuccHasWeights) {
1273 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1278 std::swap(PredCases[i], PredCases.back());
1279 PredCases.pop_back();
1286 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1287 if (PTIHandled.count(BBCases[i].Value)) {
1289 if (PredHasWeights || SuccHasWeights)
1291 PredCases.push_back(BBCases[i]);
1292 ++NewSuccessors[BBCases[i].Dest];
1299 if (PredHasWeights || SuccHasWeights)
1301 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1302 ++NewSuccessors[BBDefault];
1314 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1316 for (
auto I :
seq(NewSuccessor.second)) {
1320 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1321 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1334 for (ValueEqualityComparisonCase &V : PredCases)
1337 if (PredHasWeights || SuccHasWeights) {
1354 if (!InfLoopBlock) {
1362 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1369 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1371 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1373 DTU->applyUpdates(Updates);
1376 ++NumFoldValueComparisonIntoPredecessors;
1384bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1387 Value *CV = isValueEqualityComparison(TI);
1388 assert(CV &&
"Not a comparison?");
1390 bool Changed =
false;
1393 while (!Preds.empty()) {
1402 Value *PCV = isValueEqualityComparison(PTI);
1408 for (
auto *Succ : FailBlocks) {
1414 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1428 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1429 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1430 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1449 if (
I->mayReadFromMemory())
1453 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1470 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1480 if (
auto *CB = dyn_cast<CallBase>(
I))
1481 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1488 if (
auto *J = dyn_cast<Instruction>(
Op))
1489 if (J->getParent() == BB)
1508 auto *C1 = dyn_cast<CallInst>(I1);
1509 auto *C2 = dyn_cast<CallInst>(I2);
1511 if (C1->isMustTailCall() != C2->isMustTailCall())
1519 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1520 if (CB1->cannotMerge() || CB1->isConvergent())
1522 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1523 if (CB2->cannotMerge() || CB2->isConvergent())
1538 if (!I1->hasDbgRecords())
1540 using CurrentAndEndIt =
1541 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1547 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1548 return Pair.first == Pair.second;
1554 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1560 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1562 if (!
Other->hasDbgRecords())
1565 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1572 while (
none_of(Itrs, atEnd)) {
1573 bool HoistDVRs = allIdentical(Itrs);
1574 for (CurrentAndEndIt &Pair : Itrs) {
1591bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1613 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1617 if (isa<PHINode>(*SuccItr))
1619 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1628 if (!INonDbg->isTerminator())
1638 unsigned NumSkipped = 0;
1641 if (SuccIterPairs.
size() > 2) {
1643 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1644 if (SuccIterPairs.
size() < 2)
1648 bool Changed =
false;
1651 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1652 auto &BB1ItrPair = *SuccIterPairBegin++;
1653 auto OtherSuccIterPairRange =
1660 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1662 return I1->isIdenticalToWhenDefined(I2);
1664 if (!AllDbgInstsAreIdentical) {
1665 while (isa<DbgInfoIntrinsic>(I1))
1666 I1 = &*++BB1ItrPair.first;
1667 for (
auto &SuccIter : OtherSuccIterRange) {
1669 while (isa<DbgInfoIntrinsic>(I2))
1674 bool AllInstsAreIdentical =
true;
1675 bool HasTerminator =
I1->isTerminator();
1676 for (
auto &SuccIter : OtherSuccIterRange) {
1679 if (AllInstsAreIdentical && (!
I1->isIdenticalToWhenDefined(I2) ||
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);
1938 std::optional<unsigned> NumUses;
1939 for (
auto *
I : Insts) {
1941 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1942 I->getType()->isTokenTy())
1947 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1954 if (
const auto *
C = dyn_cast<CallBase>(
I))
1955 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1959 NumUses =
I->getNumUses();
1960 else if (NumUses !=
I->getNumUses())
1966 for (
auto *
I : Insts) {
1967 if (!
I->isSameOperationAs(I0))
1973 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1975 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1988 for (
const Use &U : I0->
uses()) {
1989 auto It = PHIOperands.find(&U);
1990 if (It == PHIOperands.end())
1993 if (!
equal(Insts, It->second))
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)) {
2061 for (
auto *
I : Insts)
2062 Ops.push_back(
I->getOperand(OI));
2072 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2077 for (
auto *BB :
Blocks) {
2080 I =
I->getPrevNode();
2081 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2082 if (!isa<DbgInfoIntrinsic>(
I))
2107 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2110 PN->insertBefore(BBEnd->begin());
2111 for (
auto *
I : Insts)
2112 PN->addIncoming(
I->getOperand(O),
I->getParent());
2121 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2124 for (
auto *
I : Insts)
2142 auto *PN = cast<PHINode>(U);
2143 PN->replaceAllUsesWith(I0);
2144 PN->eraseFromParent();
2148 for (
auto *
I : Insts) {
2153 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2154 I->replaceAllUsesWith(I0);
2155 I->eraseFromParent();
2169 class LockstepReverseIterator {
2182 for (
auto *BB : Blocks) {
2184 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2202 for (
auto *&Inst : Insts) {
2203 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2216 for (
auto *&Inst : Insts) {
2217 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2280 bool HaveNonUnconditionalPredecessors =
false;
2282 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2283 if (PredBr && PredBr->isUnconditional())
2286 HaveNonUnconditionalPredecessors =
true;
2288 if (UnconditionalPreds.
size() < 2)
2301 for (
const Use &U : PN.incoming_values())
2302 IncomingVals.
insert({PN.getIncomingBlock(U), &U});
2303 auto &Ops = PHIOperands[IncomingVals[UnconditionalPreds[0]]];
2305 Ops.push_back(*IncomingVals[Pred]);
2310 LockstepReverseIterator LRI(UnconditionalPreds);
2311 while (LRI.isValid() &&
2313 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2315 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2326 if (!followedByDeoptOrUnreachable) {
2330 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2331 unsigned NumPHIInsts = 0;
2332 for (
Use &U : (*LRI)[0]->operands()) {
2333 auto It = PHIOperands.
find(&U);
2334 if (It != PHIOperands.
end() && !
all_of(It->second, [&](
Value *V) {
2335 return InstructionsToSink.contains(V);
2343 LLVM_DEBUG(
dbgs() <<
"SINK: #phi insts: " << NumPHIInsts <<
"\n");
2344 return NumPHIInsts <= 1;
2361 while (
Idx < ScanIdx) {
2362 if (!ProfitableToSinkInstruction(LRI)) {
2365 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2368 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2378 if (
Idx < ScanIdx) {
2381 InstructionsToSink = InstructionsProfitableToSink;
2387 !ProfitableToSinkInstruction(LRI) &&
2388 "We already know that the last instruction is unprofitable to sink");
2396 for (
auto *
I : *LRI)
2397 InstructionsProfitableToSink.
erase(
I);
2398 if (!ProfitableToSinkInstruction(LRI)) {
2401 InstructionsToSink = InstructionsProfitableToSink;
2413 bool Changed =
false;
2415 if (HaveNonUnconditionalPredecessors) {
2416 if (!followedByDeoptOrUnreachable) {
2424 bool Profitable =
false;
2425 while (
Idx < ScanIdx) {
2459 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2461 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2469 NumSinkCommonInstrs++;
2473 ++NumSinkCommonCode;
2479struct CompatibleSets {
2497 if (CompatibleSets::shouldBelongToSameSet({Set.front(),
II}))
2506 getCompatibleSet(
II).emplace_back(
II);
2510 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2514 return II->cannotMerge() ||
II->isInlineAsm();
2516 if (
any_of(Invokes, IsIllegalToMerge))
2521 auto IsIndirectCall = [](
InvokeInst *
II) {
return II->isIndirectCall(); };
2522 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2523 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2524 if (HaveIndirectCalls) {
2525 if (!AllCallsAreIndirect)
2531 Value *CurrCallee =
II->getCalledOperand();
2532 assert(CurrCallee &&
"There is always a called operand.");
2535 else if (Callee != CurrCallee)
2543 return !isa<UnreachableInst>(
II->getNormalDest()->getFirstNonPHIOrDbg());
2545 if (
any_of(Invokes, HasNormalDest)) {
2548 if (!
all_of(Invokes, HasNormalDest))
2555 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2557 NormalBB = CurrNormalBB;
2558 else if (NormalBB != CurrNormalBB)
2566 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2577 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2579 UnwindBB = CurrUnwindBB;
2581 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2588 Invokes.front()->getUnwindDest(),
2589 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2595 for (
auto *
II : Invokes.drop_front())
2596 if (!
II->isSameOperationAs(II0))
2600 auto IsIllegalToMergeArguments = [](
auto Ops) {
2601 Use &U0 = std::get<0>(Ops);
2602 Use &U1 = std::get<1>(Ops);
2609 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2610 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2611 IsIllegalToMergeArguments))
2623 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2629 bool HasNormalDest =
2630 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2634 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2638 II0->
getParent()->getIterator()->getNextNode();
2643 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2645 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2647 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2649 if (!HasNormalDest) {
2653 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2660 return MergedInvoke;
2668 {DominatorTree::Insert,
II->getParent(), MergedInvoke->
getParent()});
2674 SuccBBOfMergedInvoke});
2681 {DominatorTree::Delete,
II->getParent(), SuccOfPredBB});
2684 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2687 for (
Use &U : MergedInvoke->operands()) {
2689 if (MergedInvoke->isCallee(&U)) {
2690 if (!IsIndirectCall)
2692 }
else if (!MergedInvoke->isDataOperand(&U))
2697 return II->getOperand(
U.getOperandNo()) !=
U.get();
2704 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2716 Invokes.front()->getParent());
2724 if (!MergedDebugLoc)
2725 MergedDebugLoc =
II->getDebugLoc();
2733 OrigSuccBB->removePredecessor(
II->getParent());
2735 II->replaceAllUsesWith(MergedInvoke);
2736 II->eraseFromParent();
2739 MergedInvoke->setDebugLoc(MergedDebugLoc);
2740 ++NumInvokeSetsFormed;
2743 DTU->applyUpdates(Updates);
2770 bool Changed =
false;
2776 CompatibleSets Grouper;
2782 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2786 if (Invokes.
size() < 2)
2798class EphemeralValueTracker {
2802 if (isa<AssumeInst>(
I))
2804 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2806 return EphValues.count(cast<Instruction>(U));
2812 if (isEphemeral(
I)) {
2851 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2863 unsigned MaxNumInstToLookAt = 9;
2867 if (!MaxNumInstToLookAt)
2869 --MaxNumInstToLookAt;
2872 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2875 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2879 if (SI->getPointerOperand() == StorePtr &&
2880 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
2881 SI->getAlign() >= StoreToHoist->
getAlign())
2883 return SI->getValueOperand();
2887 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2888 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2889 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
2912 unsigned &SpeculatedInstructions,
2920 bool HaveRewritablePHIs =
false;
2938 HaveRewritablePHIs =
true;
2941 if (!OrigCE && !ThenCE)
2948 if (OrigCost + ThenCost > MaxCost)
2955 ++SpeculatedInstructions;
2956 if (SpeculatedInstructions > 1)
2960 return HaveRewritablePHIs;
3000bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
3007 if (isa<FCmpInst>(BrCond))
3017 bool Invert =
false;
3026 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
3029 (TWeight + FWeight) != 0) {
3030 uint64_t EndWeight = Invert ? TWeight : FWeight;
3034 if (BIEndProb >= Likely)
3048 unsigned SpeculatedInstructions = 0;
3049 Value *SpeculatedStoreValue =
nullptr;
3051 EphemeralValueTracker EphTracker;
3054 if (isa<DbgInfoIntrinsic>(
I)) {
3062 if (isa<PseudoProbeInst>(
I)) {
3072 if (EphTracker.track(&
I))
3077 ++SpeculatedInstructions;
3078 if (SpeculatedInstructions > 1)
3084 &
I, BB, ThenBB, EndBB))))
3086 if (!SpeculatedStoreValue &&
3092 if (SpeculatedStoreValue)
3093 SpeculatedStore = cast<StoreInst>(&
I);
3098 for (
Use &
Op :
I.operands()) {
3103 ++SinkCandidateUseCounts[OpI];
3110 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3112 ++SpeculatedInstructions;
3113 if (SpeculatedInstructions > 1)
3119 bool Convert = SpeculatedStore !=
nullptr;
3122 SpeculatedInstructions,
3124 if (!Convert ||
Cost > Budget)
3128 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3131 if (SpeculatedStoreValue) {
3135 Value *FalseV = SpeculatedStoreValue;
3139 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3168 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3170 DbgAssign->replaceVariableLocationOp(OrigV, S);
3183 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3185 if (!isa<DbgAssignIntrinsic>(&
I))
3188 I.dropUBImplyingAttrsAndMetadata();
3191 if (EphTracker.contains(&
I)) {
3193 I.eraseFromParent();
3207 It.dropOneDbgRecord(&DR);
3209 std::prev(ThenBB->
end()));
3226 Value *TrueV = ThenV, *FalseV = OrigV;
3240 if (!isa<DbgAssignIntrinsic>(
I))
3241 I->eraseFromParent();
3251 EphemeralValueTracker EphTracker;
3257 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3258 if (CI->cannotDuplicate() || CI->isConvergent())
3264 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3271 for (
User *U :
I.users()) {
3273 if (UI->
getParent() != BB || isa<PHINode>(UI))
3287 auto *
I = dyn_cast<Instruction>(V);
3288 if (
I &&
I->getParent() == To)
3292 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3304static std::optional<bool>
3320 if (
auto *CB = dyn_cast<ConstantInt>(U))
3325 KnownValues[CB].
insert(Pred);
3329 if (KnownValues.
empty())
3338 for (
const auto &Pair : KnownValues) {
3356 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3359 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3367 EdgeBB->setName(RealDest->
getName() +
".critedge");
3368 EdgeBB->moveBefore(RealDest);
3378 TranslateMap[
Cond] = CB;
3384 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3391 N->insertInto(EdgeBB, InsertPt);
3394 N->setName(BBI->getName() +
".c");
3397 for (
Use &
Op :
N->operands()) {
3399 if (PI != TranslateMap.
end())
3405 if (!BBI->use_empty())
3406 TranslateMap[&*BBI] = V;
3407 if (!
N->mayHaveSideEffects()) {
3408 N->eraseFromParent();
3413 if (!BBI->use_empty())
3414 TranslateMap[&*BBI] =
N;
3420 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3421 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3422 SrcDbgCursor = std::next(BBI);
3424 N->cloneDebugInfoFrom(&*BBI);
3427 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3433 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3434 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3435 InsertPt->cloneDebugInfoFrom(BI);
3438 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3444 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3445 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3456 return std::nullopt;
3466 std::optional<bool> Result;
3467 bool EverChanged =
false;
3471 EverChanged |= Result == std::nullopt || *Result;
3472 }
while (Result == std::nullopt);
3494 if (isa<ConstantInt>(IfCond))
3501 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3504 "Will have either one or two blocks to speculate.");
3511 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3514 (TWeight + FWeight) != 0) {
3519 if (IfBlocks.
size() == 1) {
3521 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3522 if (BIBBProb >= Likely)
3525 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3533 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3534 if (IfCondPhiInst->getParent() == BB)
3542 unsigned NumPhis = 0;
3555 bool Changed =
false;
3574 PN = dyn_cast<PHINode>(BB->
begin());
3580 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3591 auto IsBinOpOrAnd = [](
Value *V) {
3611 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3624 <<
" T: " << IfTrue->
getName()
3625 <<
" F: " << IfFalse->
getName() <<
"\n");
3639 if (isa<FPMathOperator>(PN))
3659 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3677 if (Opc == Instruction::And)
3679 if (Opc == Instruction::Or)
3692 bool PredHasWeights =
3694 bool SuccHasWeights =
3696 if (PredHasWeights || SuccHasWeights) {
3697 if (!PredHasWeights)
3698 PredTrueWeight = PredFalseWeight = 1;
3699 if (!SuccHasWeights)
3700 SuccTrueWeight = SuccFalseWeight = 1;
3710static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3714 "Both blocks must end with a conditional branches.");
3716 "PredBB must be a predecessor of BB.");
3724 (PTWeight + PFWeight) != 0) {
3732 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3733 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3737 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3740 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3741 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3747 return std::nullopt;
3760 bool InvertPredCond;
3761 std::tie(CommonSucc, Opc, InvertPredCond) =
3764 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3771 {LLVMContext::MD_annotation});
3774 if (InvertPredCond) {
3787 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3789 SuccTrueWeight, SuccFalseWeight)) {
3796 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3802 (SuccFalseWeight + SuccTrueWeight) +
3803 PredTrueWeight * SuccFalseWeight);
3809 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3810 PredFalseWeight * SuccTrueWeight);
3812 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3830 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3831 {DominatorTree::Delete, PredBlock, BB}});
3858 ++NumFoldBranchToCommonDest;
3865 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3866 return U->getType()->isVectorTy();
3876 unsigned BonusInstThreshold) {
3890 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3891 !isa<SelectInst>(
Cond)) ||
3892 Cond->getParent() != BB || !
Cond->hasOneUse())
3902 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3913 bool InvertPredCond;
3915 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3947 unsigned NumBonusInsts = 0;
3948 bool SawVectorOp =
false;
3949 const unsigned PredCount = Preds.
size();
3955 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3966 NumBonusInsts += PredCount;
3974 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3975 auto *UI = cast<Instruction>(U.getUser());
3976 if (
auto *PN = dyn_cast<PHINode>(UI))
3978 return UI->
getParent() == BB &&
I.comesBefore(UI);
3982 if (!
all_of(
I.uses(), IsBCSSAUse))
3986 BonusInstThreshold *
3992 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4002 for (
auto *BB : {BB1, BB2}) {
4006 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4018 Value *AlternativeV =
nullptr) {
4036 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4037 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4038 PHI = cast<PHINode>(
I);
4044 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4045 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4053 if (!AlternativeV &&
4054 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4059 PHI->addIncoming(V, BB);
4069 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4078 if (!PStore || !QStore)
4099 if (
I.mayReadOrWriteMemory())
4101 for (
auto &
I : *QFB)
4102 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4105 for (
auto &
I : *QTB)
4106 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4110 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4126 if (
I.isTerminator())
4130 if (
auto *S = dyn_cast<StoreInst>(&
I))
4134 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4144 "When we run out of budget we will eagerly return from within the "
4145 "per-instruction loop.");
4149 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4151 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4152 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4260 bool InvertPCond =
false, InvertQCond =
false;
4266 if (QFB == PostBB) {
4285 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4288 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4296 for (
auto *BB : {PTB, PFB}) {
4301 PStoreAddresses.
insert(SI->getPointerOperand());
4303 for (
auto *BB : {QTB, QFB}) {
4308 QStoreAddresses.
insert(SI->getPointerOperand());
4314 auto &CommonAddresses = PStoreAddresses;
4316 bool Changed =
false;
4317 for (
auto *Address : CommonAddresses)
4320 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4338 !BI->
getParent()->getSinglePredecessor())
4340 if (!IfFalseBB->
phis().empty())
4350 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4361 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4362 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4373 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4374 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4453 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4455 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4459 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4462 if (CommonDestProb >= Likely)
4472 unsigned NumPhis = 0;
4494 if (OtherDest == BB) {
4501 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4502 OtherDest = InfLoopBlock;
4522 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4537 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4538 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4541 SuccTrueWeight, SuccFalseWeight);
4543 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4544 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4545 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4546 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4550 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4551 PredOther * SuccCommon,
4552 PredOther * SuccOther};
4581 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4582 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4583 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4584 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4587 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4588 PredOther * SuccCommon};
4611bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4622 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4629 if (Succ == KeepEdge1)
4630 KeepEdge1 =
nullptr;
4631 else if (Succ == KeepEdge2)
4632 KeepEdge2 =
nullptr;
4637 if (Succ != TrueBB && Succ != FalseBB)
4638 RemovedSuccessors.
insert(Succ);
4646 if (!KeepEdge1 && !KeepEdge2) {
4647 if (TrueBB == FalseBB) {
4655 if (TrueWeight != FalseWeight)
4658 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4680 for (
auto *RemovedSuccessor : RemovedSuccessors)
4681 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4682 DTU->applyUpdates(Updates);
4692bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4697 if (!TrueVal || !FalseVal)
4702 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4703 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4706 uint32_t TrueWeight = 0, FalseWeight = 0;
4711 if (Weights.
size() == 1 +
SI->getNumCases()) {
4713 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4715 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4720 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4729bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4742 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4763bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4783 if (
SI->getCondition() != V)
4789 if (
SI->getDefaultDest() != BB) {
4791 assert(VVal &&
"Should have a unique destination value");
4799 return requestResimplify();
4805 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4815 return requestResimplify();
4822 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4847 auto W0 = SIW.getSuccessorWeight(0);
4851 SIW.setSuccessorWeight(0, *NewW);
4853 SIW.addCase(Cst, NewBB, NewW);
4855 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4864 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4865 DTU->applyUpdates(Updates);
4873bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4885 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4888 Value *CompVal = ConstantCompare.CompValue;
4889 unsigned UsedICmps = ConstantCompare.UsedICmps;
4890 Value *ExtraCase = ConstantCompare.Extra;
4909 if (ExtraCase && Values.
size() < 2)
4924 <<
" cases into SWITCH. BB is:\n"
4934 nullptr,
"switch.early.test");
4958 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4964 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4965 <<
"\nEXTRABB = " << *BB);
4973 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4980 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4981 New->addCase(Values[i], EdgeBB);
4987 PHINode *PN = cast<PHINode>(BBI);
4989 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
4996 DTU->applyUpdates(Updates);
4998 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5004 return simplifyCommonResume(RI);
5005 else if (isa<LandingPadInst>(RI->
getParent()->getFirstNonPHI()) &&
5008 return simplifySingleResume(RI);
5016 auto *
II = dyn_cast<IntrinsicInst>(&
I);
5021 switch (IntrinsicID) {
5022 case Intrinsic::dbg_declare:
5023 case Intrinsic::dbg_value:
5024 case Intrinsic::dbg_label:
5025 case Intrinsic::lifetime_end:
5035bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5045 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5048 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5050 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5051 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5055 if (IncomingBB->getUniqueSuccessor() != BB)
5058 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5060 if (IncomingValue != LandingPad)
5064 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5065 TrivialUnwindBlocks.
insert(IncomingBB);
5069 if (TrivialUnwindBlocks.
empty())
5073 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5077 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5091 TrivialBB->getTerminator()->eraseFromParent();
5094 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5101 return !TrivialUnwindBlocks.empty();
5105bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5109 "Resume must unwind the exception that caused control to here");
5113 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5149 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5166 int Idx = DestPN.getBasicBlockIndex(BB);
5180 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5181 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5183 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5187 DestPN.addIncoming(
Incoming, Pred);
5214 std::vector<DominatorTree::UpdateType> Updates;
5218 if (UnwindDest ==
nullptr) {
5230 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5231 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5258 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5259 if (!SuccessorCleanupPad)
5268 SuccessorCleanupPad->eraseFromParent();
5297 bool Changed =
false;
5326 BBI->dropDbgRecords();
5330 BBI->eraseFromParent();
5336 if (&BB->
front() != UI)
5339 std::vector<DominatorTree::UpdateType> Updates;
5342 for (
unsigned i = 0, e = Preds.size(); i != e; ++i) {
5343 auto *Predecessor = Preds[i];
5346 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5350 [BB](
auto *
Successor) { return Successor == BB; })) {
5358 "The destinations are guaranteed to be different here.");
5369 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5375 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5376 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5378 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5379 if (i->getCaseSuccessor() != BB) {
5384 i = SU.removeCase(i);
5389 if (DTU &&
SI->getDefaultDest() != BB)
5390 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5391 }
else if (
auto *
II = dyn_cast<InvokeInst>(TI)) {
5392 if (
II->getUnwindDest() == BB) {
5394 DTU->applyUpdates(Updates);
5398 if (!CI->doesNotThrow())
5399 CI->setDoesNotThrow();
5402 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5403 if (CSI->getUnwindDest() == BB) {
5405 DTU->applyUpdates(Updates);
5414 E = CSI->handler_end();
5417 CSI->removeHandler(
I);
5424 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5425 if (CSI->getNumHandlers() == 0) {
5426 if (CSI->hasUnwindDest()) {
5430 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5431 Updates.push_back({DominatorTree::Insert,
5432 PredecessorOfPredecessor,
5433 CSI->getUnwindDest()});
5434 Updates.push_back({DominatorTree::Delete,
5435 PredecessorOfPredecessor, Predecessor});
5438 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5442 DTU->applyUpdates(Updates);
5451 CSI->eraseFromParent();
5454 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5456 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5457 "Expected to always have an unwind to BB.");
5459 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5467 DTU->applyUpdates(Updates);
5482 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5483 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5491 bool RemoveOrigDefaultBlock =
true) {
5493 auto *BB = Switch->getParent();
5494 auto *OrigDefaultBlock = Switch->getDefaultDest();
5495 if (RemoveOrigDefaultBlock)
5496 OrigDefaultBlock->removePredecessor(BB);
5501 Switch->setDefaultDest(&*NewDefaultBlock);
5504 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5505 if (RemoveOrigDefaultBlock &&
5507 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5515bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(
SwitchInst *SI,
5517 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5520 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5522 auto *BB =
SI->getParent();
5525 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5530 for (
auto Case :
SI->cases()) {
5534 if (Dest == DestA) {
5540 if (Dest == DestB) {
5550 "Single-destination switch should have been folded.");
5552 assert(DestB !=
SI->getDefaultDest());
5553 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5561 ContiguousCases = &CasesA;
5562 ContiguousDest = DestA;
5565 ContiguousCases = &CasesB;
5566 ContiguousDest = DestB;
5575 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5577 Value *Sub =
SI->getCondition();
5578 if (!
Offset->isNullValue())
5593 if (Weights.
size() == 1 +
SI->getNumCases()) {
5596 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5597 if (
SI->getSuccessor(
I) == ContiguousDest)
5598 TrueWeight += Weights[
I];
5600 FalseWeight += Weights[
I];
5602 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5611 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5612 unsigned PreviousEdges = ContiguousCases->
size();
5613 if (ContiguousDest ==
SI->getDefaultDest())
5615 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5616 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5618 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5619 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5620 if (OtherDest ==
SI->getDefaultDest())
5622 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5623 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5631 auto *UnreachableDefault =
SI->getDefaultDest();
5634 SI->eraseFromParent();
5636 if (!HasDefault && DTU)
5637 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5653 unsigned MaxSignificantBitsInCond =
5660 for (
const auto &Case : SI->cases()) {
5661 auto *
Successor = Case.getCaseSuccessor();
5667 const APInt &CaseVal = Case.getCaseValue()->getValue();
5670 DeadCases.
push_back(Case.getCaseValue());
5683 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5684 const unsigned NumUnknownBits =
5687 if (HasDefault && DeadCases.
empty() &&
5688 NumUnknownBits < 64 ) {
5689 uint64_t AllNumCases = 1ULL << NumUnknownBits;
5690 if (SI->getNumCases() == AllNumCases) {
5697 if (SI->getNumCases() == AllNumCases - 1) {
5698 assert(NumUnknownBits > 1 &&
"Should be canonicalized to a branch");
5705 for (
const auto &Case : SI->cases())
5706 MissingCaseVal ^= Case.getCaseValue()->getValue().getLimitedValue();
5708 cast<ConstantInt>(ConstantInt::get(
Cond->getType(), MissingCaseVal));
5717 if (DeadCases.
empty())
5723 assert(CaseI != SI->case_default() &&
5724 "Case was not found. Probably mistake in DeadCases forming.");
5726 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5731 std::vector<DominatorTree::UpdateType> Updates;
5732 for (
auto *
Successor : UniqueSuccessors)
5733 if (NumPerSuccessorCases[
Successor] == 0)
5734 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5754 if (!Branch || !Branch->isUnconditional())
5760 int Idx =
PHI.getBasicBlockIndex(BB);
5761 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5764 if (InValue != CaseValue)
5780 ForwardingNodesMap ForwardingNodes;
5782 bool Changed =
false;
5783 for (
const auto &Case : SI->cases()) {
5785 BasicBlock *CaseDest = Case.getCaseSuccessor();
5804 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
5805 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
5806 count(Phi.blocks(), SwitchBlock) == 1) {
5807 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
5815 ForwardingNodes[Phi].push_back(PhiIdx);
5818 for (
auto &ForwardingNode : ForwardingNodes) {
5819 PHINode *Phi = ForwardingNode.first;
5825 for (
int Index : Indexes)
5826 Phi->setIncomingValue(
Index, SI->getCondition());
5836 if (
C->isThreadDependent())
5838 if (
C->isDLLImportDependent())
5841 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
5842 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
5843 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
5849 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
5865 if (
Constant *
C = dyn_cast<Constant>(V))
5881 if (
A->isAllOnesValue())
5883 if (
A->isNullValue())
5889 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
5914 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
5916 if (
I.isTerminator()) {
5918 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
5921 CaseDest =
I.getSuccessor(0);
5928 for (
auto &
Use :
I.uses()) {
5931 if (
I->getParent() == CaseDest)
5934 if (Phi->getIncomingBlock(
Use) == CaseDest)
5947 *CommonDest = CaseDest;
5949 if (CaseDest != *CommonDest)
5954 int Idx =
PHI.getBasicBlockIndex(Pred);
5967 Res.push_back(std::make_pair(&
PHI, ConstVal));
5970 return Res.size() > 0;
5976 SwitchCaseResultVectorTy &UniqueResults,
5978 for (
auto &
I : UniqueResults) {
5979 if (
I.first == Result) {
5980 I.second.push_back(CaseVal);
5981 return I.second.size();
5984 UniqueResults.push_back(
5995 SwitchCaseResultVectorTy &UniqueResults,
5999 uintptr_t MaxUniqueResults) {
6000 for (
const auto &
I : SI->cases()) {
6014 const size_t NumCasesForResult =
6022 if (UniqueResults.size() > MaxUniqueResults)
6033 BasicBlock *DefaultDest = SI->getDefaultDest();
6034 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6039 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6040 if ((!DefaultResult &&
6061 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6062 ResultVector[1].second.size() == 1) {
6063 ConstantInt *FirstCase = ResultVector[0].second[0];
6064 ConstantInt *SecondCase = ResultVector[1].second[0];
6065 Value *SelectValue = ResultVector[1].first;
6066 if (DefaultResult) {
6067 Value *ValueCompare =
6068 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6069 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6070 DefaultResult,
"switch.select");
6072 Value *ValueCompare =
6073 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6074 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6075 SelectValue,
"switch.select");
6079 if (ResultVector.size() == 1 && DefaultResult) {
6081 unsigned CaseCount = CaseValues.
size();
6089 for (
auto *Case : CaseValues)
6090 if (Case->getValue().slt(MinCaseVal->
getValue()))
6095 for (
auto *Case : CaseValues)
6096 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6102 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6106 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6111 if (CaseValues.
size() == 2) {
6113 "switch.selectcmp.case1");
6115 "switch.selectcmp.case2");
6116 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6117 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6130 std::vector<DominatorTree::UpdateType> Updates;
6136 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6141 PHI->removeIncomingValueIf(
6142 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6143 PHI->addIncoming(SelectValue, SelectBB);
6146 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6152 if (DTU && RemovedSuccessors.
insert(Succ).second)
6153 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6155 SI->eraseFromParent();
6170 SwitchCaseResultVectorTy UniqueResults;
6176 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6178 Value *SelectValue =
6190class SwitchLookupTable {
6241 bool LinearMapValWrapped =
false;
6249SwitchLookupTable::SwitchLookupTable(
6253 assert(Values.
size() &&
"Can't build lookup table without values!");
6254 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6257 SingleValue = Values.
begin()->second;
6263 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6269 TableContents[
Idx] = CaseRes;
6271 if (CaseRes != SingleValue)
6272 SingleValue =
nullptr;
6276 if (Values.
size() < TableSize) {
6278 "Need a default value to fill the lookup table holes.");
6281 if (!TableContents[
I])
6282 TableContents[
I] = DefaultValue;
6285 if (DefaultValue != SingleValue)
6286 SingleValue =
nullptr;
6292 Kind = SingleValueKind;
6299 bool LinearMappingPossible =
true;
6304 bool NonMonotonic =
false;
6305 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6308 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6312 LinearMappingPossible =
false;
6317 APInt Dist = Val - PrevVal;
6320 }
else if (Dist != DistToPrev) {
6321 LinearMappingPossible =
false;
6329 if (LinearMappingPossible) {
6330 LinearOffset = cast<ConstantInt>(TableContents[0]);
6331 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6332 bool MayWrap =
false;
6333 APInt M = LinearMultiplier->getValue();
6334 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6335 LinearMapValWrapped = NonMonotonic || MayWrap;
6336 Kind = LinearMapKind;
6343 if (WouldFitInRegister(
DL, TableSize,
ValueType)) {
6345 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6347 TableInt <<=
IT->getBitWidth();
6349 if (!isa<UndefValue>(TableContents[
I - 1])) {
6350 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6351 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6354 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6355 BitMapElementTy =
IT;
6366 GlobalVariable::PrivateLinkage, Initializer,
6367 "switch.table." + FuncName);
6368 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6377 case SingleValueKind:
6379 case LinearMapKind: {
6382 false,
"switch.idx.cast");
6383 if (!LinearMultiplier->isOne())
6384 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6386 !LinearMapValWrapped);
6388 if (!LinearOffset->isZero())
6391 !LinearMapValWrapped);
6407 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6408 "switch.shiftamt",
true,
true);
6411 Value *DownShifted =
6412 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6414 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6420 Array->getInitializer()->getType()->getArrayNumElements();
6421 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6424 "switch.tableidx.zext");
6428 GEPIndices,
"switch.gep");
6430 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6437bool SwitchLookupTable::WouldFitInRegister(
const DataLayout &
DL,
6439 Type *ElementType) {
6440 auto *
IT = dyn_cast<IntegerType>(ElementType);
6447 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6449 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6458 auto *
IT = dyn_cast<IntegerType>(Ty);
6470 DL.fitsInLegalInteger(
IT->getBitWidth());
6482 return NumCases * 100 >= CaseRange * MinDensity;
6503 if (SI->getNumCases() > TableSize)
6506 bool AllTablesFitInRegister =
true;
6507 bool HasIllegalType =
false;
6508 for (
const auto &
I : ResultTypes) {
6509 Type *Ty =
I.second;
6515 AllTablesFitInRegister =
6516 AllTablesFitInRegister &&
6517 SwitchLookupTable::WouldFitInRegister(
DL, TableSize, Ty);
6522 if (HasIllegalType && !AllTablesFitInRegister)
6527 if (AllTablesFitInRegister)
6544 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6547 return all_of(ResultTypes, [&](
const auto &KV) {
6548 return SwitchLookupTable::WouldFitInRegister(
6577 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6599 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6604 for (
auto ValuePair : Values) {
6607 if (!CaseConst || CaseConst == DefaultConst ||
6608 (CaseConst != TrueConst && CaseConst != FalseConst))
6622 if (DefaultConst == FalseConst) {
6625 ++NumTableCmpReuses;
6628 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6629 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6632 ++NumTableCmpReuses;
6642 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6661 if (SI->getNumCases() < 3)
6666 assert(!SI->cases().empty());
6683 MinCaseVal = CaseVal;
6685 MaxCaseVal = CaseVal;
6690 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6700 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6706 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6714 bool HasDefaultResults =
6716 DefaultResultsList,
DL,
TTI);
6718 for (
const auto &
I : DefaultResultsList) {
6721 DefaultResults[
PHI] = Result;
6725 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6727 if (UseSwitchConditionAsTableIndex)
6736 bool DefaultIsReachable = !SI->defaultDestUndefined();
6738 bool TableHasHoles = (NumResults < TableSize);
6743 bool AllHolesAreUndefined = TableHasHoles && !HasDefaultResults;
6751 bool NeedMask = AllHolesAreUndefined && DefaultIsReachable;
6754 if (SI->getNumCases() < 4)
6756 if (!
DL.fitsInLegalInteger(TableSize))
6763 std::vector<DominatorTree::UpdateType> Updates;
6769 assert(MaxTableSize >= TableSize &&
6770 "It is impossible for a switch to have more entries than the max "
6771 "representable value of its input integer type's size.");
6782 if (UseSwitchConditionAsTableIndex) {
6783 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
6784 TableIndex = SI->getCondition();
6786 TableIndexOffset = MinCaseVal;
6789 bool MayWrap =
true;
6790 if (!DefaultIsReachable) {
6795 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
6796 "switch.tableidx",
false,
6805 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
6813 return SwitchLookupTable::WouldFitInRegister(
6814 DL, UpperBound, KV.second );
6818 TableSize = std::max(UpperBound, TableSize);
6821 DefaultIsReachable =
false;
6825 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
6826 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6829 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6834 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
6836 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
6838 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6848 MaskBB->
setName(
"switch.hole_check");
6855 APInt MaskInt(TableSizePowOf2, 0);
6856 APInt One(TableSizePowOf2, 1);
6858 const ResultListTy &ResultList = ResultLists[PHIs[0]];
6859 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
6862 MaskInt |= One <<
Idx;
6872 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
6875 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
6877 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
6878 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
6884 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6887 SI->getDefaultDest()->removePredecessor(BB,
6890 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
6894 const ResultListTy &ResultList = ResultLists[
PHI];
6898 AllHolesAreUndefined ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
6900 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
6903 Value *Result = Table.BuildLookup(TableIndex, Builder);
6907 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
6910 for (
auto *
User :
PHI->users()) {
6915 PHI->addIncoming(Result, LookupBB);
6920 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
6924 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6927 if (Succ == SI->getDefaultDest())
6930 if (DTU && RemovedSuccessors.
insert(Succ).second)
6931 Updates.push_back({DominatorTree::Delete, BB, Succ});
6933 SI->eraseFromParent();
6940 ++NumLookupTablesHoles;
6955 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
6956 if (CondTy->getIntegerBitWidth() > 64 ||
6957 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6961 if (SI->getNumCases() < 4)
6969 for (
const auto &
C : SI->cases())
6970 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
6978 int64_t
Base = Values[0];
6979 for (
auto &V : Values)
6992 unsigned Shift = 64;
6993 for (
auto &V : Values)
6997 for (
auto &V : Values)
6998 V = (int64_t)((
uint64_t)V >> Shift);
7014 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
7017 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
7019 Ty, Intrinsic::fshl,
7020 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
7021 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7023 for (
auto Case : SI->cases()) {
7024 auto *Orig = Case.getCaseValue();
7025 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base);
7026 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7042 Value *Condition = SI->getCondition();
7044 auto *CondTy = cast<IntegerType>(Condition->
getType());
7046 if (CondTy->getIntegerBitWidth() > 64 ||
7047 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7061 if (SI->getNumCases() < 4)
7067 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7072 for (
const auto &Case : SI->cases()) {
7073 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7090 for (
auto &Case : SI->cases()) {
7091 auto *OrigValue = Case.getCaseValue();
7092 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7093 OrigValue->getValue().countr_zero()));
7100 SI->setCondition(ConditionTrailingZeros);
7108 if (isValueEqualityComparison(SI)) {
7112 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7113 return requestResimplify();
7117 if (SimplifySwitchOnSelect(SI,
Select))
7118 return requestResimplify();
7123 if (FoldValueComparisonIntoPredecessors(SI, Builder))
7124 return requestResimplify();
7130 if (
Options.ConvertSwitchRangeToICmp && TurnSwitchRangeIntoICmp(SI, Builder))
7131 return requestResimplify();
7135 return requestResimplify();
7138 return requestResimplify();
7141 return requestResimplify();
7148 if (
Options.ConvertSwitchToLookupTable &&
7150 return requestResimplify();
7153 return requestResimplify();
7156 return requestResimplify();
7159 hoistCommonCodeFromSuccessors(
SI->getParent(), !
Options.HoistCommonInsts))
7160 return requestResimplify();
7167 bool Changed =
false;
7176 RemovedSuccs.
insert(Dest);
7186 std::vector<DominatorTree::UpdateType> Updates;
7187 Updates.reserve(RemovedSuccs.
size());
7188 for (
auto *RemovedSucc : RemovedSuccs)
7189 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7190 DTU->applyUpdates(Updates);
7208 if (SimplifyIndirectBrOnSelect(IBI, SI))
7209 return requestResimplify();
7241 if (isa<PHINode>(*Succ->
begin()))
7245 if (BB == OtherPred)
7251 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7257 std::vector<DominatorTree::UpdateType> Updates;
7264 assert(
II->getNormalDest() != BB &&
II->getUnwindDest() == BB &&
7265 "unexpected successor");
7266 II->setUnwindDest(OtherPred);
7268 Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
7269 Updates.push_back({DominatorTree::Delete, Pred, BB});
7276 if (isa<DbgInfoIntrinsic>(Inst))
7283 Updates.push_back({DominatorTree::Delete, BB, Succ});
7297 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7298 : simplifyCondBranch(
Branch, Builder);
7301bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7313 bool NeedCanonicalLoop =
7324 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7326 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7328 if (
I->isTerminator() &&
7329 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7336 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7346 if (
Options.SpeculateBlocks &&
7349 return requestResimplify();
7357 if (!PPred || (PredPred && PredPred != PPred))
7368 "Tautological conditional branch should have been eliminated already.");
7371 if (!
Options.SimplifyCondBranch ||
7376 if (isValueEqualityComparison(BI)) {
7381 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
7382 return requestResimplify();
7388 if (FoldValueComparisonIntoPredecessors(BI, Builder))
7389 return requestResimplify();
7392 if (&*
I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
7393 return requestResimplify();
7398 if (SimplifyBranchOnICmpChain(BI, Builder,
DL))
7411 return requestResimplify();
7417 if (
Options.SpeculateBlocks &&
7420 return requestResimplify();
7430 return requestResimplify();
7438 return requestResimplify();
7447 return requestResimplify();
7454 return requestResimplify();
7459 if (PBI != BI && PBI->isConditional())
7461 return requestResimplify();
7466 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
7467 if (PBI != BI && PBI->isConditional())
7469 return requestResimplify();
7483 if (
C->isNullValue() || isa<UndefValue>(
C)) {
7485 auto *
Use = cast<Instruction>(*
I->user_begin());
7489 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
7503 if (
GEP->getPointerOperand() ==
I) {
7510 if (!
GEP->hasAllZeroIndices() &&
7511 (!
GEP->isInBounds() ||
7513 GEP->getPointerAddressSpace())))
7514 PtrValueMayBeModified =
true;
7520 bool HasNoUndefAttr =
7521 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
7523 if (isa<UndefValue>(
C) && HasNoUndefAttr)
7526 if (
C->isNullValue() && HasNoUndefAttr &&
7527 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
7528 return !PtrValueMayBeModified;
7538 if (!LI->isVolatile())
7540 LI->getPointerAddressSpace());
7544 if (!SI->isVolatile())
7546 SI->getPointerAddressSpace())) &&
7547 SI->getPointerOperand() ==
I;
7550 if (
auto *Assume = dyn_cast<AssumeInst>(
Use)) {
7552 if (
I == Assume->getArgOperand(0))
7556 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
7560 if (CB->getCalledOperand() ==
I)
7563 if (
C->isNullValue()) {
7566 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7567 if (CB->isPassingUndefUB(ArgIdx) &&
7568 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
7570 return !PtrValueMayBeModified;
7573 }
else if (isa<UndefValue>(
C)) {
7577 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7578 if (CB->isPassingUndefUB(ArgIdx)) {
7595 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
7622 DTU->
applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
7624 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
7632 for (
const auto &Case : SI->cases())
7633 if (Case.getCaseSuccessor() == BB) {
7635 Case.setSuccessor(Unreachable);
7637 if (SI->getDefaultDest() == BB) {
7639 SI->setDefaultDest(Unreachable);
7644 { { DominatorTree::Insert, Predecessor, Unreachable },
7645 { DominatorTree::Delete, Predecessor, BB } });
7653bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
7654 bool Changed =
false;
7678 return requestResimplify();
7699 if (
Options.SpeculateBlocks &&
7703 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
7712 case Instruction::Br:
7713 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
7715 case Instruction::Resume:
7716 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
7718 case Instruction::CleanupRet:
7719 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
7721 case Instruction::Switch:
7722 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
7724 case Instruction::Unreachable:
7725 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
7727 case Instruction::IndirectBr:
7728 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
7736 bool Changed =
false;
7744 Changed |= simplifyOnce(BB);
7745 }
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 provides utility for Memory Model Relaxation Annotations (MMRAs).
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
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, bool IsExpected)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static bool ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallDenseMap< PHINode *, Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool 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 void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU, bool RemoveOrigDefaultBlock=true)
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 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 void sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
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 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 canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< const Use *, SmallVector< Value *, 4 > > &PHIOperands)
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.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
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)
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
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 * 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.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
bool hasPostDomTree() const
Returns true if it holds a PostDomTreeT.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
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:
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
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.
void setNormalDest(BasicBlock *B)
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
LLVMContext & getContext() const
Get the global data context.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents a cast from a pointer to an integer.
Resume the propagation of an exception.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
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...
void setSuccessorWeight(unsigned idx, CaseWeightOpt W)
void addCase(ConstantInt *OnVal, BasicBlock *Dest, CaseWeightOpt W)
Delegate the call to the underlying SwitchInst::addCase() and set the specified branch weight for the...
CaseWeightOpt getSuccessorWeight(unsigned idx)
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
unsigned getOperandNo() const
Return the operand # of this use in its User.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
Value(Type *Ty, unsigned scid)
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ArchKind & operator--(ArchKind &Kind)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
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 RemapDbgRecord(Module *M, DbgRecord *DR, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecord DR using the value map VM.
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....
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
auto unique(Range &&R, Predicate P)
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ And
Bitwise or logical AND of integers.
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.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
void extractFromBranchWeightMD64(const MDNode *ProfileData, SmallVectorImpl< uint64_t > &Weights)
Faster version of extractBranchWeights() that skips checks and must only be called with "branch_weigh...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
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.