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) {
870 SI->setMetadata(LLVMContext::MD_prof,
N);
877 assert(isa<BranchInst>(
I) || isa<SelectInst>(
I));
881 if (TrueWeight || FalseWeight)
884 I->setMetadata(LLVMContext::MD_prof,
N);
892bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
898 Value *ThisVal = isValueEqualityComparison(TI);
899 assert(ThisVal &&
"This isn't a value comparison!!");
900 if (ThisVal != PredVal)
907 std::vector<ValueEqualityComparisonCase> PredCases;
909 GetValueEqualityComparisonCases(Pred->
getTerminator(), PredCases);
913 std::vector<ValueEqualityComparisonCase> ThisCases;
914 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
926 if (isa<BranchInst>(TI)) {
929 assert(ThisCases.size() == 1 &&
"Branch can only have one case!");
935 ThisCases[0].Dest->removePredecessor(PredDef);
938 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
945 {{DominatorTree::Delete, PredDef, ThisCases[0].Dest}});
953 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
957 <<
"Through successor TI: " << *TI);
965 if (DeadCases.
count(i->getCaseValue())) {
974 std::vector<DominatorTree::UpdateType> Updates;
975 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
977 Updates.push_back({DominatorTree::Delete, PredDef,
I.first});
978 DTU->applyUpdates(Updates);
989 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
990 if (PredCases[i].Dest == TIBB) {
993 TIV = PredCases[i].
Value;
995 assert(TIV &&
"No edge from pred to succ?");
1000 for (
unsigned i = 0, e = ThisCases.size(); i != e; ++i)
1001 if (ThisCases[i].
Value == TIV) {
1002 TheRealDest = ThisCases[i].Dest;
1008 TheRealDest = ThisDef;
1015 if (Succ != CheckEdge) {
1016 if (Succ != TheRealDest)
1017 RemovedSuccs.
insert(Succ);
1020 CheckEdge =
nullptr;
1027 <<
"Through successor TI: " << *TI <<
"Leaving: " << *NI
1034 for (
auto *RemovedSucc : RemovedSuccs)
1035 Updates.
push_back({DominatorTree::Delete, TIBB, RemovedSucc});
1036 DTU->applyUpdates(Updates);
1046struct ConstantIntOrdering {
1048 return LHS->getValue().ult(
RHS->getValue());
1060 return LHS->getValue().ult(
RHS->getValue()) ? 1 : -1;
1078 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1089 if (Max > UINT_MAX) {
1104 if (BonusInst.isTerminator())
1109 if (!isa<DbgInfoIntrinsic>(BonusInst) &&
1134 if (isa<DbgInfoIntrinsic>(BonusInst))
1137 NewBonusInst->
takeName(&BonusInst);
1138 BonusInst.setName(NewBonusInst->
getName() +
".old");
1139 VMap[&BonusInst] = NewBonusInst;
1145 auto *UI = cast<Instruction>(U.getUser());
1146 auto *PN = dyn_cast<PHINode>(UI);
1148 assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
1149 "If the user is not a PHI node, then it should be in the same "
1150 "block as, and come after, the original bonus instruction.");
1154 if (PN->getIncomingBlock(U) == BB)
1158 assert(PN->getIncomingBlock(U) == PredBlock &&
1159 "Not in block-closed SSA form?");
1160 U.set(NewBonusInst);
1165bool SimplifyCFGOpt::PerformValueComparisonIntoPredecessorFolding(
1173 std::vector<ValueEqualityComparisonCase> BBCases;
1174 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1176 std::vector<ValueEqualityComparisonCase> PredCases;
1177 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1189 if (PredHasWeights) {
1192 if (Weights.
size() != 1 + PredCases.size())
1193 PredHasWeights = SuccHasWeights =
false;
1194 }
else if (SuccHasWeights)
1198 Weights.
assign(1 + PredCases.size(), 1);
1201 if (SuccHasWeights) {
1204 if (SuccWeights.
size() != 1 + BBCases.size())
1205 PredHasWeights = SuccHasWeights =
false;
1206 }
else if (PredHasWeights)
1207 SuccWeights.
assign(1 + BBCases.size(), 1);
1209 if (PredDefault == BB) {
1212 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1213 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1214 if (PredCases[i].Dest != BB)
1215 PTIHandled.insert(PredCases[i].
Value);
1218 std::swap(PredCases[i], PredCases.back());
1220 if (PredHasWeights || SuccHasWeights) {
1222 Weights[0] += Weights[i + 1];
1227 PredCases.pop_back();
1233 if (PredDefault != BBDefault) {
1235 if (DTU && PredDefault != BB)
1236 Updates.
push_back({DominatorTree::Delete, Pred, PredDefault});
1237 PredDefault = BBDefault;
1238 ++NewSuccessors[BBDefault];
1241 unsigned CasesFromPred = Weights.
size();
1243 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1244 if (!PTIHandled.count(BBCases[i].Value) && BBCases[i].Dest != BBDefault) {
1245 PredCases.push_back(BBCases[i]);
1246 ++NewSuccessors[BBCases[i].Dest];
1247 if (SuccHasWeights || PredHasWeights) {
1251 Weights.
push_back(Weights[0] * SuccWeights[i + 1]);
1252 ValidTotalSuccWeight += SuccWeights[i + 1];
1256 if (SuccHasWeights || PredHasWeights) {
1257 ValidTotalSuccWeight += SuccWeights[0];
1259 for (
unsigned i = 1; i < CasesFromPred; ++i)
1260 Weights[i] *= ValidTotalSuccWeight;
1262 Weights[0] *= SuccWeights[0];
1268 std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1269 std::map<ConstantInt *, uint64_t> WeightsForHandled;
1270 for (
unsigned i = 0, e = PredCases.size(); i != e; ++i)
1271 if (PredCases[i].Dest == BB) {
1274 if (PredHasWeights || SuccHasWeights) {
1275 WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1280 std::swap(PredCases[i], PredCases.back());
1281 PredCases.pop_back();
1288 for (
unsigned i = 0, e = BBCases.size(); i != e; ++i)
1289 if (PTIHandled.count(BBCases[i].Value)) {
1291 if (PredHasWeights || SuccHasWeights)
1293 PredCases.push_back(BBCases[i]);
1294 ++NewSuccessors[BBCases[i].Dest];
1301 if (PredHasWeights || SuccHasWeights)
1303 PredCases.push_back(ValueEqualityComparisonCase(
I, BBDefault));
1304 ++NewSuccessors[BBDefault];
1316 for (
const std::pair<BasicBlock *, int /*Num*/> &NewSuccessor :
1318 for (
auto I :
seq(NewSuccessor.second)) {
1322 if (DTU && !SuccsOfPred.
contains(NewSuccessor.first))
1323 Updates.
push_back({DominatorTree::Insert, Pred, NewSuccessor.first});
1336 for (ValueEqualityComparisonCase &V : PredCases)
1339 if (PredHasWeights || SuccHasWeights) {
1356 if (!InfLoopBlock) {
1364 {DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
1371 Updates.
push_back({DominatorTree::Insert, Pred, InfLoopBlock});
1373 Updates.
push_back({DominatorTree::Delete, Pred, BB});
1375 DTU->applyUpdates(Updates);
1378 ++NumFoldValueComparisonIntoPredecessors;
1386bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(
Instruction *TI,
1389 Value *CV = isValueEqualityComparison(TI);
1390 assert(CV &&
"Not a comparison?");
1392 bool Changed =
false;
1395 while (!Preds.empty()) {
1404 Value *PCV = isValueEqualityComparison(PTI);
1410 for (
auto *Succ : FailBlocks) {
1416 PerformValueComparisonIntoPredecessorFolding(TI, CV, PTI, Builder);
1430 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1431 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1432 if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1451 if (
I->mayReadFromMemory())
1455 if (
I->mayHaveSideEffects() || isa<AllocaInst>(
I))
1472 (
I->mayReadFromMemory() ||
I->mayHaveSideEffects() || isa<AllocaInst>(
I)))
1482 if (
auto *CB = dyn_cast<CallBase>(
I))
1483 if (CB->getIntrinsicID() == Intrinsic::experimental_deoptimize)
1490 if (
auto *J = dyn_cast<Instruction>(
Op))
1491 if (J->getParent() == BB)
1510 auto *C1 = dyn_cast<CallInst>(I1);
1511 auto *C2 = dyn_cast<CallInst>(I2);
1513 if (C1->isMustTailCall() != C2->isMustTailCall())
1521 if (
const auto *CB1 = dyn_cast<CallBase>(I1))
1522 if (CB1->cannotMerge() || CB1->isConvergent())
1524 if (
const auto *CB2 = dyn_cast<CallBase>(I2))
1525 if (CB2->cannotMerge() || CB2->isConvergent())
1540 if (!I1->hasDbgRecords())
1542 using CurrentAndEndIt =
1543 std::pair<DbgRecord::self_iterator, DbgRecord::self_iterator>;
1549 auto atEnd = [](
const CurrentAndEndIt &Pair) {
1550 return Pair.first == Pair.second;
1556 return Itrs[0].first->isIdenticalToWhenDefined(*
I);
1562 {I1->getDbgRecordRange().begin(), I1->getDbgRecordRange().end()});
1564 if (!
Other->hasDbgRecords())
1567 {
Other->getDbgRecordRange().begin(),
Other->getDbgRecordRange().end()});
1574 while (
none_of(Itrs, atEnd)) {
1575 bool HoistDVRs = allIdentical(Itrs);
1576 for (CurrentAndEndIt &Pair : Itrs) {
1593bool SimplifyCFGOpt::hoistCommonCodeFromSuccessors(
BasicBlock *BB,
1615 using SuccIterPair = std::pair<BasicBlock::iterator, unsigned>;
1619 if (isa<PHINode>(*SuccItr))
1621 SuccIterPairs.
push_back(SuccIterPair(SuccItr, 0));
1630 if (!INonDbg->isTerminator())
1640 unsigned NumSkipped = 0;
1643 if (SuccIterPairs.
size() > 2) {
1645 [](
const auto &Pair) {
return isa<UnreachableInst>(Pair.first); });
1646 if (SuccIterPairs.
size() < 2)
1650 bool Changed =
false;
1653 auto *SuccIterPairBegin = SuccIterPairs.
begin();
1654 auto &BB1ItrPair = *SuccIterPairBegin++;
1655 auto OtherSuccIterPairRange =
1662 bool AllDbgInstsAreIdentical =
all_of(OtherSuccIterRange, [I1](
auto &Iter) {
1664 return I1->isIdenticalToWhenDefined(I2);
1666 if (!AllDbgInstsAreIdentical) {
1667 while (isa<DbgInfoIntrinsic>(I1))
1668 I1 = &*++BB1ItrPair.first;
1669 for (
auto &SuccIter : OtherSuccIterRange) {
1671 while (isa<DbgInfoIntrinsic>(I2))
1676 bool AllInstsAreIdentical =
true;
1677 bool HasTerminator =
I1->isTerminator();
1678 for (
auto &SuccIter : OtherSuccIterRange) {
1681 if (AllInstsAreIdentical && (!
I1->isIdenticalToWhenDefined(I2) ||
1683 AllInstsAreIdentical =
false;
1687 for (
auto &SuccIter : OtherSuccIterRange)
1692 if (HasTerminator) {
1696 if (NumSkipped || !AllInstsAreIdentical) {
1701 return hoistSuccIdenticalTerminatorToSwitchOrIf(TI, I1, OtherInsts) ||
1705 if (AllInstsAreIdentical) {
1706 unsigned SkipFlagsBB1 = BB1ItrPair.second;
1707 AllInstsAreIdentical =
1709 all_of(OtherSuccIterPairRange, [=](
const auto &Pair) {
1711 unsigned SkipFlagsBB2 = Pair.second;
1721 if (AllInstsAreIdentical) {
1723 if (isa<DbgInfoIntrinsic>(I1)) {
1732 for (
auto &SuccIter : OtherSuccIterRange) {
1733 auto *I2 = &*SuccIter++;
1734 assert(isa<DbgInfoIntrinsic>(I2));
1746 for (
auto &SuccIter : OtherSuccIterRange) {
1760 NumHoistCommonCode += SuccIterPairs.
size();
1762 NumHoistCommonInstrs += SuccIterPairs.
size();
1771 for (
auto &SuccIterPair : SuccIterPairs) {
1780bool SimplifyCFGOpt::hoistSuccIdenticalTerminatorToSwitchOrIf(
1784 auto *BI = dyn_cast<BranchInst>(TI);
1786 bool Changed =
false;
1791 auto *I2 = *OtherSuccTIs.
begin();
1807 if (isa<CallBrInst>(I1))
1812 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1814 Value *BB2V = PN.getIncomingValueForBlock(OtherSuccTI->getParent());
1834 if (!
NT->getType()->isVoidTy()) {
1835 I1->replaceAllUsesWith(NT);
1837 OtherSuccTI->replaceAllUsesWith(NT);
1841 NumHoistCommonInstrs += OtherSuccTIs.size() + 1;
1847 for (
auto *OtherSuccTI : OtherSuccTIs)
1848 Locs.
push_back(OtherSuccTI->getDebugLoc());
1860 std::map<std::pair<Value *, Value *>,
SelectInst *> InsertedSelects;
1863 Value *BB1V = PN.getIncomingValueForBlock(BB1);
1864 Value *BB2V = PN.getIncomingValueForBlock(BB2);
1870 SelectInst *&
SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1874 if (isa<FPMathOperator>(PN))
1883 for (
unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1884 if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1885 PN.setIncomingValue(i, SI);
1896 Updates.
push_back({DominatorTree::Insert, TIParent, Succ});
1901 Updates.
push_back({DominatorTree::Delete, TIParent, Succ});
1905 DTU->applyUpdates(Updates);
1911 if (
auto II = dyn_cast<IntrinsicInst>(
I)) {
1912 switch (II->getIntrinsicID()) {
1915 case Intrinsic::lifetime_start:
1916 case Intrinsic::lifetime_end:
1927 return !isa<IntrinsicInst>(
I);
1941 bool HasUse = !Insts.
front()->user_empty();
1942 for (
auto *
I : Insts) {
1944 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
1945 I->getType()->isTokenTy())
1950 if (
I->getParent()->getSingleSuccessor() ==
I->getParent())
1957 if (
const auto *
C = dyn_cast<CallBase>(
I))
1958 if (
C->isInlineAsm() ||
C->cannotMerge() ||
C->isConvergent())
1962 if (HasUse && !
I->hasOneUse())
1964 if (!HasUse && !
I->user_empty())
1970 for (
auto *
I : Insts) {
1971 if (!
I->isSameOperationAs(I0))
1977 if (isa<StoreInst>(
I) &&
I->getOperand(1)->isSwiftError())
1979 if (isa<LoadInst>(
I) &&
I->getOperand(0)->isSwiftError())
1993 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
1996 auto *U = cast<Instruction>(*
I->user_begin());
1998 PNUse->getParent() == Succ &&
1999 PNUse->getIncomingValueForBlock(
I->getParent()) ==
I) ||
2000 U->getParent() ==
I->getParent();
2015 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2019 return isa<AllocaInst>(
I->getOperand(0)->stripPointerCasts());
2023 return isa<AllocaInst>(
I->getOperand(1)->stripPointerCasts());
2031 if (isa<CallBase>(I0)) {
2033 return cast<CallBase>(
I)->isIndirectCall();
2035 bool HaveIndirectCalls =
any_of(Insts, IsIndirectCall);
2036 bool AllCallsAreIndirect =
all_of(Insts, IsIndirectCall);
2037 if (HaveIndirectCalls) {
2038 if (!AllCallsAreIndirect)
2042 Value *Callee =
nullptr;
2044 Value *CurrCallee = cast<CallBase>(
I)->getCalledOperand();
2046 Callee = CurrCallee;
2047 else if (Callee != CurrCallee)
2053 for (
unsigned OI = 0, OE = I0->
getNumOperands(); OI != OE; ++OI) {
2055 if (
Op->getType()->isTokenTy())
2063 if (!
all_of(Insts, SameAsI0)) {
2068 for (
auto *
I : Insts)
2069 PHIOperands[
I].push_back(
I->getOperand(OI));
2079 auto *BBEnd =
Blocks[0]->getTerminator()->getSuccessor(0);
2084 for (
auto *BB :
Blocks) {
2087 I =
I->getPrevNode();
2088 }
while (isa<DbgInfoIntrinsic>(
I) &&
I != &BB->
front());
2089 if (!isa<DbgInfoIntrinsic>(
I))
2099 auto *PNUse = dyn_cast<PHINode>(*I0->
user_begin());
2101 auto *U = cast<Instruction>(*
I->user_begin());
2127 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
2130 PN->insertBefore(BBEnd->begin());
2131 for (
auto *
I : Insts)
2132 PN->addIncoming(
I->getOperand(O),
I->getParent());
2141 I0->
moveBefore(*BBEnd, BBEnd->getFirstInsertionPt());
2144 for (
auto *
I : Insts)
2163 PN->replaceAllUsesWith(I0);
2164 PN->eraseFromParent();
2168 for (
auto *
I : Insts) {
2173 assert(
I->user_empty() &&
"Inst unexpectedly still has non-dbg users");
2174 I->replaceAllUsesWith(I0);
2175 I->eraseFromParent();
2191 class LockstepReverseIterator {
2204 for (
auto *BB : Blocks) {
2206 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2224 for (
auto *&Inst : Insts) {
2225 for (Inst = Inst->
getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2238 for (
auto *&Inst : Insts) {
2239 for (Inst = Inst->
getNextNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
2302 bool HaveNonUnconditionalPredecessors =
false;
2304 auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
2305 if (PredBr && PredBr->isUnconditional())
2308 HaveNonUnconditionalPredecessors =
true;
2310 if (UnconditionalPreds.
size() < 2)
2322 LockstepReverseIterator LRI(UnconditionalPreds);
2323 while (LRI.isValid() &&
2325 LLVM_DEBUG(
dbgs() <<
"SINK: instruction can be sunk: " << *(*LRI)[0]
2327 InstructionsToSink.
insert((*LRI).begin(), (*LRI).end());
2338 if (!followedByDeoptOrUnreachable) {
2342 auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
2343 unsigned NumPHIdValues = 0;
2344 for (
auto *
I : *LRI)
2345 for (
auto *V : PHIOperands[
I]) {
2346 if (!InstructionsToSink.
contains(V))
2352 LLVM_DEBUG(
dbgs() <<
"SINK: #phid values: " << NumPHIdValues <<
"\n");
2353 unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.
size();
2354 if ((NumPHIdValues % UnconditionalPreds.
size()) != 0)
2357 return NumPHIInsts <= 1;
2374 while (
Idx < ScanIdx) {
2375 if (!ProfitableToSinkInstruction(LRI)) {
2378 dbgs() <<
"SINK: stopping here, too many PHIs would be created!\n");
2381 InstructionsProfitableToSink.
insert((*LRI).begin(), (*LRI).end());
2391 if (
Idx < ScanIdx) {
2394 InstructionsToSink = InstructionsProfitableToSink;
2400 !ProfitableToSinkInstruction(LRI) &&
2401 "We already know that the last instruction is unprofitable to sink");
2409 for (
auto *
I : *LRI)
2410 InstructionsProfitableToSink.
erase(
I);
2411 if (!ProfitableToSinkInstruction(LRI)) {
2414 InstructionsToSink = InstructionsProfitableToSink;
2426 bool Changed =
false;
2428 if (HaveNonUnconditionalPredecessors) {
2429 if (!followedByDeoptOrUnreachable) {
2437 bool Profitable =
false;
2438 while (
Idx < ScanIdx) {
2472 for (; SinkIdx != ScanIdx; ++SinkIdx) {
2474 << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
2484 <<
"SINK: stopping here, failed to actually sink instruction!\n");
2488 NumSinkCommonInstrs++;
2492 ++NumSinkCommonCode;
2498struct CompatibleSets {
2516 if (CompatibleSets::shouldBelongToSameSet({Set.front(), II}))
2525 getCompatibleSet(II).emplace_back(II);
2529 assert(Invokes.
size() == 2 &&
"Always called with exactly two candidates.");
2535 if (
any_of(Invokes, IsIllegalToMerge))
2541 bool HaveIndirectCalls =
any_of(Invokes, IsIndirectCall);
2542 bool AllCallsAreIndirect =
all_of(Invokes, IsIndirectCall);
2543 if (HaveIndirectCalls) {
2544 if (!AllCallsAreIndirect)
2551 assert(CurrCallee &&
"There is always a called operand.");
2554 else if (Callee != CurrCallee)
2564 if (
any_of(Invokes, HasNormalDest)) {
2567 if (!
all_of(Invokes, HasNormalDest))
2574 assert(CurrNormalBB &&
"There is always a 'continue to' basic block.");
2576 NormalBB = CurrNormalBB;
2577 else if (NormalBB != CurrNormalBB)
2585 NormalBB, {Invokes[0]->getParent(), Invokes[1]->
getParent()},
2596 assert(CurrUnwindBB &&
"There is always an 'unwind to' basic block.");
2598 UnwindBB = CurrUnwindBB;
2600 assert(UnwindBB == CurrUnwindBB &&
"Unexpected unwind destination.");
2607 Invokes.front()->getUnwindDest(),
2608 {Invokes[0]->getParent(), Invokes[1]->getParent()}))
2614 for (
auto *II : Invokes.drop_front())
2619 auto IsIllegalToMergeArguments = [](
auto Ops) {
2620 Use &U0 = std::get<0>(Ops);
2621 Use &U1 = std::get<1>(Ops);
2628 assert(Invokes.size() == 2 &&
"Always called with exactly two candidates.");
2629 if (
any_of(
zip(Invokes[0]->data_ops(), Invokes[1]->data_ops()),
2630 IsIllegalToMergeArguments))
2642 assert(Invokes.
size() >= 2 &&
"Must have at least two invokes to merge.");
2648 bool HasNormalDest =
2649 !isa<UnreachableInst>(Invokes[0]->getNormalDest()->getFirstNonPHIOrDbg());
2653 InvokeInst *MergedInvoke = [&Invokes, HasNormalDest]() {
2662 Ctx, II0BB->
getName() +
".invoke", Func, InsertBeforeBlock);
2664 auto *MergedInvoke = cast<InvokeInst>(II0->
clone());
2666 MergedInvoke->
insertInto(MergedInvokeBB, MergedInvokeBB->
end());
2668 if (!HasNormalDest) {
2672 Ctx, II0BB->
getName() +
".cont", Func, InsertBeforeBlock);
2679 return MergedInvoke;
2693 SuccBBOfMergedInvoke});
2700 {DominatorTree::Delete, II->
getParent(), SuccOfPredBB});
2703 bool IsIndirectCall = Invokes[0]->isIndirectCall();
2706 for (
Use &U : MergedInvoke->operands()) {
2708 if (MergedInvoke->isCallee(&U)) {
2709 if (!IsIndirectCall)
2711 }
else if (!MergedInvoke->isDataOperand(&U))
2723 U->getType(), Invokes.size(),
"", MergedInvoke->getIterator());
2735 Invokes.front()->getParent());
2743 if (!MergedDebugLoc)
2752 OrigSuccBB->removePredecessor(II->
getParent());
2758 MergedInvoke->setDebugLoc(MergedDebugLoc);
2759 ++NumInvokeSetsFormed;
2762 DTU->applyUpdates(Updates);
2789 bool Changed =
false;
2795 CompatibleSets Grouper;
2801 Grouper.insert(cast<InvokeInst>(PredBB->getTerminator()));
2805 if (Invokes.
size() < 2)
2817class EphemeralValueTracker {
2821 if (isa<AssumeInst>(
I))
2823 return !
I->mayHaveSideEffects() && !
I->isTerminator() &&
2825 return EphValues.count(cast<Instruction>(U));
2831 if (isEphemeral(
I)) {
2870 StoreInst *StoreToHoist = dyn_cast<StoreInst>(
I);
2882 unsigned MaxNumInstToLookAt = 9;
2886 if (!MaxNumInstToLookAt)
2888 --MaxNumInstToLookAt;
2891 if (CurI.mayWriteToMemory() && !isa<StoreInst>(CurI))
2894 if (
auto *SI = dyn_cast<StoreInst>(&CurI)) {
2898 if (SI->getPointerOperand() == StorePtr &&
2899 SI->getValueOperand()->getType() == StoreTy && SI->isSimple() &&
2900 SI->getAlign() >= StoreToHoist->
getAlign())
2902 return SI->getValueOperand();
2906 if (
auto *LI = dyn_cast<LoadInst>(&CurI)) {
2907 if (LI->getPointerOperand() == StorePtr && LI->
getType() == StoreTy &&
2908 LI->isSimple() && LI->getAlign() >= StoreToHoist->
getAlign()) {
2931 unsigned &SpeculatedInstructions,
2939 bool HaveRewritablePHIs =
false;
2957 HaveRewritablePHIs =
true;
2960 if (!OrigCE && !ThenCE)
2967 if (OrigCost + ThenCost > MaxCost)
2974 ++SpeculatedInstructions;
2975 if (SpeculatedInstructions > 1)
2979 return HaveRewritablePHIs;
3019bool SimplifyCFGOpt::SpeculativelyExecuteBB(
BranchInst *BI,
3026 if (isa<FCmpInst>(BrCond))
3036 bool Invert =
false;
3045 if (!BI->
getMetadata(LLVMContext::MD_unpredictable)) {
3048 (TWeight + FWeight) != 0) {
3049 uint64_t EndWeight = Invert ? TWeight : FWeight;
3053 if (BIEndProb >= Likely)
3067 unsigned SpeculatedInstructions = 0;
3068 Value *SpeculatedStoreValue =
nullptr;
3070 EphemeralValueTracker EphTracker;
3073 if (isa<DbgInfoIntrinsic>(
I)) {
3081 if (isa<PseudoProbeInst>(
I)) {
3091 if (EphTracker.track(&
I))
3096 ++SpeculatedInstructions;
3097 if (SpeculatedInstructions > 1)
3103 &
I, BB, ThenBB, EndBB))))
3105 if (!SpeculatedStoreValue &&
3111 if (SpeculatedStoreValue)
3112 SpeculatedStore = cast<StoreInst>(&
I);
3117 for (
Use &
Op :
I.operands()) {
3122 ++SinkCandidateUseCounts[OpI];
3129 for (
const auto &[Inst, Count] : SinkCandidateUseCounts)
3131 ++SpeculatedInstructions;
3132 if (SpeculatedInstructions > 1)
3138 bool Convert = SpeculatedStore !=
nullptr;
3141 SpeculatedInstructions,
3143 if (!Convert ||
Cost > Budget)
3147 LLVM_DEBUG(
dbgs() <<
"SPECULATIVELY EXECUTING BB" << *ThenBB <<
"\n";);
3150 if (SpeculatedStoreValue) {
3154 Value *FalseV = SpeculatedStoreValue;
3158 BrCond, TrueV, FalseV,
"spec.store.select", BI);
3187 auto replaceVariable = [OrigV, S](
auto *DbgAssign) {
3189 DbgAssign->replaceVariableLocationOp(OrigV, S);
3202 if (!SpeculatedStoreValue || &
I != SpeculatedStore) {
3204 if (!isa<DbgAssignIntrinsic>(&
I))
3207 I.dropUBImplyingAttrsAndMetadata();
3210 if (EphTracker.contains(&
I)) {
3212 I.eraseFromParent();
3226 It.dropOneDbgRecord(&DR);
3228 std::prev(ThenBB->
end()));
3245 Value *TrueV = ThenV, *FalseV = OrigV;
3259 if (!isa<DbgAssignIntrinsic>(
I))
3260 I->eraseFromParent();
3270 EphemeralValueTracker EphTracker;
3276 if (
CallInst *CI = dyn_cast<CallInst>(&
I))
3277 if (CI->cannotDuplicate() || CI->isConvergent())
3283 if (!EphTracker.track(&
I) && !isa<PHINode>(
I)) {
3290 for (
User *U :
I.users()) {
3292 if (UI->
getParent() != BB || isa<PHINode>(UI))
3306 auto *
I = dyn_cast<Instruction>(V);
3307 if (
I &&
I->getParent() == To)
3311 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
3323static std::optional<bool>
3339 if (
auto *CB = dyn_cast<ConstantInt>(U))
3344 KnownValues[CB].
insert(Pred);
3348 if (KnownValues.
empty())
3357 for (
const auto &Pair : KnownValues) {
3375 <<
" has value " << *Pair.first <<
" in predecessors:\n";
3378 dbgs() <<
"Threading to destination " << RealDest->
getName() <<
".\n";
3386 EdgeBB->setName(RealDest->
getName() +
".critedge");
3387 EdgeBB->moveBefore(RealDest);
3397 TranslateMap[
Cond] = CB;
3403 if (
PHINode *PN = dyn_cast<PHINode>(BBI)) {
3410 N->insertInto(EdgeBB, InsertPt);
3413 N->setName(BBI->getName() +
".c");
3416 for (
Use &
Op :
N->operands()) {
3418 if (PI != TranslateMap.
end())
3424 if (!BBI->use_empty())
3425 TranslateMap[&*BBI] = V;
3426 if (!
N->mayHaveSideEffects()) {
3427 N->eraseFromParent();
3432 if (!BBI->use_empty())
3433 TranslateMap[&*BBI] =
N;
3439 for (; SrcDbgCursor != BBI; ++SrcDbgCursor)
3440 N->cloneDebugInfoFrom(&*SrcDbgCursor);
3441 SrcDbgCursor = std::next(BBI);
3443 N->cloneDebugInfoFrom(&*BBI);
3446 if (
auto *Assume = dyn_cast<AssumeInst>(
N))
3452 for (; &*SrcDbgCursor != BI; ++SrcDbgCursor)
3453 InsertPt->cloneDebugInfoFrom(&*SrcDbgCursor);
3454 InsertPt->cloneDebugInfoFrom(BI);
3457 BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
3463 Updates.
push_back({DominatorTree::Delete, EdgeBB, BB});
3464 Updates.
push_back({DominatorTree::Insert, EdgeBB, RealDest});
3475 return std::nullopt;
3485 std::optional<bool> Result;
3486 bool EverChanged =
false;
3490 EverChanged |= Result == std::nullopt || *Result;
3491 }
while (Result == std::nullopt);
3513 if (isa<ConstantInt>(IfCond))
3520 return cast<BranchInst>(IfBlock->getTerminator())->isUnconditional();
3523 "Will have either one or two blocks to speculate.");
3530 if (!DomBI->
getMetadata(LLVMContext::MD_unpredictable)) {
3533 (TWeight + FWeight) != 0) {
3538 if (IfBlocks.
size() == 1) {
3540 DomBI->
getSuccessor(0) == BB ? BITrueProb : BIFalseProb;
3541 if (BIBBProb >= Likely)
3544 if (BITrueProb >= Likely || BIFalseProb >= Likely)
3552 if (
auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
3553 if (IfCondPhiInst->getParent() == BB)
3561 unsigned NumPhis = 0;
3574 bool Changed =
false;
3576 PHINode *PN = cast<PHINode>(II++);
3593 PN = dyn_cast<PHINode>(BB->
begin());
3599 auto CanHoistNotFromBothValues = [](
Value *V0,
Value *V1) {
3610 auto IsBinOpOrAnd = [](
Value *V) {
3630 if (!AggressiveInsts.
count(&*
I) && !
I->isDebugOrPseudoInst()) {
3643 <<
" T: " << IfTrue->
getName()
3644 <<
" F: " << IfFalse->
getName() <<
"\n");
3658 if (isa<FPMathOperator>(PN))
3678 Updates.
push_back({DominatorTree::Insert, DomBlock, BB});
3696 if (Opc == Instruction::And)
3698 if (Opc == Instruction::Or)
3711 bool PredHasWeights =
3713 bool SuccHasWeights =
3715 if (PredHasWeights || SuccHasWeights) {
3716 if (!PredHasWeights)
3717 PredTrueWeight = PredFalseWeight = 1;
3718 if (!SuccHasWeights)
3719 SuccTrueWeight = SuccFalseWeight = 1;
3729static std::optional<std::tuple<BasicBlock *, Instruction::BinaryOps, bool>>
3733 "Both blocks must end with a conditional branches.");
3735 "PredBB must be a predecessor of BB.");
3743 (PTWeight + PFWeight) != 0) {
3751 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3752 return {{BI->
getSuccessor(0), Instruction::Or,
false}};
3756 return {{BI->
getSuccessor(1), Instruction::And,
false}};
3759 if (PBITrueProb.
isUnknown() || PBITrueProb < Likely)
3760 return {{BI->
getSuccessor(1), Instruction::And,
true}};
3766 return std::nullopt;
3779 bool InvertPredCond;
3780 std::tie(CommonSucc, Opc, InvertPredCond) =
3783 LLVM_DEBUG(
dbgs() <<
"FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
3790 {LLVMContext::MD_annotation});
3793 if (InvertPredCond) {
3806 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3808 SuccTrueWeight, SuccFalseWeight)) {
3815 NewWeights.
push_back(PredTrueWeight * SuccTrueWeight);
3821 (SuccFalseWeight + SuccTrueWeight) +
3822 PredTrueWeight * SuccFalseWeight);
3828 NewWeights.
push_back(PredTrueWeight * (SuccFalseWeight + SuccTrueWeight) +
3829 PredFalseWeight * SuccTrueWeight);
3831 NewWeights.
push_back(PredFalseWeight * SuccFalseWeight);
3849 DTU->
applyUpdates({{DominatorTree::Insert, PredBlock, UniqueSucc},
3850 {DominatorTree::Delete, PredBlock, BB}});
3877 ++NumFoldBranchToCommonDest;
3884 return I.getType()->isVectorTy() ||
any_of(
I.operands(), [](
Use &U) {
3885 return U->getType()->isVectorTy();
3895 unsigned BonusInstThreshold) {
3909 (!isa<CmpInst>(
Cond) && !isa<BinaryOperator>(
Cond) &&
3910 !isa<SelectInst>(
Cond)) ||
3911 Cond->getParent() != BB || !
Cond->hasOneUse())
3921 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
3932 bool InvertPredCond;
3934 std::tie(CommonSucc, Opc, InvertPredCond) = *Recipe;
3966 unsigned NumBonusInsts = 0;
3967 bool SawVectorOp =
false;
3968 const unsigned PredCount = Preds.
size();
3974 if (isa<DbgInfoIntrinsic>(
I) || isa<BranchInst>(
I))
3985 NumBonusInsts += PredCount;
3993 auto IsBCSSAUse = [BB, &
I](
Use &U) {
3994 auto *UI = cast<Instruction>(U.getUser());
3995 if (
auto *PN = dyn_cast<PHINode>(UI))
3997 return UI->
getParent() == BB &&
I.comesBefore(UI);
4001 if (!
all_of(
I.uses(), IsBCSSAUse))
4005 BonusInstThreshold *
4011 auto *PBI = cast<BranchInst>(PredBlock->getTerminator());
4021 for (
auto *BB : {BB1, BB2}) {
4025 if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
4037 Value *AlternativeV =
nullptr) {
4055 for (
auto I = Succ->
begin(); isa<PHINode>(
I); ++
I)
4056 if (cast<PHINode>(
I)->getIncomingValueForBlock(BB) == V) {
4057 PHI = cast<PHINode>(
I);
4063 BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
4064 if (
PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
4072 if (!AlternativeV &&
4073 (!isa<Instruction>(V) || cast<Instruction>(V)->
getParent() != BB))
4078 PHI->addIncoming(V, BB);
4088 BasicBlock *PostBB,
Value *Address,
bool InvertPCond,
bool InvertQCond,
4097 if (!PStore || !QStore)
4118 if (
I.mayReadOrWriteMemory())
4120 for (
auto &
I : *QFB)
4121 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4124 for (
auto &
I : *QTB)
4125 if (&
I != QStore &&
I.mayReadOrWriteMemory())
4129 if (&*
I != PStore &&
I->mayReadOrWriteMemory())
4145 if (
I.isTerminator())
4149 if (
auto *S = dyn_cast<StoreInst>(&
I))
4153 if (!isa<BinaryOperator>(
I) && !isa<GetElementPtrInst>(
I))
4163 "When we run out of budget we will eagerly return from within the "
4164 "per-instruction loop.");
4168 const std::array<StoreInst *, 2> FreeStores = {PStore, QStore};
4170 (!IsWorthwhile(PTB, FreeStores) || !IsWorthwhile(PFB, FreeStores) ||
4171 !IsWorthwhile(QTB, FreeStores) || !IsWorthwhile(QFB, FreeStores)))
4279 bool InvertPCond =
false, InvertQCond =
false;
4285 if (QFB == PostBB) {
4304 !HasOnePredAndOneSucc(QFB, QBI->
getParent(), PostBB))
4307 (QTB && !HasOnePredAndOneSucc(QTB, QBI->
getParent(), PostBB)))
4315 for (
auto *BB : {PTB, PFB}) {
4320 PStoreAddresses.
insert(SI->getPointerOperand());
4322 for (
auto *BB : {QTB, QFB}) {
4327 QStoreAddresses.
insert(SI->getPointerOperand());
4333 auto &CommonAddresses = PStoreAddresses;
4335 bool Changed =
false;
4336 for (
auto *Address : CommonAddresses)
4339 InvertPCond, InvertQCond, DTU,
DL,
TTI);
4359 if (!IfFalseBB->
phis().empty())
4369 return I.mayWriteToMemory() ||
I.mayHaveSideEffects();
4380 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4381 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4392 {{DominatorTree::Insert, BI->
getParent(), IfFalseBB},
4393 {DominatorTree::Delete, BI->
getParent(), OldSuccessor}});
4472 if (!PBI->
getMetadata(LLVMContext::MD_unpredictable) &&
4474 (
static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]) != 0) {
4478 static_cast<uint64_t>(PredWeights[0]) + PredWeights[1]);
4481 if (CommonDestProb >= Likely)
4491 unsigned NumPhis = 0;
4513 if (OtherDest == BB) {
4520 Updates.
push_back({DominatorTree::Insert, InfLoopBlock, InfLoopBlock});
4521 OtherDest = InfLoopBlock;
4541 createLogicalOp(Builder, Instruction::Or, PBICond, BICond,
"brmerge");
4556 uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
4557 uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
4560 SuccTrueWeight, SuccFalseWeight);
4562 PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4563 PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4564 SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4565 SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4569 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
4570 PredOther * SuccCommon,
4571 PredOther * SuccOther};
4600 uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
4601 uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
4602 uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
4603 uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
4606 uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
4607 PredOther * SuccCommon};
4629bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(
Instruction *OldTerm,
4640 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB :
nullptr;
4647 if (Succ == KeepEdge1)
4648 KeepEdge1 =
nullptr;
4649 else if (Succ == KeepEdge2)
4650 KeepEdge2 =
nullptr;
4655 if (Succ != TrueBB && Succ != FalseBB)
4656 RemovedSuccessors.
insert(Succ);
4664 if (!KeepEdge1 && !KeepEdge2) {
4665 if (TrueBB == FalseBB) {
4673 if (TrueWeight != FalseWeight)
4676 }
else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
4698 for (
auto *RemovedSuccessor : RemovedSuccessors)
4699 Updates.
push_back({DominatorTree::Delete, BB, RemovedSuccessor});
4700 DTU->applyUpdates(Updates);
4710bool SimplifyCFGOpt::SimplifySwitchOnSelect(
SwitchInst *SI,
4715 if (!TrueVal || !FalseVal)
4720 BasicBlock *TrueBB =
SI->findCaseValue(TrueVal)->getCaseSuccessor();
4721 BasicBlock *FalseBB =
SI->findCaseValue(FalseVal)->getCaseSuccessor();
4724 uint32_t TrueWeight = 0, FalseWeight = 0;
4729 if (Weights.
size() == 1 +
SI->getNumCases()) {
4731 (
uint32_t)Weights[
SI->findCaseValue(TrueVal)->getSuccessorIndex()];
4733 (
uint32_t)Weights[
SI->findCaseValue(FalseVal)->getSuccessorIndex()];
4738 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
4747bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(
IndirectBrInst *IBI,
4760 return SimplifyTerminatorOnSelect(IBI,
SI->getCondition(), TrueBB, FalseBB, 0,
4781bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
4801 if (
SI->getCondition() != V)
4807 if (
SI->getDefaultDest() != BB) {
4809 assert(VVal &&
"Should have a unique destination value");
4817 return requestResimplify();
4823 if (
SI->findCaseValue(Cst) !=
SI->case_default()) {
4833 return requestResimplify();
4840 if (PHIUse ==
nullptr || PHIUse != &SuccBlock->
front() ||
4865 auto W0 = SIW.getSuccessorWeight(0);
4869 SIW.setSuccessorWeight(0, *NewW);
4871 SIW.addCase(Cst, NewBB, NewW);
4873 Updates.
push_back({DominatorTree::Insert, Pred, NewBB});
4882 Updates.
push_back({DominatorTree::Insert, NewBB, SuccBlock});
4883 DTU->applyUpdates(Updates);
4891bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(
BranchInst *BI,
4903 ConstantComparesGatherer ConstantCompare(
Cond,
DL);
4906 Value *CompVal = ConstantCompare.CompValue;
4907 unsigned UsedICmps = ConstantCompare.UsedICmps;
4908 Value *ExtraCase = ConstantCompare.Extra;
4927 if (ExtraCase && Values.
size() < 2)
4942 <<
" cases into SWITCH. BB is:\n"
4952 nullptr,
"switch.early.test");
4976 Updates.
push_back({DominatorTree::Insert, BB, EdgeBB});
4982 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain unhandled condition: " << *ExtraCase
4983 <<
"\nEXTRABB = " << *BB);
4991 CompVal,
DL.getIntPtrType(CompVal->
getType()),
"magicptr");
4998 for (
unsigned i = 0, e = Values.
size(); i != e; ++i)
4999 New->addCase(Values[i], EdgeBB);
5005 PHINode *PN = cast<PHINode>(BBI);
5007 for (
unsigned i = 0, e = Values.
size() - 1; i != e; ++i)
5014 DTU->applyUpdates(Updates);
5016 LLVM_DEBUG(
dbgs() <<
" ** 'icmp' chain result is:\n" << *BB <<
'\n');
5022 return simplifyCommonResume(RI);
5026 return simplifySingleResume(RI);
5034 auto *II = dyn_cast<IntrinsicInst>(&
I);
5039 switch (IntrinsicID) {
5040 case Intrinsic::dbg_declare:
5041 case Intrinsic::dbg_value:
5042 case Intrinsic::dbg_label:
5043 case Intrinsic::lifetime_end:
5053bool SimplifyCFGOpt::simplifyCommonResume(
ResumeInst *RI) {
5063 auto *PhiLPInst = cast<PHINode>(RI->
getValue());
5066 for (
unsigned Idx = 0,
End = PhiLPInst->getNumIncomingValues();
Idx !=
End;
5068 auto *IncomingBB = PhiLPInst->getIncomingBlock(
Idx);
5069 auto *IncomingValue = PhiLPInst->getIncomingValue(
Idx);
5073 if (IncomingBB->getUniqueSuccessor() != BB)
5076 auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
5078 if (IncomingValue != LandingPad)
5082 make_range(LandingPad->getNextNode(), IncomingBB->getTerminator())))
5083 TrivialUnwindBlocks.
insert(IncomingBB);
5087 if (TrivialUnwindBlocks.
empty())
5091 for (
auto *TrivialBB : TrivialUnwindBlocks) {
5095 while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
5109 TrivialBB->getTerminator()->eraseFromParent();
5112 DTU->applyUpdates({{DominatorTree::Delete, TrivialBB, BB}});
5119 return !TrivialUnwindBlocks.empty();
5123bool SimplifyCFGOpt::simplifySingleResume(
ResumeInst *RI) {
5127 "Resume must unwind the exception that caused control to here");
5131 make_range<Instruction *>(LPInst->getNextNode(), RI)))
5167 make_range<Instruction *>(CPInst->
getNextNode(), RI)))
5184 int Idx = DestPN.getBasicBlockIndex(BB);
5198 Value *SrcVal = DestPN.getIncomingValue(
Idx);
5199 PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
5201 bool NeedPHITranslation = SrcPN && SrcPN->
getParent() == BB;
5205 DestPN.addIncoming(
Incoming, Pred);
5232 std::vector<DominatorTree::UpdateType> Updates;
5236 if (UnwindDest ==
nullptr) {
5248 Updates.push_back({DominatorTree::Insert, PredBB, UnwindDest});
5249 Updates.push_back({DominatorTree::Delete, PredBB, BB});
5276 auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->
front());
5277 if (!SuccessorCleanupPad)
5286 SuccessorCleanupPad->eraseFromParent();
5315 bool Changed =
false;
5344 BBI->dropDbgRecords();
5348 BBI->eraseFromParent();
5354 if (&BB->
front() != UI)
5357 std::vector<DominatorTree::UpdateType> Updates;
5360 for (
unsigned i = 0, e = Preds.size(); i != e; ++i) {
5361 auto *Predecessor = Preds[i];
5364 if (
auto *BI = dyn_cast<BranchInst>(TI)) {
5368 [BB](
auto *
Successor) { return Successor == BB; })) {
5376 "The destinations are guaranteed to be different here.");
5387 Options.AC->registerAssumption(cast<AssumeInst>(Assumption));
5393 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5394 }
else if (
auto *SI = dyn_cast<SwitchInst>(TI)) {
5396 for (
auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
5397 if (i->getCaseSuccessor() != BB) {
5402 i = SU.removeCase(i);
5407 if (DTU &&
SI->getDefaultDest() != BB)
5408 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5409 }
else if (
auto *II = dyn_cast<InvokeInst>(TI)) {
5412 DTU->applyUpdates(Updates);
5416 if (!CI->doesNotThrow())
5417 CI->setDoesNotThrow();
5420 }
else if (
auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
5421 if (CSI->getUnwindDest() == BB) {
5423 DTU->applyUpdates(Updates);
5432 E = CSI->handler_end();
5435 CSI->removeHandler(
I);
5442 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5443 if (CSI->getNumHandlers() == 0) {
5444 if (CSI->hasUnwindDest()) {
5448 for (
auto *PredecessorOfPredecessor :
predecessors(Predecessor)) {
5449 Updates.push_back({DominatorTree::Insert,
5450 PredecessorOfPredecessor,
5451 CSI->getUnwindDest()});
5452 Updates.push_back({DominatorTree::Delete,
5453 PredecessorOfPredecessor, Predecessor});
5456 Predecessor->replaceAllUsesWith(CSI->getUnwindDest());
5460 DTU->applyUpdates(Updates);
5469 CSI->eraseFromParent();
5472 }
else if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
5474 assert(CRI->hasUnwindDest() && CRI->getUnwindDest() == BB &&
5475 "Expected to always have an unwind to BB.");
5477 Updates.push_back({DominatorTree::Delete, Predecessor, BB});
5485 DTU->applyUpdates(Updates);
5500 for (
size_t I = 1, E = Cases.
size();
I != E; ++
I) {
5501 if (Cases[
I - 1]->getValue() != Cases[
I]->getValue() + 1)
5510 auto *BB = Switch->getParent();
5511 auto *OrigDefaultBlock = Switch->getDefaultDest();
5512 OrigDefaultBlock->removePredecessor(BB);
5517 Switch->setDefaultDest(&*NewDefaultBlock);
5520 Updates.
push_back({DominatorTree::Insert, BB, &*NewDefaultBlock});
5522 Updates.
push_back({DominatorTree::Delete, BB, &*OrigDefaultBlock});
5530bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(
SwitchInst *SI,
5532 assert(
SI->getNumCases() > 1 &&
"Degenerate switch?");
5535 !isa<UnreachableInst>(
SI->getDefaultDest()->getFirstNonPHIOrDbg());
5537 auto *BB =
SI->getParent();
5540 BasicBlock *DestA = HasDefault ?
SI->getDefaultDest() :
nullptr;
5545 for (
auto Case :
SI->cases()) {
5549 if (Dest == DestA) {
5555 if (Dest == DestB) {
5565 "Single-destination switch should have been folded.");
5567 assert(DestB !=
SI->getDefaultDest());
5568 assert(!CasesB.
empty() &&
"There must be non-default cases.");
5576 ContiguousCases = &CasesA;
5577 ContiguousDest = DestA;
5580 ContiguousCases = &CasesB;
5581 ContiguousDest = DestB;
5590 ConstantInt::get(
Offset->getType(), ContiguousCases->
size());
5592 Value *Sub =
SI->getCondition();
5593 if (!
Offset->isNullValue())
5608 if (Weights.
size() == 1 +
SI->getNumCases()) {
5611 for (
size_t I = 0, E = Weights.
size();
I != E; ++
I) {
5612 if (
SI->getSuccessor(
I) == ContiguousDest)
5613 TrueWeight += Weights[
I];
5615 FalseWeight += Weights[
I];
5617 while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
5626 for (
auto BBI = ContiguousDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5627 unsigned PreviousEdges = ContiguousCases->
size();
5628 if (ContiguousDest ==
SI->getDefaultDest())
5630 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5631 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5633 for (
auto BBI = OtherDest->
begin(); isa<PHINode>(BBI); ++BBI) {
5634 unsigned PreviousEdges =
SI->getNumCases() - ContiguousCases->
size();
5635 if (OtherDest ==
SI->getDefaultDest())
5637 for (
unsigned I = 0, E = PreviousEdges - 1;
I != E; ++
I)
5638 cast<PHINode>(BBI)->removeIncomingValue(
SI->getParent());
5646 auto *UnreachableDefault =
SI->getDefaultDest();
5649 SI->eraseFromParent();
5651 if (!HasDefault && DTU)
5652 DTU->applyUpdates({{DominatorTree::Delete, BB, UnreachableDefault}});
5668 unsigned MaxSignificantBitsInCond =
5675 for (
const auto &Case : SI->cases()) {
5676 auto *
Successor = Case.getCaseSuccessor();
5682 const APInt &CaseVal = Case.getCaseValue()->getValue();
5685 DeadCases.
push_back(Case.getCaseValue());
5698 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5699 const unsigned NumUnknownBits =
5702 if (HasDefault && DeadCases.
empty() &&
5703 NumUnknownBits < 64 &&
5704 SI->getNumCases() == (1ULL << NumUnknownBits)) {
5709 if (DeadCases.
empty())
5715 assert(CaseI != SI->case_default() &&
5716 "Case was not found. Probably mistake in DeadCases forming.");
5718 CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
5723 std::vector<DominatorTree::UpdateType> Updates;
5724 for (
auto *
Successor : UniqueSuccessors)
5725 if (NumPerSuccessorCases[
Successor] == 0)
5726 Updates.push_back({DominatorTree::Delete, SI->getParent(),
Successor});
5746 if (!Branch || !Branch->isUnconditional())
5752 int Idx =
PHI.getBasicBlockIndex(BB);
5753 assert(
Idx >= 0 &&
"PHI has no entry for predecessor?");
5756 if (InValue != CaseValue)
5772 ForwardingNodesMap ForwardingNodes;
5774 bool Changed =
false;
5775 for (
const auto &Case : SI->cases()) {
5777 BasicBlock *CaseDest = Case.getCaseSuccessor();
5796 int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
5797 if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
5798 count(Phi.blocks(), SwitchBlock) == 1) {
5799 Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
5807 ForwardingNodes[Phi].push_back(PhiIdx);
5810 for (
auto &ForwardingNode : ForwardingNodes) {
5811 PHINode *Phi = ForwardingNode.first;
5813 if (Indexes.
size() < 2)
5816 for (
int Index : Indexes)
5817 Phi->setIncomingValue(
Index, SI->getCondition());
5827 if (
C->isThreadDependent())
5829 if (
C->isDLLImportDependent())
5832 if (!isa<ConstantFP>(
C) && !isa<ConstantInt>(
C) &&
5833 !isa<ConstantPointerNull>(
C) && !isa<GlobalValue>(
C) &&
5834 !isa<UndefValue>(
C) && !isa<ConstantExpr>(
C))
5840 Constant *StrippedC = cast<Constant>(CE->stripInBoundsConstantOffsets());
5856 if (
Constant *
C = dyn_cast<Constant>(V))
5872 if (
A->isAllOnesValue())
5874 if (
A->isNullValue())
5880 for (
unsigned N = 0, E =
I->getNumOperands();
N != E; ++
N) {
5905 ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
5907 if (
I.isTerminator()) {
5909 if (
I.getNumSuccessors() != 1 ||
I.isSpecialTerminator())
5912 CaseDest =
I.getSuccessor(0);
5919 for (
auto &
Use :
I.uses()) {
5922 if (
I->getParent() == CaseDest)
5925 if (Phi->getIncomingBlock(
Use) == CaseDest)
5938 *CommonDest = CaseDest;
5940 if (CaseDest != *CommonDest)
5945 int Idx =
PHI.getBasicBlockIndex(Pred);
5958 Res.push_back(std::make_pair(&
PHI, ConstVal));
5961 return Res.size() > 0;
5967 SwitchCaseResultVectorTy &UniqueResults,
5969 for (
auto &
I : UniqueResults) {
5970 if (
I.first == Result) {
5971 I.second.push_back(CaseVal);
5972 return I.second.size();
5975 UniqueResults.push_back(
5986 SwitchCaseResultVectorTy &UniqueResults,
5990 uintptr_t MaxUniqueResults) {
5991 for (
const auto &
I : SI->cases()) {
6005 const size_t NumCasesForResult =
6013 if (UniqueResults.size() > MaxUniqueResults)
6024 BasicBlock *DefaultDest = SI->getDefaultDest();
6025 getCaseResults(SI,
nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
6030 DefaultResults.
size() == 1 ? DefaultResults.
begin()->second :
nullptr;
6031 if ((!DefaultResult &&
6052 if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
6053 ResultVector[1].second.size() == 1) {
6054 ConstantInt *FirstCase = ResultVector[0].second[0];
6055 ConstantInt *SecondCase = ResultVector[1].second[0];
6056 Value *SelectValue = ResultVector[1].first;
6057 if (DefaultResult) {
6058 Value *ValueCompare =
6059 Builder.
CreateICmpEQ(Condition, SecondCase,
"switch.selectcmp");
6060 SelectValue = Builder.
CreateSelect(ValueCompare, ResultVector[1].first,
6061 DefaultResult,
"switch.select");
6063 Value *ValueCompare =
6064 Builder.
CreateICmpEQ(Condition, FirstCase,
"switch.selectcmp");
6065 return Builder.
CreateSelect(ValueCompare, ResultVector[0].first,
6066 SelectValue,
"switch.select");
6070 if (ResultVector.size() == 1 && DefaultResult) {
6072 unsigned CaseCount = CaseValues.
size();
6080 for (
auto *Case : CaseValues)
6081 if (Case->getValue().slt(MinCaseVal->
getValue()))
6086 for (
auto *Case : CaseValues)
6087 BitMask |= (Case->getValue() - MinCaseVal->
getValue());
6093 Condition = Builder.
CreateSub(Condition, MinCaseVal);
6097 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6102 if (CaseValues.
size() == 2) {
6104 "switch.selectcmp.case1");
6106 "switch.selectcmp.case2");
6107 Value *Cmp = Builder.
CreateOr(Cmp1, Cmp2,
"switch.selectcmp");
6108 return Builder.
CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
6121 std::vector<DominatorTree::UpdateType> Updates;
6127 Updates.push_back({DominatorTree::Insert, SelectBB, DestBB});
6132 PHI->removeIncomingValueIf(
6133 [&](
unsigned Idx) {
return PHI->getIncomingBlock(
Idx) == SelectBB; });
6134 PHI->addIncoming(SelectValue, SelectBB);
6137 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6143 if (DTU && RemovedSuccessors.
insert(Succ).second)
6144 Updates.push_back({DominatorTree::Delete, SelectBB, Succ});
6146 SI->eraseFromParent();
6161 SwitchCaseResultVectorTy UniqueResults;
6167 assert(
PHI !=
nullptr &&
"PHI for value select not found");
6169 Value *SelectValue =
6181class SwitchLookupTable {
6232 bool LinearMapValWrapped =
false;
6240SwitchLookupTable::SwitchLookupTable(
6244 assert(Values.
size() &&
"Can't build lookup table without values!");
6245 assert(TableSize >= Values.
size() &&
"Can't fit values in table!");
6248 SingleValue = Values.
begin()->second;
6254 for (
size_t I = 0, E = Values.
size();
I != E; ++
I) {
6260 TableContents[
Idx] = CaseRes;
6262 if (CaseRes != SingleValue)
6263 SingleValue =
nullptr;
6267 if (Values.
size() < TableSize) {
6269 "Need a default value to fill the lookup table holes.");
6272 if (!TableContents[
I])
6273 TableContents[
I] = DefaultValue;
6276 if (DefaultValue != SingleValue)
6277 SingleValue =
nullptr;
6283 Kind = SingleValueKind;
6290 bool LinearMappingPossible =
true;
6295 bool NonMonotonic =
false;
6296 assert(TableSize >= 2 &&
"Should be a SingleValue table.");
6299 ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[
I]);
6303 LinearMappingPossible =
false;
6308 APInt Dist = Val - PrevVal;
6311 }
else if (Dist != DistToPrev) {
6312 LinearMappingPossible =
false;
6320 if (LinearMappingPossible) {
6321 LinearOffset = cast<ConstantInt>(TableContents[0]);
6322 LinearMultiplier = ConstantInt::get(
M.getContext(), DistToPrev);
6323 bool MayWrap =
false;
6324 APInt M = LinearMultiplier->getValue();
6325 (void)
M.smul_ov(
APInt(
M.getBitWidth(), TableSize - 1), MayWrap);
6326 LinearMapValWrapped = NonMonotonic || MayWrap;
6327 Kind = LinearMapKind;
6334 if (WouldFitInRegister(
DL, TableSize,
ValueType)) {
6336 APInt TableInt(TableSize *
IT->getBitWidth(), 0);
6338 TableInt <<=
IT->getBitWidth();
6340 if (!isa<UndefValue>(TableContents[
I - 1])) {
6341 ConstantInt *Val = cast<ConstantInt>(TableContents[
I - 1]);
6342 TableInt |= Val->
getValue().
zext(TableInt.getBitWidth());
6345 BitMap = ConstantInt::get(
M.getContext(), TableInt);
6346 BitMapElementTy =
IT;
6357 GlobalVariable::PrivateLinkage, Initializer,
6358 "switch.table." + FuncName);
6359 Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
6368 case SingleValueKind:
6370 case LinearMapKind: {
6373 false,
"switch.idx.cast");
6374 if (!LinearMultiplier->isOne())
6375 Result = Builder.
CreateMul(Result, LinearMultiplier,
"switch.idx.mult",
6377 !LinearMapValWrapped);
6379 if (!LinearOffset->isZero())
6382 !LinearMapValWrapped);
6398 ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
6399 "switch.shiftamt",
true,
true);
6402 Value *DownShifted =
6403 Builder.
CreateLShr(BitMap, ShiftAmt,
"switch.downshift");
6405 return Builder.
CreateTrunc(DownShifted, BitMapElementTy,
"switch.masked");
6411 Array->getInitializer()->getType()->getArrayNumElements();
6412 if (TableSize > (1ULL << std::min(
IT->getBitWidth() - 1, 63u)))
6415 "switch.tableidx.zext");
6419 GEPIndices,
"switch.gep");
6421 cast<ArrayType>(
Array->getValueType())->getElementType(),
GEP,
6428bool SwitchLookupTable::WouldFitInRegister(
const DataLayout &
DL,
6430 Type *ElementType) {
6431 auto *
IT = dyn_cast<IntegerType>(ElementType);
6438 if (TableSize >= UINT_MAX /
IT->getBitWidth())
6440 return DL.fitsInLegalInteger(TableSize *
IT->getBitWidth());
6449 auto *
IT = dyn_cast<IntegerType>(Ty);
6461 DL.fitsInLegalInteger(
IT->getBitWidth());
6473 return NumCases * 100 >= CaseRange * MinDensity;
6494 if (SI->getNumCases() > TableSize)
6497 bool AllTablesFitInRegister =
true;
6498 bool HasIllegalType =
false;
6499 for (
const auto &
I : ResultTypes) {
6500 Type *Ty =
I.second;
6506 AllTablesFitInRegister =
6507 AllTablesFitInRegister &&
6508 SwitchLookupTable::WouldFitInRegister(
DL, TableSize, Ty);
6513 if (HasIllegalType && !AllTablesFitInRegister)
6518 if (AllTablesFitInRegister)
6535 MaxCaseVal.
getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
6538 return all_of(ResultTypes, [&](
const auto &KV) {
6539 return SwitchLookupTable::WouldFitInRegister(
6568 const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
6588 DefaultValue, CmpOp1,
true);
6589 if (DefaultConst != TrueConst && DefaultConst != FalseConst)
6594 for (
auto ValuePair : Values) {
6596 ValuePair.second, CmpOp1,
true);
6597 if (!CaseConst || CaseConst == DefaultConst ||
6598 (CaseConst != TrueConst && CaseConst != FalseConst))
6612 if (DefaultConst == FalseConst) {
6615 ++NumTableCmpReuses;
6618 Value *InvertedTableCmp = BinaryOperator::CreateXor(
6619 RangeCmp, ConstantInt::get(RangeCmp->
getType(), 1),
"inverted.cmp",
6622 ++NumTableCmpReuses;
6632 assert(SI->getNumCases() > 1 &&
"Degenerate switch?");
6651 if (SI->getNumCases() < 3)
6656 assert(!SI->cases().empty());
6673 MinCaseVal = CaseVal;
6675 MaxCaseVal = CaseVal;
6680 if (!
getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
6690 ResultLists[
PHI].push_back(std::make_pair(CaseVal,
Value));
6696 ResultTypes[
PHI] = ResultLists[
PHI][0].second->getType();
6704 bool HasDefaultResults =
6706 DefaultResultsList,
DL,
TTI);
6708 for (
const auto &
I : DefaultResultsList) {
6711 DefaultResults[
PHI] = Result;
6715 *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes,
DL,
TTI);
6717 if (UseSwitchConditionAsTableIndex)
6723 bool TableHasHoles = (NumResults < TableSize);
6724 bool NeedMask = (TableHasHoles && !HasDefaultResults);
6727 if (SI->getNumCases() < 4)
6729 if (!
DL.fitsInLegalInteger(TableSize))
6736 std::vector<DominatorTree::UpdateType> Updates;
6742 assert(MaxTableSize >= TableSize &&
6743 "It is impossible for a switch to have more entries than the max "
6744 "representable value of its input integer type's size.");
6749 bool DefaultIsReachable =
6750 !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
6761 if (UseSwitchConditionAsTableIndex) {
6762 TableIndexOffset = ConstantInt::get(MaxCaseVal->
getIntegerType(), 0);
6763 TableIndex = SI->getCondition();
6765 TableIndexOffset = MinCaseVal;
6768 bool MayWrap =
true;
6769 if (!DefaultIsReachable) {
6774 TableIndex = Builder.
CreateSub(SI->getCondition(), TableIndexOffset,
6775 "switch.tableidx",
false,
6784 if (UseSwitchConditionAsTableIndex && HasDefaultResults) {
6792 return SwitchLookupTable::WouldFitInRegister(
6793 DL, UpperBound, KV.second );
6797 TableSize = std::max(UpperBound, TableSize);
6800 DefaultIsReachable =
false;
6804 const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
6805 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6808 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6813 TableIndex, ConstantInt::get(MinCaseVal->
getType(), TableSize));
6815 Builder.
CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
6817 Updates.push_back({DominatorTree::Insert, BB, LookupBB});
6827 MaskBB->
setName(
"switch.hole_check");
6834 APInt MaskInt(TableSizePowOf2, 0);
6835 APInt One(TableSizePowOf2, 1);
6837 const ResultListTy &ResultList = ResultLists[PHIs[0]];
6838 for (
size_t I = 0, E = ResultList.size();
I != E; ++
I) {
6841 MaskInt |= One <<
Idx;
6851 Value *Shifted = Builder.
CreateLShr(TableMask, MaskIndex,
"switch.shifted");
6854 Builder.
CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
6856 Updates.push_back({DominatorTree::Insert, MaskBB, LookupBB});
6857 Updates.push_back({DominatorTree::Insert, MaskBB, SI->getDefaultDest()});
6863 if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
6866 SI->getDefaultDest()->removePredecessor(BB,
6869 Updates.push_back({DominatorTree::Delete, BB, SI->getDefaultDest()});
6873 const ResultListTy &ResultList = ResultLists[
PHI];
6876 Constant *DV = NeedMask ? ResultLists[
PHI][0].second : DefaultResults[
PHI];
6878 SwitchLookupTable Table(
Mod, TableSize, TableIndexOffset, ResultList, DV,
6881 Value *Result = Table.BuildLookup(TableIndex, Builder);
6885 if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
6888 for (
auto *
User :
PHI->users()) {
6893 PHI->addIncoming(Result, LookupBB);
6898 Updates.push_back({DominatorTree::Insert, LookupBB, CommonDest});
6902 for (
unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
6905 if (Succ == SI->getDefaultDest())
6908 if (DTU && RemovedSuccessors.
insert(Succ).second)
6909 Updates.push_back({DominatorTree::Delete, BB, Succ});
6911 SI->eraseFromParent();
6918 ++NumLookupTablesHoles;
6933 auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
6934 if (CondTy->getIntegerBitWidth() > 64 ||
6935 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
6939 if (SI->getNumCases() < 4)
6947 for (
const auto &
C : SI->cases())
6948 Values.
push_back(
C.getCaseValue()->getValue().getSExtValue());
6956 int64_t
Base = Values[0];
6957 for (
auto &V : Values)
6970 unsigned Shift = 64;
6971 for (
auto &V : Values)
6975 for (
auto &V : Values)
6976 V = (int64_t)((
uint64_t)V >> Shift);
6992 auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
6995 Builder.
CreateSub(SI->getCondition(), ConstantInt::get(Ty,
Base));
6997 Ty, Intrinsic::fshl,
6998 {Sub, Sub, ConstantInt::get(Ty, Ty->getBitWidth() - Shift)});
6999 SI->replaceUsesOfWith(SI->getCondition(), Rot);
7001 for (
auto Case : SI->cases()) {
7002 auto *Orig = Case.getCaseValue();
7003 auto Sub = Orig->getValue() -
APInt(Ty->getBitWidth(),
Base);
7004 Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
7020 Value *Condition = SI->getCondition();
7022 auto *CondTy = cast<IntegerType>(Condition->
getType());
7024 if (CondTy->getIntegerBitWidth() > 64 ||
7025 !
DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
7039 if (SI->getNumCases() < 4)
7045 if (!isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg()))
7050 for (
const auto &Case : SI->cases()) {
7051 uint64_t CaseValue = Case.getCaseValue()->getValue().getZExtValue();
7068 for (
auto &Case : SI->cases()) {
7069 auto *OrigValue = Case.getCaseValue();
7070 Case.setValue(ConstantInt::get(OrigValue->getIntegerType(),
7071 OrigValue->getValue().countr_zero()));
7078 SI->setCondition(ConditionTrailingZeros);
7086 if (isValueEqualityComparison(SI)) {
7090 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
7091 return requestResimplify();
7095 if (SimplifySwitchOnSelect(SI,
Select))
7096 return requestResimplify();
7101 if (FoldValueComparisonIntoPredecessors(SI, Builder))
7102 return requestResimplify();
7108 if (
Options.ConvertSwitchRangeToICmp && TurnSwitchRangeIntoICmp(SI, Builder))
7109 return requestResimplify();
7113 return requestResimplify();
7116 return requestResimplify();
7119 return requestResimplify();
7126 if (
Options.ConvertSwitchToLookupTable &&
7128 return requestResimplify();
7131 return requestResimplify();
7134 return requestResimplify();
7137 hoistCommonCodeFromSuccessors(
SI->getParent(), !
Options.HoistCommonInsts))
7138 return requestResimplify();
7145 bool Changed =
false;
7154 RemovedSuccs.
insert(Dest);
7164 std::vector<DominatorTree::UpdateType> Updates;
7165 Updates.reserve(RemovedSuccs.
size());
7166 for (
auto *RemovedSucc : RemovedSuccs)
7167 Updates.push_back({DominatorTree::Delete, BB, RemovedSucc});
7168 DTU->applyUpdates(Updates);
7186 if (SimplifyIndirectBrOnSelect(IBI, SI))
7187 return requestResimplify();
7219 if (isa<PHINode>(*Succ->
begin()))
7223 if (BB == OtherPred)
7229 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7235 std::vector<DominatorTree::UpdateType> Updates;
7243 "unexpected successor");
7246 Updates.push_back({DominatorTree::Insert, Pred, OtherPred});
7247 Updates.push_back({DominatorTree::Delete, Pred, BB});
7254 if (isa<DbgInfoIntrinsic>(Inst))
7261 Updates.push_back({DominatorTree::Delete, BB, Succ});
7275 return Branch->isUnconditional() ? simplifyUncondBranch(Branch, Builder)
7276 : simplifyCondBranch(
Branch, Builder);
7279bool SimplifyCFGOpt::simplifyUncondBranch(
BranchInst *BI,
7291 bool NeedCanonicalLoop =
7302 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I))
7304 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7306 if (
I->isTerminator() &&
7307 tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
7314 for (++
I; isa<DbgInfoIntrinsic>(
I); ++
I)
7324 if (
Options.SpeculateBlocks &&
7327 return requestResimplify();
7335 if (!PPred || (PredPred && PredPred != PPred))
7346 "Tautological conditional branch should have been eliminated already.");
7349 if (!
Options.SimplifyCondBranch ||
7354 if (isValueEqualityComparison(BI)) {
7359 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
7360 return requestResimplify();
7366 if (FoldValueComparisonIntoPredecessors(BI, Builder))
7367 return requestResimplify();
7370 if (&*
I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
7371 return requestResimplify();
7376 if (SimplifyBranchOnICmpChain(BI, Builder,
DL))
7389 return requestResimplify();
7395 if (
Options.SpeculateBlocks &&
7398 return requestResimplify();
7408 return requestResimplify();
7416 return requestResimplify();
7425 return requestResimplify();
7432 return requestResimplify();
7437 if (PBI != BI && PBI->isConditional())
7439 return requestResimplify();
7444 if (
BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
7445 if (PBI != BI && PBI->isConditional())
7447 return requestResimplify();
7461 if (
C->isNullValue() || isa<UndefValue>(
C)) {
7463 auto *
Use = cast<Instruction>(*
I->user_begin());
7467 if (
Use->getParent() !=
I->getParent() ||
Use ==
I ||
Use->comesBefore(
I))
7481 if (
GEP->getPointerOperand() ==
I) {
7488 if (!
GEP->hasAllZeroIndices() &&
7489 (!
GEP->isInBounds() ||
7491 GEP->getPointerAddressSpace())))
7492 PtrValueMayBeModified =
true;
7498 bool HasNoUndefAttr =
7499 Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
7501 if (isa<UndefValue>(
C) && HasNoUndefAttr)
7504 if (
C->isNullValue() && HasNoUndefAttr &&
7505 Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
7506 return !PtrValueMayBeModified;
7516 if (!LI->isVolatile())
7518 LI->getPointerAddressSpace());
7522 if (!SI->isVolatile())
7524 SI->getPointerAddressSpace())) &&
7525 SI->getPointerOperand() ==
I;
7527 if (
auto *CB = dyn_cast<CallBase>(
Use)) {
7531 if (CB->getCalledOperand() ==
I)
7534 if (
C->isNullValue()) {
7537 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7538 if (CB->isPassingUndefUB(ArgIdx) &&
7539 CB->paramHasAttr(ArgIdx, Attribute::NonNull)) {
7541 return !PtrValueMayBeModified;
7544 }
else if (isa<UndefValue>(
C)) {
7548 unsigned ArgIdx = CB->getArgOperandNo(&Arg);
7549 if (CB->isPassingUndefUB(ArgIdx)) {
7566 for (
unsigned i = 0, e =
PHI.getNumIncomingValues(); i != e; ++i)
7593 DTU->
applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
7595 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(
T)) {
7603 for (
const auto &Case : SI->cases())
7604 if (Case.getCaseSuccessor() == BB) {
7606 Case.setSuccessor(Unreachable);
7608 if (SI->getDefaultDest() == BB) {
7610 SI->setDefaultDest(Unreachable);
7615 { { DominatorTree::Insert, Predecessor, Unreachable },
7616 { DominatorTree::Delete, Predecessor, BB } });
7624bool SimplifyCFGOpt::simplifyOnce(
BasicBlock *BB) {
7625 bool Changed =
false;
7649 return requestResimplify();
7670 if (
Options.SpeculateBlocks &&
7674 if (
auto *PN = dyn_cast<PHINode>(BB->
begin()))
7683 case Instruction::Br:
7684 Changed |= simplifyBranch(cast<BranchInst>(Terminator), Builder);
7686 case Instruction::Resume:
7687 Changed |= simplifyResume(cast<ResumeInst>(Terminator), Builder);
7689 case Instruction::CleanupRet:
7690 Changed |= simplifyCleanupReturn(cast<CleanupReturnInst>(Terminator));
7692 case Instruction::Switch:
7693 Changed |= simplifySwitch(cast<SwitchInst>(Terminator), Builder);
7695 case Instruction::Unreachable:
7696 Changed |= simplifyUnreachable(cast<UnreachableInst>(Terminator));
7698 case Instruction::IndirectBr:
7699 Changed |= simplifyIndirectBr(cast<IndirectBrInst>(Terminator));
7707 bool Changed =
false;
7715 Changed |= simplifyOnce(BB);
7716 }
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.
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Provides some synthesis utilities to produce sequences of values.
This file defines generic set operations that may be used on set's of different types,...
This file implements a set that has insertion order iteration characteristics.
static bool ValidLookupTableConstant(Constant *C, const TargetTransformInfo &TTI)
Return true if the backend will be able to handle initializing an array of constants like C.
static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB)
Return true if we can thread a branch across this block.
static StoreInst * findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2)
static Constant * ConstantFold(Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool)
Try to fold instruction I into a constant.
static Constant * LookupConstant(Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
If V is a Constant, return it.
static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
static bool SafeToMergeTerminators(Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
Return true if it is safe to merge these two terminator instructions together.
static void CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
static cl::opt< unsigned > MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))
static std::optional< std::tuple< BasicBlock *, Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination(BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
Determine if the two branches share a common destination and deduce a glue that joins the branches' c...
static bool mergeCleanupPad(CleanupReturnInst *RI)
static bool isVectorOp(Instruction &I)
Return if an instruction's type or any of its operands' types are a vector type.
static void GetBranchWeights(Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
Get Weights of a given terminator, the default weight is at the front of the vector.
static cl::opt< unsigned > MaxSwitchCasesPerResult("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select"))
static BasicBlock * allPredecessorsComeFromSameSource(BasicBlock *BB)
static ConstantInt * GetConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to transform a switch that has "holes" in it to a contiguous sequence of cases.
static bool getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
Try to determine the resulting constant values in phi nodes at the common destination basic block,...
static bool performBranchToCommonDestFolding(BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified=false)
Check if passing a value to an instruction will cause undefined behavior.
static void EliminateBlockCases(BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
static bool isSafeToHoistInstr(Instruction *I, unsigned Flags)
static std::optional< bool > FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
If we have a conditional branch on something for which we know the constant value in predecessors (e....
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static cl::opt< bool > MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
static PHINode * FindPHIForConditionForwarding(ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i....
static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}{Tru...
static cl::opt< unsigned > TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If we have a conditional branch as a predecessor of another block, this function tries to simplify it...
static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block.
static cl::opt< bool > SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static cl::opt< int > MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
static bool SinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU)
Check whether BB's predecessors end with unconditional branches.
static void setBranchWeights(SwitchInst *SI, ArrayRef< uint32_t > Weights)
static Value * foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
static bool isCleanupBlockEmpty(iterator_range< BasicBlock::iterator > R)
static Value * ensureValueAvailableInSuccessor(Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static bool ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallDenseMap< PHINode *, Type * > &ResultTypes)
Determine whether a lookup table should be built for this switch, based on the number of cases,...
static Value * createLogicalOp(IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2, const TargetTransformInfo &TTI)
Helper function for hoistCommonCodeFromSuccessors.
static bool IncomingValuesAreCompatible(BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr)
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values...
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
@ SkipImplicitControlFlow
static cl::opt< bool > EnableMergeCompatibleInvokes("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate"))
static bool FoldCondBranchOnValueKnownInPredecessor(BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If a switch is only used to initialize one or more phi nodes in a common successor block with only tw...
static cl::opt< unsigned > BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static bool isSwitchDense(uint64_t NumCases, uint64_t CaseRange)
static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
static bool ForwardSwitchConditionToPHI(SwitchInst *SI)
Try to forward the condition of a switch instruction to a phi node dominated by the switch,...
static bool eliminateDeadSwitchCases(SwitchInst *SI, DomTreeUpdater *DTU, AssumptionCache *AC, const DataLayout &DL)
Compute masked bits for the condition of a switch and use it to remove dead cases.
static int ConstantIntSortPredicate(ConstantInt *const *P1, ConstantInt *const *P2)
static Value * isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
Determine if we can hoist sink a sole store instruction out of a conditional block.
static cl::opt< bool > HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static void createUnreachableSwitchDefault(SwitchInst *Switch, DomTreeUpdater *DTU)
static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults)
static void FitWeights(MutableArrayRef< uint64_t > Weights)
Keep halving the weights until all can fit in uint32_t.
static cl::opt< bool > HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
static InstructionCost computeSpeculationCost(const User *I, const TargetTransformInfo &TTI)
Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to specu...
static void EraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
static unsigned skippedInstrFlags(Instruction *I)
static bool replacingOperandWithVariableIsCheap(const Instruction *I, int OpIdx)
static bool ValuesOverlap(std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
Return true if there are any keys in C1 that exist in C2 as well.
static bool canSinkInstructions(ArrayRef< Instruction * > Insts, DenseMap< Instruction *, SmallVector< Value *, 4 > > &PHIOperands)
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
If the switch is only used to initialize one or more phi nodes in a common successor block with diffe...
static size_t mapCaseToResult(ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
static void MergeCompatibleInvokesImpl(ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU)
static bool ShouldUseSwitchConditionAsTableIndex(ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal, bool HasDefaultResults, const SmallDenseMap< PHINode *, Type * > &ResultTypes, const DataLayout &DL, const TargetTransformInfo &TTI)
static void reuseTableCompare(User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant * > > &Values)
Try to reuse the switch table index compare.
static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
If the previous block ended with a widenable branch, determine if reusing the target block is profita...
static bool simplifySwitchOfPowersOfTwo(SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
Tries to transform switch of powers of two to reduce switch range.
static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const DataLayout &DL)
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
static bool CasesAreContiguous(SmallVectorImpl< ConstantInt * > &Cases)
static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB, DomTreeUpdater *DTU)
Given an block with only a single landing pad and a unconditional branch try to find another basic bl...
static cl::opt< bool > MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static bool isLifeTimeMarker(const Instruction *I)
static bool MergeCompatibleInvokes(BasicBlock *BB, DomTreeUpdater *DTU)
If this block is a landingpad exception handling block, categorize all the predecessor invokes into s...
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
static void hoistLockstepIdenticalDbgVariableRecords(Instruction *TI, Instruction *I1, SmallVectorImpl< Instruction * > &OtherInsts)
Hoists DbgVariableRecords from I1 and OtherInstrs that are identical in lock-step to TI.
static cl::opt< unsigned > HoistCommonSkipLimit("simplifycfg-hoist-common-skip-limit", cl::Hidden, cl::init(20), cl::desc("Allow reordering across at most this many " "instructions when hoisting"))
static bool removeEmptyCleanup(CleanupReturnInst *RI, DomTreeUpdater *DTU)
static cl::opt< unsigned > PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
static bool removeUndefIntroducingPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, AssumptionCache *AC)
If BB has an incoming value that will always trigger undefined behavior (eg.
static ConstantInt * getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To)
static bool dominatesMergePoint(Value *V, BasicBlock *BB, SmallPtrSetImpl< Instruction * > &AggressiveInsts, InstructionCost &Cost, InstructionCost Budget, const TargetTransformInfo &TTI, unsigned Depth=0)
If we have a merge point of an "if condition" as accepted above, return true if the specified value d...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
uint64_t getZExtValue() const
Get zero extended value.
unsigned popcount() const
Count the number of bits set.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool sle(const APInt &RHS) const
Signed less or equal comparison.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
const T & front() const
front - Get the first element.
size_t size() const
size - Get the array size.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
bool getValueAsBool() const
Return the attribute's value as a boolean.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
bool isLandingPad() const
Return true if this basic block is a landing pad.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class represents a no-op cast from one type to another.
The address of a basic block.
BasicBlock * getBasicBlock() const
Conditional or Unconditional Branch instruction.
iterator_range< succ_op_iterator > successors()
void setCondition(Value *V)
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
bool isInlineAsm() const
Check if this call is an inline asm statement.
bool cannotMerge() const
Determine if the call cannot be tail merged.
bool isIndirectCall() const
Return true if the callsite is an indirect call.
Value * getCalledOperand() const
Intrinsic::ID getIntrinsicID() const
Returns the intrinsic ID of the intrinsic called or Intrinsic::not_intrinsic if the called function i...
This class represents a function call, abstracting a target machine's calling convention.
CleanupPadInst * getCleanupPad() const
Convenience accessor.
BasicBlock * getUnwindDest() const
This class is the base class for the comparison instructions.
Predicate getPredicate() const
Return the predicate for this instruction.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
A constant value that is initialized with an expression using other constant values.
static Constant * getICmp(unsigned short pred, Constant *LHS, Constant *RHS, bool OnlyIfReduced=false)
get* - Return some common constants without having to specify the full Instruction::OPCODE identifier...
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
static ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
bool isEmptySet() const
Return true if this set contains no members.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DILocation * getMergedLocations(ArrayRef< DILocation * > Locs)
Try to combine the vector of locations passed as input in a single one.
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Base class for non-instruction debug metadata records that have positions within IR.
simple_ilist< DbgRecord >::iterator self_iterator
Record of a variable value-assignment, aka a non instruction representation of the dbg....
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool hasPostDomTree() const
Returns true if it holds a PostDominatorTree.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
const BasicBlock & getEntryBlock() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
UnreachableInst * CreateUnreachable()
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
BasicBlock::iterator GetInsertPoint() const
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
void CollectMetadataToCopy(Instruction *Src, ArrayRef< unsigned > MetadataKinds)
Collect metadata with IDs MetadataKinds from Src which should be added to all created instructions.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateNot(Value *V, const Twine &Name="")
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles=std::nullopt)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Indirect Branch Instruction.
BasicBlock * getDestination(unsigned i)
Return the specified destination.
unsigned getNumDestinations() const
return the number of possible destinations in this indirectbr instruction.
void removeDestination(unsigned i)
This method removes the specified successor from the indirectbr instruction.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const LLVM_READONLY
This function determines if the specified instruction executes the same operation as the current one.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
void dropUBImplyingAttrsAndMetadata()
Drop any attributes or metadata that can cause immediate undefined behavior.
bool isUsedOutsideOfBlock(const BasicBlock *BB) const LLVM_READONLY
Return true if there are any uses of this instruction in blocks other than the specified block.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
BasicBlock * getUnwindDest() const
void setNormalDest(BasicBlock *B)
void setUnwindDest(BasicBlock *B)
BasicBlock * getNormalDest() const
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
const MDOperand & getOperand(unsigned I) const
unsigned getNumOperands() const
Return number of MDNode operands.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
LLVMContext & getContext() const
Get the global data context.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
op_range incoming_values()
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents a cast from a pointer to an integer.
Resume the propagation of an exception.
Value * getValue() const
Convenience accessor.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
std::optional< uint32_t > CaseWeightOpt
SwitchInst::CaseIt removeCase(SwitchInst::CaseIt I)
Delegate the call to the underlying SwitchInst::removeCase() and remove correspondent branch weight.
BasicBlock * getSuccessor(unsigned idx) const
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
unsigned getNumSuccessors() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
unsigned getOperandNo() const
Return the operand # of this use in its User.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
Value(Type *Ty, unsigned scid)
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ArchKind & operator--(ArchKind &Kind)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
pred_iterator pred_end(BasicBlock *BB)
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool operator<(int64_t V1, const APSInt &V2)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
APInt operator*(APInt a, uint64_t RHS)
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void RemapDbgVariableRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgVariableRecord V using the value map VM.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
constexpr bool has_single_bit(T Value) noexcept
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
pred_iterator pred_begin(BasicBlock *BB)
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It)
Advance It while it points to a debug instruction and return the result.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
bool FoldBranchToCommonDest(BranchInst *BI, llvm::DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr, const TargetTransformInfo *TTI=nullptr, unsigned BonusInstThreshold=1)
If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our ...
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
void sort(IteratorTy Start, IteratorTy End)
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void RemapDbgVariableRecord(Module *M, DbgVariableRecord *V, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Remap the Values used in the DbgVariableRecord V using the value map VM.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
@ And
Bitwise or logical AND of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
auto max_element(R &&Range)
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
unsigned succ_size(const MachineBasicBlock *BB)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
Constant * ConstantFoldIntegerCast(Constant *C, Type *DestTy, bool IsSigned, const DataLayout &DL)
Constant fold a zext, sext or trunc, depending on IsSigned and whether the DestTy is wider or narrowe...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
unsigned getBitWidth() const
Get the bit width of this value.
A MapVector that performs no allocations if smaller than a certain size.